第7章 查找
1．选择题
（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
A．(n-1)/2 B． n/2 C．(n+1)/2 D．n 答案：C
解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。 （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。
A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 答案：D
解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 （3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。
A．顺序查找 C．分块查找 答案：C
解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，
就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。
（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 答案：A
解释：表中共10个元素，第一次取?(1+10)/2?=5，与第五个元素20比较，58大于20，
再取?(6+10)/2?=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。
（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A．3 B．4 C．5 D．6 答案：B
解释：22个记录的有序表，其折半查找的判定树深度为 ?log222? + 1=5，且该判定树不
是满二叉树，即查找失败时至多比较5次，至少比较4次。
（6）折半搜索与二叉排序树的时间性能（ ）。
A．相同 B．完全不同 C．有时不相同 D．数量级都是O(log2n) 答案：C
21
B．折半查找 D．哈希查找
（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D．(100，80， 60， 90， 120，130，110) 答案：C
解释：A、B、C、D四个选项构造二叉排序树都以100为根，易知A、B、D三个序
列中第一个比100小的关键字为80，即100的左孩子为80，而C选项中100的左孩子为60，故选C。
（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。
A．LL B．LR C．RL D．RR 答案：C
（9）下列关于m阶B-树的说法错误的是（ ）。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上
C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D．根结点中的数据是有序的 答案：D
（10）下面关于B-和B+树的叙述中，不正确的是（ ）。
A．B-树和B+树都是平衡的多叉树 B．B-树和B+树都可用于文件的索引结构 C．B-树和B+树都能有效地支持顺序检索 D．B-树和B+树都能有效地支持随机检索 答案：C
（11）m阶B-树是一棵（ ）。
A．m叉排序树 B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树 答案：B 2．应用题
（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树； ② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 答案：
①先画出判定树如下（注：mid=?(1+12)/2?=6）：
30
5 63
22
3 7 42 87
4 24 54 72 95
②查找元素54，需依次与30, 63, 42, 54 元素比较； ③查找元素90，需依次与30, 63,87, 95元素比较；
④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。
答案：
12
7
17
2 11 16 21
4 9 13
验算方法： 用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21 3．算法设计题
（1）试写出折半查找的递归算法。 [算法描述]
int BinSrch（rectype r[ ]，int k，low，high）
//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2；
if（r[mid].key==k）return （mid）；
else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; }
else return （0）；//查找失败。 }//算法结束
（2）试写一个判别给定二叉树是否为二叉排序树的算法。
[题目分析] 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。
[算法描述] #define true 1 #define false 0 typedef struct node
23
{datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBST（BTree T,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（T!=null && flag）
{ Judgebst（T->lchild,flag）；// 中序遍历左子树
if（pre==null）pre=T；// 中序遍历的第一个结点不必判断 else if（pre->data
第8章 排序
1．选择题
（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A．归并排序 B．冒泡排序 C．插入排序 D．选择排序 答案：C
（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A．归并排序 B．冒泡排序 C．插入排序 D．选择排序 答案：D
（3）对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
A．从小到大排列好的 B．从大到小排列好的 C．元素无序 D．元素基本有序 答案：B
解释：对关键字进行冒泡排序，关键字逆序时比较次数最多。
（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。 A．n+1 B．n C．n-1 D．n(n-1)/2 答案：D
解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1
次，即(n-1)+(n-2)+…+1= n(n-1)/2。
（5）快速排序在下列（ ）情况下最易发挥其长处。 A．被排序的数据中含有多个相同排序码 B．被排序的数据已基本有序
24
C．被排序的数据完全无序
D．被排序的数据中的最大值和最小值相差悬殊 答案：C
解释：B选项是快速排序的最坏情况。
（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。 A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 答案：B
解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好
序的情况下，时间复杂度为O(n2)。
（7）若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79 答案：C
（8）下列关键字序列中，（ ）是堆。
A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72 答案：D
解释：D选项为小根堆 （9）堆是一种（ ）排序。
A．插入 B．选择 C．交换 D．归并 答案：B
（10）堆的形状是一棵（ ）。
A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树 答案：C
（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。
A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 答案：B
（12）下述几种排序方法中，要求内存最大的是（ ）。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序 答案：C
解释：堆排序、希尔排序的空间复杂度为O(1)，快速排序的空间复杂度为O(log2n)，
归并排序的空间复杂度为O(n)。
（13）下述几种排序方法中，（ ）是稳定的排序方法。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序 答案：C
25
数据结构（C语言版）第2版习题答案—严蔚敏（简化版）
