数据结构与算法试题解析：二分查找、快速排序、连通图、哈夫曼树、二叉树高度

数据结构与算法试题解析

1. 若有 18 个元素的有序表存放在一维数组 A 中，第一个元素放 A[1] 中，现进行二分查找，则查找 A[3] 的比较序列的下标依次为 ( )。

A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3

答案：C. 9，5，3

解析： 二分查找的步骤：

1. 首先找到中间元素下标为 9 (18/2=9)。
2. 比较 A[9] 与 A[3]，由于 A[3] 小于 A[9]，所以需要在左半部分继续查找。
3. 左半部分中间元素下标为 5 (9/2=4+1=5)。
4. 比较 A[5] 与 A[3]，由于 A[3] 小于 A[5]，所以需要在左半部分继续查找。
5. 左半部分中间元素下标为 3 (5/2=2+1=3)。
6. 比较 A[3] 与 A[3]，找到目标元素。

2. 对 n 个记录的顺序表进行快速排序，所需要的辅助存储空间大致为（ ）。

A. O（1） B. O（n） C. O（log2n） D. O（n2）

答案：C. O（log2n）

解析： 快速排序的辅助存储空间主要用于递归调用栈，递归深度约为 log2n，因此辅助存储空间为 O(log2n)。

3. 设有 6 个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A. 5 B. 6 C. 7 D. 8

答案：C. 7

解析： 一个连通图至少要有 n-1 条边，其中 n 为节点数。当节点数为 6 时，至少要有 5 条边。但是，如果只存在 5 条边，可能会形成两个独立的连通子图，例如：

1 -- 2
3 -- 4
5 -- 6

因此，至少要有 6 个节点中的 5 个节点都相连，才能确保是一个连通图，即需要 7 条边。

4. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

A. 2m-1 B. 2m C. 2m+1 D. 4m

答案：A. 2m-1

解析： 哈夫曼树有 m 个叶子节点，而每个非叶子节点都有两个孩子节点，因此非叶子节点总数为 m-1。每个节点都有两个指针域，所以总指针域个数为 2m + 2(m-1) = 4m-2。由于每个非叶子节点都有两个指针域指向孩子节点，所以空指针域个数为 4m-2 - 2(m-1) = 2m-1。

5. 设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ ）。

A. 9 B. 10 C. 11 D. 12

答案：B. 10

解析： 完全二叉树的高度最小，而 2000 个结点的完全二叉树的高度为 10，因为 2^9 < 2000 < 2^10。