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

数据结构题目及答案一、数组题目及答案题目一：给定一个整数数组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．描述以下概念的区别：空格串与空串。

Βιβλιοθήκη 12.D 13.A 14.B
补充习题:
15.两维数组是一种非线性结构。（ A)正确 B)不正确 ）
16.数组A三维的长度分别为b3,b2,b1；每个数组元素占一个 存储单元；LOC[0，0，0]为基址。若以行序为主序，则元素 A[i][j][k]的地址为( )(其中0<=i<b3,0<=j<b2,0<=k<b1) A)LOC[0,0,0]+i*b2*b1+j*b1+k
B）任意个字母的序列 D）有限个字符的序列
C）串中所含字符的个数，且大于0
D）串中所含字符的个数
1.C 2.D 3.D
补充习题:
4.设有两个串p和q,求q在p中首次出现的位置的运算( A）连接 C）求子串 B）模式匹配 D）求串长 )存储方式最为节 ).
5.若某串的长度小于一个常数，则采用( 省空间。 A)链式 A)正确 A)正确 B)堆结构 B)不正确 C)顺序
(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元 组表中第3个三元组为（ ）。
A) (2,1,3)
C) (3,2,-1)
B) (3,1,5)
D) (2,3,-1)
14.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素 的行下标和列下标互换，就完成了对该矩阵的转置运算，这 种观点（ ） A)正确 B)不正确
A）表达变得简单 B）减少不必要的存储空间的开销 C）去掉矩阵中的多余元素 D）对矩阵元素的存取变得简单
8.B 9.D 10.B 11.B
补充习题:
12.三元组表不包括（ A) 行数 B) 列数 ）。 C) 元素值 D) 元素总数
13.设已知一个稀疏矩阵的三元组如下：(1,2,3),(1,6,1),

C. 三元组和十字链表 D. 散列表和十字链表
4、一个非空广义表的表头（
）。
A. 不可能是子表
B. 只能是子表
C. 只能是原子
D. 可以是子表或原子
5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000
的内存单元中，则元素A[5][5]的地址是（ ）。
A. 1175
int i; for(i=0;i<s1->length&&i<s1->length;i++)
if(s->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i];
return s1->length-s2->length; }
4、写出算法的功能。 int fun(sqstring *s,sqstring *t,int start){
A. 顺序的存储结构
B. 链式存储结构
C. 数 据 元 素 是
一个字符
D. 数据元素任意
4、设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为（ ）。
A. O(m)
B. O(n)
C. O(m*n)
D.
O(nlog2m)
5、空串和空格串（ ）。
A. 相同
B. 不相同
C. 可能相同
D. 无法确定
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ ）。
A. 连接
B. 求子串
C. 模式匹配 D. 判断子串
2、已知串S=’aaab’，则next数组值为（ ）。

数据结构练习题第一部分绪论一、单选题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. 排序。

第一趟：从第一个字符开始比较，失配时i=3，j=3
主 串
a
a
d
a
a
d
a
a
a
d
a
a
c
aaadaac
复习题
第二趟：next[3]=2，从模式串的第2个字符开始比较，失配时i=3，j=2
主 串
a
a
d
a
a
d
a
a
a
d
a
a
c
aaadaac
第三趟：next[2]=1，从模式串的第1个字符开始比较，失配时i=3，j=1
3、对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求 从顶点A到其他各顶点的最短路径和路径长度。
复习题
3、解：初始状态如下
顶点
A
B
C
D
E
Final
true
false
false
false
false
disk
0
10
18
∞
∞
path
-1
A
A
-1
-1
复习题
第一轮遍历后状态如下
顶点
A
B
C
D
E
Final
④ 快速排序和堆排序都不是稳定排序
复习题
5、将关键字序列（7、18、20、5、28、19、24、33）散列存 储到散列表中，散列表的存储空间是一个下标从0开始的一维 数组，散列函数为：H（key）=（key×3）MOD 7，处理冲突采 用线性探测再散列法，要求装填（载）因子为0.8： (1) 请画出所构造的散列表 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长 度

数据结构-第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中每一个字符出现的次数。

数据结构练习题及答案题目一：给定一个整数数组，找出数组中第二小的元素。

示例输入：[3,6,2,7,1]示例输出：2题目二：实现一个栈的数据结构，并实现栈的push、pop、isEmpty、size等基本操作。

示例输入：push(1)，push(2)，push(3)，pop(，isEmpty示例输出：3，False题目三：给定一个字符串，判断该字符串是否为有效的括号序列。

有效的括号序列定义如下：1.字符串必须是一个空字符串或者由'('、')'、'['、']'、'{'、'}'构成；2.左括号必须用相同类型的右括号闭合；3.左括号必须以正确的顺序闭合。

示例输入："{[((]}"示例输出：True题目四：实现一个队列的数据结构，并实现队列的enqueue、dequeue、isEmpty、size等基本操作。

示例输入：enqueue(1)，enqueue(2)，enqueue(3)，dequeue(，isEmpty示例输出：1，False题目五：给定一个整数数组，找出数组中出现次数最多的元素。

示例输入：[1,2,3,2,1,2,3,3,3]示例输出：3题目六：实现一个链表的数据结构，并实现链表的插入、删除、查找等基本操作。

示例输入：insert(1)，insert(2)，insert(3)，remove(2)，find(3)示例输出：1，False题目七：给定两个有序链表，将其合并为一个有序链表。

示例输入：链表1：1->2->4，链表2：1->3->4示例输出：1->1->2->3->4->4题目八：给定一个字符串，判断该字符串是否为回文串。

回文串定义如下：忽略字母大小写，只考虑字母和数字字符，字符顺序从左到右与从右到左一致。

示例输入："A man, a plan, a canal: Panama"示例输出：True题目九：实现一个二叉树的数据结构，并实现二叉树的插入、删除、查找等基本操作。

完美 WORD 格式数据结构习题集含答案目录目录1选择题2第一章绪论 .2第二章线性表.4第三章栈和队列.6第四章串.7第五章数组和广义表8第六章树和二叉树8第七章图.11第八章查找.13第九章排序.14简答题19第一章绪论 .19第二章线性表.24第三章栈和队列.26第四章串.28第五章数组和广义表29第六章树和二叉树31第七章图.36第八章查找.38第九章排序.39编程题41第一章绪论 .41第二章线性表.41第三章栈和队列.52第四章串.52第五章数组和广义表52第六章树和二叉树52第七章图.52第八章查找.52第九章排序.57选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得X三同学的各科成绩记录，其中数据结构考了 90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.* 数据结构是指（ A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（ A ）。

第四章串一、选择题1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。

A. 连接B. 求子串C. 模式匹配D. 判断子串2、已知串S=’aaab’，则next数组值为（）。

A. 0123B. 1123C. 1231D. 12113、串与普通的线性表相比较，它的特殊性体现在（）。

A. 顺序的存储结构B. 链式存储结构C. 数据元素是一个字符D. 数据元素任意4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

A. O(m)B. O(n)C. O(m*n)D. O(nlog2m)5、空串和空格串（）。

A. 相同B. 不相同C. 可能相同D. 无法确定6、与线性表相比，串的插入和删除操作的特点是（）。

A. 通常以串整体作为操作对象B. 需要更多的辅助空间C. 算法的时间复杂度较高D. 涉及移动的元素更多7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（）。

A. ‘ijing’B. ‘jing&’C.‘ingNa’D. ‘ing&N’8、串是一种特殊的线性表，其特殊性体现在：（）A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符9、设有两个串p和q，求q在p中首次出现的位置的运算称作：（）A．连接B．模式匹配C．求子串D．求串长10、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：（）A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF二、填空题1、求子串在主串中首次出现的位置的运算称为________。

数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。

一、判断题四．串1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。

（）3、一个任意串是其自身的子串。

（）1、∨2、Χ3、∨五．数组和广义表1、多维数组是向量的推广。

（）/*数组和广义表线性表在含义上的扩展*/2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）/*顶点*/3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）/*稀疏矩阵中0元素的分布无规律*/5. 如果采用如下方式定义一维字符数组：const int maxSize = 30;/*常变量在程序运行中不能进行修改*/char a[maxSize];则这种数组在程序执行过程中不能扩充。

6. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。

7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。

/*对于数组一旦规定了它的维数和各维长度，便可为它分配存储空间*/8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。

1-5ΧΧΧΧ∨6-10ΧΧ∨∨∨11、一个广义表的深度是指该广义表展开后所含括号的层数。

（）12. 一个广义表的表头总是一个广义表。

( )13. 一个广义表的表尾总是一个表。

( )14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。

( )15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) )）。

第4章串与数组习题解析（答）习题四串与数组一、选择题1、设有两个串p和q,求q和p中首次出现的位置的运算称作。

A、连接B、求子串C、模式匹配D、求串长2、若串S=’good student’,其子串的数目是。

A、12B、79C、78D、133、串是一种特殊的线性表,其特殊性体现在。

A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符4、串是任意有限个。

A、符号构成的集合B、符号构成的序列C、字符构成的集合D、字符构成的序列5、已知模式串T=’abcdabcd’,则其next数组值为。

A、00123412B、01111234C、01232412D、112134126、数组SZ[-3..50,0..10]含有元素数目为。

A、88B、99C、80D、907、稀疏矩阵一般的压缩存储方法有两种。

A、二维数组和三维数组B、三元组和散列表C、三元组和十字链表D、散列表和十字链表8、一个nⅹn的对称矩阵,如果以行或列为主序放入内存,则其容量为。

A、nⅹnB、nⅹn/2C、(n+1)ⅹ n/2D、(n+1)ⅹ(n+1)/29、对数组经常进行的两种基本操作是。

A、建立与删除B、索引与修改C、查找与修改D、查找与索引10、二维数组A[10..20,5..10]采用行序为主序方式存储,每个数据元素占4个存储单元,且A[10,5]的存储地址是1000,则A[18,9]的地址是。

A、1208B、1212C、1368D、1364二、填空题1、两个字符串相等的充分必要条件是长度相等且对应位置上字符相同。

2、字符在串中的位置,即是字符在该序列中的序号。

3、串是指含n个字符的有限序列且n>=0 。

4、设有串S1=’I an a student’,S2=’st’,其index(S1,S2)= 8 。

5、含零个字符的串称为空串,用Φ表示;其他串称为非空串。

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

6、一个串中任意个连续字符组成的子序列称为该串的子串,该串称为它的所有子串的主串。

数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。