文档库

最新最全的文档下载
当前位置:文档库 > 数据结构第九、十章作业题及答案

数据结构第九、十章作业题及答案

第九章 查找

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。

2. 线性有序表(a 1,a 2,a 3,…,a 256)是从小到大排列的,对一个给定的值k ,用二分法检索

表中与k 相等的元素,在查找不成功的情况下,最多需要检索 8 次。设有100个结点,用二分法查找时,最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找,则比较一次查找成功的结点数为1;比较两

次查找成功的结点数为 2 ;比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______,平均查找长度为 3.7 。

解:显然,平均查找长度=O (log 2n )<5次(25)。但具体是多少次,则不应当按照公式

)1(log 12++=n n n ASL 来计算(即(21×log 221)/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

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.在表长为n的链表中进行顺序查找,它的平均查找长度为

A. ASL=n; B. ASL=(n+1)/2;

C. ASL=n+1; D. ASL≈log

(n+1)-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. 折半搜索与二叉搜索树的时间性能

n) A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O(log

2 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(log

2n) B) O(n) C) O(nlog

2

n) 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-树的说法错误的是

数据结构第九、十章作业题及答案

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.叶结点之间通过指针链接

A、

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)进行折半查找,试回答下列问题:

(1)画出描述折半查找过程的判定树;

(2)若查找元素54,需依次与哪些元素比较?

(3)若查找元素90,需依次与哪些元素比较?

(4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。

解:

(1)先画出判定树如下(注: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表,试回答下列问题:

(1)画出哈希表的示意图;

(2)若查找关键字63,需要依次与哪些关键字进行比较?

(3)若查找关键字60,需要依次与哪些关键字比较?

(4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

解:(1)画表如下:

数据结构第九、十章作业题及答案

然后顺移,与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),处理冲突方法为线性探测再散列或链地址法,要求构造哈希表,并求出等概率情况下查找成功平均查找长度。

数据结构第九、十章作业题及答案

数据结构第九、十章作业题及答案

数据结构第九、十章作业题及答案

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

解:14 01 23 84

19 55 20 27 68

7(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec )

(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序

树,并求其在等概率的情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查

找成功的平均查找长度。 100 50 302 30 66 200 450 260

100 50 260 30 66 200 450

(3)按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找

数据结构第九、十章作业题及答案

长度。

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

succ

以关键字27为例:H(27)=27%7=6(冲突) H

1

=(6+1)%10=7(冲突)

H 2=(6+22)%10=0(冲突) H

3

=(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

succ

数据结构第九、十章作业题及答案

地址

值 链接指针 0

22 1 1

66 2

41 3 3

08 4,7 4

30 5

53 6

46 7

01 8

31 9

10

ASL unsucc =(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 1 3 4,

7

五、算法设计题

1.已知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=T->data;

if(T->rchild&&flag) Is_BSTree(T->rchild);

return flag;

}//Is_BSTree

3.已知一个含有1000个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈希表

设计方案,要求它在等概率情况下查找成功的平均查找长度不超过3。

解:设计哈希表的步骤为:

a)根据所选择的处理冲突的方法求出装载因子a的上界;

b)由a值设计哈希表的长度m;

c)根据关键字的特性和表长m选定合适的哈希函数。

刘注:要求ASL≤3,则m必然要尽量长,以减少冲突;

4.已知某哈希表的装载因子小于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插入到有序表时,为寻找插入位置至少需比较 6 次。

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.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序

( D )3.从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为

A. 希尔排序B. 归并排序C. 插入排序D. 选择排序

( B )4.对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多。

A. 从小到大排列好的B. 从大到小排列好的C. 元素无序D. 元素基本有序

( D )5.对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为A. n+1 B. n C. n-1 D. n(n-1)/2

( C )6.快速排序在下列哪种情况下最易发挥其长处。

A. 被排序的数据中含有多个相同排序码B. 被排序的数据已基本有序

C. 被排序的数据完全无序D. 被排序的数据中的最大值和最小值相差悬殊

( B )7.对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是

n) D.O(n3)

A.O(n) B.O(n2) C.O(nlog

2

( C )8.若一组记录的排序码为(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

( D )9.下列关键字序列中,是堆。

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

( B )10.堆是一种排序。

A. 插入B.选择C. 交换D. 归并

( C )11.堆的形状是一棵

A. 二叉排序树B.满二叉树C. 完全二叉树D. 平衡二叉树

( 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/2B.n/2 -1 C.1 D.n/2 +2

15、1.将5个不同的数据进行排序,至多需要比较( C )次。

A. 8 B. 9 C. 10 D. 25

16.下述几种排序方法中,要求辅助内存最多的是( C )

A. 插入排序B.快速排序C. 归并排序D. 选择排序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(log

2n) B. O(1) C. O(n) D. O(nlog

2

n)

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(nlog

2

n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( C )。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序24.在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序,k<

A.快速排序 B.直接插入排序 C. 二路归并排序 D.起泡排序

25.下面给出的四种排序方法中,排序过程中的比较次数与排序方法无关的是。( A ) A.选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序26、某内排序方法的稳定性是指(D )。

A.该排序算法不允许有相同的关键字记录

B.该排序算法允许有相同的关键字记录

C.平均时间为0(n log n)的排序方法

D.以上都不对

27、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是(D)

A:递归次数与初始数据的排列次序无关