第九章 查找
一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是  顺序查找（线性查找）  。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索  9   次。设有100个结点，用二分法查找时，最大比较次数是  7    。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为  2   ；比较四次查找成功的结点数为  8   ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为   3.7  。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7  ！！！
4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素    28，6，12，20    比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是  散列查找   。
6. 散列法存储的基本思想是由  关键字的值     决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查找次数 ≤n-1)
8、设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选（  97 ）  
9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法   
10、对线性表进行二分查找时，要求线性表必须以   顺序     方式存储，且结点按关键字              有序排列。
11 在分块查找方法中，首先查找索引，然后再查找相应的   块。
12． 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ n __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ n+1  。
13．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_____6,9,11,12  _____。
14. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 _
15.  已知二叉排序树的左右子树均不为空，则____左子树______上所有结点的值均小于它的根结点值，____右子树______上所有结点的值均大于它的根结点的值。
16、中序遍历二叉排序树得到的序列是   有序    序列（填有序或无序）。
17、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为1   和3  ·

二、单项选择题
（  B  ）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为
Ａ. ＡＳＬ＝ｎ;         Ｂ. ＡＳＬ＝（ｎ＋１）／２;   
Ｃ. ＡＳＬ＝＋１;    Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（  A  ）2．折半查找有序表（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
（  C  ）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较        次关键字。
A．3         B．4          C．5           D． 6
（  A  ）4. 链表适用于       查找
A．顺序       B．二分法      C．顺序，也能二分法      D．随机
（ C   ）5.  折半搜索与二叉搜索树的时间性能
    A. 相同       B.  完全不同        C. 有时不相同       D. 数量级都是O（log2n）
6．散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ D   ）。
A．  8         B.   9        C.  10       D.  11
7. 当采用分快查找时，数据的组织方式为  ( B   )  
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
 8.  散列函数有一个共同的性质，即函数值应当以(  D  )取其值域的每个值。
A. 最大概率       B. 最小概率       C. 平均概率       D. 同等概率
9. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(  D  )    
A．k-1次     B. k次      C. k+1次      D. k（k+1）/2次
10、 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行(    )次探测。【西安电子科技大学 1998 一、8 （2分）】
A． k        B. k+1      C. k(k+1)/2      D.1+k(k+1)/2
11、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作(   C  ) 型调整以使其平衡。
A.  LL           B. LR          C.  RL          D.  RR
12、二叉查找树的查找效率与二叉树的( C)有关, 在 (B）)时其查找效率最低
    (1):  A. 高度         B. 结点的多少     C. 树型       D. 结点的位置
    (2):  A. 结点太多     B. 完全二叉树     C. 呈单枝树   D. 结点太复杂。
13、在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为（  C）
  A) 2          B) 3          C) 4          D) 5
14、对包含n个元素的哈希表进行查找，平均查找长度为（ D）
A) O(log2n)     B) O(n)     C) O(nlog2n)     D) 不直接依赖于n
15、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C   )。
 A． (n-1)/2       B. n/2        C. (n+1)/2        D. n
16. 下面关于二分查找的叙述正确的是  ( D   ) 
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储  C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型        D. 表必须有序，且表只能以顺序方式存储
17. 对线性表进行二分查找时，要求线性表必须（  B ）
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
18．适用于折半查找的表的存储方式及元素排列要求为(  D  )
    A．链接方式存储，元素无序     B．链接方式存储，元素有序
C．顺序方式存储，元素无序     D．顺序方式存储，元素有序
19. 用二分（对半）查找表的元素的速度比用顺序法(  D  ) 
A．   必然快      B. 必然慢      C. 相等      D. 不能确定
20．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(  C  )                      
A．必定快     B.不一定     C. 在大部分情况下要快    D. 取决于表递增还是递减
21. 具有12个关键字的有序表，折半查找的平均查找长度（  A ）
  A. 3.1            B. 4            C. 2.5            D. 5
22. 折半查找的时间复杂性为（ D  ）
A. O（n2）     B. O（n）     C. O（nlogn）     D.  O（logn）
23．设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ D ）。
    (A) 6    (B) 11    (C) 5    (D) 6.5
24. 二叉排序树的查找效率与二叉树的( C)有关
    A. 高度         B. 结点的多少     C. 树型       D. 结点的位置
25．在等概率情况下,一棵平衡树的ASL为 ( B )
A. O(1)    B. O( log2n )    C. O((log2n)2)     D.O(nlog2n)   
26．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(  C  ) 
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)
27. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作(  C  ) 型调整以使其平衡。
A.  LL           B. LR          C.  RL          D.  RR
28、下列二叉排序树中，满足平衡二叉树定义的是（B）
  

29．下列关于m阶B-树的说法错误的是( D   )  
A．根结点至多有m棵子树     B．所有叶子都在同一层次上
C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树  D. 根结点中的数据是有序的
30. 下面关于m阶B树说法正确的是( B   )
  ①每个结点至少有两棵非空子树；   ②树中每个结点至多有m一1个关键字;
 ③所有叶子在同一层上;  ④当插入一个数据项引起B树结点分裂后，树长高一层。
A． ①②③      B. ②③       C. ②③④       D. ③
31. 下面关于B和B+树的叙述中，不正确的是(  C  )  
A.  B树和B+树都是平衡的多叉树。       B.  B树和B+树都可用于文件的索引结构。
C.  B树和B+树都能有效地支持顺序检索。 D.  B树和B+树都能有效地支持随机检索。
32、下列叙述中，不符合m阶B树定义要求的是（    D）
 A．根节点最多有m棵子树    B.所有叶结点都在同一层上  
 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接  
33、设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（  B）。
    (A) 小于等于m的最大奇数    (B) 小于等于m的最大素数
    (C) 小于等于m的最大偶数    (D) 小于等于m的最大合数
34、适于对动态查找表进行高效率查找的组织结构是（ C  ）
A．有序表      B．分块有序表   C．二叉排序树  D．线性链表
35、当采用分快查找时，数据的组织方式为  (  B  ) 
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

三、判断题
1、查找相同结点的效率折半查找总比顺序查找高。(× )
2、索引顺序表的特点是块内可无序，块间要有序。（ √ ）
3、 在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。(  ()
4、在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。(√ )
5、若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。（√ ）
6、折半搜索适用于有序表，包括有序的顺序表和有序的链表。(╳ )
7．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（√  ）
8．在散列检索中，“比较”操作一般也是不可避免的。（√  ）
9．在m阶B-树中每个结点上至少有 个关键字，最多有m个关键字。(× )
10．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（√  ）
11. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（√  ）
12. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 (× )
13. 若散列表的负载因子α<1，则可避免冲突的产生。(× )
14．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。(× )
15. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。(× )
16. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（×　）
 17. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。(× )
18．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（√ ）
19．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间. (× )
20、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。(× )
21、顺序查找法适用于存储结构为顺序或链接存储的线性表。（√ ）
四、简答题
1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
2.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
画出描述折半查找过程的判定树；
若查找元素54，需依次与哪些元素比较？
若查找元素90，需依次与哪些元素比较？
假定每个元素的查找概率相等，求查找成功时的平均查找长度。
解：
先画出判定树如下（注：mid=((1+12)/2(=6）：
30
5           63
3     7       42        87
             4    24      54    72      95
(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；
(3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；
（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
3.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K  MOD  16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
        （10，24，32，17，31，30，46，47，40，63，49）
造出Hash表，试回答下列问题：
画出哈希表的示意图；
若查找关键字63，需要依次与哪些关键字进行比较？
若查找关键字60，需要依次与哪些关键字比较？
假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
解： （1）画表如下：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

32
17
63
49

24
40
10

30
31
46
47

（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55
4、设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。
0
1
2
3
4
5
6
7
8
9
10

K
TA
BA
M
D
CI
X
 
 
TN
I

ASL=20/9
 0
1
2
3
4
5
6
7
8
9
10

 
 
 
 
 
 
 
 
 
 
 

 

ASL=15/9
5、输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴ 画出该二叉排序树；
⑵ 画出删除结点302后的二叉排序树。
解： 

6、 设有一组关键字：{19，01，23，14，55，20，84，27，68}，采用哈希函数：
H（key）=key mod 7，采用开放地址法的线性探测再散列方法解决冲突。
要求：在0∽11的散列地址空间中对该关键字序列构造哈希表。
0   1   2   3    4   5   6  7    8    9  10  11  
  

解：            0   1   2   3   4    5   6   7    8   9  10   11  
14
01
23
84

19
55
20
27
68

7、已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
8、用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
解：
散列地址
0
1
2
3
4
5
6
7
8
9

关键字
14
01
9
23
84
27
55
20
 
 

比较次数
1
1
1
2
 3  
4
1
2
 
 

平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H（27）=27%7=6（冲突）   H1=（6+1）%10=7（冲突） 
H2=（6+22）%10=0（冲突）   H3=（6+33）%10=5   所以比较了4次。
设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc
解：1）
散列地址
0
1
2
3
4
5
6
7
8
9
10

关键字
 
4
 
12
49
38
13
24
32
21
 

比较次数
 
1
 
1
1
2
1
2
1
2
 

ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8
ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

9、选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。
解：由题意知，m=11(刚好为素数)
则(22*3)%11=6……0     
(41*3)%11=11……2
 (53*3)%11=14……5
(08*3)%11=2……2
(46*3)%11=12……6
(30*3)%11=8……2
(01*3)%11=0……3
(31*3)%11=8……5
(66*3)%11=9……0
22
66
41
8
30
53
46
1
31

0
1
2
3
4
5
6
7
8
9
10

1

3
4，7

五、算法设计题
已知11个元素的有序表为（05  13  19  21  37  56  64  75  80  88  92）, 请写出折半查找的算法程序，查找关键字为key的数据元素 (建议上机调试)。
解：折半查找的C程序有很多参考资料，注意此题要求是整型量。
折半查找的一个递归算法如下，形式非常简洁！
int Search_Bin_Recursive(SSTable ST, int key, int low, int high)  //折半查找的递归算法 
{ 
  if(low>high) return 0;   //查找不到时返回0 
  mid=(low+high)/2; 
  if(ST.elem[mid].key= =key) return mid; 
  else if(ST.elem[mid].key>key) 
    return Search_Bin_Recursive(ST, key, low, mid-1); 
  else return Search_Bin_Recursive(ST, key, mid+1, high); 
  } 
}//Search_Bin_Recursive 

2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”
（刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。
若要采用递归算法，建议您采用如下的函数首部：
bool BisortTree(BiTree T,  BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。
（或者直接存储前驱的数值，随时与当前根结点比较）
一个漂亮的算法设计如下：
int last=0, flag=1;          //  last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。
int Is_BSTree(Bitree T)       //判断二叉树T是否二叉排序树，是则返回1，否则返回0 
{ 
  if(T->lchild&&flag) Is_BSTree(T->lchild); 
  if(T->data<last) flag=0;     //与其中序前驱相比较, flag=0表示当前结点比直接前驱小，则立即返回
  last=T->data; 
  if(T->rchild&&flag) Is_BSTree(T->rchild); 
  return flag; 
}//Is_BSTree 

已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。
解：设计哈希表的步骤为：
根据所选择的处理冲突的方法求出装载因子a的上界；
由a值设计哈希表的长度m；
根据关键字的特性和表长m选定合适的哈希函数。
刘注：要求ASL≤3，则m必然要尽量长，以减少冲突；
已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
解：注意此题给出的条件：装载因子a〈1, 则哈希表未填满。由此可写出下列形式简明的算法：
void PrintWord(Hash Table ht)
{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。
for(i=1; i<=26; i++){
j=i;
While(ht.elem[j].key){
if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);
j=(j+1)%m;
}
}}//PrintWord
第10章   排序

一、填空题（每空1分，共24分）
1. 大多数排序算法都有两个基本的操作：   比较和   移动。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较   3   次。 
3. 在插入和选择排序中，若初始数据基本正序，则应选用 插入  排序算法；若初始数据基本反序，则应选用   选择   排序算法。
4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用   堆排序；若初始记录基本无序，则最好选用 快速排序  。
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2)。若对其进行快速排序，在最坏的情况下所需要的时间是  O(n2)           。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是  O(nlog2n) 
，所需要的附加空间是  O(n)  。
7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐     趟（遍）。
8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y  ；归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；快速排序一趟扫描的结果是 F H C D P A M Q R S Y X  ；堆排序初始建堆的结果是 A D C R F Q M S Y P H X    。
9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是冒泡算法，最费时间的是快速算法。 
10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为___ n(n-1)/2 ____。

二、单项选择题（每小题1分，共18分）
1、下列四个序列中，（  C  ）是堆。 
A. 75,65,30,15,25,45,20,10     B. 75,65,45,10,30,25,20,15
C. 75,45,65,30,15,25,20,10     D. 75,45,65,10,25,30,20,15
（  C  ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
Ａ. 希尔排序      Ｂ. 冒泡排序        Ｃ. 插入排序       Ｄ. 选择排序
（  D  ）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
Ａ. 希尔排序      Ｂ. 归并排序        Ｃ. 插入排序       Ｄ. 选择排序
（   B  ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的   Ｂ. 从大到小排列好的    Ｃ. 元素无序   Ｄ. 元素基本有序
（  D ）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
Ａ. n+1           Ｂ. n           Ｃ. n-1         Ｄ. n(n-1)/2
（  C ）6．快速排序在下列哪种情况下最易发挥其长处。
Ａ.  被排序的数据中含有多个相同排序码   Ｂ. 被排序的数据已基本有序
Ｃ.  被排序的数据完全无序    Ｄ. 被排序的数据中的最大值和最小值相差悬殊
（  B  ）7．  对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是
A．O(n)     B．O(n2)    C．O(nlog2n)     D．O(n3)
（  C  ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
Ａ.   38,  40,  46,  56,  79,  84            Ｂ.  40, 38,  46 ,  79,  56,  84      
Ｃ.   40,  38，46,  56,  79,  84            Ｄ.  40,  38, 46,  84,  56,  79
（  D  ）9．下列关键字序列中，       是堆。
Ａ.  16, 72, 31, 23, 94, 53         Ｂ.  94, 23, 31, 72, 16, 53     
Ｃ.  16, 53, 23, 94，31, 72        Ｄ.  16, 23, 53, 31, 94, 72
（  B  ）10．堆是一种       排序。
Ａ. 插入          Ｂ.选择        Ｃ. 交换       Ｄ. 归并
（  C  ）11．堆的形状是一棵       
Ａ. 二叉排序树       Ｂ.满二叉树        Ｃ. 完全二叉树       Ｄ. 平衡二叉树
（  B  ）12．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为
12、 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是  ( B   ) 
  A. l              B. 4             C. 3              D. 2
13、 快速排序方法在（ D   ）情况下最不利于发挥其长处。  
A. 要排序的数据量太大       B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数   D. 要排序的数据已基本有序
14、在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ D  ）位置上。
   A．n/2     B．n/2 -1    C．1     D．n/2 +2    
15、1．将5个不同的数据进行排序，至多需要比较（ C  ）次。
Ａ. 8                Ｂ. 9             Ｃ. 10         Ｄ. 25

16． 下述几种排序方法中，要求辅助内存最多的是（  C  ）
Ａ. 插入排序      Ｂ.快速排序        Ｃ. 归并排序       Ｄ. 选择排序
17、对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A  ）
A）{21、25、5、17、9、23、30}     B）{25、23、30、17、21、5、9}
B）{21、9、17、30、25、23、5}     D）{5、9、17、21、23、25、30}
18、稳定的排序方法是（B    ）  
A．直接插入排序和快速排序       B．折半插入排序和起泡排序
C．简单选择排序和四路归并排序   D．树形选择排序和shell排序
19、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（  B  ）。
    A. O(log2n) B. O(1)  C. O(n)  D. O(nlog2n)
20、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（  C）
   A、O（1）   　　B、O（n）　　   C、O（1og2n）       D、O（n2）

21、下列排序方法中，哪一个是稳定的排序方法？（  B　）  
A．堆排序     B．二分法插入排序     C．希尔排序       D．快速排序
22、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ C   ）就是不稳定的排序方法。
A．起泡排序    B．归并排序    C．Shell排序    D．直接插入排序
23．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（  C  ）。
  A. 快速排序    B. 堆排序      C. 归并排序      D. 直接插入排序
24．在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（ B   ）
A．快速排序   B.直接插入排序  C. 二路归并排序  D.起泡排序  
25．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(  A  )
A．选择排序法    B. 插入排序法     C. 快速排序法     D. 堆排序
26、某内排序方法的稳定性是指(D    )。 
A．该排序算法不允许有相同的关键字记录      
B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法       
 D．以上都不对 
27、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（D）
A：递归次数与初始数据的排列次序无关
B：每次划分后，先处理较长的分区可以减少递归次数
C：每次划分后，先处理较短的分区可以减少递归次数
D：递归次数与每次划分后得到的分区处理顺序无关
28、对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下（A）
第一趟：2，12，16，5，10，88
第二趟：2，12，5，10，16，88
第三趟：2，5，10，12，16，88
则采用的排序方法可能是：
A：起泡排序   B：希尔排序   C：归并排序   D：基数排序
29、已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是  （A）
A．3，5，12，8，28，20，15，22，19  
 B. 3，5，12，19，20，15，22，8，28  
C．3，8，12，5，20，15，22，28，19  
 D. 3，12，5，8，28，20，15，22，19  
30、设有10000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ B ）方法可以达到此目的。
A、快速排序    B、 堆排序      C、归并排序    D、 插入排序

三、判断题
1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ √   ）
2．内排序要求数据一定要以顺序方式存储。 （  ×  ）
3．交换排序算法中的比较次数与初始元素序列的排列无关。（√）
4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（  ×  ）
5．影响外排序的时间因素主要是内存与外设交换信息的总次数。( √ )
6．简单选择排序算法的时间复杂度为O（N）。（× ）
7．中序遍历二叉排序树，可得到关键码的有序序列。（  √  ）
8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ ×   ）
9．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（  ×  ）
10. 归并排序在任何情况下都比所有简单排序速度快。（× ）
11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（   × ）
12．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ √   ）
13．堆是一个完全二叉树。（√ ）
14．（101，88，46，70，34，39，45，58，66，10）是堆。（√ ）
15．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（  × ）
16、在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。（√　）
17、在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（×  ）
18、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（  √ ）
19、冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ × ）
20、在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ ×   ）
四、问答题
1、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需多少趟？写出第一趟结束后，数组中数据的排列次序。
答：[略]
2、 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
  答：[略]
3、给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？ 
答：一趟快速排序：22,19,13,6,24,38,43,32
        初始大堆：43,38,32,22,24,6,13,19
    二路并归：第一趟：19,24,32,43,6,38,13,22
              第二趟：19,24,32,43,6,13,22,38
              第三趟：6,13,19,22,24,32,38,43
堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。
4、设待排序的关键码分别为28，13，72，85，39，41，6，20，请用快速排序方法排序，写出其排序过程。
答：[略]
5、对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）
答：[略]
6、对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。
答：125，11，22，34，15，44，76，66，100，8，14，20，2，5，1
设D=7     1，11，8，14，15，2，5，66，100，22，34，20，44，76，125
D=3        1，11，2，5，15，8，14，34，20，22，66，100，44，76，125
D=1     1，2，5，8，11，14，15，20，22，34，44，66，76，100，125
7、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。
(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。
(2) 输出最小值后，如何得到次小值。（并画出相应结果图）
答：[略]
8、有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 
初  始:25,84,21,46,13,27,68,35,20    
第一趟:20,13,21,25,46,27,68,35,84
第二趟:13,20,21,25,35,27,46,68,84   
第三趟:13,20,21,25,27,35,46,68,84  
答：该排序方法为快速排序
9、对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
答：初始序列：[28],07,39,10,65,14,61,17,50,21   21移动：21,07,39,10,65,14,61,17,50,[]
39移动：21,07,[],10,65,14,61,17,50,39     17移动：21,07,17,10,65,14,61,[],50,39
65移动：21,07,17,10,[],14,61,65,50,39     14移动：21,07,17,10,14,[28],61,65,50,39
10、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。
建立堆结构：_____________
交换与调整：
（1）87 70 26 61 45 12 3 97;（2）____________________; 
（3）61 45 26 3 12 70 87 97;（4）____________________; 
（5）26 12 3 45 61 70 87 97;（6）____________________; 
（7）3 12 26 45 61 70 87 97; 
答：建立堆结构:97,87,26,61,70,12,3,45    (2)70,61,26,3,45,12,87,97
(4)45,12,26,3,61,70,87,97            (6)12,3,26,45,61,70,87,97

四、算法设计题
1、下面是冒泡排序算法，请阅读并完成该程序，并回答以下问题：
PROCEDURE  bubblesort (r,n)
  BEGIN
    i:=1; m:=n-1; flag:=1;
    WHILE (i<=(1)___)AND(flag=(2)____) DO 
      BEGIN
         flag:= (3)___;
         FOR j:=1 TO m DO
           IF r[j].key>r[j+1].key   THEN
                BEGIN  flag:= (4)___; t:=r[j]; r[j]:=r[j+1]; r[j+1]:=t
                END;
         i:=i+1;m:=m-1
END;  
  END. 
（1） 请在上面横线上填上适当的语句，完成该算法程序。
（2） 设计标志flag的作用是什么？
（3） 该算法结点的最大比较次数和最大移动次数是多少？
（4） 该分类算法稳定吗？
答：[略]
2、有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）
 答： typedef struct node
       { ElemType data;
         struct node *prior,*next;
       }node，*DLinkedList;
void  TwoWayBubbleSort(DLinkedList la)
//对存储在带头结点的双向链表la中的元素进行双向起泡排序。
{int exchange=1;  // 设标记 
 DLinkedList p,temp,tail;
 head=la         //双向链表头，算法过程中是向下起泡的开始结点
 tail=null;      //双向链表尾，算法过程中是向上起泡的开始结点
while (exchange)
{p=head->next;    //p是工作指针，指向当前结点
exchange=0;      //假定本趟无交换 
while (p->next!=tail)  // 向下（右）起泡，一趟有一最大元素沉底
  if (p->data>p->next->data) //交换两结点指针，涉及6条链
{temp=p->next; exchange=1;//有交换
p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下
temp->next=p; p->prior->next=temp;     //将temp插到p结点前
temp->prior=p->prior; p->prior=temp;
}
          else p=p->next; //无交换，指针后移
          tail=p; //准备向上起泡
          p=tail->prior;
while (exchange && p->prior!=head) 
 //向上（左）起泡，一趟有一最小元素冒出
     if (p->data<p->prior->data)  //交换两结点指针，涉及6条链
{temp=p->prior; exchange=1;  //有交换
p->prior=temp->prior;temp->prior->next=p
；//先将temp结点从链表上摘下
temp->prior=p; p->next->prior=temp;       
 //将temp插到p结点后（右）
temp->next=p->next; p->next=temp;
}
            else p=p->prior;  //无交换，指针前移
          head=p;             //准备向下起泡
 }// while (exchange)
} //算法结束
3、对单链表中元素用插入法按从小到大排序的算法描述如下（L为链表头结点指针），请将该算法补充完整。
typedef struct node
      {int data;  struct node *next;
      }linknode,*link;
void Insertsort(link L)
    { link p,q,r,s;
      p=L->next;    L->next=null ;
      while(p!=null)
        { r=L;  q=L->next;
          while(_ q!=null  &&   （1）         ； )
 {r=q;
  （2）        ;}
          s=p->next;   （3）       _; _ （4）_____;  p=s;
         }
}
 （1）               _ （2）               _  
（3）               _ （4）                _
（1）q->data<=p->data  （2）q=q->next   （3）p->next=r->next  （4）r->next=p 
4、