山东大学数据结构课程第七次试卷与答案详解

本资源是一份山东大学数据结构课程第七次考试的试卷及其参考答案，涉及的数据结构基础知识涵盖无向图、排序算法、二叉树、链表、栈与队列、时间复杂度以及查找算法等多个方面。以下是部分内容的详细解析： 1. 无向图邻接表：邻接表是表示无向图的一种数据结构，每个顶点对应一个链表，链表中的表头结点代表该顶点的相邻顶点。因此，对于无向图，无论图有多少顶点，邻接表都有n个表头结点，对应n个顶点。 2. 最小生成树：无向图的最小生成树是指连接所有顶点且边权之和最小的树。在连通图中，最小生成树有n-1条边，因为任何树中至少有一条边，而多加一条边将增加总权重。 3. 快速排序：快速排序是一种高效的排序算法，通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小。在这里，以45为基准进行划分，由于初始序列未给出，无法确定具体结果，但选项(A)最符合一般快速排序过程。 4. 二叉排序树的遍历：二叉排序树的中序遍历会按照升序输出节点，所以从中序遍历可以得到一个从小到大的有序序列。 5. 完全二叉树的编号规则：在完全二叉树中，结点i的左孩子编号为2i，而左孩子的左孩子编号为2i+1。 6. 循环链表和时间复杂度：do-while循环的时间复杂度为O(n)，因为它至少执行一次循环，直到i大于n时退出。 7. 单向循环链表的判空：在单向循环链表中，由于有头结点且最后一个节点的next指针指向头节点形成循环，所以判空条件是head->next==head。 8. 二叉树的叶子节点数量：一棵高度为10的满二叉树（每个层级都是满的）有最大2^10-1个节点，其中叶子节点是所有层的最后一个节点，共2^(10-1)=512个。 9. 二分查找法：对于已排序序列，二分查找法每次比较将搜索范围减半，查找关键字90位于有序序列中，需要比较的关键字个数为log2(11) = 4次，因此是4次。 10. 删除栈顶元素：在链式栈中，删除栈顶元素即弹出操作，需要更新栈顶指针，通常做法是top=top->next，使得top指向下一个结点。 关于判断题部分： 1. 对于顺序存储结构，如队列和栈，如果数据结构满时进行插入或删除操作，确实可能遇到“溢出”情况，因此说法正确。 2. 向二叉排序树插入结点不一定会使其立即成为叶子结点，只有当插入结点的位置刚好没有其他子节点时，才会这样，否则新结点会成为非叶子结点，故说法错误。 以上是山东大学数据结构课程试卷第七次考试的主要知识点概要，涵盖了基本概念和算法操作，有助于学习者理解和巩固数据结构理论。