数据结构篇•卷4•2020天勤计算机考研八套模拟卷.pdf

### 数据结构知识点解析 #### 一、选择题知识点解析 **1. 非空循环单链表与静态链表** - **非空循环单链表：** - 在题目中提到的“非空循环单链表head的尾结点p满足p→next=head”，这是非空循环单链表的基本特性之一。在一个非空循环单链表中，尾结点的`next`指针指向链表的头结点。 - “带头结点的循环单链表的头指针为head，如果head→next→next→next=head成立，则该单链表的长度为3”。这一陈述也符合循环单链表的特点。当head指针指向的下一个节点的下一个节点的下一个节点又指向了head时，说明链表中除了头结点外还有两个节点，因此整个链表的长度为3。 - **静态链表：** - “静态链表中的指针表示的是下一个元素在数组中的位置”是正确的。静态链表实际上是用数组实现的链表，其中的“指针”实际上是数组下标，用于表示下一个元素的位置。 **2. 三对角线矩阵的存储** - **三对角线矩阵：** - 三对角线矩阵是一种特殊类型的稀疏矩阵，只保留主对角线及其上下两条对角线上的元素。 - “设有一个n阶三对角线矩阵A[n][n]，现把它的三条对角线上的非零元素按行存放到一个一维数组B[]中，A[1][1]存放到B[1]中（假定不用0下标），那么B[k]存放的元素的行号是（ ）。” - 这里需要计算B[k]对应的行号。由于每行有三个元素被存储，可以通过`(k+1)/3`或`(k+2)/3`来估算行号。根据题目要求，正确答案应该是取整后最接近实际值的结果，即`(k+2)/3`。 **3. B-树的结构** - **B-树：** - B-树是一种自平衡的树数据结构，广泛应用于数据库和文件系统中。题目中的“已知一棵5阶B-树有53个关键字，并且每个结点的关键字都达到最少状态，则它包含关键字的结点共有几层”。 - 对于5阶B-树，每个结点至少包含2个关键字（最小状态），因此可以计算出层数。通过分析，可以得知这棵树有4层。 **4. 二叉树的性质** - **二叉树的性质：** - “具有10个叶子结点的二叉树中有9个度为2的结点”这一说法是正确的，因为在任何满二叉树或多叉树中，叶子节点的数量总是比度为2的节点多1。 - “设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9”也是正确的，因为在这种情况下，最小的二叉树是由一个根节点和四个叶子节点组成的。 - “一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个”也是正确的，完全二叉树的叶子节点数量可以根据总节点数计算得出。 - “高度为h的完全二叉树最少有2h个结点”这一说法不准确，正确说法应该是“高度为h的完全二叉树最少有2^(h-1)个结点”。 **5. 平衡二叉树的调整** - **平衡二叉树调整：** - 平衡二叉树（如AVL树）在插入或删除操作后可能需要进行旋转调整以保持平衡。 - 题目中提到“在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则为使其平衡，应做（ ）型调整”。在这种情况下，需要进行LR型调整。 **6. 无向图的性质** - **无向图的性质：** - “无向图中某个顶点的度是指图中与该顶点连通的顶点数”是正确的定义。 - “在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边”也是正确的，因为最少的边数构成的是一个树形结构。 - “无向图的邻接矩阵是对称矩阵”是正确的，因为无向图的邻接关系是双向的。 - “具有n个顶点的无向图，最多有n个连通分量”也是正确的，每个顶点都可以是一个独立的连通分量。 **7. 强连通图的定义** - **强连通图：** - “n个顶点构成的强连通图至少有n条边”是正确的，因为在强连通图中，任意两个顶点之间都存在路径。 - “强连通图是任何顶点到其他所有顶点都有边”是不准确的表述，应当是“任意两个顶点间都存在双向路径”。 - “完全有向图一定是强连通图”是正确的，因为完全有向图中任意两个顶点之间都存在双向边。 **8. 散列表的插入** - **散列表插入：** - “假设初始为空的散列表的地址空间为（0 10），散列函数为H（key）=keymod11，采用线性探测再散列法处理冲突，若依次插入关键字37、95、27、14、48，则最后一个关键字值48的插入位置是（ ）。” - 根据散列函数H(key)=key mod 11，可以计算出各个关键字的散列位置。插入顺序决定了冲突的处理方式。对于48，其散列位置为48 mod 11 = 5，但由于前面插入的关键字可能会导致冲突，所以最终的插入位置为6。 **9. 排序算法的速度** - **排序算法速度：** - “设待排序元素序列所有元素的关键字都相等，则下列排序方法中排序速度最慢的是（ ）。” - 在这种情况下，简单选择排序的速度是最慢的，因为它总是会进行完整的n(n-1)/2次比较，即使数组已经是有序的。 **10. 归并排序的比较次数** - **归并排序的比较次数：** - “假设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若采用败者树的方法，总的关键词比较次数不超过（ ）。” - 在5路平衡归并排序中，每个比较会涉及多个归并段，而败者树可以减少不必要的比较。对于这个问题，总的比较次数为396次。 #### 二、综合题知识点解析 **1. 栈与队列的识别** - **栈与队列的识别：** - 要判断输入的数据结构是栈还是队列，可以通过比较输入序列和输出序列来实现。如果输入序列与输出序列满足先进先出（FIFO）的原则，则为队列；如果是先进后出（FILO）的原则，则为栈。 - 提供的伪代码实现了队列的比较逻辑，检查两个队列是否相等。 **2. 拓扑排序** - **拓扑排序：** - 拓扑排序是对于有向无环图(DAG)的一种排序方法，可以确定图中顶点的一个线性顺序。 - 在没有使用栈或队列的情况下实现拓扑排序，可以通过遍历图的邻接表，并维护一个入度数组来记录每个顶点的入度。每次找到入度为0的顶点输出，并将其指向的所有顶点的入度减1，重复此过程直到所有顶点都被输出。 - 时间复杂度为O(V+E)，其中V是顶点数，E是边数。 以上是对给定文件中的知识点进行了详细的解析和扩展。