严蔚敏数据结构复习题及解析

"这是一份针对严蔚敏版数据结构课程的复习题集，涵盖了多项选择题和判断题，但未提供答案。" 在数据结构的学习中，掌握各种数据结构的特性和操作至关重要。这份复习题涉及到的知识点广泛，包括线性表、链表、队列、字符串、二叉树、树、图、排序算法和存储结构等多个方面。 1. **线性表**：线性表的长度是指表中的元素个数，而不是存储空间的大小。在链式存储中，线性表的元素可以在内存中不连续存放；而在顺序存储中，元素的物理顺序与逻辑顺序一致，但这并不代表线性表的逻辑顺序与物理顺序总是一致，因为链式存储允许不连续。 2. **链表**：双循环链表的每个节点的后继指针并不总是指向逻辑后继，可能因为环形结构而指向其他位置。链队列的front指针在出队操作时可能会改变，因为出队会移动front指针。 3. **串**：两个字符串相等不仅要求字符相同，还需要字符的顺序相同。二叉树的结点度为1意味着该结点有一个子树，可能是左子树或右子树。 4. **二叉树**：由先序序列和后序序列无法唯一确定一棵二叉树，因为对于非叶子结点，只知道其左右子树的相对顺序，无法确定它们的绝对顺序。 5. **树**：最小代价生成树的代价是最小的，但不一定小于其他生成树的代价。图的拓扑排序序列不唯一，即使弧数为n-1，也可能有多个不同的拓扑序列。 6. **堆**：堆是满足堆性质的数据结构，(101, 88, 46, 70, 34, 39, 45, 58, 66, 10) 构成了大顶堆。将一棵树转换成二叉树，根结点可能有左子树，这取决于转换规则。不同的入栈和出栈组合可能导致不同的输出序列，尤其是当有重复元素时。 7. **哈夫曼树**：哈夫曼树是最优二叉树，具有最小带权路径长度，权值较大的结点通常离根较近。索引文件的索引表信息量较少，可常驻内存以提高访问速度。快速排序法是不稳定的排序算法，而堆排序法在空间效率方面较优。 8. **选择题**：涉及栈和循环队列的操作，如栈的输出序列推断和循环队列中元素个数的计算。栈遵循后进先出（LIFO）原则，循环队列的元素个数计算需考虑循环特性。 这些题目涵盖了数据结构的基础概念和操作，通过解答这些题目，学生可以检验自己对数据结构的理解程度，加深对各种数据结构特性的认识，并熟悉相关算法的应用。然而，没有答案的情况下，学生可能需要借助教材或在线资源来验证自己的解答。