数据结构习题

1、单项选择题 1. 下面程序段的时间复杂度为 ( C ) 。 for(int i=0; im; i+) for(int j=0; jnext=headDhead!=NULL 8. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 ( C )最节省时间。 A)单链表B)循环链单表 C)带尾指针的循环链单表D)带头结点的 双循环链表 栈的插入与删除操作在（ A ）进行。 A. 栈顶B.栈底 C任意位置D.指定位置 设一个栈的输入序列为 A、B、C D,则借助一个栈所能得到的输出序 列不可能是（ D ）。 AABCDB DCBAC ACDBD DABC 在一个链队中，假设 F 和 R 分别是

2、队首和队尾指针，则删除一个结点 的运算是 （ C ） 。 A R=F-next;B R=R-next; C F=F-next; D F=R-next; 串是一种特殊的线性表，其特殊性体现在 （ B ）。 A .可以顺序存储 C.可以链接存储 以下说法正确的是（ C ）。 A）空串与空格串是相同的 C）空串是零个字符组成的串 B. 数据元素是一个字符 D.数据元素可以是多个字符 B） fox”是FoxBasd的子串 D）空串长度等于1 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 若 n 为主串长， m 为子串长 mn） ，则用简单模式匹配算法最坏

3、情况 下，需要比较字符总数是（ C ）。 Am B m(n-m+1)C n*m D (n-m)*(m-1) 将一个 A1.100,1.100的三对角矩阵， 按行优先存入一维数组B1.298 中，A中元素 A66, 65在B数组中的位置 k为（B ）。 A） 198B） 195C） 197 一个稀疏矩阵的转置矩阵应是（ B ）。 A. 下三角矩阵B.稀疏矩阵C.非稀疏矩阵 D.有时为稀疏矩阵 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 广义表(e)的表头是(C )。 A )e B) ( ) C) (e) D) (e) 深

4、度为 5 的二叉树至多有 ( C )个结点。 A16B 32 具有 10 个叶子结点的二叉树中有( A 8B9 在二叉树的中序遍历递归算法中， 时作访问操作。 A1B2C 3 C 31D 10 B)个度为2的结点。 C 10D 11 顺着搜索路径， 在第( B )次经过结点 D4 在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是 A 左子树的最右下结点 B 右子树的最右下结点 C 左子树的最左下结点 D 右子树的最左下结点 按照二叉树的定义，具有 3 个结点的二叉树有 ( C )种形态。 A3 B4 C5 D6 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(B)的 二叉树。

5、 A .空或只有一个结点 C. 任一结点无左孩子 图的广度优先搜索类似于树的 A.先根B.中根 B. 高度等于其结点数 D. 任一结点无右孩子 ( D )次序遍历。 C. 后根D.层次 An-l 条有向边 B n 条有向边 C. n(n-1)/2条有向边D. n(n-1)条有向边 36. 任何一个无向连通图的最小生成树(B)。 37. A.只有一棵B.有一棵或多棵C. 一定有多棵D.可能不存在 38. 设 G1=(V1,E1)和G2=(V2,E2)为两个图，如果 V2包含 V1, E2包含 E1, 则称 ( A )。 39. A. G1 是 G2 的子图B. G1 是 G2 的连通分量 40.

6、 C. G2 是 G1 的连通分量D. G2 是 G1 的子图 41. 下面关于图的存储的叙述中，哪一个是正确的。 ( A ) 42. A 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，与 边数无关 43. B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，与结点 个数无关 44. C.用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边 数无关 45. D.用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个 数无关 46. ( D )适合用邻接表表示。 47. A.稠密图B.有向完全图 48. C.无向完全图D.稀疏图 49. 一般，图的DFS生成树的高度(

7、C )BFS生成树的高度。 50. A.小于B.等于C.大于D.小于或等于 51. 从一棵二叉排序树中查找一个元素时，其平均时间复杂度为(C )。 A. 0(1)B. 0(n)C. O(1og2n)D. 0(n2) 52. 二分查找法要求查找表中各元素的键值必须是(A )排列。 53. A.递增或递减 B.递增C.递减D.无序 54. 向具有n个结点的、结构均衡的二叉排序树中插入一个元素的时间复 杂度为(B )。 A. 0(1)B. O(log2n)C. 0(n)D. 0(nlog2n) 55. 线性表必须是(D ),才能进行二分查找。 56. A.用向量存储的线性表B.用链表存储的有序表 5

8、7. C.用链表存储的线性表D.用向量存储的有序表 58. 按照不同的顺序输入 4, 5, 6三个关键字，能建立(B )棵不同的二 叉排序树。 A) 6B) 5C) 4D) 3 59. 在一棵m阶B揺中，若在某结点中插入一个新关键字而引起该结点的 分裂，则该结点中原有( D )个关键字。 A)m/2B)m/2- 1C) mD)m-1E)m/2F)m/2 -1 60. 设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大 的元素，最好选用(C )法。 61. A.冒泡排序 B快速排序 62. C.堆排序 D.基数排序 63. 下列序列中(B )是执行第 趟快速排序后得到的序列 (排序

9、的关键字类 型是字符串） 64. A. da,ax,eb,de,bbffba,gc B. cd,eb,ax,da,bbffha,gc 65. C. gc,ax,cb,cd,bbffda,ba D. ax,bb,cd,daffeb,gc,ba 66. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时 间复杂度是（B ）。 67. A. 0(1)B.0(n)C. O(n2) D.O(log2n) 68. 以下排序方法中，稳定的排序方法是 (B )。 69. A .直接插入排序和希尔排序 B. 直接插入排序和冒泡排序 70. C.希尔排序和快速排序 D. 冒泡排序和快速排序 71. 在快

10、速排序中，每次划分选择的基准元素为该区间的（D ）时，得到的两 个子区间是均匀的。 72. A .最大值B.最小值 C.任意值D.中间值 73. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按关键字 有序，则该二叉树是下列树中的哪种（ C） A.二叉排序树 B.哈夫曼树C.堆。 二、填空题 1. 在一个长度为n的顺序表中删除第i个元素，要移动_n-i_个元素。 2. 在顺序表中插入或删除一个元素，需要平均移动表长的一半元 素，具体移动元素的个数与元素所在的位置有关。 3. 若线性表采用顺序存储结构存放，那么在长度为n的线性表中删除第i （1 next = h 。 5. 一个队列的入队序

11、列是a、b、c、d，则队列的输出序列为abed。 6. 栈结构通常采用的两种存储结构是顺序栈 和链栈。 7. 设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈 S,个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、 c、f、e、a，则栈S的容量至少应该是3。 8. 设有一个nxn勺对称矩阵A,将其上三角部分按行存放在一个一维数 组B中，A00存放于B0中，那么第i行的对角元素 Aii存放于B 中(2n-i+1)*i / 2 处。 9. 设有5对角矩阵A = (aj)2o*2o，按特殊矩阵压缩存储的方式将其5条对 角线上的元素存于数组B0 : m中，计算元素A10,1

12、0的存储位置 44。 10. 已知广义表L= (a,( ),b),(e),利用取表头和取表尾的操作分离出原子 e 的运算是GetHead(GetHead(GetHead(GetTail(GetTail(L)。 11. 设广义表 B=( ) ,(a, (b, c), (e,f),(),表头为 (),表尾为 (a, (b, c), (e,f), ( )_。 12. 在空串和空格串中，长度不为0的是_空格串_。 13. 有n个结点的二叉链表中，其中空的指针域为n+1.指向孩子的指针个 数为 _n-1_。 14. 中缀算术表达式5+6/(23-(6+15)*8所对应的后缀算术表达式为 5,6,23,6

13、,15,+,-,/,8, *,+。 15假定一棵二叉树的结点个数为50 ,则它的最小深度为 _6,最大深 度为 _50_ o 16. 一棵树的后根序列与其转换的二叉树的中 序列相同，先根序列 与其转换的二叉树的先序列相同。 17. 具有400个结点的完全二叉树的深度为 9o 18. 一棵二叉树有 67个结点，这些结点的度要么是0,要么是2。这棵二 叉树中度为2的结点有_33_个。 19. 已知森林的先序访问序列为ABCDEFGHIJKL中序访问序列为 CBEFDGAJIKLH则该森林有_2_棵树。 20. 当对字符集进行编码时，字符集中任一字符的编码都不是其他字符的 编码的前缀，这种编码称二进

14、制前缀编码o 21. 高度为h的二叉树只有度为 0和2的结点，则此类二叉树的结点数至 少为2h-1+1个结点，至多为2h-1 个结点。 22. 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。 23. 一个有30个结点的完全二叉树有15 个叶子结点；有个度 为2的结点。 24. 高度为i(i 1)的完全二叉树按自上而下，从左到右的次序给结点编号 (从1开始)，则可能的编号最小的叶子结点的编号为2k-2+1o 25. 设图 G= (V, E), V= 1 , 2, 3, 4, E= , , , ，从顶点1出发，对图G进行广度优先搜索的序列有 _2_种。 26. 有向图G用

15、邻接矩阵A仁n,1.n存储，矩阵中元素值1代表有弧，0代 表无弧，其第i行的所有元素之和等于顶点i的_出度度。 27. 一个连通图的生成树是该图的极小连通子图。若这个连通图有n 个顶点，则它的生成树有 _n-1_ 条边。 28. n个顶点的无向连通图的邻接矩阵中至少有2(n-1)个非零元素，至 多有_n(n-1)_个非零元素。 29. PRIM算法与图的边数无关，适合求解稠密图的最小生成树。 30. 一棵3阶B-树中每个结点最多有3 棵子树，每个结点最多有2 个关键字。含有9个叶子结点的3阶B拥至少有4个非叶结点， 至多有 7个非叶结点。 31. 从有序表(12，18，30，43，56, 78

16、，82，95)中依次二分查找 43和56 元素时，其查找长度分别为_1和_3_。 32. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值， 则应把它插入到根结点的左 子树上。 33. 分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态递 增序列按递增顺序排序，最省时间的是算法插入排序，最费时间 的是算法快速排序。 三、简答及图示说明题 1. 广义表的基本概念，如A = (a,b),c,(d,e,f)，用GetGead和GetTail操作 取元素d 2. 根据给定二叉树的先序和中序序列，构造二叉树 3. 根据给定树的先序和后序序列，构造树 4. 已知二叉树，画出中序的线索。

17、5. 森林和二叉树的相互转换 6. 有7个带权结点，其权值分别为3，乙8，2，6，10，14,试以它们 为叶子结点生成一棵哈夫曼树，画出相应的哈夫曼树(左子树根结点的 权小于等于右子树根结点的权)，并写出哈夫曼编码，计算带权路径长 度。 7. 给出图的顶点集合和边的集合，能画出图的邻接矩阵、邻接表，或者 给出图的存储结构，能够画出对应的图 8. 用普里姆(prim )算法或克鲁斯卡尔(Kruskal)算法构造最小生成树。 9. 从某个顶点出发，画出图的深度优先生成树和广度优先生成树。 10. 设图 G=( V, E), V=1, 2，3，4，5，6, E=, , , , , , 。请写出图 G

18、中顶点的所有拓 扑序列。 11. 已知一个图的顶点集 V和边集G分别为： V=0, 1, 2, 3, 4, 5, 6, 7； G=(0,1)3,(0,3)5,(0,5)18,(1,3)7,(1,4)6,(2,4)10,(2,7)20,(3,5)15,(3,6)12,(4,6)8 ,(4,7)12; 按照普里姆算法从顶点 2 出发得到最小生成树，试写出在最小生成树 中依次得到的各条边。 12. 设al、a2、a3是不同的关键字，且 a1a2a3,可组成六种不同的输入 序列。问其中哪几种输入序列所构造的二叉排序树的高度为 3 13. 构造二叉排序树，在查找每个结点概率相等情况下的平均查找长度， 二叉排序树的插入和删除算法 14. 画出用线性探测再散列（线性探查法）处理冲突时生成的哈希表及计 算平