数据结构复习题及答案

数据结构习题

一、 名词解释

1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度 。

2. 线性表、顺序表、单链表 、双向链表 、循环链表 、双向循环链表 、三个概念的区别：头指针、头结点、首元结点(第1个元素结点 )。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。

4. 树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树 、哈夫曼树、WPL、哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。

6. 查找表、关键字、静态查找、动态查找、 ASL、顺序查找、折半查找、分块查找、二叉排序树。 7、排序、内（外）排序、稳定性、插入（直接、希尔）， 交换（起泡、快速），选择（直接、堆），2路归并。

一、 填空题

1. 数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实

现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。

2. 数据的基本单位是__数据元素__ ，数据的最小单位是__数据项_ 。 3. 算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为 O（n3） _。 5. 一个算法具有5个特性： 确定性 、 可行性 、 有穷性 、输入和输出。

6. 算法性能的分析和度量，可以从算法的 时间复杂度 和 空间复杂度 来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、 线性结构 、 树形结构 和 图型结构 四种类型。 8. 数据结构在计算机中的表示称为数据的 物理结构 ，它可以采用__顺序存储___或__链式存储_

两种存储方法。

9. 线性表有两种存储结构，分别为 顺序存储 和 链式存储 。 10. 链式存储的特点是利用 指针 来表示数据元素之间的逻辑关系。

11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储__存储结构。

12. 线性表中的数据元素之间具有 一对一 的线性关系，除第一个和最后一个元素外，其他数据

元素有且只有 一个 直接后继和直接前趋。

13. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__p->next______和

p->next=__s______的操作。

14. 在一个单链表中删除p的后继结点q时，应执行以下操作p->next= q->next 。 15. 对带头结点head的单链表，则判断其为空的条件为 head->next=NULL 。

1

16. 对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为 p->next=head 。 17. 在栈结构中，允许插入的一端称为 栈顶 ；在队列结构中，允许插入的一端称为 队尾 。 18. 队列中元素的入队和出队应遵循__先进先出 ____原则，数据元素1，2，3，4，5按照次序入队

后，第一个出队的是__1 ____。

19. 在循环队列中，存储空间为0～n-1。设队头指针front指向队头元素前一个空闲元素，队尾指

针指向队尾元素，那么其队空标志为rear=front，队满标志为 (rear+1)% n=front 。 20. 设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存

储地址为 239 。

21. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动 n-i 个元素。

22. 在一个长度为n的顺序表中第i个元素前（1≤i≤n），插入一个元素，需向后移动 n-i+1

个元素。

23. 在顺序存储的线性表中插入或删除一个元素平均约移动表中__50%_（或一半）_的元素。 24. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据

结构。

25. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 26. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为__5___，深度为__3___。 27. 已知广义表A=((a,b,c),(d,e,f))，则运算tail (head (tail(A)))=(e,f)__。

28. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是

_head(head(tail(LS)))___。

29. 广义表((a,b),c,d)的表头是 (a,b) 表尾是 (c,d) 。 30. 广义表(a,b,c,d)的表头是 a 表尾是 (b,c,d)___。

31. 两个串相等的充分必要条件是:__ 串长相等___ 且 __对应的字符相等_。 32. 不含任何字符的串称为 空串 其长度为 0 。

33. 对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的

行 、 列 以及它的值。

34. 若二叉树中有20个叶子结点，则该二叉树有 19 个度为2的结点。 35. 若二叉树中度为2的结点有15个，则该二叉树有__16________个叶子结点。 36. 深度为h且有__2^h-1____个结点的二叉树称为满二叉树。

37. 深度为k的二叉树最多有 _2^k-1 个结点，最少有 k 个结点，第i 层上最多有

_2^(i-1)____个结点。

38. 深度为5的满二叉树共有 31 个结点，其中有__16_____个叶子节点。

39. 若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有 34 个结点。 40. 深度为15的满二叉树上，第11层有 _2^(11-1)=1024 个结点。

2

41. 一棵具有100个结点的完全二叉树，它的深度为 7 ，其中度为1的结点有 1 个。 42. 某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为 dab 。

43. 哈夫曼树是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度

的二叉树。

44. 具有m个叶子结点的哈夫曼树共有 2m-1 个结点。

45. 已知一棵哈夫曼树含有60个叶子结点，则该树中共有 59 个非叶子结点。

46. 在一个具有n个顶点无向完全图中，含有 n(n-1)/2 边；在一个具有n个顶点有向完全

图中，含有 n(n-1) 边。一个具有4个顶点的无向完全图有 6 条边。 47. 具有n个顶点的连通图至少需有 n-1 条边。

48. 一个连通图的生成树是该图的 极小 连通子图。若这个连通图有n个顶点，则它的生成树

有 n-1 条边。

49. 在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的 出度 ；第i列中非零

元素的个数正好是第i个顶点的 入度 。

50. 在一个图中，所有顶点的度数之和等于所有边数的 2 倍。

51. 在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于 1 。 52. 对二叉排序树进行 中序 遍历，可以得到按关键字从小到大排列的结点序列。

53. 一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的

结点时，经过 4 次比较后查找成功。

54. 在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用___顺序

存储__存储方法。

55. 在简单选择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是__归并排序。 56. 冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行 n-1 趟。该

排序方法的时间复杂度为 O(n) 。

57. 给定序列{100，86，48，73，35，39，42，57，66，21}，按堆的定义，则它一定 大根 堆。 58. 数据结构是指数据及其相互之间的_一种或多种关系____。当结点之间存在M对N（M：N）的联

系时，称这种结构为____图状结构_____。

59. 队列的插入操作是在队列的__队尾___进行，删除操作是在队列的__队头__进行。

60. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__直接

插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__简单选择(或直接选择)____排序。

61. 二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，，H，

其后序遍历序列为__ E,F,C,G,H,D,B,A____。

62. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(0＜i＜n-1），则它的左孩子结点的编

3

2

号为 2i ，右孩子结点的编号为 2i+1 ，双亲结点的编号为 i/2 。 63. 在一个具有6个顶点的无向完全图中，包含有 15 条边，在一个具有6个顶点的有向完全

图中，包含有 30 条弧。

64. 快速排序在平均情况下的时间复杂度为__O(nlog2n)__，在最坏情况下的时间复杂度为__

O(n)__。

65. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明__查找成功_____，

若元素的值小于根结点的值，则继续向__左子树______查找，若元素的大于根结点的值，则继续向__右子树______查找。

66. 在循环单链表中，最后一个结点的指针域指向___首___结点。

67. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_9_个，树

的深度为__3___，树的度为__3__。

68. 通常从四个方面评价算法的质量：_正确性_、_可读性_、__健壮性__和__效率与低存储量

需求_。

69. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___499___。 70. 一个算法的时间复杂度为(3n+2n—7)／(5n)，其数量级表示为 O(n) 。

71. 在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n)的排序算法有_快速排序_____。

2

3

2

2

72. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有

限集合。

73. 在归并排序中，进行每趟归并的时间复杂度为____O(n)_____，整个排序过程的时间复杂度为

___O(nlog2n)_______，空间复杂度为___ O(n)_____。

74. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为__9___。

75. 对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 O(n) ，

对用邻接表表示的图进行任一种遍历时，其时间复杂度为___ O(n+e) __。

76. 从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分

别为__1____和___3___。

77. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中_ n-1__个用

于指向孩子， n+1__个指针是空闲的。

78. 从逻辑结构看，线性表是典型的___线性结构__，树是典型的___非线性结构___。

79. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子

结点的条件是____p->lchild==NULL && p->rchild==NULL 。 80. 栈是一种__先进后出___表。队列又称为___先进先出___表。

81. 若对序列(49，38，65，97，76，13，27，50)采用直接选择排序法排序，则第三趟结束后序列的

4

2

状态是__(13,27,38),97,76,49,65,50_。

82. 利用关键码分别为10， 20， 30， 40的四个结点，能构造出__14__种不同的二叉排序树. 83. 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对

其进行（按递增排序），__冒泡排序___最省时间， __快速排序___最费时间。

84. 空串的长度是__0_；空格串的长度是__空格的个数_。串中所含字符个数称为该串的____长度_. 85. 在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为__ O(n)_。 86. 设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是__ front=

（front+1）% m____。

87. 树的度是指__树内各结点的度____的最大值。

88. 已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为__

__p->next=top___和_top=p__。 89. 堆排序的空间复杂度___ O(1)__。

90. 深度为n(n>0)的二叉树最多有_____2^n-1___个结点。

91. 设关键字序列为(Kl，K2，?，Kn)，则用筛选法建初始堆必须从第_ n/2____个元素开始进行筛选。 92. 图有_邻接矩阵___ 、____邻接表__等存储结构，遍历图有 _深度优先搜索____ 、 ___广度优

先搜索__等方法。

93. 在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的__出度__ ，在逆邻接

表中，一个顶点的链表中结点的个数等于这个顶点的___入度__ 。

94. 对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有

序表中的位置可能是_1，3，6，9___。

95. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次

与表中元素______________比较大小。

96. 在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序

过程中需进行_8__趟才能完成。

97. 对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为__48，44，52，63，

80，91__。

98. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序___；若初始记录基本无序，

则最好选用__快速排序___。

99. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录

60插入到有序表时，为寻找插入位置至少需比较 __3________次。

100. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_（80，

70，56，65，24，33，48）或_(24，65，33，80，70，56，48)。

5

二、单选题

1. 在数据结构中，数据的基本单位是( )

A. 数据项 B. 数据元素 C. 数据对象 D. 数据文件 2. 数据结构是（ ）

A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合

D．相互之间存在一种或多种特定关系的数据元素的集合 3. 在数据结构的讨论中把数据结构从逻辑上分为（ ）.

A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构。 4. 算法指的是（ ）。

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 5. 算法分析的目的是（ ）

A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 6. 某程序的时间复杂度为（3n+nlog2

2n+n+8）, 其数量级表示为（ ）。

A．O（n） B．O（nlog2

2n） C．O（n） D．O（log2n） 7. for（i=0；i

for（j=0；j

A［i］［j］=i*j；

上述程序段的时间复杂度为( )

A.O（n2

） B.O（n） C.O（2n） D.O（1） 8. 以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

9. 设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )

A.5 B.6 C.7 D.9

10. 线性表采用链式存储结构时，要求内存中可用存储单元的地址( )

A. 必须是连续的

B. 必须是部分连续的

C. 一定是不连续的 D. 连续和不连续都可以 11. 线性表是具有相同数据类型的n个__________的有限序列。 A.数据项 B.数据元素 C.表元素 D.字符

6

12. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 A. O(1) B. O(n) C. O(n) D. O(nlog2n) 13. 用链接方式存储的队列，在进行插入运算时（ ） A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改

14. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i

15. 若带头结点的单链表的头指针为head，则该链表为空的判定条件是( )

A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head

16. 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）

A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3，2，5，4，1，6 D.1，4，6，5，2，3

17. 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

A．单链表 B.双链表 C.单向循环 D.顺序表 18. 对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 19. 队列的删除操作是在（ ）进行。

A．队首 B．队尾 C．队前 D．对后 20. 计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 21. 串是任意有限个（ ）

①符号构成的序列 ②符号构成的集合 ③字符构成的序列 ④字符构成的集合

22. 如果以链表作为栈的存储结构，则退栈操作时（ ）

① 必须判别栈是否满 ② 对栈不作任何判别 ③ 必须判别栈是否空 ④ 判别栈元素的类型 23. 二分查找要求被查找的表是（ ）

① 键值有序的链接表 ②链接表但键值不一定有序 ③ 键值有序的顺序表 ④顺序表但键值不一定有序

7

2

24. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）

①n2 ②nlog2n ③log2n ④n-1

25. 堆是一个键值序列{k1,k2,?, kn},对i=1,2,?,|_n/2_|,满足( )

①ki≤k2i≤k2i+1 ②ki

③ki≤k2i且ki≤k2i+1(2i+1≤n) ④ki≤k2i 或ki≤k2i+1(2i+1≤n) 26. 队列的插入操作是在（ ）进行。

A．队首 B．队尾 C．队前 D．对后 27. 一棵具有５层满二叉树中节点总数为（ ）。

A、３１ B、３２ C、３３ D、１６ 28. 快速排序在最坏情况下的时间复杂度为（ ）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n) 29. 广义表是线性表的推广，它们之间的区别在于( )。

A．能否使用子表 B．能否使用原子项 C．表的长度 D．是否能为空

30. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( )。 A.有向完全图 B.连通图

C.强连通图 D.有向无环图

31. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( ) A.O(1) B.O(log2n) C.O(n) D.O(n log2n) 32. 与线性表相比，串的插入和删除操作的特点是（ ） A.通常以串整体作为操作对象 B.需要更多的辅助空间 C.算法的时间复杂度较高 D.涉及移动的元素更多

33. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）。

A.head= =NULL B.head–>next= =NULL C.head!=NULL D.head–>next= =head

34. 在单链表中，指针p指向值为x的结点，能实现“删除x的后继”的语句是__________。

A. p=p->next ; B. p=p->next->next ; C. p->next=p ; D. p->next=p->next->next ;

35. 一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( )

A. dceab

B. decba

C. edcba

D. abcde

2

36. 若进栈序列为a，b，c，进栈过程中允许出栈，则以下_____是不可能得到的出栈序列。

A. a,b,c B. b,a,c C. c,a,b D. c,b,a

37. 若进栈序列为１，２，３，４，进栈过程中允许出栈，则可能的出栈序列是_____。

8

A. ２，４，１，３ B. ３，１，４，２ C. ３，４，１，２ D. １，２，３，４

38. 设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( )

A.DCBA B.CDAB C.DBAC D.DCAB

39. 一个队列的入队序列是1，2，3，4，则队列的输出序列是( ) A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1

40. 一个最多能容纳m个元素的顺序存储循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是__________

A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rear C. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear

41. 设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）.

A.front=front+1 B.front=(front+1)% m C.rear=(rear+1)%m D.front=(front+1)%(m+1)

42. 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n

43. 若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队里中删除一个元素，再加入两个元素后，rear和front的值分别是（ ） A. 1和5 B. 5和1 C. 2和4 44. 两个字符串相等的条件是（ ）

A. 串的长度相等 B. 含有相同的字符集 C. 都是非空串

D. 串的长度相等且对应的字符相同

D. 4和2

45. 如下陈述中正确的是______。

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空格串 46. 一棵含18个结点的二叉树的高度至少为_______。

A. 3 B. 4 C. 5 D. 6

47. 将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_______。

A. 16 B. 30 C. 31 D.32

48. 在程序的执行过程中，对实现函数的递归调用应该借助于_______结构。

9

A. 线性表 B. 栈 C . 队列 D. 树

49. 具有100个结点的完全二叉树的深度为__________。

A.6 B. 7 C. 8 D. 9

50. 已知二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为_______。

A．DEBAFC

B．DEFBCA

C． DEBCFA D．DEBFCA

51. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )

A. 栈 B. 队列 C. 树 D. 图

52. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）

A. 0 B. 1 C. 48

D. 49

53. 具有100个结点的完全二叉树，其中含有__________个度为1的结点。

A.1 B. 0 C. 2 D. 不确定

54. 已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为_______。

A．ABCD

B．BCDA

C．CDBA

D．DCBA

55. 对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（A.99

B.98

C.97 D.50

56. 有m个叶子结点的哈夫曼树，其结点总数是（ ）

A.2m-1 B.2m

C.2m+1

D.2(m+1)

57. 无向图的邻接矩阵是一个_______。

A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵 58. 广义表中元素分为( )

A．原子元素 B．表元素 C．原子元素和表元素 D．任意元素 59. 广义表A=(( )，(a)，(b，(c，d)))的长度为( ) .

A．2 B．3 C．4 D．5

60. 广义表A：(( )，(a)，(b，(c，d)))的深度为( ) .

A．2 B．3 C．4 D．5

61. 若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）

A．图中每个顶点的入度

B．图中每个顶点的出度

C．图中弧的条数 D．图中连通分量的数目 62. 邻接矩阵为对称矩阵的图是( )

A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图 63. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )

A. n/2 B. n C. n-1 D. n+1 64. 下面的序列中________是大根堆。

10

）

A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2 C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,1

65. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为________。

A.38，40，46，56，79，84 B.40，38，46，79，56，84 C.40，38，46，56，79，84 D.40，38，46，84，56，79

66. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为（ ）

A．（1，2，3，4，5，6，7，8） C．（2，1，4，3，5，7，8，6）

B．（1，4，3，2，5，7，8，6） D．（8，7，6，5，4，3，2，1）

67. 使用折半查找，线性表必须_______。

Ａ.以顺序方式存储 Ｂ.以顺序方式存储，且元素已按值排好序 Ｃ.以链式方式存储 Ｄ.以链式方式存储，且元素已按值排好序

68. 已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）

A.4 B.5 C.6 D.7

69. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在折半查找关键字b的过程中，先后进行比较的关键字依次为（ ）

A．f,c,b B．f,d,b C．g,c,b D．g,d,b

70. 在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表

C.静态查找表与动态查找表

B.动态查找表

D.静态查找表或动态查找表

71. 有一个有序表为：(2,5,8,11,15,16,22,24,27,35,50)当折半查找值为24的结点时，经过_____次比较后查找成功。

A. 1 B. 2 C. 3 D. 4

72. 有一个有序表为：(21,32,41,45,62,75,77,82,95),当折半查找值为82的结点时，经过_____次比较后查找成功。

A. 1 B. 2 C. 4 D. 3 73. 下面排序算法的时间复杂度最小的是_______。 A．直接插入排序

B．简单选择排序 C．冒泡排序 D．快速排序

74. 以下排序方法中，稳定的排序方法是__________。

A. 直接插入排序和冒泡排序 B. 简单选择排序和归并排序

11

C. 冒泡排序和快速排序 D. 堆排序和基数排序 75. 按排序过程中依据的原则分类，快速排序属于( ) A.插入类的排序方法

B.选择类的排序方法

C.交换类的排序方法 D.归并类的排序方法

76. 在一棵二叉排序树中，若左子树不空，左子树上所有结点的值均（ ）根结点的值。

A．大于 B．小于 C．不小于 D．大于等于

75. 用邻接表表示图进行深度优先遍历时，通常是采用（ ）来实现算法的。

A．栈 B. 队列 C. 树 D. 图 76. 用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的。

A．栈 B. 队列 C. 树 D. 图 77.从一个顺序队列删除元素时，首先要（ ）。

A．前移一位队首指针 B.后移一位队首指针

C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 78.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。

A．n B．2n C．n-1 D．n+1

79.在有向图的邻接表存储表示中，顶点V在链表结点中出现的次数是（ ）。

A.顶点V的入度 B.顶点V的出度

C.顶点V的度 D.依附于顶点V的边的数目

80.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A．74 B．23 C．51 D．53

81.设串sl=″Data Structures with ″，s2=″it″，则子串定位函数index的值为（ ）。

A．15 B．16 C．17 D．18 82.一棵深度为6的二叉树至多有（ ）个结点。

A．64 B．32 C．31 D．63

83. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号

为1，编号为49的结点X的双亲编号为（ ）。 A．24 B．25 C．23 D．无法确定

84. 树的后根遍历与其转换的相应二叉树的（ ）遍历的结果序列相同。

A.先序 B.中序 C.后序 D.层次遍历

85. 链表适用于（ ）查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机

86. 折半查找有序表{6,15,30,37,65,70,72,89,99},若要查找元素37，需要依次与表中元素

__________进行比较。

A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，37

12

87．下列排序方法中，稳定的排序方法为（ ）。

A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序

88．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N;

89．在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。

A．基地址 B．结点大小

C．向量大小 D．基地址和结点大小 90．在一棵二叉树中，第4层上的结点数最多为（ ）。

A．31 B．8 C．15 D．16 91．线性表的顺序存储结构是一种_______的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取 92.数据结构在计算机内存储器中的表示是指（ ） A.数据结构 B.数据元素之间的关系 C.数据的逻辑结构 D.数据的物理存储结构

93. 下述几种排序方法中，要求内存最大的是（ ）

Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序

94.若长度为n的线性表采用顺序存储结构，则在表中第i个位置（1<=i<=n+1）插入一个新元素的算法的时间复杂度为（ ）

A.O(0) B.O(1) C.O(n) D.O(n)

95.一个栈的输入序列为ABCDE，则不可能出现的输出序列是（ ） A.ABCDE B.EDCBA C.CABED D.BADCE

96. 对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，

19，22，49，30，65，35，86），则可以认为使用的排序方法是（ ） A．选择排序

B．冒泡排序 C．快速排序

D．插入排序

2

97.对二叉树的结点从1开始编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小于其右(孩子如果有的话）的编号，则可以采用（ ）次序的遍历实现二叉树的结点编号 A.先序 B.中序 C.后序 D.层次遍历 98. ________是一棵满二叉树。

A．二叉排序树 B．深度为5有31个结点的二叉树 C．有15个结点的完全二叉树 D．哈夫曼（Huffman）树

99.某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括（ ）棵树 A.1 B.2 C.3 D.4

100. 下面关于图的存储的叙述中正确的是（ ）

13

A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关

B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 D.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 三、判断题：（对的打?，错的打?） （ ? ） 1.数据元素是数据处理的最小单位。 （ ? ） 2.数据项是数据处理的最小单位。

（ ? ） 3.线性表的顺序存储结构优于链式存储结构。

（ ? ） 4.顺序存储的线性表可以随机访问,链式存储的线性表只能顺序访问。

（ ? ） 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。 （ ? ） 6.线性表的顺序存储和链式存储都必须占用内存中的连续存储单元。 （ ? ） 7.栈和队列的存储方式,既可以顺序存储也可以链式存储。 （ ? ） 8.栈和队列都是操作受限制的线性表。

（ ? ） 9.栈的特点是先进后出,队列的特点是先进先出。 （ ? ） 10.空串是任意串的子串。

（ ? ） 11.串中任意个字符组成的子序列称为该串的子串。 （ ? ） 12.树型结构中每个结点都有一个直接前趋。

（ ? ） 13.二叉树中每个结点的度最大为2,因此二叉树是一种特殊的树。 （ ? ） 14.满二叉树中存在度为1的结点。

（ ? ） 15.完全二叉树中每个结点或者没有孩子或者有2个孩子。

（ ? ） 16.在任意一棵二叉树中,叶子结点的个数等于度为2结点的个数加1。 （ ? ） 17.由树转化为二叉树,其根结点的右子树总是空的。 （ ? ） 18.最小生成树是指边数最少的生成树。

（ ? ） 19. 一棵哈夫曼树有m 个叶子结点,则其结点总数为2m-1。 （ ? ） 20.树的先根遍历序列等同于该树对应的二叉树中序遍历序列。 （ ? ） 21. “顺序查找法”是指在顺序表上进行查找的方法。 （ ? ） 22.快速排序在任何情况下圴可得到最块的排序效果。 （ ? ） 23.在有向图中每个顶点的度等于各顶点的入度与出度之和。 （ ? ） 24.二叉排序树是用来进行排序的。

（ ? ） 25.衡量排序算法的两个主要性能指标是执行排序算法所需要的时间和执行排序算法所需

要的附加空间。

（ ? ） 26.哈夫曼树是带权值的树,且权值较大的结点离树较近。 1．双链表中至多只有一个结点的后继指针为空。（ ? ）

14

2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ? ）

3．对链表进行插入和删除操作时，不必移动结点。（ ? ） 4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ? ） 5．线性表的逻辑顺序与物理顺序总是一致的。（ ? ）

6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( ? )

7．边数很多的稠密图，适宜用邻接矩阵表示。（ ? ）

8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ? ） 9．键值序列{A，C，D，E，F，E，F}是一个堆。（ ? ）

10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（ ? ） 11. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( ? ) 12. 每种数据结构都应具备三种基本运算：插入、删除和搜索。（? ）

13. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。( ? ) 14. 空串与由空格组成的串没有区别。( ? ) 15. 单链表可以实现随机存取。( ? )

16. 深度为h的非空二叉树的第i层最多有2h-1 个结点。( ? ) 17. 完全二叉树就是满二叉树。( ? )

18. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ? ) 19. 非空二叉排序树的任意一棵子树也是二叉排序树。( ? ) 20. 有向图是一种非线性结构。( ? )

21. 图的广度优先搜索算法通常采用递归算法求解。（ ? ）

22. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（? ） 23. 折半查找方法适用于按值有序的线性链表的查找。( ? )

24. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。( ? ) 25. 选择排序过程中元素之间的比较次数与原始序列的状态无关。( ? ) 26．栈是一种线性结构。（ ? ）

27．顺序表中所有结点的类型必须相同。（ ? ）

28．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( ? ) 29．递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（? ） 30．用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2。（? ）

15

int Depth (BiTree T ) { // 返回二叉树的深度

if (__T==NULL ______________) depthval = 0; else {

depthLeft = Depth(___T-> lchild_________); depthRight= Depth(____T-> rchild_________);

depthval = 1 + (depthLeft > depthRight ？ depthLeft：depthRight); }

return depthval; }

6.以下是用简单选择排序算法完成按关键字升序排序的功能。

其中数据类型定义为: #define MAXSIZE 20 typedef struct { int key;

Infotype otherinfo; }RcdType; Typedef struct

{ RcdType r[MAXSIZE+1]; int length ; }SqList; 算法：

Void SelectSort(SqList &L) { for (i=1；i

for(j=i+1;j <=L.length;++j)

if (_L->r[j].key< L->r[k].key_) k=j; if (__k!=i__) { temp= L.r[i]; L.r[i]=L.r[k];

L.r[k]=temp ；} } }

21

7.以如下为折半查找的非递归算法，其功能是从一维数组A[n]中查找关键字为K的元素，若查找成功则返回对应元素的下标，否则返回-1，试将其填写完整。 算法: int Bin_search (ElemType A[ ],int n,KeyType K)

{ int low，high ，mid； low =0; high=n-1; while (<=high)

{ mid=___(low+high)/2_____； if (K==A[mid].key) return mid;

else if (K<[mid].key) ___high =mid-1___; else __low =mid+1____; }

return -1; }

8.以下是用直接插入排序算法完成按关键字升序进行排序的功能。

其中数据类型定义为: #define MAXSIZE 20 typedef struct { int key;

Infotype otherinfo; }RcdType; Typedef struct

{ RcdType r[MAXSIZE+1]; int length ; }SqList; 算法：

Void InsertSort(SqList &L) { for (i=2；i<=L.length；++i)

if (__L->r[i].key <_ L->r[i-1].key_____){

L.r[0]=L.r[i];

for(j=i-1;L.r[0].key< L.r[j] .key;--j) _ L->r[j+1].key = L->r[j].key______ ; L.r[j+1]=L.r[0]; } }

22

9.此为以BST为树根指针的二叉排序树上插入值为item的结点的递归算法。

Void Insert(BtreeNode &BST，ElemType item) {

if(BST==NULL)

{ BtreeNode *p=newBTreeNode; p->data=item;

_ p->lchild=p->rchild=NULL____; BST=p; }

else if(itemdata)____ T->lchild=p______; else__ T->rchild=p_________; }

10.将下列单链表的插入算法补充完整。

算法说明，在带有头结点的单链线性表中第i个位置之前插入元素x；

typedef _ struct node _ { DateType data; struct node *next;

}Lnode,*LinkList;

int listinsert(LinkList head,int i,DataType x) {

LinkList p=head,s; int j=0;

while(p!=NULL&&jnext___; j++; }

if (p==NULL) return(0);

s=_(Lnode*)__malloc(sizeof(Lnode)); s->data=x;

__s->next=p->next______; __ p->next=s __________; return(1); }

23

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