二 、 单项选择题

1. 线性表的顺序存储结构是一种【】的存储结构。

A. 散列存取 B. 索 引 存 取 C. 随机存取 D. 顺序存取
答案：C
解析：
A. 散列存取：顺序存储结构并不依赖于散列函数来确定元素的存储位置，因此A选项不正确。
B. 索引存取：虽然索引存取可以提供快速查找，但顺序存储结构本身并不包含索引表，因此B选项也不正确。
C. 随机存取：顺序存储结构允许通过元素的序号直接计算出其存储地址，从而实现随机访问。这是顺序存储结构的一个重要特点，因此C选项是正确的。
D. 顺序存取：虽然顺序存储结构的元素在物理上是连续的，但“顺序存取”更多指的是一种按物理顺序依次访问的方式，并不强调能够直接通过序号计算地址的能力。因此，相比C选项，D选项的描述不够准确。
综上所述，线性表的顺序存储结构是一种随机存取的存储结构。
答案
C. 随机存取

2. 循环队列用数组A[m]存放其元素值，已知队列的头和尾分别用front和 rear来 指示，初始化时置front=rear=0, 则当前队列长度是【】

A.(rear-front+m)%m
B.rear-front+1
C.rear-front-1
D.rear-front
答案：A
解析：
长度 = (rear - front + m) % m

3. 线性表的链式存贮结构的优点为 【】

A. 存储空间可充分利用
B. 可随机存取表中任一元素
C. 插入删除操作较为方便
D. 便于查找线性表中的元素
答案：C
解析：
A. 存储空间可充分利用
链式存储结构确实可以动态地分配和释放存储空间，但这并不意味着它能比顺序存储结构更“充分”地利用存储空间。实际上，由于指针的存在，链式存储可能会有一些额外的空间开销。因此，这个选项不是链式存储结构的主要优点。
B. 可随机存取表中任一元素
链式存储结构不支持随机存取。在链式存储中，要访问某个元素，必须从链表的头部或尾部开始，沿着指针顺序遍历，直到找到该元素。因此，这个选项是不正确的。
C. 插入删除操作较为方便
链式存储结构在插入和删除操作方面具有显著的优势。由于不需要移动大量元素来腾出空间或填补空缺，只需修改相应的指针即可完成插入或删除操作。这使得链式存储结构在处理频繁插入和删除操作的场景中非常高效。因此，这个选项是正确的。
D. 便于查找线性表中的元素
如前所述，链式存储结构不支持随机存取，因此在查找特定元素时可能需要遍历整个链表。这与顺序存储结构相比，在查找效率方面并不占优势。因此，这个选项是不正确的。

4. 折半插入排序是对直接插入排序算法的改进，它着眼于减少【】

A. 移动元素的次数
B. 排序的趟数
C. 与关键字比较的次数
D. 空间复杂度
答案：C
解析：
A. 移动元素的次数
折半插入排序在确定插入位置后，仍然需要移动元素以腾出空间给待插入元素。因此，它并没有减少移动元素的次数。
B. 排序的趟数
折半插入排序与直接插入排序在排序趟数上是一致的，都是需要遍历整个序列。所以，这个选项也不正确。
C. 与关键字比较的次数
折半插入排序通过折半查找来确定插入位置，这显著减少了与关键字比较的次数。在最好情况下，每次比较都能将搜索范围减半，从而大大提高了效率。这正是折半插入排序相对于直接插入排序的主要改进点。
D. 空间复杂度
折半插入排序和直接插入排序都是原地排序算法，它们的空间复杂度都是O(1)，即不需要额外的存储空间。因此，这个选项也不符合题意。
综上所述，折半插入排序是对直接插入排序算法的改进，它主要着眼于减少与关键字比较的次数。
因此，正确答案是C。

5. 设有向图的顶点个数为n, 则该有向图最多有【】条弧。

A.n-1 B.n(n-1) C.n(n+1) D.n²
答案：C
解析：
在有向图中，每个顶点都可以向其他任何顶点发出一条有向边（弧）。因此，对于n个顶点的有向图，（因为它不能向自己发出弧）每个顶点最多可以发出n-1条弧。
所以，如果我们考虑所有的顶点，那么最多可能的弧数是n乘以(n-1)，即每个顶点都发出n-1条弧。但这里需要注意的是，我们计算的是“最多”有多少条弧，而不是“总共有”多少条弧。实际上，图中可能并没有所有的顶点都相互连接。
根据这个逻辑，最多可能的弧数是：
n * (n - 1) = n(n - 1)

6. 如果二义树中任何一个非终端结点的值都人于其左子树上所有结点的值而小丁 其右子树上所有结点的值，要得到各结点值的递增序列，应按【】遍历次序排列结点。

A. 先 序 B. 中 序 C. 后 序 D. 层序
答案：B
解析：
A. 先序遍历：先访问根结点，然后依次遍历左子树和右子树。这种遍历方式并不能保证得到递增的序列。
B. 中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。在二叉排序树中，由于左子树的所有值都小于根结点，而右子树的所有值都大于根结点，因此中序遍历能够确保得到的结点值序列是递增的。
C. 后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点。这种遍历方式同样不能保证得到递增的序列。
D. 层序遍历：按照从上到下、从左到右的顺序逐层遍历结点。这种方式也不能保证得到递增的序列。
综上所述，为了得到各结点值的递增序列，在二叉排序树中应采用中序遍历的方式。因此，正确答案是 B. 中序。
所以，最终选择B选项。

7. 具 有n 个结点的Huffman 树有【】个叶子结点。

A.n-1 B.[n/2]- C.[n/2]+ D. 不 定
注：-：表示向下取整，+：表示向上取整
答案：A
解析：
具有n个结点的Huffman树有n-1个叶子结点。
因此，正确答案是：A. n-1

8. 已知广义表L=((x,y,z),a,(u,t,w)),从 L中取出原子项y 的运算是【】

A.head(tail(head(L))) B.tail(head(head(tail(L))))
C.tail(tail(head(tail(L)))) D.head(tail(head(head(L))))

答案：A
解析：
在广义表L=((x,y,z),a,(u,t,w))中，要取出原子项y，我们需要逐步解析广义表的结构。
首先，广义表L的第一个元素是另一个列表(x,y,z)。我们可以使用head和tail操作来访问这个列表的元素。
1.head(L)将返回广义表L的第一个元素，即列表(x,y,z)。
2.接着，tail(head(L))将返回列表(x,y,z)去掉第一个元素x后的部分，即(y,z)。
3.最后，head(tail(head(L)))将返回(y,z)的第一个元素，即y。
因此，从L中取出原子项y的运算是head(tail(head(L)))。
选项A正确，即： A. head(tail(head(L)))
其他选项的解析如下： B. tail(head(head(tail(L))))：这个表达式首先会得到L的第二个元素a，然后尝试对a进行head和tail操作，但a是原子项，不是列表，所以这个表达式是错误的。 C. tail(tail(head(tail(L))))：这个表达式在B的基础上多了一次tail操作，同样因为a是原子项，所以这个表达式也是错误的。 D. head(tail(head(head(L))))：这个表达式在A的基础上多了一次head操作，会得到x而不是y，所以这个表达式也是错误的。

9. 已知待排序的关键字序列为：36,21,78,63,6,52,15,39,48,70,10,需按非递减 次序排序，则希尔排序第一趟(增量为5)的结果为 (1) ;起泡排序第一趟的 结果为 (2) ;快速排序第一趟(以第一个元素为支点)的结果为 (3) ;堆排序初始建堆(大顶堆)的结果为 (4) 。

A.21,36,63,6,52,15,39,48,70,10,78
B.78,70,52,63,21,36,15,39,48,6,10 C.78,52,63,70,21,15,36,39,48,6,10 D.10,21,15,6,36,52,63,39,48,70,78 E.10,15,39,48,6,36,21,78,63,70,52 F.21,36,78,63,6,52,15,39,48,70,10

答案：A,F,E,B
解析：
希尔排序第一趟结果：A. 21, 36, 63, 6, 52, 15, 39, 48, 70, 10, 78
起泡排序第一趟结果：F. 21, 36, 63, 6, 52, 15, 39, 48, 70, 10, 78
快速排序第一趟结果：E. 10, 15, 39, 48, 6, 36, 21, 78, 63, 70, 52
堆排序初始建堆结果：B. 78, 70, 52, 63, 21, 36, 15, 39, 48, 6, 10