数据结构模拟试卷二：重点习题与答案解析

本资源是一份数据结构模拟试卷二及其答案，包含10道选择题，主要考察了单链表操作、循环队列容量、顺序存储与链式存储的优势、二维数组索引计算、二叉树遍历、二叉树结点数、二分查找的前提、堆排序的辅助空间需求、散列函数的应用以及数据结构基础知识的理解。 1. 题目涉及到了单链表的操作，如在带有附加表头的链表中插入新节点，正确操作是将新节点的next指针指向原表头的下一个节点，然后更新表头指针，选项B是正确的：`p->next=HL->next; HL->next=p;`。 2. 循环队列的最大存储容量是队头和队尾之差加1，即`n-1`个元素，因为队列的特性是最后一个元素的下一个位置是第一个元素，所以答案是B。 3. 顺序存储方式的优点包括存储密度大和获取符合某种条件的元素方便（如通过索引快速定位），但插入和删除操作通常效率较低，因此选项C正确。 4. 二维数组的索引计算是基于行和列的，已知A[0][0]的位置，可以推算出A[2][3]的地址为`600 + (3 * m + 3 - 1) * 每个元素的大小`。由于m=25，每个元素占1个空间，所以A[2][3]的位置是`600 + (3 * 25 + 3 - 1) = 648`，选B。 5. 在二叉树遍历中，前序遍历先根节点后左子树再右子树，而中序遍历是先左子树后根节点再右子树。一个叶子节点作为前序遍历的最后一个节点，说明它是根节点的最后一个孩子，因此也是中序遍历的最后一个非叶节点，选项D正确。 6. k层完全二叉树的结点总数最多为第k层最后一个节点，即`2^(k-1)`，当k层不满时，最多的是倒数第二层满，此时结点数为`2^(k-1) - 1`，所以k层二叉树的结点总数最多为`2^(k-1)`，选A。 7. 二分法查找适用于有序的线性表，无论顺序还是链式存储，只要能够根据键值进行比较即可，所以选项C是前提：线性表以顺序方式存储，并且按关键码值排好序。 8. 堆排序是一种不稳定的排序算法，需要O(n)的辅助空间来存储临时堆，因此选项B是正确的。 9. 对于线性表中的散列存储，如果选择散列函数`H(K)=K%7`，当散列地址为0时，意味着模7的结果为0，对应数字为7的倍数。在这个例子中，只有7和64满足条件，所以散列地址为0的元素有2个，选B。 10. 数组是一种基本的数据结构，但题目可能在询问关于数组的特定描述，这里没有提供完整的选项，但从一般理解来看，数组是同类型元素的集合，选项D可能是强调数组的一致性和连续性，但具体表述未给出，需要更多信息才能判断。 这些题目全面涵盖了数据结构中的重要概念，包括线性表、队列、数组、二叉树、查找算法和散列等内容，有助于学习者理解和巩固相关知识。