2019暨南大学计算机考研930真题：数据结构及算法详解

本文档是关于暨南大学2019年的计算机科学与技术、软件工程、网络空间安全以及工程硕士专业的考研真题，涵盖了数据结构（830）这一考试科目。这份试题集主要包含了930号试卷，涉及了多项选择题部分，旨在测试考生对计算机基础知识的理解和应用能力。 1. 题目考查了二叉树的相关概念：题目询问在任意一棵二叉树的先序序列和后序序列中，叶子节点的相对次序关系。正确答案是D，因为二叉树的先序遍历（根-左-右）和后序遍历（左-右-根）中，叶子节点的相对顺序保持不变，这是因为它们总是最后访问的。 2. 深度为4的二叉树的最大节点数可以通过满二叉树的性质来计算，每个层次除了最后一个，都是满的，最后一个层次可能不满，但最多有2个空位，所以最多节点数为2^(4+1)-1 = 16 - 1 = 15。 3. 在有向图中，入度是出度的相反数，如果所有顶点的入度之和为m，那么所有顶点的度数之和（包括出度和入度）为2m。 4. 快速排序的效率依赖于数据的初始状态，当输入数据基本有序时，由于划分不均衡，会导致效率下降，因此最不利的情况是D，即数据已基本有序。 5. 堆排序是通过构建最大堆或最小堆来实现的，对于给定的记录关键字序列，堆排序建立的初始堆应该是最大的，因此答案是B，对应的是最大堆。 6. 对于有序表查找特定值，折半查找的步骤是每次将搜索范围减半，直到找到目标或搜索范围为空。查找A[3]意味着目标值应该位于数组的中间位置，因此在18个元素的有序表中，第一次比较应在第9位，然后逐步缩小范围。最终比较序列的下标为9, 5, 3。 7. 完全有向图中，每个顶点都有n-1条出边，因此总边数为n*(n-1)，去掉重复的边（每条边都出现两次），结果是n*(n-1)/2。 8. 逐点插入法建立二叉排序树时，查找操作的时间复杂度通常是O(log n)。对于给出的序列，查找元素35的过程会经过50、72、43等元素的比较，直到找到35，所以需要进行5次比较。 9. 题目未完成，但提到了判定有向图是否存在回路的问题，这通常涉及到拓扑排序或者广度优先搜索(BFS)或深度优先搜索(DFS)的算法，回路的存在会使得图无法进行拓扑排序。 总结起来，这份试题涵盖了数据结构的基础概念，如二叉树、图论、排序算法以及查找方法等，对于准备参加暨南大学计算机科学与技术相关专业考研的学生来说，是复习的重要参考资料。