数据结构查找排序经典试题
一、填空
1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度
ASL=_______。

2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有____________。

3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行
_________趟的
插入才能完成排序。

4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_________趟的
排序。

5、直接插入排序算法的时间复杂度为________________。

6、按（）遍历二叉排序树，可以得到按值递增的关键字序列，在下图
所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（）。

50
95
20
55
70
10 30 85
二、判断
1、平衡二叉树中子树的深度不能大于1。

（）
2、快速排序法是稳定的排序方法。

（）
3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地
方。

（）
4、冒泡排序法是稳定的排序方法。

（）
5、折半插入排序法是稳定的排序方法。

（）
三、选择
1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的
插入才能完成排序。

A、n
B、(n-1)/2
C、n+1
D、n-1
2、采用顺序查找法查找长度为n的线性表时，平均查找长度为（）
A、n
B、(n-1)/2
C、n/2
D、(n+1)/2
3、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行（）次比较。

A、1
B、2
C、3
D、4
4、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。

A、5
B、4
C、3
D、2
5、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，
则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

A、起泡排序
B、归并排序
C、直接插入排序
D、简单选择排序
四、综合题
1、给定一组数{6，7，9，4，3，5，8}，要求（a）构造一棵平衡的二叉排序树；（b）先根
遍历该树；（c）从该树中删除结点6，并保持其特性。

2、给定一组关键字{43，52，10，39，91，2，14，67}，请采用快速排序法将其排列成递增的序列，写出排序的中间过程。

3、给定一组数{4,5,7,2,1,3,6}，要求（a）构造一棵平衡的二叉排序树；（b）先根遍历该
树；（c）从该树中删除结点6，并保持其特性。

4、给定一组关键字{43，52，10，39，91，2，14，67}，请采用选择排序法将其排列成递
增的序列，写出排序的中间过程。

5、给定一组关键字{54，63，21，50，102，13，25，78}，请采用快速排序法将其排列成
递减的序列，写出排序的中间过程。

6、 6、给定一组关键字{54，63，21，50，102，13，25，78}，请采用冒泡排序法将其排列
成递减的序列，写出排序的中间过程。

7、给定一组关键字{46，55，13，42，94，5，17，70}，请采用直接插入排序法将其排列
成递增的序列，写出排序的中间过程。

8、应用希尔排序算法从小到大进行排序，键值序列为
503,17,512,908,170,897,275,653,426，增量序列为{4，2，1}，试写出每趟排序的结果。