大二数据结构复习-查找排序练习题
- 格式:doc
- 大小:64.00 KB
- 文档页数:4
第九章查找一、选择题1•若查找每个记录的概率均等,则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL 为()。
A .(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序,表可以顺序方式存储,也可以链表方式存储C.表必须有序,而且只能从小到大排列B. 表必须有序且表中数据必须是整型,实型或字符型D.表必须有序,且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表,折半查找的平均查找长度()A.3.1B.4C.2.5D.55.当采用分块查找时,数据的组织方式为()A. 数据分成若干块,每块内数据有序B. 数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D. 数据分成若干块,每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) :A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。
7. 对大小均为n 的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是()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)10. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。
资料范本本资料为word版本,可以直接编辑和打印,感谢您的下载数据结构第九章排序习题及答案地点:__________________时间:__________________说明:本资料适用于约定双方经过谈判,协商而共同承认,共同遵守的责任与义务,仅供参考,文档可直接下载或修改,不需要的部分可直接删除,使用时请详细阅读内容习题九排序一、单项选择题1.下列内部排序算法中:A.快速排序 B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序(1)其比较次数与序列初态无关的算法是()(2)不稳定的排序算法是()(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序,k<<n)的情况下,排序效率最高的算法是()(4)排序的平均时间复杂度为O(n•logn)的算法是()为O(n•n)的算法是()2.比较次数与排序的初始状态无关的排序方法是( )。
A.直接插入排序 B.起泡排序 C.快速排序 D.简单选择排序3.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序的过程中的变化为(1) 84 47 25 15 21 (2) 15 47 25 84 21(3) 15 21 25 84 47 (4) 15 21 25 47 84则采用的排序是 ( )。
A. 选择B. 冒泡C. 快速D. 插入4.下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择B. 冒泡C. 归并D. 堆5.一组记录的关键码为(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)6.下列排序算法中,在待排序数据已有序时,花费时间反而最多的是( )排序。
一、单选题1.下列查找方法中,不属于动态的查找方法是( )。
A .二叉排序树法B .平衡树法C .散列法D .二分查找法2.适用于静态的查找方法为( )。
A .二分查找、二叉排序树查找B .二分查找、索引顺序表查找C .二叉排序树查找、索引顺序表查找D .二叉排序树查找、散列法查找3.静态查找表与动态查找表二者的根本差别在于( )。
A .它们的逻辑结构不一样B .施加在其上的操作不同C .所包含的数据元素的类型不一样D .存储实现不一样4.对长度为10的顺序表进行查找,若查找前面5个元素的概率相同,均为1/8,查找后面5个元素的概率相同,均为3/40,则查找任一元素的平均查找长度为( )。
A .5.5B .5C .39/8D .19/45.( )存储方式适用于折半查找。
A .键值有序的单链表B .键值有序的顺序表C .键值有序的双链表D .键值无序的顺序表6.对线性表进行二分查找时,要求线性表必须( )。
A .以顺序方式存储B .以链接方式存储C .顺序存储,且结点按关键字有序排序D .链式存储,且结点按关键字有序排序7.在索引顺序表中查找一个元素,可用的且最快的方法是( )。
A .用顺序查找法确定元素所在块,再用顺序查找法在相应块中查找B .用顺序查找法确定元素所在块,再用二分查找法在相应块中查找C .用二分查找法确定元素所在块,再用顺序查找法在相应块中查找D .用二分查找法确定元素所在块,再用二分查找法在相应块中查找8.在索引查找中,若主表长度为144,它被均分为12子表,每个子表的长度均为12,则索引查找的平均查找长度为( )。
A .13B .24C .12D .799.由同一关键字集合构造的各棵二叉排序树( )。
A .形态和平均查找长度都不一定相同B .形态不一定相同,但平均查找长度相同C .形态和平均查找长度都相同D .形态相同,但平均查找长度不一定相同10.对二叉排序树进行( ),可以得到各结点键值的递增序列。
1、静态查找表和动态查找表的区别是( )。
A.所包含的数据元素的类型不同B.施加其上的操作不同C.它们的逻辑结构相同D.以上都不对正确答案:B解析:B、若在查找的同时对表做修改操作(如插入和删除),则相应的查找表称之为动态查找表。
若在查找中不涉及表的修改操作,则相应的查找表称之为静态查找表。
2、顺序查找法适合于存储结构为( )的线性表。
A.索引存储B.压缩存储C.顺序存储或者链式存储D.哈希存储正确答案:C解析:C、顺序查找可以从前向后或者从后向前挨次查找,既适合于顺序存储结构也适合于链式存储结构。
3、采用顺序查找方法查找长度为n 的顺序表时,在等概率时成功查找的平均查找长度为( )。
A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案:D解析:D、顺序查找时,元素ai 需i 次比较,成功查找的平均查找长度=(1+2+ …+n)/n=(n+1)/2。
4、采用顺序查找方法查找长度为n 的顺序表时,在等概率时不成功查找的平均查找长度为( )。
A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案:B解析:B、当查找的元素不在线性表中时,均需要n 次元素之间的比较。
5、适合于折半查找的数据组织方式是( )。
A.以链表存储的有序线性表B.以顺序表存储的有序线性表C.以链表存储的线性表D.以顺序表存储的线性表正确答案:B解析:B、折半查找的数据必须是有序的。
此外,折半查找中需要确定查找区间,这要求存储结构最好具有随机存取特性,而顺序表满足这个特性。
6、采用折半查找方法查找长度为n 的线性表,当n 很大时,在等概率时不成功查找的平均查找长度为( )。
n)A. O(nlog2B. O(n2)C. O(n)n)D. O(log2正确答案:D解析:D、采用折半查找时,若n 很大,对应的判定树可以看成是一棵满二叉树,失败节点(外部节点)集中在最下一层,落在每一个失败节点时比较的次都均为log n。
27、设有100 个元素的有序表,采用折半查找方法,在等概率时成功时最大的比较次数是( )。
数据结构查找排序经典试题一、填空1、针对有n条记录的顺序表做顺序查找,假定各记录的查找机会均等,则平均查找长度ASL=_______。
2、在二叉平衡树中,平衡因子hl-hr的所有可能取值有____________。
3、在排序操作中,待排序的记录有n条,若采用直接插入排序法,则需进行_________趟的插入才能完成排序。
4、在排序操作中,待排序的记录有n条,若采用冒泡排序法,则至多需进行_________趟的排序。
5、直接插入排序算法的时间复杂度为________________。
6、按()遍历二叉排序树,可以得到按值递增的关键字序列,在下图所示的二叉排序树中,查找关键字85的过程中,需和85进行比较的关键字序列为()。
509520557010 30 85二、判断1、平衡二叉树中子树的深度不能大于1。
()2、快速排序法是稳定的排序方法。
()3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地方。
()4、冒泡排序法是稳定的排序方法。
()5、折半插入排序法是稳定的排序方法。
()三、选择1、在排序操作中,待排序的记录有n条,若采用直接插入排序法,则需进行_________趟的插入才能完成排序。
A、nB、(n-1)/2C、n+1D、n-12、采用顺序查找法查找长度为n的线性表时,平均查找长度为()A、nB、(n-1)/2C、n/2D、(n+1)/23、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行()次比较。
A、1B、2C、3D、44、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用折半查找法查找12需做()次比较。
A、5B、4C、3D、25、如果待排序序列中两个数据元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。
()就是不稳定的排序方法。
A、起泡排序B、归并排序C、直接插入排序D、简单选择排序四、综合题1、给定一组数{6,7,9,4,3,5,8},要求(a)构造一棵平衡的二叉排序树;(b)先根遍历该树;(c)从该树中删除结点6,并保持其特性。
查找与排序部分习题一、选择题1.设有100个元素,用折半查找法进行查找时,最大比较次数是______。
A、25 B、8 C、10 D、72.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值82的结点时,______次比较后查找成功。
(注:计算中间位置时取下整)A、1B、2C、4D、83.顺序查找法适合于存储结构为______的线性表。
A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储4.某顺序存储的表格中有90000个元素,以按关键字值升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字的值皆不相同,用顺序查找法查找时,平均比较次数约为______;最大比较次数约为______。
A、25000B、30000C、45000D、900005.设散列地址空间为0到m-1,k为关键字,用p去除k,将所得的余数作为k的散列地址,即H(k)=k%p。
为了减少发生冲突的频率,一般取p为______。
A、小于m的最大奇数B、小于m的最大偶数C、小于m的最大素数D、大于m的最大素数6.设有9个数据记录组成的线性表,它们的排序关键字的取值分别是(11,15,20,27,30,35,46,88,120),已将它们按照排序关键字递增有序的方式存放在一维结构数组a[0..8]中从下标0开始到下标8结束的位置,则当采用折半查找算法查找关键字值等于20的数据记录时,所需比较的元素下标依次是:______。
(注:计算中间位置时取下整)A、0,1,2B、4,1,2C、4,2D、4,3,27.顺序查找一个共有n个元素的线性表,其时间复杂度为______。
A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)8.设有100个元素,用折半查找法进行查找时,最小比较次数是______。
A、7B、4C、2D、19.哈希法中,除了考虑构造“均匀”的哈希函数外,还要解决冲突的问题,以下选项中______不是解决冲突的办法。
第九章查找一、选择题1.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( )A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法( )A.必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表,折半查找的平均查找长度()A. 3.1B. 4C. 2.5D. 55.当采用分块查找时,数据的组织方式为 ( )A.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D. 数据分成若干块,每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:A. 相同的B.不同的9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ) 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)10. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法,它通过重复地交换相邻两个元素的位置来实现排序。
算法的基本思想是从待排序的元素中比较相邻的两个元素大小,并根据需要交换它们的位置,直到整个序列有序为止。
冒泡排序的原理如下:首先从序列的第一个元素开始,比较相邻的两个元素的大小,若前面的元素大于后面的元素,则交换它们的位置;否则,继续比较下一对相邻元素,直到比较到序列的最后一个元素。
这样一趟比较下来,序列中最大的元素就会被交换到最后一个位置。
接着,对序列中剩下的 n-1 个元素重复上述过程,执行 n-1 趟比较,直到整个序列有序。
在实践中,冒泡排序的时间复杂度为 O(n^2),其中 n 为待排序序列的长度。
尽管冒泡排序存在其它更好的排序算法,但它具有编码简单、实现容易以及对小规模数据排序的优势。
二、选择排序选择排序也是一种简单直观的排序算法,它的思想是将待排序序列分为已排好序的部分和未排序的部分,每次选取未排序部分中最小(或最大)的元素,将其放置在已排好序的部分的末尾。
重复此过程,直到整个序列有序。
选择排序的具体步骤如下:首先从待排序序列中找到最小(或最大)的元素,然后将其与序列的第一个元素交换位置,将该元素视为已排序部分;接着,在剩下的未排序部分中找到最小(或最大)的元素,将其与第二个元素交换位置,将该元素视为已排序部分的最后一个元素;以此类推,每次选择序列中最小(或最大)的元素,并将该元素放置在已排序部分的末尾。
最终完成排序。
选择排序的时间复杂度同样为 O(n^2),其中 n 为待排序序列的长度。
相比于冒泡排序,选择排序的交换操作较少,因此在实际应用中,选择排序的性能要优于冒泡排序。
三、插入排序插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素逐个插入已排好序的部分中,直到整个序列有序。
与冒泡排序和选择排序不同,插入排序是一种原地排序算法。
第9章查找一、单选题1.对一棵二叉搜索树按〔〕遍历,可得到结点值从小到大的排列序列。
A. 先序B. 中序C. 后序D. 层次2.从具有n个结点的二叉搜索树中查找一个元素时,在平均情况下的时间复杂度大致为〔〕。
A. O(n)B. O(1)C. O(logn)D. O(n2)3.从具有n个结点的二叉搜索树中查找一个元素时,在最坏情况下的时间复杂度为〔〕。
A. O(n)B. O(1)C. O(logn)D. O(n2)4.在二叉搜索树中插入一个结点的时间复杂度为〔〕。
A. O(1)B. O(n)C. O(logn)D. O(n2)5.分别以下列序列构造二叉搜索树,与用其它三个序列所构造的结果不同的是〔〕。
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〕6.在一棵AVL树中,每个结点的平衡因子的取值X围是〔〕。
A. -1~1B. -2~2C. 1~2D. 0~17.根据一组关键字〔56,42,50,64,48〕依次插入结点生成一棵A VL树,当插入到值为〔〕的结点时需要进行旋转调整。
A. 42B. 50C. 64D. 488.深度为4的A VL树至少有〔〕个结点。
A.9 B.8C.7D.69.一棵深度为k的A VL树,其每个分支结点的平衡因子均为0,则该平衡二叉树共有〔〕个结点。
A.2k-1-1B.2k-1+1C.2k-1D.2k10.在A VL树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作〔〕型调整以使其平衡。
A. LLB. LRC. RLD. RR二、判断题1.二叉搜索树的任意一棵子树中,关键字最小的结点必无左孩子,关键字最大的结点必无右孩子。
2.二叉搜索树中每个结点的关键字值大于其左非空子树〔若存在的话〕所有结点的关键字值,且小于其右非空子树〔若存在的话〕所有结点的关键字值。
数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( ) A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A.链接方式存储,元素无序 B.链接方式存储,元素有序C.顺序方式存储,元素无序D.顺序方式存储,元素有序3.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为()。
A.35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为()A. O(n2)B. O(n)C. O(nlogn)D. O(logn)6.对有18个元素的有序表作折半查找,则查找A[3]的比较序列的下标为()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,37.设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法查找健值为84的结点时,经()次比较后查找成功。
A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树,最低高度为()A.n/2B.、nC.lognD.logn+19.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ) 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)10.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key% 13,散列地址为1的链中有()个记录。
数据结构查找与排序练习题一、选择题1.对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( ) A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A.链接方式存储,元素无序 B.链接方式存储,元素有序C.顺序方式存储,元素无序 D.顺序方式存储,元素有序3.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为()。
A.35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为()A. O(n2)B. O(n)C. O(nlogn)D. O(logn)6.对有18个元素的有序表作折半查找,则查找A[3]的比较序列的下标为()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,37.设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法查找健值为84的结点时,经()次比较后查找成功。
A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树,最低高度为()A.n/2B.、nC.lognD.logn+19.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ) 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)10.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key% 13,散列地址为1的链中有()个记录。
A.1 B. 2 C. 3 D. 411.已知一采用开放地址法解决Hash表冲突,要从此Hash表中删除出一个记录,正确的做法是()A.将该元素所在的存储单元清空。
B.将该元素用一个特殊的元素代替C.将与该元素有相同Hash地址的后继元素顺次前移一个位置。
D.用与该元素有相同Hash地址的最后插入表中的元素替代。
12.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( )A.k-1次 B. k次C. k+1次D. k(k+1)/2次13.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。
采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。
(1)元素59存放在散列表中的地址是()。
A. 8 B. 9 C. 10 D. 11(2)存放元素59需要搜索的次数是()。
A. 2 B. 3 C. 4 D. 514.将10个元素散列到100000个单元的哈希表中,则()产生冲突。
A. 一定会B. 一定不会C. 仍可能会15.对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)=K %7作为散列函数,则散列地址为0的元素有()个。
A.1B.2C.3D.416.下列排序方法中,哪一个是稳定的排序方法?()A.直接选择排序 B.直接插入排序 C.希尔排序 D.快速排序17.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()。
A.直接插入排序B.气泡排序C. 快速排序D.直接选择排序18.比较次数与排序的初始状态无关的排序方法是( )。
A.直接插入排序B.起泡排序C.快速排序D.简单选择排序19.对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{4,9,-1,8,20,7,15};则采用的是()排序。
A.选择B.快速C.希尔D.冒泡20.一组记录的关键码为(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)21.就平均性能而言,目前最好的内排序方法是( )排序法。
A.冒泡B.希尔插入C.交换D.快速22.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为( )排序法。
A.插入B.选择C.希尔D.快速23.用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是()。
A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,4024.直接插入排序在最好情况下的时间复杂度为()A.O(logn)B.O(n)C.O(n*logn)D.O(n2)25.对序列{15,9,7,8,20,-1,4,} 用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是 ( )A.lB.4C.3D.226.对下列关键字序列用快速排序法进行排序时,速度最快的情形是()。
A.{21,25,5,17,9,23,30}B.{25,23,30,17,21,5,9}C.{21,9,17,30,25,23,5} D.{5,9,17,21,23,25,30}27.快速排序方法在()情况下最不利于发挥其长处。
A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序28.对n个记录进行希尔排序,所需要的辅助存储空间为()。
A.O(1og2n)B.O(n)C.O(1)D.O(n2)29.下列四个序列中,哪一个是堆()。
A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1530.就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是()A.堆排序〈快速排序〈归并排序B.堆排序〈归并排序〈快速排序C.堆排序〉归并排序〉快速排序D.堆排序 > 快速排序>归并排序E.以上答案都不对二、判断题1.查找相同结点的效率折半查找总比顺序查找高。
2.对无序表用二分法查找比顺序查找快。
3.对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的。
4.二叉排序树或者是一棵空树;或者是具有如下特性的二叉树:(1)若它的左子树不空,则左子树上所有结点的值均小于根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于根结点的值。
5.在查找树(二叉树排序树)中插入一个新结点,总是插入到叶结点下面。
6.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
7.二叉树中除叶结点外, 任一结点X,其左子树根结点的值小于该结点(X)的值;其右子树根结点的值≥该结点(X)的值,则此二叉树一定是二叉排序树。
8.在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。
9.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。
10.在散列检索中,“比较”操作一般也是不可避免的。
11.散列函数越复杂越好,因为这样随机性好,冲突概率小.12.Hash表的平均查找长度与处理冲突的方法无关。
13.负载因子 (装填因子)是散列表的一个重要参数,它反映散列表的装满程度。
14.若散列表的负载因子α<1,则可避免碰撞的产生。
15.哈希表的平均查找长度不为0,是因为哈希函数在绝大多数情况下是多对一的映射,即存在冲突。
16.可以创建一种查找表,其在十亿个元素中查找与在10个元素中查找所用的时间差不多。
17.当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是影响时间复杂度的主要因素。
18.内排序要求数据一定要以顺序方式存储。
19.排序算法中的比较次数与初始元素序列的排列无关。
20.排序的稳定性是指排序算法中的比较次数保持不变,且算法能够终止。
21.在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的。
22.直接选择排序算法在最好情况下的时间复杂度为O(N)。
23.在初始数据表已经有序时,快速排序算法的时间复杂度为O(nlog2n )。
24.当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省25.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
26.堆是满二叉树。
27.在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”。
28.堆排序是稳定的排序方法。
29.归并排序辅助存储为O(1)。
30.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。
31.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。
32.归并排序在任何情况下都比所有简单排序速度快。
33.快速排序总比简单排序快。
三、填空题1.顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为__ __次。
2.在有序表A[1..20]中,按二分查找方法进行查找,查找长度为5的元素个数是__ _3.在有序表A[1…20]中,按二分查找方法进行查找,查找长度为4的元素的下标从小到大依次是 ______。
4.有序表(12,18,24,35,47,50,62,83,90,115,134)使用二分法查找90时,需____ ___次查找成功,查100时,需____ _____次才能确定不成功。
5.平衡因子的定义是__________6.高度为8的平衡二叉树的结点数至少有___ ___个。
7. 动态查找表和静态查找表的重要区别在于前者包含有__ __和__ __运算,而后者不包含这两种运算。
四、应用题1.假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:(1).画出描述折半查找过程的判定树;(2).若查找元素54,需依次与那些元素比较?(3).若查找元素90,需依次与那些元素比较?(4).假定每个元素的查找概率相等,求查找成功时的平均查找长度。