考研备考资料真题-2019年全国硕士研究生统一入学考试自命题试题(A卷).doc

根据给定文件的信息，我们可以提炼出以下几个主要的知识点： ### 1. 自命题试题的特点与作用 - **自命题试题**通常是指各个招生单位自主编制的考试题目，它旨在考查考生的专业基础知识和综合运用能力。 - **作用**：这类试题能够更加精准地评估考生对于特定领域或专业知识的理解程度，有助于选拔真正具备研究潜力的人才。 ### 2. 计算机科学与技术专业的核心课程——数据结构 - **课程内容**：数据结构作为计算机科学与技术专业的核心课程之一，主要涉及如何有效地组织和管理数据。 - **涵盖知识点**： - **基本概念**：如线性表、链表、栈、队列、数组、树、图等。 - **算法分析**：包括时间复杂度与空间复杂度的计算方法。 - **具体应用**：比如排序算法、查找算法等。 ### 3. 数据结构的选择题解析 #### 例题分析 - **例题1**：任何一棵二叉树 T, 假如度为 1 的结点数为 2，度为 0 结点数为 11，其分支数为？ - **解析**：根据二叉树的性质，可以推导出分支数=度为 1 的结点数 + 度为 2 的结点数。由于度为 0 的结点数已给出为 11，则度为 2 的结点数为结点总数减去度为 0 和 1 的结点数，即 \(n_2 = n - n_0 - n_1\)。其中 \(n = n_0 + n_1 + n_2\) 为总结点数，这里总共有 \(n_0 = 11\) 和 \(n_1 = 2\)，但总节点数未知。然而，根据二叉树的性质，度为 2 的结点数加上度为 1 的结点数再加上 1 就等于度为 0 的结点数。即 \(n_2 + n_1 + 1 = n_0\)。因此，\(n_2 = 8\)，分支数=度为 1 的结点数 + 度为 2 的结点数 = 2 + 8 = 10。但此题选项中没有10这个选项，可能存在题目描述的问题或理解偏差。 - **例题2**：深度为 k 的二叉树至多有多少个结点？ - **解析**：深度为 k 的二叉树的最大结点数可以通过公式 \(2^k - 1\) 来计算。因此正确答案应为 \(2^k - 1\)，选项中的 \(2^{k-1}\) 更接近，但是没有完全符合数学上的定义。 - **例题3**：一棵二叉树结点的中序序列为 BDCEAFHG, 后序序列为 DECBHGFA, 那么结点的先序序列为？ - **解析**：根据中序和后序遍历结果，可以逐步确定二叉树的结构。中序序列中，根节点位于后序序列的最后一个位置，即 F。根据这一信息，可以进一步推断出其他节点的位置。最终得出的先序序列为 ABCDEFGH。 - **例题4**：在有向图的逆邻接表存储结构中，顶点 v 在表结点中出现的次数是多少？ - **解析**：逆邻接表是用来存储每个顶点的逆邻接点列表的一种结构。顶点 v 在表结点中出现的次数实际上是顶点 v 的入度。 - **例题5**：顺序栈 s 的 GetTop(s, e)操作是如何实现的？ - **解析**：顺序栈是一种基于数组实现的栈，GetTop(s, e)操作是获取栈顶元素。在顺序栈中，通常会维护一个 top 指针指向当前栈顶元素的位置，因此正确答案是 e=*(s.top)。 - **例题6**：如果线性表最常用的操作是存取第 i 个元素及其前驱的值，哪种存储方式更节省时间？ - **解析**：顺序表能够直接通过索引访问元素及其前驱，因此在这种情况下，顺序表的效率更高。 - **例题7**：在一颗非空 m 阶的 B-树上，除根之外的所有非终端结点至少有多少棵子树？ - **解析**：B-树的每个非叶节点至少有 m/2 个子节点（m 为阶数），因此正确答案是至少有 \(\lceil m/2 \rceil\) 棵子树。 - **例题8**：用单链表表示队列时，哪种形式更适合队列操作？ - **解析**：带尾指针的循环链表更适合队列操作，因为这种方式可以方便地进行队首元素的插入和删除操作。 - **例题9**：下面的序列中，哪个是堆？ - **解析**：堆是一种特殊的完全二叉树，其中每个父节点的键都小于等于其所有子节点的键（最小堆）或大于等于其所有子节点的键（最大堆）。选项 D 满足最大堆的条件。 - **例题10**：设有一个 10 阶的对称矩阵 A, 采用压缩存储方式, 以行序为主序存储其下三角,a11 为第一个元素，那么元素 a85 的地址是什么？ - **解析**：对于 10 阶的对称矩阵 A，元素 a85 实际上是第 5 行第 5 列的元素。按照压缩存储的方式，a85 的地址可以通过公式计算得到，通常情况下，元素 aij 的地址可通过 \((i-1)i/2 + j - i\) 的公式计算得出，但这里需要具体了解存储方式和起始位置才能确定正确答案。 - **例题11**：使用带头结点的单链表存储队列，在进行出队操作时，队头指针和队尾指针会发生什么变化？ - **解析**：出队操作通常只修改队头指针，因为每次出队都是移除队头元素。 - **例题12**：由权为 7,2,4,5 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度是多少？ - **解析**：哈夫曼树的带权路径长度(WPL)可以通过将所有叶子结点的权重乘以其到根节点的距离再求和得到。在这个例子中，假设构建的哈夫曼树满足最优条件，那么 WPL 为 36。 - **例题13**：哪种数据结构最适合表示“遗传”关系？ - **解析**：树形结构最适合表示具有层次关系的数据结构，例如“遗传”关系，因此选项 C（树）是最佳答案。 这些知识点不仅涵盖了数据结构的基本概念和原理，还深入到了具体的算法分析和应用案例，对于准备考研的考生来说是非常宝贵的复习资料。