中央电大数据结构期末考试试题解析：完全二叉树高度与算法复杂度

本资源是一份中央广播电视大学2007-2008学年度第一学期开放本科计算机专业数据结构期末考试试卷，包含单项选择题和填空题，考察了多个数据结构和算法的基础知识点。 1. **完全二叉树高度计算**： 题目询问一棵具有35个节点的完全二叉树的高度。完全二叉树的特点是除了最后一层外，每一层都是满的，且最后一层的节点都尽可能地集中在左边。假定空树的高度为-1，根据完全二叉树性质，我们可以用公式(35+1)/2 - 1来计算高度。计算得到高度为6。 2. **一维数组存储特性**： 一维数组在内存中的存储是连续的，这意味着相邻元素在物理位置上也是连续的。虽然数组元素的逻辑顺序通常是按照索引进行的，但题目提到不一定顺序存取，可能指的是数组可以有非连续的索引访问，但仍保持连续存储。 3. **矩阵压缩存储**： 对于一个n阶对称矩阵，其上三角或者下三角部分的元素是对称的。如果只存储非对角线部分，一维数组至少需要存储n(n-1)/2个元素，因为这是上三角形的元素数量，下三角形的相同。 4. **双向链表的优势**： 双向链表作为线性表的存储结构，优点在于可以双向遍历，即既能从前往后，也能从后往前，这使得插入和删除操作更为灵活，尤其是在尾部和头部的插入和删除操作上。 5. **链式栈的插入操作**： 在链式栈中，若要在栈顶插入一个新结点，需要先将新结点的link指向前一个结点（即栈顶），然后更新栈顶指针指向新结点，正确答案是B。 6. **堆和插入操作复杂度**： 堆是一种特殊的树形数据结构，用于实现优先队列。向具有n个节点的堆中插入一个新元素，由于堆的性质，插入操作通常在O(log2n)时间内完成。 7. **AVL树的平衡因子范围**： AVL树是一种自平衡二叉搜索树，其每个节点的平衡因子（左子树高度减去右子树高度）的范围是-1到1。 8. **无向图的性质**： 一个有n个顶点和n条边的无向图，由于每条边连接两个顶点，所以必定是连通的，因为只要有n条边，最坏情况下可以形成n个单独的孤立点，但只要有n-1条边就可以将所有点连成一个连通的图。 9. **理想平衡二叉树的结点数**： 一棵高度为h的理想平衡二叉树中，最少结点数可通过公式2^(h+1) - 1计算，当h=3时，最少结点数为8。 以上是试卷中涉及的数据结构知识点，涵盖了二叉树的高度、数组存储、矩阵压缩、链表操作、堆的插入、AVL树的平衡因子、图的性质以及平衡二叉树的结构。这些知识点在数据结构的学习中非常重要，有助于理解和应用这些数据结构在实际问题中的解决方案。