数据结构与算法：二分查找、快速排序、图论、哈夫曼树、二叉树

数据结构与算法：五道经典题目解析

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 二分查找的过程是不断将待查找的区间缩小，每次将区间中间的元素与目标元素进行比较，如果相等则找到，否则根据大小关系缩小区间。对于有序表，可以利用中间元素的位置来进行比较。因此，查找A[3]的比较序列的下标依次为：9（数组下标从1开始），5，3。

2. 快速排序

对n个记录的顺序表进行快速排序，所需要的辅助存储空间大致为（ ）。 A．O（1） B．O（n） C． O（log2n） D． O（n2）

解答：C 快速排序需要用到递归，每次递归需要开辟新的栈空间。最坏情况下，递归树的高度为n，因此需要O(log2n)的辅助存储空间。

3. 图论

设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A．5 B．6 C．7 D．8

解答：C 对于一个无向图，如果它是连通图，那么任意两个结点之间都有至少一条路径。假设该图有n个结点，则最少需要n-1条边才能保证该图是连通图。因此，对于6个结点的无向图，至少需要6-1=5条边才能确保是一个连通图。

4. 哈夫曼树

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A．2m-1 B．2m C．2m+1 D．4m

解答：B 哈夫曼树中的叶子结点总数为m，则该树共有2m-1个结点。对于二叉链表，每个结点有两个指针域，因此共有2m个指针域，但是根节点没有父节点，因此需要减去1，即2m-1个空指针域。

5. 二叉树

设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 A． 9 B． 10 C．11 D． 12

解答：B 对于有n个结点的二叉树，最小高度为log2(n+1)-1。因此，对于有2000个结点的二叉树，最小高度为log2(2001)-1≈10。注意：log2表示以2为底的对数。