数据结构复习题及答案

《数据结构复习题及答案》由会员分享，可在线阅读，更多相关《数据结构复习题及答案（23页珍藏版）》请在金锄头文库上搜索。

1、数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度 。2.线性表、顺序表、单链表 、双向链表 、循环链表 、双向循环链表 、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树 、哈夫曼树、WPL、哈夫曼编码。5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表

2、、DFS、BFS。6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。7、排序、内（外）排序、稳定性、插入（直接、希尔）， 交换（起泡、快速），选择（直接、堆），2路归并。一、 填空题1. 数据结构是研究数据的_逻辑结构_和_物理结构_，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_时间复杂度_和_空间复杂度_。学号2. 数据的基本单位是_数据元素_ ，数据的最小单位是_数据项_ 。3. 算法是对特定问题求解_步骤_的一种描述，是指令的有限序列。4. 一个算法的时间复杂度为(3n3+2n

3、7)，其数量级表示为 O（n3） _。5. 一个算法具有5个特性： 确定性 、 可行性 、 有穷性 、输入和输出。6. 算法性能的分析和度量，可以从算法的 时间复杂度 和 空间复杂度 来评价算法的优劣。学号7. 数据的逻辑结构包括集合结构、 线性结构 、 树形结构 和 图型结构 四种类型。8. 数据结构在计算机中的表示称为数据的 物理结构 ，它可以采用_顺序存储_或_链式存储_两种存储方法。9. 线性表有两种存储结构，分别为 顺序存储 和 链式存储 。10. 链式存储的特点是利用 指针 来表示数据元素之间的逻辑关系。姓名11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储_存储

4、结构。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. 在栈结构中，允许插入的一端称为 栈顶 ；在队列结构中

5、，允许插入的一端称为 队尾 。18. 队列中元素的入队和出队应遵循_先进先出 _原则，数据元素1，2，3，4，5按照次序入队后，第一个出队的是_1 _。19. 在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 (rear+1)% n=front 。20. 设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为 239 。21. 在一个长度为n的顺序表中删除第i个元素（1in），需向前移动 n-i 个元素。22. 在一个长度为n的顺序表中第i个元素前（

6、1in），插入一个元素，需向后移动 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

7、,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. 若二叉树中度为

8、2的结点有15个，则该二叉树有_16_个叶子结点。36. 深度为h且有_2h-1_个结点的二叉树称为满二叉树。37. 深度为k的二叉树最多有 _2k-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，中根遍历序列为

9、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. 在有

10、向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的 出度 ；第i列中非零元素的个数正好是第i个顶点的 入度 。50. 在一个图中，所有顶点的度数之和等于所有边数的 2 倍。51. 在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 1 。52. 对二叉排序树进行 中序 遍历，可以得到按关键字从小到大排列的结点序列。53. 一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值为82的结点时，经过 4 次比较后查找成功。54. 在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用_顺序存储_存储方法。55. 在简单选

11、择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是_归并排序。56. 冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行 n-1 趟。该排序方法的时间复杂度为 O(n2) 。57. 给定序列100，86，48，73，35，39，42，57，66，21，按堆的定义，则它一定 大根 堆。58. 数据结构是指数据及其相互之间的_一种或多种关系_。当结点之间存在M对N（M：N）的联系时，称这种结构为_图状结构_。59. 队列的插入操作是在队列的_队尾_进行，删除操作是在队列的_队头_进行。60. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排

12、序方法叫做_直接插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_简单选择(或直接选择)_排序。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(0in-1），则它的左孩子结点的编号为 2i ，右孩子结点的编号为 2i+1 ，双亲结点的编号为 i/2 。 63. 在一个具有6个顶点的无向完全图中，包含有 15 条边，在一个具有6个顶点的有向完全图中，包含有 30 条弧。64. 快速排序

13、在平均情况下的时间复杂度为_O(nlog2n)_，在最坏情况下的时间复杂度为_ O(n2)_。65. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_查找成功_，若元素的值小于根结点的值，则继续向_左子树_查找，若元素的大于根结点的值，则继续向_右子树_查找。66. 在循环单链表中，最后一个结点的指针域指向_首_结点。67. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_9_个，树的深度为_3_，树的度为_3_。68. 通常从四个方面评价算法的质量：_正确性_、_可读性_、_健壮性_和_效率与低存储量需求_。69. 假设一棵完全二叉树

14、含1000个结点,则其中度为2的结点数为_499_。70. 一个算法的时间复杂度为(3n3+2n7)(5n)，其数量级表示为 O(n2) 。71. 在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有_快速排序_。72. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。 73. 在归并排序中，进行每趟归并的时间复杂度为_O(n)_，整个排序过程的时间复杂度为_O(nlog2n)_，空间复杂度为_ O(n)_。74. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_9_。 75. 对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 O(n2) ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_ O(n+e) _。76. 从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元