数据结构 串和数组 练习试题

数据结构题目及答案一、数组题目及答案题目一：给定一个整数数组nums和一个目标值target，请你在数组中找出和为目标值的两个整数，并返回它们的索引。

题目描述：给定一个整数数组nums，以及一个目标值target，请找出数组中两个数字的和等于目标值target，并返回它们的索引。

示例输入：nums = [2, 7, 11, 15], target = 9示例输出：[0, 1]解释：nums[0] + nums[1] = 2 + 7 = 9，因此返回[0, 1]。

解题思路：1. 使用哈希表存储已经遍历过的数字及其索引；2. 遍历数组，对于每个元素，计算该元素与目标值的差值；3. 如果差值存在于哈希表中，则返回对应的索引；4. 如果不存在，则将当前元素加入哈希表中。

代码实现：```pythondef twoSum(nums, target):hashmap = {}for i, num in enumerate(nums):complement = target - numif complement in hashmap:return [hashmap[complement], i]hashmap[num] = ireturn []# 测试样例nums = [2, 7, 11, 15]target = 9print(twoSum(nums, target))```二、链表题目及答案题目二：给定一个链表，删除链表的倒数第N个节点，并返回链表的头节点。

题目描述：给定一个链表，删除链表的倒数第N个节点，并返回链表的头节点。

示例输入：1->2->3->4->5, N = 2示例输出：1->2->3->5解释：删除倒数第二个节点(4)，得到链表1->2->3->5。

解题思路：1. 使用双指针技巧，使用两个指针pre和cur，其中cur指针先向前移动N个节点；2. 使用dummy节点作为头节点的前一个节点，以应对删除头节点的情况；3. cur指针到达链表的尾部时，pre指针的下一个节点即为要删除的节点；4. 删除节点后，返回dummy节点的下一个节点即为新链表的头节点。

数据结构(C语言)【经典题库】含答案数据结构（C语言）【经典题库】含答案数据结构是计算机科学中的重要基础，对于程序员和软件工程师来说，熟练掌握数据结构是必不可少的。

在C语言中，有许多经典的数据结构题目，通过解答这些题目，可以深入理解数据结构的原理和应用。

本文将介绍一些经典的数据结构题目，同时附上详细的答案。

一、数组题目1. 给定一个整型数组arr和一个整数target，找出数组中两个数的和为target的所有组合。

```C#include <stdio.h>void findPairs(int arr[], int n, int target) {int i, j;for (i = 0; i < n - 1; i++) {for (j = i + 1; j < n; j++) {if (arr[i] + arr[j] == target) {printf("%d, %d\n", arr[i], arr[j]);}}}}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 14;int n = sizeof(arr) / sizeof(arr[0]);findPairs(arr, n, target);return 0;}```答案解析：使用两层循环遍历数组中的每对元素，判断它们的和是否等于目标值target，如果是则输出。

时间复杂度为O(n^2)。

2. 给定一个整型数组arr和一个整数k，求出数组中连续子数组的最大和。

```C#include <stdio.h>int maxSubArraySum(int arr[], int n) {int maxSum = arr[0];int currentSum = arr[0];for (int i = 1; i < n; i++) {currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] : arr[i];if (currentSum > maxSum) {maxSum = currentSum;}}return maxSum;}int main() {int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int n = sizeof(arr) / sizeof(arr[0]);int maxSum = maxSubArraySum(arr, n);printf("最大和为：%d\n", maxSum);return 0;}```答案解析：使用动态规划的思想，定义两个变量`maxSum`和`currentSum`，分别表示当前的最大和和累加和。

习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“software”,其子串的个数是（）。

A．8 B．37 C．36 D．9二、填空题1．含零个字符的串称为______串。

任何串中所含______的个数称为该串的长度。

2．空格串是指__ __，其长度等于__ __。

3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。

一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。

4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。

5．模式串P=‘abaabcac’的next函数值序列为________。

6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)__ ______){int i=0,j=0;while (s[j])(2)___ _____;for(j--; i<j && s[i]==s[j]; i++,j--);return((3)___ ____)}7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

void maxcomstr(orderstring *s,*t; int index, length){int i,j,k,length1,con;index=0;length=0;i=1;while (i<=s.len){j=1;while(j<=t.len){ if (s[i]= =t[j]){ k=1;length1=1;con=1;while(con)if (1) _ { length1=length1+1;k=k+1; }else (2) __;if (length1>length) { index=i; length=length1; }(3)__ __;}else (4) ___;}(5) __} }三、应用题1．描述以下概念的区别：空格串与空串。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

数据结构历年真题及解析题一、选择题1. 下列关于数组的描述，正确的是（）。

A. 数组在内存中是连续存放的。

B. 数组一经定义，其长度不可改变。

C. 数组的每个元素可以是不同的数据类型。

D. 数组可以通过下标随机访问元素。

答案：A、B、D2. 链表相比于数组的优势在于（）。

A. 内存使用更高效。

B. 插入和删除操作更加方便。

C. 可以通过下标随机访问元素。

D. 存储空间可以动态分配。

答案：B、D3. 栈（Stack）的特点是（）。

A. 先进先出（FIFO）。

B. 后进先出（LIFO）。

C. 只能在一端进行插入和删除。

D. 可以通过索引随机访问元素。

答案：B、C4. 队列（Queue）与栈的主要区别在于数据的（）。

A. 存取方式。

B. 存储结构。

C. 操作速度。

D. 内存占用。

答案：A5. 二叉树的前序遍历的顺序是（）。

A. 根-左-右。

B. 左-根-右。

C. 右-根-左。

D. 根-右-左。

答案：A6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 通过增加哈希表的大小来解决冲突。

B. 通过链表来链接具有相同哈希值的元素。

C. 寻找表中下一个空闲位置来存储冲突元素。

D. 重新计算哈希值，直到找到空闲位置。

答案：C8. 图的遍历算法中，深度优先搜索（DFS）与广度优先搜索（BFS）的主要区别在于（）。

A. DFS使用递归，BFS使用队列。

B. DFS使用栈，BFS使用递归。

C. DFS使用队列，BFS使用栈。

D. DFS和BFS都使用链表。

答案：A9. 堆（Heap）结构中，最大堆的性质是（）。

A. 父节点的值小于子节点。

B. 父节点的值大于子节点。

C. 父节点的值等于子节点。

D. 没有固定的大小关系。

答案：B10. 动态规划算法通常用于解决（）类型的问题。

A. 排序。

数据结构-第5章--数组练习题第5章数组一、选择题3.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(A)。

A.BA+141B.BA+180C.BA+222D.BA+2254.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（A）。

A.808B.818C.1010D.10205.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。

1195A.1175B.1180C.1205D.12107.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。

供选择的答案：A.198B.195C.1972+64某3=19410.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（iA.i某(i-1)/2+jB.j某(j-1)/2+iC.i某(i+1)/2+jD.j某(j+1)/2+i11.设A是n某n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(C)。

A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（AB）。

第四章串和数组一．选择题1．串是一种特殊的线性表，其特殊性体现在（）A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符2．串的长度是（）A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数，且大于0 D．串中所含字符个数3．若串S=”software”，其子串数目是（）A．8 B．37 C．36 D．94．数组A[0..5，0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][5]的地址为（）A．1175 B．1180 C．1205 D．12105．对矩阵压缩存储是为了（）A．方便运算B．节省存储空间C．方便存储D．提高运算速度6．一个n 阶对称矩阵，如果采用压缩存储方式，则容量为（）A．n2B．n2/2 C．n(n+1)/2 D．(n+1)2/27．对稀疏矩阵采用压缩存储，其缺点之一是（）A．无法判断矩阵有多少行多少列B．无法根据行列号查找某个矩阵元素C．无法根据行列号计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂二．填空1．设串s1=”I am a student”，则串长为（）2．设有两个串p和q，其中q是p的子串，求子串q 在p中首次出现位置的算法称为（）3．一维数组的逻辑结构是（），存储结构是（）；对于二维或多维数组，分为按（）和（）两种不同的存储结构。

4．数组A[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为（）5．三维数组R[C1..D1,C2..D2,C3..D3]共含有（）个元素。

三、算法设计1．编写下列算法（假定下面所用的串均采用顺序存储方式，参数c、c1和c2均为字符型）：（1）将串S中所有其值为c1的字符换成c2的字符。

（2）将串S中所有字符逆序（3）从串S中删除其值等于c的所有字符（4）从串S中第index个字符起求出首次与字符串S1相同的子串的起始位置（5）从串S中删除重第i个字符起的j 个字符（6）从串S中删除所有与串S1相同的子串（允许调用第（4）题和第（5）题的算法）2．设计程序，计算串str中每一个字符出现的次数。