还剩19页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第九章查找
一、填空题
1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找)
2.线性有序表(a1,a2,a3,…,a256是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索8次设有100个结点,用二分法查找时,最大比较次数是
73.假设在有序线性表a[
1..20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为2;比较四次查找成功的结点数为8其下标从小到大依次是136811131619______,平均查找长度为
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(nm)个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法如果这n个关键码的散列地址都相同,则探测的总次数是nn-1/2=(1+2+…+n-1)而任一元素查找次数≤n-
18、设一哈希表表长M为100,用除留余数法构造哈希函数,即H(K)=KMODP(P=M)为使函数具有较好性能,P应选( 97)
9、在各种查找方法中,平均查找长度与结点个数无关的是哈希查找法
10、对线性表进行二分查找时,要求线性表必须以顺序方式存储,且结点按关键字有序排列11在分块查找方法中,首先查找索引,然后再查找相应的块12.顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为_ n __次;当使用监视哨时,若查找失败,则比较关键字的次数为__n+1 13.在有序表A[
1..12]中,采用二分查找算法查等于A
[12]的元素,所比较的元素下标依次为_____691112 _____
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=+1;D.ASL≈log2(n+1)-1(A)2.折半查找有序表(4,6,10,12,20,30,50,70,88,100)若查找表中元素58,则它将依次与表中比较大小,查找结果是失败A.20,70,30,50B.30,88,70,50C.20,50D.30,88,50(C)3.对22个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字A.3B.4C.5D.6(A)
4.链表适用于查找A.顺序B.二分法C.顺序,也能二分法D.随机(C)
5.折半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量级都是O(log2n)6.散列表的地址区间为0-17散列函数为HK=Kmod17采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中元素59存放在散列表中的地址是(D)A.8B.9C.10D.
117.当采用分快查找时,数据的组织方式为BA.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C.数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D.数据分成若干块,每块(除最后一块外)中数据个数需相同
8.散列函数有一个共同的性质,即函数值应当以D取其值域的每个值A.最大概率B.最小概率C.平均概率D.同等概率
9.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?DA.k-1次B.k次C.k+1次D.k(k+1)/2次
10、哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行次探测【西安电子科技大学1998
一、8(2分)】A.kB.k+1C.kk+1/2D.1+kk+1/
211、在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A并已知A的左孩子的平衡因子为0右孩子的平衡因子为1则应作C型调整以使其平衡A.LLB.LRC.RLD.RR
12、二叉查找树的查找效率与二叉树的C有关在B)时其查找效率最低1:A.高度B.结点的多少C.树型D.结点的位置2:A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂
13、在顺序表3681012151618212530中,用折半法查找关键码值11,所需的关键码比较次数为(C)A2B3C4D
514、对包含n个元素的哈希表进行查找,平均查找长度为(D)AOlog2nBOnCOnlog2nD不直接依赖于n
15、若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为CA.n-1/2B.n/2C.n+1/2D.n
16.下面关于二分查找的叙述正确的是DA.表必须有序,表可以顺序方式存储,也可以链表方式存储C.表必须有序,而且只能从小到大排列B.表必须有序且表中数据必须是整型,实型或字符型D.表必须有序,且表只能以顺序方式存储
17.对线性表进行二分查找时,要求线性表必须(B)A.以顺序方式存储B.以顺序方式存储且数据元素有序C.以链接方式存储D.以链接方式存储且数据元素有序18.适用于折半查找的表的存储方式及元素排列要求为DA.链接方式存储,元素无序B.链接方式存储,元素有序C.顺序方式存储,元素无序D.顺序方式存储,元素有序
19.用二分(对半)查找表的元素的速度比用顺序法DA.必然快B.必然慢C.相等D.不能确定20.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度CA.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减
21.具有12个关键字的有序表,折半查找的平均查找长度(A)A.
3.1B.4C.
2.5D.
522.折半查找的时间复杂性为(D)A.O(n2)B.O(n)C.O(nlogn)D.O(logn)23.设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分块查找,则其平均查找长度为(D)A6B11C5D
6.
524.二叉排序树的查找效率与二叉树的C有关A.高度B.结点的多少C.树型D.结点的位置25.在等概率情况下一棵平衡树的ASL为BA.O1B.Olog2nC.Olog2n2D.Onlog2n26.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是CA.(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,
11027.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A并已知A的左孩子的平衡因子为0右孩子的平衡因子为1则应作C型调整以使其平衡A.LLB.LRC.RLD.RR
28、下列二叉排序树中,满足平衡二叉树定义的是(B) 29.下列关于m阶B-树的说法错误的是DA.根结点至多有m棵子树B.所有叶子都在同一层次上C.非叶结点至少有m/2m为偶数或m/2+1(m为奇数)棵子树D.根结点中的数据是有序的
30.下面关于m阶B树说法正确的是B
①每个结点至少有两棵非空子树;
②树中每个结点至多有m一1个关键字;
③所有叶子在同一层上;
④当插入一个数据项引起B树结点分裂后,树长高一层A.
①②③B.
②③C.
②③④D.
③
31.下面关于B和B+树的叙述中,不正确的是CA.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索
32、下列叙述中,不符合m阶B树定义要求的是(D) A.根节点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接
33、设散列表中有m个存储单元,散列函数Hkey=key%p,则p最好选择(B)A小于等于m的最大奇数B小于等于m的最大素数C小于等于m的最大偶数D小于等于m的最大合数
34、适于对动态查找表进行高效率查找的组织结构是(C)A.有序表B.分块有序表C.二叉排序树D.线性链表
35、当采用分快查找时,数据的组织方式为BA.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C.数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D.数据分成若干块,每块(除最后一块外)中数据个数需相同
三、判断题
1、查找相同结点的效率折半查找总比顺序查找高×
2、索引顺序表的特点是块内可无序,块间要有序(√)
3、 在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻r
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)305633742874245472952查找元素54,需依次与30634254等元素比较;3查找元素90,需依次与3063879572等元素比较;
(4)求ASL之前,需要统计每个元素的查找次数判定树的前3层共查找1+2×2+4×3=17次;但最后一层未满,不能用8×4,只能用5×4=20次,所以ASL=1/12(17+20)=37/12≈
3.
083.设哈希(Hash)表的地址范围为0~17,哈希函数为H(K)=KMOD16K为关键字,用线性探测法再散列法处理冲突,输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)造出Hash表,试回答下列问题
(1)画出哈希表的示意图;
(2)若查找关键字63,需要依次与哪些关键字进行比较?
(3)若查找关键字60,需要依次与哪些关键字比较?
(4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度解
(1)画表如下012345678910111213141516173217634924401030314647
(2)查找63首先要与H63=63%16=15号单元内容比较,即63vs31no;然后顺移,与4647321763相比,一共比较了6次!
(3)查找60首先要与H60=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.
554、设哈希表长度为11,哈希函数H(K)=(K的第一字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),处理冲突方法为线性探测再散列或链地址法,要求构造哈希表,并求出等概率情况下查找成功平均查找长度012345678910KTABAMDCIX TNIASL=20/9 012345678910 ASL=15/
95、输入一个正整数序列{100,50,302,450,66,200,30,260},建立一棵二叉排序树,要求⑴画出该二叉排序树;⑵画出删除结点302后的二叉排序树解
6、设有一组关键字{19,01,23,14,55,20,84,27,68},采用哈希函数H(key)=keymod7,采用开放地址法的线性探测再散列方法解决冲突要求在0∽11的散列地址空间中对该关键字序列构造哈希表01234567891011解
012345678910111401238419552027687、已知如下所示长度为12的表(JanFebMarAprMayJuneJulyAugSepOctNovDec)1试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度2若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度3按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度
8、用开放地址法的二次探测再散列方法Hi=Hkey+dimod10di=122232…解决冲突要求对该关键字序列构造哈希表,并计算查找成功的平均查找长度解散列地址0123456789关键字140192384275520 比较次数1112 3 412 平均查找长度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)=3Kmod11,散列地址空间为0~10,对关键字序列
(321349243821412)按下述两种解决冲突的方法构造哈希表
(1)线性探测再散列
(2)链地址法,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc解1)散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc=(1+1+1+2+1+2+1+2)/8=11/8ASLunsucc=(1+2+1+8+7+6+5+4+3+2+1)/11=40/
119、选取散列函数H(key)=(3*key)%11,用线性探测法处理冲突,对下列关键码序列构造一个散列地址空间为0~10,表长为11的散列表,{22,41,53,08,46,30,01,31,66}解由题意知,m=11刚好为素数则22*3%11=6……041*3%11=11……253*3%11=14……508*3%11=2……246*3%11=12……630*3%11=8……201*3%11=0……331*3%11=8……566*3%11=9……02266418305346131012345678910134,7
五、算法设计题
1.已知11个元素的有序表为
(0513192137566475808892)请写出折半查找的算法程序,查找关键字为key的数据元素建议上机调试解折半查找的C程序有很多参考资料,注意此题要求是整型量折半查找的一个递归算法如下,形式非常简洁!intSearch_Bin_RecursiveSSTableSTintkeyintlowinthigh//折半查找的递归算法{iflowhighreturn0;//查找不到时返回0mid=low+high/2;ifST.elem[mid].key==keyreturnmid;elseifST.elem[mid].keykeyreturnSearch_Bin_RecursiveSTkeylowmid-1;elsereturnSearch_Bin_RecursiveSTkeymid+1high;}}//Search_Bin_Recursive
2.试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构且树中结点的关键字均不同解注意仔细研究二叉排序树的定义易犯的典型错误是按下述思路进行判别“若一棵非空的二叉树其左、右子树均为二叉排序树,且左子树的根的值小于根结点的值,又根结点的值不大于右子树的根的值,则是二叉排序树”(刘注即不能只判断左右孩子的情况,还要判断左右孩子与双亲甚至根结点的比值也要遵循(左小右大)原则)若要采用递归算法,建议您采用如下的函数首部boolBisortTreeBiTreeTBiTreePRE,其中PRE为指向当前访问结点的前驱的指针(或者直接存储前驱的数值,随时与当前根结点比较)一个漂亮的算法设计如下intlast=0flag=1;//last是全局变量,用来记录前驱结点值,只要每个结点都比前驱大就行intIs_BSTreeBitreeT//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ifT-lchildflagIs_BSTreeT-lchild;ifT-datalastflag=0;//与其中序前驱相比较flag=0表示当前结点比直接前驱小,则立即返回last=T-data;ifT-rchildflagIs_BSTreeT-rchild;returnflag;}//Is_BSTree
3.已知一个含有1000个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈希表设计方案,要求它在等概率情况下查找成功的平均查找长度不超过3解设计哈希表的步骤为a根据所选择的处理冲突的方法求出装载因子a的上界;b由a值设计哈希表的长度m;c根据关键字的特性和表长m选定合适的哈希函数刘注要求ASL≤3,则m必然要尽量长,以减少冲突;
4.已知某哈希表的装载因子小于1,哈希函数Hkey为关键字(标识符)的第一个字母在字母表中的序号,处理冲突的方法为线性探测开放定址法试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法解注意此题给出的条件装载因子a〈1则哈希表未填满由此可写出下列形式简明的算法voidPrintWordHashTableht{//按第一个字母的顺序输出哈希表ht中的标识符哈希函数为表示符的第一个字母在字母表中的序号,处理冲突的方法是线性探测开放定址法fori=1;i=26;i++{j=i;Whileht.elem[j].key{ifHashht.elem[j].key==iprintfht.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个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是On2若对其进行快速排序,在最坏的情况下所需要的时间是On
26.对于n个记录的集合进行归并排序,所需要的平均时间是Onlog2n,所需要的附加空间是On7.对于n个记录的表进行2路归并排序,整个归并排序需进行┌log2n┐趟(遍)
8.设要将序列(QHCYPAMSRDFX)中的关键码按字母序的升序重新排列,则冒泡排序一趟扫描的结果是HCQPAMSRDFXY;初始步长为4的希尔(shell)排序一趟的结果是PACSQHFXRDMY;归并排序一趟扫描的结果是HQCYAPMSDRFX;快速排序一趟扫描的结果是FHCDPAMQRSYX;堆排序初始建堆的结果是ADCRFQMSYPHX
9.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是冒泡算法,最费时间的是快速算法
10、对n个记录的表r[
1..n]进行简单选择排序,所需进行的关键字间的比较次数为___nn-1/2____
二、单项选择题(每小题1分,共18分)
1、下列四个序列中,( C )是堆A.7565301525452010 B.7565451030252015C.7545653015252010 D.7545651025302015(C)2.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为A.希尔排序B.冒泡排序C.插入排序D.选择排序(D)3.从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方法,称为A.希尔排序B.归并排序C.插入排序D.选择排序(B)4.对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序(D)5.对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为A.n+1B.nC.n-1D.nn-1/2(C)6.快速排序在下列哪种情况下最易发挥其长处A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊(B)7.对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是A.OnB.On2C.Onlog2nD.On3(C)8.若一组记录的排序码为
(467956384084),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为A.384046567984B.403846795684C.4038,46567984D.403846845679(D)9.下列关键字序列中,是堆A.167231239453B.942331721653C.16532394,3172D.162353319472(B)10.堆是一种排序A.插入B.选择C.交换D.归并(C)11.堆的形状是一棵A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树(B)12.若一组记录的排序码为
(467956384084),则利用堆排序的方法建立的初始堆为
12、对序列{15,9,7,8,20,-1,4,}用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是 B A.l B.4 C.3 D.
213、快速排序方法在( 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)次A.8B.9C.10D.2516.下述几种排序方法中,要求辅助内存最多的是(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.Olog2nB.O1 C.On D.Onlog2n
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.若需在Onlog2n的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( C ) A.快速排序 B.堆排序 C.归并排序 D.直接插入排序24.在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序,kn)的情况下,排序效率最高的算法是( B )A.快速排序 B.直接插入排序 C.二路归并排序 D.起泡排序 25.下面给出的四种排序方法中,排序过程中的比较次数与排序方法无关的是 A A.选择排序法 B.插入排序法 C.快速排序法 D.堆排序
26、某内排序方法的稳定性是指D A.该排序算法不允许有相同的关键字记录 B.该排序算法允许有相同的关键字记录C.平均时间为0(nlogn)的排序方法 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.在初始数据表已经有序时,快速排序算法的时间复杂度为Onlog2n( × )9.当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省( × )
10.归并排序在任何情况下都比所有简单排序速度快(×)11.快速排序的速度在所有排序方法中为最快而且所需附加空间也最少( ×)12.在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”( √ )13.堆是一个完全二叉树(√ )14.(101,88,46,70,34,39,45,58,66,10)是堆(√)15.快速排序和归并排序在最坏情况下的比较次数都是Onlog2n( ×)
16、在待排序的记录集中,存在多个具有相同键值的记录,若经过排序,这些记录的相对次序仍然保持不变,称这种排序为稳定排序(√ )
17、在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的(× )
18、当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是影响时间复杂度的主要因素( √)
19、冒泡排序算法关键字比较的次数与记录的初始排列次序无关(×)
20、在初始数据表已经有序时,快速排序算法的时间复杂度为Onlog2n( × )
四、问答题
1、设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称增量序列)依次是4,2,1则排序需多少趟?写出第一趟结束后,数组中数据的排列次序答[略]
2、在各种排序方法中,哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一个不稳定的实例答[略]
3、给定一个关键字序列{24,19,32,43,38,6,13,22},请写出快速排序第一趟的结果;堆排序时所建的初始堆;归并排序的全过程然后回答上述三中排序方法中那一种方法使用的辅助空间最少?在最坏情况下那种方法的时间复杂度最差? 答一趟快速排序221913624384332 初始大堆433832222461319 二路并归第一趟192432436381322 第二趟192432436132238 第三趟613192224323843堆排序辅助空间最少,最坏情况下快速排序时间复杂度最差
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,125D=3 1,11,2,5,15,8,14,34,20,22,66,100,44,76,125D=1 1,2,5,8,11,14,15,20,22,34,44,66,76,100,
1257、已知待排序的序列为(503,87,512,61,908,170,897,275,653,462),试完成下列各题1根据以上序列建立一个堆(画出第一步和最后堆的结果图),希望先输出最小值2输出最小值后,如何得到次小值(并画出相应结果图)答[略]
8、有一随机数组258421461327683520现采用某种方法对它们进行排序其每趟排序结果如下则该排序方法是什么初 始:258421461327683520 第一趟:201321254627683584第二趟:132021253527466884 第三趟:132021252735466884 答该排序方法为快速排序
9、对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分,写出其快速排序第一遍的排序过程答初始序列
[28]073910651461175021 21移动210739106514611750[]39移动2107[]10651461175039 17移动21071710651461[]503965移动21071710[]1461655039 14移动2107171014
[28]
6165503910、已知一关键码序列为3,87,12,61,70,97,26,45试根据堆排序原理,填写完整下示各步骤结果建立堆结构_____________交换与调整
(1)877026614512397;
(2)____________________;
(3)614526312708797;
(4)____________________;
(5)261234561708797;
(6)____________________;
(7)312264561708797;答建立堆结构:978726617012345 27061263451287974451226361708797 6123264561708797
四、算法设计题
1、下面是冒泡排序算法,请阅读并完成该程序,并回答以下问题PROCEDUREbubblesortrnBEGINi:=1;m:=n-1;flag:=1;WHILEi=1___ANDflag=2____DOBEGINflag:=3___;FORj:=1TOmDOIFr[j].keyr[j+1].keyTHENBEGINflag:=4___;t:=r[j];r[j]:=r[j+1];r[j+1]:=tEND;i:=i+1;m:=m-1END;END.
(1)请在上面横线上填上适当的语句,完成该算法程序
(2)设计标志flag的作用是什么?
(3)该算法结点的最大比较次数和最大移动次数是多少?
(4)该分类算法稳定吗?答[略]
2、有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法(注双向起泡排序即相邻两趟排序向相反方向起泡) 答 typedefstructnode {ElemTypedata; structnode*prior*next; }node,*DLinkedList;void TwoWayBubbleSortDLinkedListla//对存储在带头结点的双向链表la中的元素进行双向起泡排序{intexchange=1; //设标记 DLinkedListptemptail; head=la //双向链表头,算法过程中是向下起泡的开始结点 tail=null; //双向链表尾,算法过程中是向上起泡的开始结点whileexchange{p=head-next; //p是工作指针,指向当前结点exchange=0; //假定本趟无交换whilep-next!=tail //向下(右)起泡,一趟有一最大元素沉底 ifp-datap-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;} elsep=p-next;//无交换,指针后移 tail=p;//准备向上起泡 p=tail-prior;whileexchangep-prior!=head //向上(左)起泡,一趟有一最小元素冒出 ifp-datap-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;} elsep=p-prior; //无交换,指针前移 head=p; //准备向下起泡 }//whileexchange}//算法结束
3、对单链表中元素用插入法按从小到大排序的算法描述如下(L为链表头结点指针),请将该算法补充完整typedefstructnode {intdata; structnode*next; }linknode*link;voidInsertsortlinkL {linkpqrs; p=L-next; L-next=null ; whilep!=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、C、D、B、A、100503023066200450260100502603066200450地址值链接指针0221166241330847430553646701831910。