中科大计算机真题程序设计 数据结构

中国科学技术大学 一九九八年招收硕士学位研究生入学考试试题 试题名称:程序设计 中国科学技术大学 一九九八年招收硕士学位研究生入学考试试题 试题名称:编译原利于操作系统 中国科学技术大学 一九九七年招收硕士研究生入学考试试题 试题名称：程序设计 等等 【知识点详解】 1. **数据结构基础** - 邻接矩阵：无向图的邻接矩阵是对称的，每个顶点至少与其自身相连，所以至少有n个非零元素；对于强连通图（每个顶点都可以通过边到达其他任何顶点），至少需要n条边。 - 折半查找：适用于有序存储结构，如有序数组，查找过程中关键字必须有序，查找成功最多比较log₂n次，不成功最多比较n次。 - 广义表：广义表的长度是指元素个数，深度是表中嵌套的最深深度。L的长度为3，深度为3，head(L)为空表，tail(L)为((y), B), L)。 2. **二叉树与排序** - 二叉树的高度与节点数量的关系：高度为h的二叉树，无度为1的结点，最小节点数为2^(h-1)，最大节点数为2^h-1。 - 二叉树的存储：将二叉树写入磁盘文件通常使用二叉链表或二叉树的序列化方法。 - 散列表：线性探测法解决冲突时，k个同义词至少需要k次探测。 - 排序算法：稳定的排序算法如冒泡、插入排序，就地排序算法如快速排序、希尔排序。 3. **B树和遍历** - B树的分裂与合并：分裂时原有关键字个数为m-1，合并时为m/2。 - ISAM文件组织方式适合于随机访问，如磁盘存储。 - 遍历二叉树：完全二叉树的任意遍历结果可能相同。 - 拓扑排序：主对角线以下元素全为零的有向图可以有拓扑排序序列。 - 外部排序的k路平衡归并效率与k有关，败者树能有效优化。 4. **排序算法的时间复杂度** - 分治策略：n/k个组，每个组k个元素的排序，时间复杂度下界为O(nk)。 - 有序表归并：最多比较次数为2n-1。 - Fibonacci树与平衡二叉树：Fibonacci树是平衡二叉树，但不是相同深度的平衡二叉树中节点最少的类型，例如AVL树和红黑树等更平衡。 5. **Fibonacci树** - Fibonacci树构造算法：用于构造特定形态的二叉树，深度为d的Fibonacci树的节点总数与Fibonacci数列有关。 - 平衡二叉树：Fibonacci树是平衡的，但不是最小节点数的平衡二叉树。 6. **二叉排序树的性质** - 二叉排序树的中序遍历得到有序序列，如果一个节点有两个子节点，其中序后继节点没有左孩子，意味着它是右子树中最小的节点；同理，中序前驱节点没有右孩子，因为它在左子树中是最大的节点。 7. **数组操作** - 数组A[1..n]包含n个不同元素，涉及数组操作的问题可能涉及排序、查找等，这部分内容未给出具体问题，故无法详细展开。 这些知识点涵盖了数据结构的基础概念，包括图、排序算法、二叉树、B树、散列表、广义表、平衡二叉树以及数组操作等。它们是计算机科学特别是计算机专业研究生入学考试的重点内容，对于深入理解计算机科学原理至关重要。