数据结构各章作业题目

第一章作业 一、选择题

1. 被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的

这种关系称为( )。 A. 规则 B. 结构 C. 集合 D. 运算 2. 在Data_Structure=(D,S)中，D是( )的有限集合。

A. 数据元素 B. 算法 C. 数据操作 D.数据对象 3. 计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。

A. 数据与数据 B. 数据元素与数据元素 C. 元素内数据项与数据项 D. 数据文件内记录与记录 4. 顺序存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 5. 链接存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 6. 从逻辑上可将数据结构分为( )。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 7. 以下选项属于线性结构的是( )。

A. 广义表 B. 二叉树 C. 串 D. 稀疏数组 8. 以下选项属于非线性结构的是( )。

A. 广义表 B. 队列 C. 优先队列 D. 栈 9. 以下属于逻辑结构的是( )

A. 顺序表 B. 散列表 C. 有序表 D. 单链表 10. 一个完整的算法应该具有( )等特性。

A. 可执行性、可修改性和可维护性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和可靠性 D. 正确性、可读性和有效性

11. 若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。

A. 迭代 B. 递归 C. 先递归后迭代 D. 先迭代后递归 12. 一个递归算法必须包括( )

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分

13. 算法的时间复杂度与( )有关。

A. 问题规模 B. 源程序长度 C. 计算机硬件运行速度 D. 编译后执行程序的质量

二、指出下列各算法的功能并求出其时间复杂度。 (1)

int Prime(int n){

int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根 while(i<=x){

if(n%i==0)break; i++; }

if(i>x) return 1;

1

elsereturn 0; } (2)

int sum1(int n){ int p=1,s=0;

for(int i=1;i<=n;i++){ p*=i;s+=p; }

return s; } (3)

int sum2(int n){ int s=0;

for(int i=1;i<=n;i++){ int p=1;

for(int j=1;i<=i;j++) p*=j; s+=p; }

return s; } (4)

int fun(int n){ int i=1,s=1;

while(s

void mtable(int n){

for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++)

cout<

2

第二章作业

一、选择题

1. 在线性表中的每一个表元素都是不可再分的( )

A. 数据项 B. 数据记录 C. 数据元素 D. 数据字段 2. 顺序表是线性表的( )存储表示。

A. 有序 B. 连续 C. 数组 D. 顺序存取

3. 若长度为n的非空线性表采用顺序存储结构，在表中的第i个位置插入一个数据元素，i的合法值

应该是( ) A. 1?i?n B. 1?i?n?1 C. 0?i?n?1 D. 0?i?n

4. 若设一个顺序表的长度为n，那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，

查找成功的数据平均比较次数为( ) A. n B. n/2 C. (n?1)/2 D. (n?1)/2 5. 在长度为n的顺序表的表尾插入一个新的元素的时间复杂度为( )

A. O(n)

B. O(1)

C. O(n)

2D. O(log2n)

6. 数据结构反映了数据元素之间的结构关系。单链表是一种( )。 A. 顺序存储线性表 B. 非顺序存储非线性表 C. 顺序存储非线性表 D. 非顺序存储线性表 7. 单链表又称为线性链表，在单链表上实施插入和删除操作( )

A. 不需移动结点，不需改变结点指针 B. 不需移动结点，只需改变结点指针 C. 只需移动结点，不需改变结点指针 D. 既需移动结点，又需改变结点指针 8. 已知L是带头结点的单链表，则删除首元素结点的语句是( )

A. L=L->next; B. L->next=L->next->next; C. L=L->next->next; D. L->next=L; 9. 已知单链表A长度为m，单链表B长度为n，若将B链接在A的末尾，在没有链尾指针的情况下，算法的时间复杂度应为( )。

A. O(1)

B. O(m)

C. O(n)

D. O(m?n)

10. 给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是( )

A. O(1)

B. O(n)

C. O(n)

2D. O(nlog2n)

二、算法设计

1. 设计一个算法，从顺序表L中(SqList L)删除具有给定值x(ElemType x)的所有元素。

2. 设计一个算法，从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。 3. 设计一个算法，在非递减有序的带头结点的单链表中删除值相同的多余结点。

3

第三章作业

一、选择题

1. 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，

相应的S和X的操作序列为( ) A. SXSXSSXX B. SSSXXSXX C. SXSSXXSX D. SXSSXSXX 2. 假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是( )

A. 1,2,3,4 B. 4,1,2,3 C. 4,3,2,1 D. 1,3,4,2 3. 已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是( )。

A. j?i

B. n?i

C.j?i?1

D. 不确定

4. 已知一个栈的进栈序列为1,2,3,?,n，其输出序列是p1,p2,p3,?,pn。若p1?n，则pi的值是( )

A. i

B. n?i

C.n?i?1

D. 不确定

5. 已知一个栈的进栈序列为1,2,3,?,n，其输出序列是p1,p2,p3,?,pn。若p1?3，则p2的值是( )

A.一定是2

B. 一定是1

C.可能是1

D. 可能是2

6. 已知一个栈的进栈序列为p1,p2,p3,?,pn，其输出序列是1,2,3,?,n。若p3?1，则p1的值是( )

A.一定是2

B. 可能是2

C.不可能是2

D. 一定是3

7. 已知一个栈的进栈序列为p1,p2,p3,?,pn，其输出序列是1,2,3,?,n。若p3?3，则p1的值是( )

A.一定是2

B. 可能是2

C.不可能是1

D. 一定是1

8. 已知一个栈的进栈序列为p1,p2,p3,?,pn，其输出序列是1,2,3,?,n。若pn?1，则p1的值是( ) A. n?i?1 B. n?i C.i D. 不确定

9. 设栈S和队列Q的初始状态均为空，元素1,2,3,4,5,6,7，依次进入S。如果每个元素出栈后立即进

入队列Q，且7个元素的出队顺序为2,4,3,6,5,1,7，则栈S的容量至少是( ) A. 1 B. 2 C. 3 D. 4

10. 对中缀表达式3?2*(4?2*2?6*3)?5求值，在求值过程中扫描到6时，操作数栈和操作符栈的内容分别是( )

A. 3,2,4,2,2和+,*,(,+,* B. 3,2,4,4和+,*,(,+ C. 3,2,8和+,*,( 二、算法设计题

1. 详见《数据结构题集(C语言版)》第25页3.24。 2. 详见《数据结构题集(C语言版)》第25页3.25。

D. 3,2,8,6和+,*,(,-

4

第四章作业

11. 串是一种特殊的线性表，其特殊性体现在( )

A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符

12. 设有两个串T和P，求P在T中首次出现的位置的运算叫做( )。

A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 13. 下面关于串的叙述中，哪一个是不正确的？（ ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 14. 串的长度是指（ ）

A．串中所含不同字母的个数 B．串中所含字符的个数

C．串中所含不同字符的个数 D．串中所含非空格字符的个数 15. 两个串相等的充分必要条件是（）

A．串中所含的字符相同 B．串中所含字符的个数相同，且对应位置上的字符也相同 C．串中所含的字符个数相同 D．串中对应位置上的字符相同 6. 已知p=”abcaabbabcabaacbacb”，求出next函数值。

5

21. 求最短路径的Dijkstra算法的时间复杂度为( )。 A. O(n) B. O(n?e) C. O(n2) 22. 求最短路径的Floyd算法的时间复杂度为( )。

D. O(ne)

A. O(n) B. O(ne) C. O(n2) D. O(n3) 23. 设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为( )。 A. O(n) B. O(n?e) C. O(n2) D. O(ne)

24. 设有向图具有n个顶点和e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度

为( )。 A. O(nlog2e) B. O(n?e) C. O(n2) 二、应用题

25. 针对图1所示的有向图，画出该图的邻接矩阵、邻接表和逆邻接表。

ADD. O(ne)

BEabdcegf 图1 图2

26. 对图2所示的无向图，从顶点a开始进行深度优先遍历，给出2个可得到的顶点访问序列；从顶

点a开始进行广度优先遍历，给出2个可得到的顶点访问序列。

27. 已知一个带权连通图如图3所示，分别使用Prim算法和Kruskal算法求其最小生成树。

B1220CFa3b12cA586D1510C98FE1510651

4

d8e9f

图3 图4

28. 已知一个带权有向图如图4所示，用Dijkstra算法求从顶点a到其余各顶点的最短路径及路径长

度。

29. 如图所示的AOE网，求

(1) 完成此工程最少要多少天(设弧上的权值为天数)； (2) 每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai)； (3) 哪些是关键活动；

(4) 是否存在某些活动，当其提高速度后能使整个工程缩短工期?

11

BF5A3D4G4J36C631E52I24H

图5

12

第九章作业 一、选择题

30. 顺序查找算法适用于( )。

A. 线性表 B. 查找树 C. 查找网 31. 顺序查找法适用于线性表的( )。

A.散列存储 B.压缩存储 C. 索引存储

32. 采用顺序查找方式查找长度为n的顺序表时，平均查找长度为( )

D. 连通图 D. 顺序或链接存储

A. n B. n/2 C. (n?1)/2 D. (n?1)/2

33. 如果有5个关键吗{a,b,c,d,e}放在顺序表中，他们的查找概率分别为{0.35,0.25,0.20,.015,0.05}，可

使平均查找长度达到最小的存放方式是( )。 A. d,a,b,c,e B. e,d,c,b,a C. a,b,c,d,e D. a,c,e,d,b

34. 对于长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功

的平均查找长度为( ) A. n/4 B. n/2 C. (n?1)/2 D. (n?1)/2 35. 对线性表进行折半查找时，要求线性表必须( )

A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键吗有序排列 D. 以链接方式存储，且结点按关键吗有序排列 36. 采用折半查找法查找长度为n的有序顺序表时，平均查找长度为( )

A. O(n) B. O(log2n) C. O(n) D. O(nlogn) 37. 对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为( )。

A. 3 B.4 C. 5 D. 6 38. 已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值为18的元素时，查

找成功的数据比较次数为( )。 A. 1 B.2 C. 3 D. 4 39. 使用散列法时确定元素存储地址的依据是( )。

A. 元素的序号 B. 元素个数 C. 关键吗 D. 非码属性 40. 设一个散列表中有n个元素，用散列法进行查找的平均查找长度是( )。

A. O(1) B. O(n) C. O(log2n) D. O(n) 41. 使用散列函数将元素的关键吗映射为散列地址时，常会发生冲突。此时的冲突是指( )。

A. 两个元素具有相同的序号 B. 两个元素的关键码不同，而非关键码相同 C. 不同关键码对应到相同的存储地址 D. 装载因子过大，数据元素过多 42. 计算出的地址分布最均匀的散列函数是( )。

A. 数值分析法 B. 除留余数法 C. 平方取中法 D. 折叠法 43. 将10个元素散列到大小为100000个元素的散列表中，( )产生冲突。

A. 一定会 B. 一定不会 C. 仍可能会 D. 以上都不对 44. 采用线性探测法解决冲突时计算出的一系列“下一个空位”( )。

A. 必须大于等于原散列地址 B. 必须小于等于原散列地址 C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制 45. 包含有4个结点的元素值互不相同的二叉查找树有( )棵。

A. 4 B. 6 C. 10 D. 14

46. 利用逐个数据插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}对应的二叉查找树后，查找元素

20需要进行( )次元素之间的比较。 A. 4 B. 5 C. 7 D. 10

47. 一颗高度为h的AVL树，若其每个非叶子结点的平衡因子都是0，则该树共有( )个结点。

2213

A. 2?1 B. 2

48. 高度为7的AVL树最少有( )个结点。

A. 12 B. 21 49. 高度为7的AVL树最多有( )个结点。 A. 63 B. 64 二、应用题

h?1h?1C. 2h?1?1 D. 2?1 D. 54 D. 127

hC. 33 C. 65

50. 设有一个关键码的输入序列{55,31,11,37,46,73,63}，从空树开始构造AVL树，画出每加入一个新结

点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。

51. 分别画出在图1所示的AVL树中插入15、36后树的变化。如果有平衡化旋转，注明相关结点平

衡因子的变化(注意，15和36是各自独立插入到图1所示的AVL树中)。

1396112202427413843471821263140 图1

52. 已知含12个关键字的有序表及其相应的权值如下表，试按次优查找树的构造算法，画出由这12

个关键字构造所得的次优查找树，并计算它的PH值。

关键字 权值 A 8 B 2 C 3 D 4 E 9 F 3 G 2 H 6 I 7 J 1 K 1 L 4 53. 对于23题有序表及其相应的权值，试按次优查找树的构造算法并加适当调整，画出由这12个关

键字构造所得的次优查找树，并计算它的PH值。通过适当调整后得到的次优查找树是否更优？ 54. 设哈希表HT[15]，哈希函数为H(key)?key。用开放地址法解决冲突，对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。采用线性探测法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。

55. 设哈希表HT[15]，哈希函数为H(key)?key。用开放地址法解决冲突，对下列关键码序列

12,23,45,57,20,03,78,31,15,36造表。采用再哈希法寻找下一个空位，再哈希函数为RH(key)?(7key)?1，寻找下一个空位置的公式为Hi?(Hi?1?RH(key))，H0?H(key)。画

出相应的哈希表，并计算等概率下查找成功的平均查找长度。

14

第十章作业 一、选择题

56. 排序算法的稳定性是指( )。

A. 经过排序后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序后，能使值相同的数据保持原顺序中的绝对位置不变 C. 经过排序后，数据序列的存放数组的结构保持不变 D. 经过排序后，数据序列的存放数组的结构随之变化

57. 若要求在最坏情况下也能尽快地对序列进行稳定的排序，则应选( )。

A.起泡排序 B.快速排序 C. 归并排序 D. 堆排序

58. 每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已

排序序列中的适当位置，此种排序方法叫做( ) A. 起泡排序 B. 直接插入排序 C. 简单选择排序 59. 对5个不同数据元素做直接插入排序，其数据比较次数最多是( )。

A. 8 B. 10 C. 15 60. 直接插入排序在最好情况下的时间复杂度是( )

D. 二路归并排序 D. 25

2A. O(log2n) B. O(n) C. O(nlog2n) D. O(n) 61. 每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法是( )

A. 堆排序 B. 选择排序 C. 起泡排序 D. 基数排序

62. 一个元素序列的排序码为{46,79,56,38,40,84}，采用快速排序(以第一个元素为枢轴)得到的第一次

划分结果为( ) A. {38,46,79,56,40,84} B. {38,79,56,46,40,84} C. {40,38,46,79,56,84} D. {38,46,56,79,40,84} 63. 每次从待排序序列中挑选从一个最小或最大元素，吧它们交换到该序列的最前端，此种排序方法

是( )。 A. 起泡排序 B.直接插入排序 C. 简单选择排序 D. 二路归并排序 64. 堆是一种有用的数据结构。在以下排序码序列中小顶堆是( )。

A. {16,72,31,23,94,53} B.{94,53,31,72,16,53} C. {16,53,23,94,31,72} D. {16,31,23,94,53,72} 65. 向具有n个元素的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) 66. 从具有n个元素的堆中删除一个元素的时间复杂度为( )。

D. O(nlog2n)

A. O(1) B. O(n) C. O(log2n) D. O(nlog2n) 67. 在用二叉树实现的应用中，从任意结点出发到根的路径上所经过的结点序列是按其排序码有序的，

这样的树是( )。 A. 完全二叉树 B. AVL树 C. 堆 D. 二叉排序树 68. 下列排序算法中最坏情况下的时间代价不高于O(nlog2n)的是( )。

A. 插入排序 B. 归并排序 C. 快速排序 D. 希尔排序 69. 下列算法中不稳定的算法是( )。

A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 70. 以下不属于内排序方法的是( )。

A. 起泡排序 B. 拓扑排序 C. 基数排序 D. 快速排序 二、应用题

71. 设待排序的排序码序列为{12,2,16,30,28,10,16*,20,6,18}，试写出使用希尔排序(增量为5,2,1)方法每

趟排序后的结果，并说明做了多少次排序码比较。

72. 设待排序的排序码序列为{38,07,72,12,43,65,62,88,31,27,15,54}，试给出使用快速排序算法(以第一

15

个元素为枢轴)每一趟排序结束时的排序码状态。

73. 设待排序的排序码序列为{12,2,16,30,10,16*,15,6}，试写出使用堆排序进行从小到大排序，每趟排

序后的结果。

74. 如果只想得到一个序列中第K个最小元素之前的部分排序序列，那么最好应采用哪种排序算法？

为什么？如由这样一个序列：57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 得到其第3个最小元素之前的部分排序序列：6,7,9, 用你选用算法实现时，共执行多少次比较？

16

个元素为枢轴)每一趟排序结束时的排序码状态。

73. 设待排序的排序码序列为{12,2,16,30,10,16*,15,6}，试写出使用堆排序进行从小到大排序，每趟排

序后的结果。

74. 如果只想得到一个序列中第K个最小元素之前的部分排序序列，那么最好应采用哪种排序算法？

为什么？如由这样一个序列：57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 得到其第3个最小元素之前的部分排序序列：6,7,9, 用你选用算法实现时，共执行多少次比较？

16

本文来源：https://www.bwwdw.com/article/reh7.html