当前位置: 首页 > >

本科数据结构期末考试复*资料

14 级本科数据结构与算法期末考试复*资料
一、单项选择题
1. 假设在一棵二叉树中,双分支结点数为 15,单分支结点数为 30 个,则叶子结点数为 (B )个。 A. 15 B. 16 C. 17 D. 47 2. 在一棵二叉树上第 4 层的结点数最多为( D ) 。 A. 2 B. 4 C. 6 D. 8 3. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中 R[1..n],结点 R[i] 若有左孩子,其左孩子的编号为结点( B ) 。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 4. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为 ( D ) 。 A. 24 B. 48 C. 72 D. 53 5. 设 n , m 为一棵二叉树上的两个结点, 在中序遍历序列中 n 在 m 前的条件是 ( B ) 。 A. n 在 m 右方 B. n 在 m 左方 C. n 是 m 的祖先 D. n 是 m 的子孙 6. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( A ) 。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 7. 根据先序序列 ABDC 和中序序列 DBAC 确定对应的二叉树,该二叉树( A ) 。 A. 是完全二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树 8. 在一个具有 n 个顶点的无向完全图中,所含的边数为( C )。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 9. 在一个具有 n 个顶点的有向完全图中,所含的边数为( B )。 A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 10. 若一个图中包含有 k 个连通分量,若要按照深度优先搜索的方法访问所有顶点,则 必须调用( A )次深度优先搜索遍历的算法。 A. k B. 1 C. k-1 D. k+1 11. 若要把 n 个顶点连接为一个连通图,则至少需要( C )条边。 A. n B. n+1 C. n-1 D. 2n 12. 对于一个有向图,若一个顶点的度为 k1,出度为 k2,则对应邻接表中该顶点单链 表中的边结点数为( B )。 A. k1 B. k2 C. k1-k2 D. k1+k2 13. 对于一个有向图,若一个顶点的度为 k1,出度为 k2,则对应逆邻接表中该顶点单 链表中的边结点数为( C )。 A. k1 B. k2 C. k1-k2 D. k1+k2 14. 由一个具有 n 个顶点的连通图生成的最小生成树中,具有( B )条边。 A. n B. n-1 C. n+1 D. 2?n 15. 已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},则由该图产生的一 种可能的*诵蛄形( A )。
1

A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 16. 对于长度为 18 的顺序存储的有序表,若采用折半查找,则查找第 15 个元素的比较 次数为( B )。 A. 3 B. 4 C. 5 D. 6 17. 对具有 n 个元素的有序表采用折半查找,则算法的时间复杂度为( D )。 2 A. O(n) B. O(n ) C. O(1) D. O(log2n) 18. 从具有 n 个结点的二叉排序树中查找一个元素时, 在*均情况下的时间复杂度大致 为( C )。 2 A. O(n) B. O(1) C. O(log2n) D. O(n ) 19. 从具有 n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为 ( A )。 2 A. O(n) B. O(1) C. O(log2n) D. O(n ) 20. 在一棵*衡二叉排序树中,每个结点的*衡因子的取值范围是( A )。 A. -1?1 B. -2?2 C. 1?2 D. 0?1 21. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表, 采用 h(K)=K%13 计算哈希 地址,则元素 64 的哈希地址为( C )。 A. 4 B. 8 C. 12 D. 13 22. 若根据查找表建立长度为 m 的哈希表,采用线性探测法处理冲突,假定对一个元素 第一次计算的哈希地址为 d,则下一次的哈希地址为( D )。 A. d B. d+1 C. (d+1)/m D. (d+1)%m 23. 若对 n 个元素进行直接插入排序,则进行任一趟排序的过程中,为寻找插入位置而 需要的时间复杂度为( B ) 。 2 A. O(1) B. O(n) C. O(n ) D. O(log2n) 24. 在对 n 个元素进行冒泡排序的过程中,第一趟排序至多需要进行( B )对相邻 元素之间的交换。 A. n B. n-1 C. n+1 D. n/2 25. 在对 n 个元素进行快速排序的过程中,*均情况下的时间复杂度为( D ) 。 2 A. O(1) B. O(log2n) C. O(n ) D. O(nlog2n) 26. 在对 n 个元素进行快速排序的过程中,最坏情况下的时间复杂度为( C ) 。 2 A. O(1) B. O(log2n) C. O(n ) D. O(nlog2n) 27. 假定对元素序列(7, 3, 5, 9, 1, 12, 8, 15)进行快速排序,则进行第一次划分后,得到 的左区间中元素的个数为( B ) 。 A. 2 B. 3 C. 4 D. 5 28. 在对 n 个元素进行堆排序的过程中,时间复杂度为( D ) 。 2 A. O(1) B. O(log2n) C. O(n ) D. O(nlog2n) 29. 若要从 1000 个元素中得到 10 个最小值元素,最好采用( B )方法。 A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序 30. 若要对 1000 个元素排序,要求既快又节省存储空间,则最好采用( C )方法。 A. 直接插入排序 B. 归并排序 C. 堆排序 D. 快速排序

2

二、填空题
1. 对于一个有 n 个结点的二叉树,当它为一棵________二叉树时具有最小高度,即为 _______,当它为一棵单支树具有_______高度,即为_______。 2. 由带权为 3,9,6,2,5 的 5 个叶子结点构成一棵哈夫曼树,则带权路径长度为___。 3. 在一棵二叉排序树*確______遍历得到的结点序列是一个有序序列。 4. 对于一棵具有 n 个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总 数为_______个,其中_______个用于链接孩子结点,_______个空闲着。 5. 在一棵二叉树中,度为 0 的结点个数为 n0,度为 2 的结点个数为 n2,则 n0=______。 6. 一棵深度为 k 的满二叉树的结点总数为_______, 一棵深度为 k 的完全二叉树的结点 总数的最小值为_____,最大值为______。 7. 对于一棵具有 n 个结点的二叉树,若一个结点的编号为 i(1≤i≤n),则它的左孩子 结点的编号为________,右孩子结点的编号为________,双亲结点的编号为________。 8. 对于一棵具有 n 个结点的二叉树,采用二叉链表存储时,链表中指针域的总数为 _________个,其中___________个用于链接孩子结点,_____________个空闲着。 9. 二叉树的链式存储结构有______________和_______________两种。 10. 三叉链表比二叉链表多一个指向______________的指针域。 11. 在一个图中,所有顶点的度数之和等于所有边数的____2____倍。 12. 在一个具有 n 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点 的有向完全图中,包含有________条边。 13. 假定一个有向图的顶点集为{a,b,c,d,e,f}, 边集为{<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>},则出度为 0 的顶点个数为________,入度为 1 的顶点个数为________。 14. 在一个具有 n 个顶点的无向图中,要连通所有顶点则至少需要________条边。 15. 表示图的两种存储结构为__________和__________。 16. 对 于 一 个 具 有 n 个 顶 点 的 图 , 若 采 用 邻 接 矩 阵 表 示 , 则 矩 阵 大 小 至 少 为 ____n____?_____n___。 17. 对于具有 n 个顶点和 e 条边的有向图和无向图,在它们对应的邻接表中,所含边结 点的个数分别为__2e______和__e______。 18. 在有向图的邻接表和逆邻接表表示中,每个顶点邻接表分别链接着该顶点的所有 ________和________结点。 19. 对于一个具有 n 个顶点和 e 条边的无向图,当分别采用邻接矩阵和邻接表表示时, 求任一顶点度数的时间复杂度分别为________和________。 20. 假定一个图具有 n 个顶点和 e 条边,则采用邻接矩阵和邻接表表示时,其相应的空 间复杂度分别为________和________。 21. 图的________优先搜索遍历算法是一种递归算法, 图的________优先搜索遍历算法 需要使用队列。 22. 对于一个具有 n 个顶点和 e 条边的连通图,其生成树中的顶点数和边数分别为 __n______和____n-1____。 23. 若一个连通图中每个边上的权值均不同,则得到的最小生成树是 ________(唯一/ 不唯一)的。 24. 根据图的存储结构进行某种次序的遍历,得到的顶点序列是__(唯一/不唯一)的。 25. 假定一个有向图的边集为{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},对该图进行*伺 序得到的顶点序列为__aebdcf______。

3

26. 以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时,*均查找长度为 ________,时间复杂度为__o(n)______。 27 以折半查找方法在一个查找表上进行查找时,该查找表必须组织成________存储的 ________表。 28. 假定对长度 n=50 的有序表进行折半查找,则对应的判定树高度为________,最后 一层的结点数为________。 29. 在一棵二叉排序树中, 每个分支结点的左子树上所有结点的值一定________该结点 的值,右子树上所有结点的值一定________该结点的值。 30. 对一棵二叉排序树进行中序遍历时,得到的结点序列是一个________。 31. 从一棵二叉排序树中查找一个元素时,若元素的值等于根结点的值,则表明 _______,若元素的值小于根结点的值,则继续向________查找,若元素的值大于根结点的 值,则继续向________查找。 32. 在一棵*衡二叉排序树中,每个结点的左子树高度与右子树高度之差的绝对值不超 过____1____。 33. 在线性表的哈希存储中,装填因子 ? 又称为装填系数,若用 m 表示哈希表的长度, n 表示线性表中的元素的个数,则 ? 等于________。 34. 对线性表(18,25,63,50,42,32,90)进行哈希存储时,若选用 H(K)=K % 9 作为哈希 函数,则哈希地址为 0 的元素有________个,哈希地址为 5 的元素有________个。 35. 每次从无序子表中取出一个元素,把它插入到有序子表中的适当位置,此种排序方 法叫做________排序; 每次从无序子表中挑选出一个最小或最大元素, 把它交换到有序表的 一端,此种排序方法叫做________排序。 36. 每次直接或通过支点元素间接比较两个元素, 若出现逆序排列时就交换它们的位置, 此种排序方法叫做________排序; 每次使两个相邻的有序表合并成一个有序表的排序方法叫 做________排序。 37. 快速排序在*均情况下的时间复杂度为________,在最坏情况下的时间复杂度为 ________。 38. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序, 当把第 8 个记录插入 到前面已排序的有序表时,为寻找插入位置需比较________次。 39. 假定一组记录为 (46,79,56,38,40,84) , 则利用堆排序方法 建立的初始小根堆 为 ____________________。 40. 假定一组记录为(46,79,56,64,38,40,84,43), 在冒泡排序的过程中进行第一趟排序时, 元素 79 将最终下沉到其后第_______个元素的位置。 41. 假定一组记录为(46,79,56,25,76,38,40,80),对其进行快速排序的第一次划分后,右 区间内元素的个数为__________。 42. 假定一组记录为(46,79,56,38,40,80,46,75,28,46), 对其进行归并排序的过程中, 第二 趟归并后的子表个数为________________。 43. 在时间复杂度为 O(nlog2n)的所有排序方法中,________排序方法是稳定的。 2 44. 在时间复杂度为 O(n )的所有排序方法中,________排序方法是不稳定的。 45. 在所有排序方法中,________排序方法采用的是二分法的思想。 46. 在所有排序方法中,________方法使数据的组织采用的是完全二叉树的结构。

4

三、应用题
4---1. 已知用一维数组存放的一棵完全二叉树:ABCDEFGHIJKL,写出该二叉树的先 序、中序和后序遍历序列。 6---2. 找出所有满足下列条件的二叉树: (1)它们在先序遍历和中序遍历时,得到的遍历序列相同; (2)它们在后序遍历和中序遍历时,得到的遍历序列相同; (3)它们在先序遍历和后序遍历时,得到的遍历序列相同; 7---3. 假设一棵二叉树的先序序列为 EBADCFHGIKJ,中序序列为 ABCDEFGHIJK,请 画出该二叉树,并写出该二叉树的后序遍历序列。ACDBGJKIHFE 10---4.给定一组权值(5,9,11,2,7,16) ,试设计相应的哈夫曼树。 13---5. 已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8,11, 试填写出其对应哈夫曼树 HT 的存储结构的初态和终态。 3---6. 已知一个无向图的邻接矩阵如图 6-12(a)所示, 试写出从顶点 0 出发分别进行深 度优先和广度优先搜索遍历得到的顶点序列。 4---7. 已知一个无向图的邻接表如图 6-12(b)所示, 试写出从顶点 0 出发分别进行深度 优先和广度优先搜索遍历得到的顶点序列。

(a) 图 6-12

(b)

5---8. 已知图 6-13 所示的一个网,按照 Prim 方法,从顶点 1 出发,求该网的最小生成 树的产生过程。 6---9. 已知图 6-13 所示的一个网, 按照 Kruskal 方法, 求该网的最小生成树的产生过程。 V1 65 50 V5 60 52 V4 V3 42 30 70 V6

50 V2 40

45 V7

图 6-13

1---16. 已知一组记录为 (46,74,53,14,26,38,86,65,27,34),给出采用直接插入排序法进行

5

排序时每一趟的排序结果。 3---17. 已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序 时每一趟的排序结果。 4---18. 已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用简单选择排序法进行 排序时每一趟的排序结果。

四、算法设计题
1. 在单链表上实现线性表的求表长 ListLength(L)运算。 2. 已知线性表的元素按递增顺序排列,并以带头结点的单链表作存储结构。试编写一 个删除表中所有值大于 min 且小于 max 的元素(若表中存在这样的元素)的算法。

6




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版