《数据结构与算法(五)》由会员分享，可在线阅读，更多相关《数据结构与算法(五)（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法 （ 五）（ 总分： 62.00 ，做题时间： 90 分钟 ）一、选择题 （总题数： 43，分数： 44.00）1. 下述是顺序存储方式的优点。A） 存储密度大 B） 插入运算方便C） 删除运算方便 D） 可方便地用于各种逻辑结构的存储表示（分数： 1.00 ）A. VB.C.D.解析：以下各题基于下面的叙述：某二叉树节点的中序序列为A, B, C,D,E, F, G,后序序列为B,D,C,A, F,G,E。（分数： 2.00 ）（1）. 该二叉树节点的前序序列为 A. E, G, F, A, C, D, B B. E, A,C, B,D,G,FC. E, A, G, C, FB
2、, D D. E,G,A,C,D,F,B (分数：1.00 )A.B.VC.D.解析(2).该二叉树对应的森林包括 _棵树。A. 1 B. 2C. 3 D. 4 （分数： 1.00）A.B. VC.D.解析：2. 对于一个线性表,若既要求能够进行较快的插入和删除,又要求存储结构能够反映数据元素之间的逻辑 关系,则应该 。A） 以顺序方式存储 B） 以链接方式存储C） 以散列方式存储 D） 可以以上面任意一种方式存储（分数： 1.00 ）A.B. VC.D.3. 在表长为 n 的顺序表中，实行顺序查找，在查找不成功时，与关键字比较的次数为A) n B) 1C) n+1 D) n-1(分数： 1.
3、00 )A. VB.C.D.解析：4.3 个节点可以构造出 种不同的二叉树A) 2 B) 3C) 4 D) 5(分数： 1.00 )A.B.C.D. V解析：5. 设待排序的记录为 (20 ，16，13，14，19) ，并经过下列过程将这些记录排序，则所用的排序方法是 20 16 13 14 1916 20 13 14 1913 16 20 14 1913 14 16 20 1913 14 16 19 20A) 冒泡排序 B) 希尔排序C) 堆排序 D) 直接插入排序(分数： 1.00 )A.B.C.D. V解析：6. 一个栈的入栈序列是 a, b, c, d, e,则栈不可能的出栈序列是 。
4、A) e d c b a B) d e c b aC) d c e a b D) a b c d e(分数： 1.00 )A.B.C. VD.7. 对 5个不同的数据进行排序，最少需要比较 次A) 3 B) 4C) 5 D) 6(分数： 1.00 )A.B. VC.D.解析：8. 一维数组与线性表的区别是 。A) 后者长度固定，前者长度可变 B) 两者长度均可变 C) 前者长度固定，后者长度可变 D) 两者长度均固定(分数： 1.00 )A.B.C. VD.解析：9. 在一个顺序存储的循环队列中，队首指针指向队首元素的 A) 前一个位置 B) 后一个位置C) 队首元素位置 D) 任意位置(分数
5、： 1.00 )A. VB.C.D.解析：10. 一个序列中有若干个元素，若只想得到其中 I 个元素之前的部分排序，最好采用 排序。A) 堆排序 B) 插入排序C) 希尔排序 D) 快速排序(分数： 1.00 )A. VB.C.D.解析：11. 在下列存储形式中， 不是树的存储形式。A) 双亲表示法 B) 孩子链表表示法C) 孩子兄弟表示法 D) 顺序存储表示法(分数： 1.00 )A.B.C. VD.解析：(假12. 采用二分查找的方法查找长度为 n 的有序表时，查找每个元素时平均比较次数与对应判定树的高度 定高度不小于 2) 的关系为 。A) 前者小于后者 B) 前者大于后者C) 前者等于
6、后者 D) 前者大于等于后者(分数： 1.00 )A. VB.C.D.解析：13. 如果T2是由有序树T转换而来的二叉树，那么T中节点的前序就是 T2中节点的 。A) 后序 B) 层次序C) 前序 D) 中序 (分数： 1.00 )A.B.C. VD.解析：14. 由分别带权为 9， 2， 5， 7 的 4 个叶节点构造一棵哈夫曼树，该树的带权路径长度为 A) 23 B) 37C) 44 D) 46(分数： 1.00 )A.B.C. VD.解析：15. 在一个单链表中，若要在 Pf节点之后插入节点qT,应执行的操作是 A) P Tnext ：=qB) P Tnext ：=q；qT next ：
7、=PT next T nextC) q Tnext ：=PT next ； PT next ： =qD) PTnext ：=q；qTnext=PT next分数： 1.00 )A.B.C. VD.解析：16. 假定一棵二叉树的节点数为97，则它的最小高度为 A) 4 B) 5C) 6 D) 7(分数： 1.00 )A.B.C. VD.解析：17. 向顺序栈中压入元素时，是 。A) 先移动栈顶指针，后存入元素B) 先存入元素，后移动栈顶指针C) 谁先谁后无关紧要 D) 同时进行(分数： 1.00 )A. VB.C.D.解析：18. 用直接插入排序方法对下面 4 个序列进行由小到大的排序，元素比较
8、次数最少的是 A) 94 ，32，40，90，80，46，21，69 B) 32 ， 40， 21， 46， 69， 94， 90， 80C) 21 ，32，46，40，80，69，90，94 D) 90 ， 69， 80， 46， 21， 32， 94， 40(分数： 1.00 )A.B.C. VD.解析：19. 二分查找法适用于存储结构为 的、按关键字排好序的线性表。A) 顺序存储或链式存储 B) 顺序存储C) 索引存储 D) 链式存储(分数： 1.00 )A.B. VC.D.解析：20. 对树中的一个节点x,在先根序列中的序号为 pre(x)，在后根序列中的序号为post(z)，若树中节
9、点x是节点y的祖先，则下列4个序列中，是正确的。A) pre(x) pre(y) 和 post(x) post(y) B) pre(x) pre(y)和 post(x) post(y)C) pre(x) post(y) D) pre(x) pre(y)和 post(x) post(y)(分数：1.00 )A.B.D.解析：21. 设栈S和队列Q的初始状态为空，元素 e1, e2，e3，e4, e5, e6依次通过栈，一个元素出栈后立即进入队列Q。若6个元素出队的顺序是 e2，e4，e3，e6，e5，el，则栈S的容量至少应该是 。A) 4 B) 6C) 3 D) 2（分数：1.00 ）A.B.
10、C. VD.解析：22. 树最适合用来表示。A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的数据(分数：1.00 )A.B.C. VD.解析：23. 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 数据结构A）栈B）树C）双向队列D）广义表(分数：1.00 )A. VB.C.D.解析:H的左线索指向24. 将下图所示的二叉树存储为对称序线索二叉树，则节点A）节点A B）节点CC) 节点 E D) 节点 C(分数： 1.00 )A.B. VC.D.解析：25. 已知 12 个数据元素为 (34 ，76，45，18，26，54，92，60，25，3
11、7，03，78) ，对该数列按从小到大的顺序排序。若采用希尔排序方法排序，设第一趟排序的增量为6，第二趟排序的增量为3，则第二趟排序后的序列为 。A) 34 ， 60，25，18，03，54，92，76，45，37，26，78B) 18 ，25，03，26，34，37，54，60，45，76，78，92C) 18 ， 03，25，34，26，45，37，60，54，92，76，78D) 以上都不正确(分数： 1.00 )A.B.C. VD.解析：26. 若待排序序列已基本有序， 要使它完全有序， 则从关键码比较次数和移动次数考虑， 应当使用的排序方 法是 。A) 快速排序 B) 直接选择排序C
12、) 归并排序 D) 直接插入排序(分数： 1.00 )A.B. VC.D.解析：27. 静态查找表与动态查找表的根本区别在于 。A) 它们的逻辑结构不一样 B) 施加于其上的操作不同C) 所包含的数据元素的类型不一样 D) 存储实现不一样(分数： 1.00 )A.B. VC.D.解析：28. 用顺序查找法对具有 n 个节点的线性表查找，查找一个节点所需要的平均查找时间为 。A) O(n 2) B) O(nlog 2n)C) O(n) D) O(log 2n)(分数： 1.00 )A.B.C. VD.解析：29. 一组序列的关键字为 (25，48，16，35，79，82，23，40，36，72)
13、，其中含有 5 个长度为 2的有序表， 按归并排序方法对该序列进行一趟归并后的结果为 。A) (16 ， 25， 35， 48， 23， 40， 79， 82， 36， 72) B) (16 ， 25， 35， 48， 79， 82， 23， 36，40， 72)C) (16 ， 25， 48， 35， 79， 82， 23， 36， 40， 72) D) (16 ， 25， 35， 48， 79， 23， 36， 40，72， 82)(分数： 1.00 )A. VB.C.D.解析：30. 用链表表示线性表的优点是 。A) 便于随机存取 B) 花费的存储空间较顺序存储少C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同(分数： 1.00 )A.B.C. VD.解析：31. 已知一棵二叉树节点的先根序列为ABDGCF,中根序列为DGBAFC,则节点的后根序列为。A) ACFKBDG B) GDBFKCAC) KCFAGDB D) ABCDFKG(分数： 1.00 )A.B. VC.D.解析：32. 对 n 个记录的文件进行快速排序，所需的辅助存储空间为 。A) O(1) B) O(nlog
