数据结构复习题及答案

数据结构习题

一、 名词解释

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 。

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 个结点。

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），则它的左孩子结点的编

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)采用直接选择排序法排序，则第三趟结束后序列的

2