《数据结构模拟试卷(一)参考答案》由会员分享，可在线阅读，更多相关《数据结构模拟试卷(一)参考答案（5页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 5 页数 据 结 构 模 拟 试 卷 (一 )参 考 答 案一单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）1如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用( A )方法最快。A、起泡排序 B、快速排序C、堆排序 D、直接选择排序 2算法分析的目的是（B ）A辨别数据结构的合理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A插入 B删除C定位 D排序4若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A3，2，6，
2、1，4，5 B5，6，4，2，3，1C1，2，5，3，4，6 D3，4，2，1，6，55设串 sl=DataStructureswithJava,s2=it，则子串定位函数 index(s1,s2)的值为（A）A15 B16C17 D 186一个顺序存储的线性表的第一个元素的存储地址是 100，每个元素的长度为 4，则第 4 个元素的存储地址是（B） 。A. 108 B. 112 C. 116 D. 1207从一个具有 n 个结点的单链表中查找其值等于 x 的结点，在查找成功的情况下，平均需要比较（C）个结点。A. n B. n/2 C. (n+1)/2 D. (n-1)/28在任意一棵二叉树
3、的前序序列和后序序列中，各叶子之间的相对次序关系（D）A不一定相同 B互为逆序C都不相同 D都相同9高度为 5 的二叉树至多有结点数为（A ）A. 63 B. 32 C. 24 D.6410若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（B）A图中每个顶点的出度 B图中每个顶点的入度C图中弧的条数 D图中连通分量的数目11图的邻接矩阵表示法适用于表示（C）A无向图 B有向图C稠密图 D稀疏图12在一个单链表中，若 p 所指的结点不是最后一个结点，在 p 之后插入 s 所指的结点，则执行（D） 。A. s-next=p; p-next=s B. p-next=s; s-next=p第
4、2 页 共 5 页C. p=s; s-next=p-next D. s-next=p-next; p-next=s13下列排序算法中，其时间复杂度和记录的初始排列无关的是（A）A直接选择排序 B插入排序C快速排序 D冒泡排序14若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t） ，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为（B）Af,d,b Bf,c,bCg,c,b Dg,d,b15如下图所示的 4 棵二叉树中， （C）不是完全二叉树。二填空题（本大题共 15 小题，每小题 2 分，共 30 分）1. 在数据结构中，数据的逻辑结构分线性结构和 非线性结构 。2.
5、 称算法的时间复杂度为 O(f(n)，其含义是指算法的执行时间和_ f(n)_的数量级相同。3. 在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为_ O(n)_。4. 假设为循环队列分配的向量空间为 Q20，若队列的长度和队头指针值分别为 13 和 17，则当前尾指针的值为_10_。5. 对于栈只能在_栈顶_插入和删除元素。6. 通常从正确性、_可使用性_、可读性、效率和健壮性等 5 个方面评价算法（包括程序）的质量。7. 在具有 n 个单元的循环队列中，队满时共有n-1个元素。8. 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）
6、进行一趟增量为 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，则顺序栈的
7、容量至少应为 3 。13. 根据一组记录(56，42，50，64，48)依次插入结点生成一棵 AVL 树(高度平衡的二叉搜索树)时，当插人到值为 50 的结点时需要进行旋转调整。14. n（n0）个顶点的无向图最多有 n(n-1)2 条边。15. 设无向图的邻接表如下图所示，则该图的边的数目是 5 。A B C D第 3 页 共 5 页三判断题(本大题共 10 小题，每小题 1 分，共 10 分)1. （）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 2. （）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。3. （）通常递归
8、的算法简单、易懂、容易编写，而且执行的效率也高。 4. （）一个广义表的表尾总是一个广义表。 5. （）对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为O（h） 。 6. （）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。7. （）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 8. （）进行折半搜索的表必须是顺序存储的有序表。 9. （）直接选择排序是一种稳定的排序方法。10. （）在用单链表表示的链式队列中，队头在链表的链尾位置。四问答题 (本大题共 5
9、 小题，每小题 6 分，共 30 分)1由如图所示的二叉树，回答以下问题。a.其中序遍历序列为d g b a e c h i f 。b.其先序遍历序列为a b d g c e f h i 。c.其后序遍历序列为g d b e i h f c a 。adcbe fg hi第 4 页 共 5 页2已知图 G=(V,E)，其中 Va,b,c,d,e,f,g，E, , ，请画出图 G，并写出其邻接矩阵和邻接表表示。邻接矩阵：邻接表：3写出利用直接选择排序对关键字序列 (40,24,80,39,43,18,20) 进行从小到大排序的每一趟结果。参考答案：18,24,80,39,43,40,2018,20
10、,80,39,43,40,2418,20,24,39,43,40, 8018,20,24,39,43,40, 8018,20,24,39,40,43, 8018,20,24,39,40,43, 80abcgfe d0 1 0 0 0 0 10 0 0 0 0 0 10 1 0 0 0 0 00 0 1 0 0 1 00 0 0 1 0 0 01 0 0 0 1 0 00 0 1 1 0 1 01abcdefga b c d e f g0123456abcdefg1 6 6 1 2 5 3 0 4 2 3 5 第 5 页 共 5 页4设 A、B、C 是不同的关键字且 ABC，可组成 6 种不同的
11、输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为 2?参考答案：4 种。A BCA C BC A BC B A评分标准：次序不限，写对一种得 1 分，4 种全写对得 6 分。若在 4 种正确答案之外，又多写一种则只能得 4 分，若 6 种排列顺序全写上则 0 分。5在如图所示的 AOE 网中，试回答如下问题：（ 1）计算出每个顶点所表示的事件的最早发生时间和最迟发生时间；（2）计算出每条边所表示的活动的最早开始时间和最迟开始时间；（3）找出此网络中的关键活动和关键路径。事件的最早发生时间和最迟发生时间：活动的最早开始时间和最迟开始时间：网络中的关键活动：ab,be,eh,hk关键路径: abehk64521187244abcehgkd f
