数据结构期末复习关键题解

"《数据结构》期末复习题答案包含了多项选择题，涵盖了数据结构的基础概念、存储结构、链表、栈、二叉树、排序、图等重要知识点。" 1. 数据结构中的存储结构是数据组织和存储的方式，包括顺序存储、链式存储、哈希表等。哈希表是一种通过哈希函数快速定位数据的结构，与存储位置有关，而题目中的C选项表明它与存储结构无关。 2. 向量(数组)的地址计算是基于元素的大小和数组下标的。例如，如果第一个元素地址是100，每个元素长度为2，那么第5个元素的地址是100 + (5 - 1) * 2 = 108。 3. 单向循环链表的空链表判断通常检查头节点的下一个节点是否指向自身，即head->next == head。 4. 进栈和出栈序列的规则遵循栈的先进后出（FILO）原则。选项D违反了这一原则，因为1在5之前进栈，却在5之后出栈。 5. 堆是一种特殊的树形数据结构，分为大根堆和小根堆。小根堆的特点是父节点的键值小于或等于其子节点的键值。选项A符合小根堆的定义。 6. 二叉树是一种每个节点最多有两个子节点的数据结构。B树是一种自平衡的查找树，虽然包含多个子节点，但它是多路搜索树，不属于二叉树。 7. 顺序存储的二叉树中，如果节点A[i]有右孩子，根据二叉树的顺序存储规则，其右孩子通常存储在A[2i+1]的位置。 8. 高度为4的树，若度为1、2、3、4的节点数分别为4、2、1、1，根据树的性质，叶子数（度为0的节点）可以通过公式2n0 - n1 + n2 - n3 + n4计算得出，此处n0 = 8。 9. 构建最小高度的二叉排序树，应遵循中序遍历的原则，将数值较大的元素尽可能地放在较高的层级，选项B符合这个原则。 10. 有向图的拓扑排序是指将无环有向图的所有节点排成一个线性的序列，使得对于每一条有向边(u, v)，u总是在v之前。选项C违反了拓扑排序的规则。 11. m阶B-树的非根节点至少包含[m/2]-1个关键字，保证了B-树的平衡性。 12. 散列文件又称作索引文件，是一种通过散列函数快速查找数据的存储结构。 13. 数据结构是数据元素之间存在特定关系的集合，它可以是线性结构、树型结构、图形结构或集合结构。 14. 逻辑关系上，数据元素的直接前驱为0个或1个的数据结构可能是线性结构（如队列、栈）或树型结构（如二叉树）。 15. 双向循环链表中，指针p所指向结点的反向指针可以用p->llink->rlink表示。 16. 两栈共享空间时，栈满的条件是栈1的栈顶指针加1等于栈2的栈顶指针。 17. 在二叉树中，度为2的节点个数和叶子结点个数之间的关系满足公式：n0 = n2 + 1，所以如果有11个叶子结点，度为2的节点个数为10。 18. 先根序列是树中每个节点先访问根节点再按左右子树顺序遍历的结果，对应二叉树的先序遍历。 这些题目涉及了数据结构的核心概念，对理解并掌握数据结构的基本原理和操作至关重要。