文档介绍：
参考答案1
数据构造模拟试卷(一)
一．单项选择题〔本大题共15小题，每题2分，共30分〕
1．假如只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。 A、 B C D
二．填空题〔本大题共15小题，每题2分，共30分〕
1. 在数据构造中，数据的逻辑构造分线性构造和 非线性构造 。 2. 称算法的时间困难度为O(f(n))，其含义是指算法的执行时间和___ f(n)____的数量级一样。 3. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间困难度为_____ O(n)____。 4. 假设为循环队列安排的向量空间为Q[20]，假设队列的长度和队头指针值分别为13和17，那么
当前尾指针的值为__10____。
5. 对于栈只能在___栈顶_____插入和删除元素。
6. 通常从正确性、____可运用性___、可读性、效率和强健性等5个方面评价算法〔包括程序〕
的质量。
7. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。
8. 假设对关键字序列〔43，02，80，48，26，57，15，73，21，24，66〕进展一趟增量为3的希
尔排序，那么得到的结果为 (15,02,21,24,26,57,43,66,80,48,73) 。 9. 在索引存储中，假设一个索引项对应数据对象表中的一个表项〔记录〕，那么称此索引为 稠密
索引，假设对应数据对象表中的假设干个表项，那么称此索引为 稀疏 索引。
10. 二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 89 。 11. 广义表A((a，b，c)，(d，e，f))的表尾为 〔(d，e，f)〕 。
12. 设有一个依次栈S，元素sl，s2，s3，s4，s5，s6依次进栈，假如6个元素的出栈依次为
s2，s3，s4，s6，s5，sl，那么依次栈的容量至少应为 3 。
13. 依据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二叉搜寻树)
时，当插人到值为 50 的结点时须要进展旋转调整。 14. n〔n＞0〕个顶点的无向图最多有 n(n-1)／2 条边。
15. 设无向图的邻接表如下列图所示，那么该图的边的数目是 5 。
三．判定题(本大题共10小题，每题1分，共10分)
1. 〔×〕链式存储在插人和删除时须要保持物理存储空间的依次安排，不须要保持数据元素之间的
逻辑依次。
2. 〔√〕在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
3. 4. 5. 6.
〔×〕通常递归的算法简洁、易懂、简单编写，而且执行的效率也高。 〔√〕一个广义表的表尾总是一个广义表。 〔×〕对于一棵具有n个结点，其高度为h的二叉树，进展任一种次序遍历的时间困难度为O〔h〕。 〔√〕当从一个最小堆中删除一个元素时，须要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到适宜位置为止。 7. 〔×〕存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 8. 〔√〕进展折半搜寻的表必需是依次存储的有序表。 9. 〔×〕干脆选择排序是一种稳定的排序方法。
10. 〔×〕在用单链表表示的链式队列中，队头在链表的链尾位置。
四．问答题 (本大题共5小题，每题6分，共30分)
1．由如下图的二叉树，答复以下问题。
d g b a e c h i f 。 a b d g c e f h i 。