数据结构期末复习：核心概念与试题解析

"这是一份关于数据结构的期末复习题，包含了是非题和选择题，主要涵盖线性表、栈、队列、字符串、图、树、二叉树、排序算法、查找方法以及数据结构的基本特性等内容。" 一、是非题解析： 1. 线性表的链式存储结构并不总是优于顺序存储结构，两者各有优势。顺序存储结构在连续内存空间中存储，访问效率高，但插入和删除操作涉及大量元素移动；链式存储结构插入和删除灵活，但访问速度相对较慢。 2. 栈和队列是线性表的特例，栈只允许在一端进行操作（后进先出），队列允许在两端操作（先进先出），所以不能任意位置操作元素。 3. 字符串是特定的数据对象，它是由字符构成的线性表。 4. 单链表插入操作应该先将S结点的next指向P结点的next，然后将P结点的next指向S，所以题目给出的操作顺序错误。 5. 无向图的连通分量定义正确，是其极大的连通子图。 6. 邻接表可以灵活表示有向图或无向图，是图数据结构的有效表示方式。 7. 二叉树的后根遍历与对应的B树的中序遍历结果相同。 8. 二叉树的第i层最多有2^(i-1)个节点，但不一定是这样，例如完全二叉树。 9. 对于m阶的B-树，非叶节点至少有m/2个关键字，而不是题目中所说的ém/2ù。 10. 快速排序在最坏情况下时间复杂度为O(n^2)，但在平均情况下为O(nlogn)，而起泡排序平均时间复杂度也为O(n^2)。 二、选择题解析： 1. c.快速排序在平均情况下时间复杂度为O(nlogn)，最坏情况下为O(n^2)；d.堆排序在所有情况下时间复杂度均为O(nlogn)。 2. b.在n个节点的二叉树的二叉链表表示中，有n个节点和n+1个空指针（每个节点两个指针，根节点的父指针为空）。 3. a.最优二叉树（哈夫曼树）用于实现不等长编码，提高编码效率。 4. a.顺序查找适用于有序单链表，因为无法利用索引快速定位，只能逐个比较。 5. a.设置监视哨是在查找表末尾添加一个特殊元素，便于查找结束条件的判断。 6. c.队列具有先进先出（FIFO）特性，b.栈具有先进后出（LIFO）特性。 7. f.具有m个节点的二叉排序树的最大深度为m，最小深度为log2m（完全二叉树情况）。 8. c.快速排序一趟后可能得到的中间结果是28,34,37,52,56,57,58,64,79,84。b.希尔排序初始步长为4的一趟排序可能会得到28,34,52,56,37,57,58,64,79,84。d.基数排序一趟后结果可能是26,28,34,37,52,56,57,58,64,79,84。a.初始堆（大堆顶）应为84,79,64,58,57,52,37,28,26,34,56。