还剩6页未读,继续阅读
文本内容:
第章查找8选择题
8.1顺序查找法适合于存储结构为()的线性表
1.A)散列存储B)顺序存储或者链接存储C)压缩存储D)索引存储下面哪些操作不属于静态查找表()
2.)查询某个特定元素是否在表中)检索某个特定元素的属性A B)插入一个数据元素)建立一个查找表C D下面描述不正确的是()
3.)顺序查找对表中元素存放位置无任何要求,当较大时,效率低A n)静态查找表中关键字有序时,可用二分查找B)分块查找也是一种静态查找表C)时常进行插入和删除操作时可以采用二分查找D.散列查找时,解决冲突的方法有()4)除留余数法)数字分析法)直接定址法)链地址法A BC D若表中的记录顺序存放在一个一维数组中,在等概率情况下顺序查找的平均查找长度为()
5.)())())())()A01B O log n C0n D0M2对长度为的顺序表进行查找,若第一个元素的概率为第二个元素的概率为第三个元素的概率为
6.41/8,1/4,3/8,第四个元素的概率为则查找任一个元素的平均查找长度为()1/4,))))A11/8B7/4C9/4D11/4静态查找表与动态查找表二者的根本差别在于()
7.)它们的逻辑结构不一样)施加在其上的操作不同A B)所包含的数据元素的类型不一样)存储实现不一样C D若查找表中的记录按关键字的大小顺序存放在一个一维数组中,在等概率情况下二分法查找的平均检索长度
8.是())())())())((产)A0n BO log n C O nlog n D Olog2n22对有个数据元素的有序表(假设下标从开始)进行二分查找,搜索到的关键码等于给定值,
9.14R
[14]1R
[4]此时元素比较顺序挨次为()))A R
[1],R
[2],R
[3],R
[4]B R
[1],R
[13],R
[2],R
[3]))C R
[7],R
[3],R
[5],R
[4]D R
[7],R
[4],R
[2],R
[3]设有一个长度为的已排好序的表,用二分查找进行查找,若查找不成功,至少比较()次
10.100))))A9B8C7D6请指出在顺序表{}中,用二分法查找关键码需做()次关键码比较
11.2,5,7,10,14,15,18,23,35,41,5212))))A2B3C4D5从具有个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为()
12.n)())())())()A0n BO1COlog nDO n22分块查找时确定块的查找可以用顺序查找,也可以用(),而在块中只能是()
13.)静态查找,顺序查找)二分查找,顺序查找A B)二分查找,二分查找)散列查找,顺序查找C D采用分块查找时,若线性表中共有个元素,查找每一个元素的概率相同,假设采用顺序查找来确定结
14.625点所在的块时,每块应分()个结点最佳))))A10B25C6D625采用分块查找法(块长为以二分查找确定块)查找长度为的线性表时,每一个元素的平均查找长度为
15.s,n())))())()A s+n Blogn+s/2C logn/s+1+s/2D n+s/222对一棵二叉排序树根结点而言,左子树中所有结点与右子树中所有结点的关键字大小关系是()
16.)小于)大于)等于)不小于A BC D若二叉排序树中关键字互不相同,则下面命题中不正确的是()
17.)最小元和最大元一定是叶子)最大元必无右孩子A B)最小元必无左孩子)新结点总是作为叶结点插入二叉排序树C D设二叉排序树中关键字由至的整数构成,现要查找关键字为的结点,下述关键字序列()不可
18.11000363能是在二叉排序树上查找到的序列?)A2,252,401,398,330,344,397,363)B924,220,911,244,898,258,362,363)C2,399,387,219,266,382,381,278,363)在初始为空的散列表中挨次插入关键字序列(丁火皿£口,用D925,202,911,240,912,245,
36319.1\/101\1,下卬$人丁$)散列函数为()113,H k=i其中,为关键字的第一个字母在英文字母表中的序号,地址值域为[],采用线性再散列法MOD7,i k0:6A012346THU TUEWED FRISUN SATMONB012346TUE THUWED FRISUN SATMONC012346TUE THUWED FRISAT SUNMOND012346处理冲突插入后的散列表应该如()所示TUE THUWED SUNSAT FRIMON若根据查找表建立长度为的散列表,采用线性探测法处理冲突,假定对一个元素第一次计算的散列地址
20.m为,则下一次的散列地址为dA dB d+1%m Cd+1/m Dd+1若根据查找表建立长度为的散列表,采用二次探测法处理冲突,假定对一个元素第一次计算的散列地址
21.m为则第四次计算的散列地址为d,Ad+1%m Bd-1%m Cd+4%m Dd-4%m.下面有关散列查找的说法中正确的是22直接定址法所得地址集合和关键字集合的大小不一定相同A除留余数法构造的哈希函数其中必须选择素数B Hkey=key MODp,P构造哈希函数时不需要考虑记录的查找频率C数字分析法合用于对哈希表中浮现的关键字事先知道的情况D下面有关散列冲突解决的说法中不正确的是
23.处理冲突即当某关键字得到的哈希地址已经存在时,为其寻觅另一个空地址A使用链地址法在链表中插入元素的位置随意,即可以是表头表尾,也可以在中间B二次探测能够保证只要哈希表未填满,总能找到一个不冲突的地址C线性探测能够保证只要哈希表未填满,总能找到一个不冲突的地址D设哈希表长哈希函数表中已有个结点
24.m=14,Hkey=key%11o4addr15=4,addr38=5,addr61=6,其余地址为空,如用二次探测处理冲突,关键字为的结点的地址是addr84=749A8B3C5D9填空题252在散列函数中,应取
1.Hkey=key%p D采用分块查找法块长为以顺序查找确定块查找长度为的线性表时的平均查找长度为
2.s,n己知一个有序表为当二分查找值为和的元素时,分别
3.12,18,20,25,29,32,40,62,83,90,95,98,2990需要次和次比较才能查找成功;若采用顺序查找时,分别需要次和次比较才干查找成功从一棵二叉排序树中查找一个元素时,若元素的值等于根结点的值,则表明,若元素的值小于根结点的值,
4.则继续向查找,若元素的值大于根结点的值,则继续向_______________查找二分查找的存储结构仅限于,且是
5.o.假设在有序线性表上进行二分查找,则比较一次查找成功的结点数为个,比6A[
1..20]较二次查找成功的结点数为,比较三次查找成功的结点数为—,比较四次查找成功的结点数为,比较五次查找成功的结点数为,平均查找长度为在对有个元素的递增有序表作二分查找时,查找长度为的元素的下标从小到大挨次为
7.205设下标从开始1对于线性表进行散列存储时,若选用作为散列函数,则散列地址为
8.70,34,55,23,65,41,20,100HK=K%91的元素有,个,散列地址为的元素有个7索引顺序表上的查找分两个阶段一一
9.分块查找中,要得到最好的平均查找长度,应对个元素的线性查找表分成块,每
10.256块的最佳长度是若每块的长度为则等概率下平均查找长度为8,o是一棵二叉树,如果不为空,则它必须满足下面的条件
11.若左子树不空,则左子树上所有结点的值均小于根的值A若右子树不空,则右子树上所有结点的值均大于根的值B其摆布子树均为二叉排序树C假定有个关键字互为同义词,若用线性探测法把这些同义词存入散列表中,至少要进行次探测
13.k应用题
8.3设有序表为请分别画出对给定值和进行折半查找的过程
1.a,b,c,d,e,f,g,h,i,j,k,p,q,a,gn已知一棵二叉排序树如下
2.假如删除关键字画出新二叉树128,若查找需和哪些关键字比较256,已知散列表的地址区间为散列函数为()采用线性探测法处理冲突,将关键字序列
3.0~11,H k=k%11,挨次存储到散列表中,试构造出该散列表,并求出在等概率情况下的平均查找长度20,30,70,15,8,12,18,63,19设散列函数为()采用拉链法处理冲突,将上例中关键字序列挨次存储到散列表中,并求出在等
4.H k=k%11,概率情况下的平均查找长度.假定一个待散列存储的线性表为()散列地址空间为若采用除留余532,75,29,63,48,94,25,46,18,70,HT
[13],数法构造散列函数和线性探测法处理冲突,试求出每一元素的初始散列地址和最终散列地址,画出最后得到的散列表,求出平均查找长度第章排序9选择题
9.1从末排序的序列中挨次取出一个元素与己排序序列中的元素挨次进行比较,然后将其放在排序序列的合适位
1.置,该排序方法称为()排序法)插入)选择)希尔)二路归并A BC D下面各种排序方法中,最好情况下时间复杂度为()的是()
2.On)快速排序)直接插入排序)堆排序)归并排序A BC D用某种排序方法对线性表()进行排序时,无序序列的变化情况如下
3.25,84,21,47,15,27,68,35,20258421471527683520201521254727683584152021253527476884152021252735476884则所采用的排序方法是())选择排序)希尔排序归并排序)快速排序A B0D下面给出的四种排序法中,()排序是不稳定排序法
4.)插入)冒泡)二路归并)堆A BC D.快速排序方法在()情况下最不利于发挥其长处5)要排序的数据量太大A)要排序的数据中含有多个相同值B)要排序的数据已基本有序C)要排序的数据个数为奇数D一组记录的关键码为()则利用快速排序的方法,以第一个记录为基准得到的一次
6.46,79,56,38,40,84,划分结果为())A38,40,46,56,79,84)B40,38,46,79,56,84)C40,38,46,56,79,84)D40,38,46,84,56,79对记录的关键码{}进行排序,各趟排序结束时的结果为
7.50,26,38,80,70,90,8,30,40,2050,26,38,80,70,90,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是())快速排序)基数排序)希尔排序)归并排序A BC D在文件“局部有序”或者文件长度较小的情况下,最佳内部排序方法是()
8.)直接插入排序)冒泡排序)简单选择排序)归并排序A BC D在下列算法中,()算法可能浮现下列情况在最后一趟开始之前,所有的元素都不在其最终的位置上
9.)堆排序)冒泡排序)插入排序)快速排序A BC D设有个无序的元素,希翼用最快速度挑选出其中前个最大的元素,在以下的排序方法中,采用()
10.500010方法最好)快速排序)堆排序)基数排序A BC对给出的一组关键字{}若按关键字非递减排序,第一趟排序结果为{
11.14,5,19,20,11,1914,5,}问采用的排序算法是()19,20,11,19,)简单选择排序)快速排序)希尔排序)二路归并排序A BC D以下序列不是堆的是()
12.)A100,85,98,77,80,60,82,40,20,10,66)B100,98,85,82,80,77,66,60,40,20,10)C10,20,40,60,66,77,80,82,85,98,100)D100,85,40,77,80,60,66,98,82,10,20下面排序方法中,关键字比较次数与记录的初始罗列无关的是()
13.)希尔排序)冒泡排序)直接插入排序)直接选择排序A BC D一组记录的关键字为{}则利用堆排序的方法建立的初始堆为()
14.45,80,55,40,42,85,)A80,45,50,40,42,85)B85,80,55,40,42,45)C85,80,55,45,42,40)D85,55,80,42,45,40一组记录的关键字为{}其中含有个长度为的有序表,用归并
15.25,50,15,35,80,85,20,40,36,70,52排序方法对该序列进行一趟归并后的结果为()A15,25,35,50,20,40,80,85,36,70B15,25,35,50,80,20,85,40,70,36C15,25,50,35,80,85,20,36,40,70D15,25,35,50,80,20,36,40,70,85个元素进行冒泡排序的过程中,最好情况下的时间复杂度为
16.nA01B OlognCOn2D On2个元素进行快速排序的过程中,第一次划分最多需要挪移次元素包括开始将基准元素移到暂时变量的
17.n那一次A n/2B n-1C nD n+l下述几种排序方法中,要求内存量最大的是
18.插入排序选择排序快速排序归并排序A BC D下面排序方法中,时间复杂度不是的是
19.OM直接插入排序二路归并排序冒泡排序直接选择排序A BC D对下列个序列用快速排序方法进行排序,以序列的第个元素为基准进行划分在第趟划分过程中,
20.411元素挪移次数最多的是序列A70,75,82,90,23,16,10,68B70,75,68,23,10,16,90,82C82,75,70,16,10,90,68,23D23,10,16,70,82,75,68,90填空题212当数据量特殊大需借助外部存储器对数据进行排序,则这种排序称为
1.0在堆排序、快速排序和归并排序中,若从节省存储空间考虑,则应首先选取方法,其次选取方法;若只从
2.排序结果的稳定性考虑,则应先择方法;若只从平均情况下排序的速度来考虑,则选择方法;若只从最坏情况下排序最快并且要节省内存考虑,则应选取方法对个元素的序列进行冒泡排序,至少的比较次数是,此时元素的罗列情况为,在情况下比较次数最多,其
3.n比较次数为4;希尔排序是把记录按下标的一定增量分组,对每组记录进行直接插入排序,随着增量,所分成的组包含的记
4.录越来越多,当增量的值为时,整个数组合为一组直接插入排序需借助的存储单元个数空间复杂度为最好情况下直接插入排序的算法时间复杂度为,最坏情
5.况下该篁法的寸间复杂度为」H对个数据进行简单选择排序,所需讲行的关键字间的比较次数为—时间复杂度为
6.n对于关键字序列用筛选法建堆,必须从键值为
7.12,13,11,18,60,15,7,20,25,100,的关键字开始对一组记录进行直接插入排序时,当把第个记录插入到已排序的有
8.54,38,96,23,15,72,60,45,83760序表时,为寻觅其插入位置需比较次若对顺序存储在[『[]的记录进行堆排序,已知除第一个元素
9.A A976,38,62,53,80,74,83,65,8576外,以其余元素为根的结点都已是堆,则对第一个元素进行筛运算时,它将最终被筛到数组下标为的位置上A在时间复杂度为的排序方法中,排序方法是稳定的;在时间复杂度为的排序方法中,排序方
10.0192e On法是不稳定的设表中元素的初态是按键值递增的,若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺
11.序进行排序,则最省时间,塌费时间从一个无序序列建立一个堆的方法是首先将要排序的个键值分放到一棵的各个结点中,然后从
12.n i=一的结占%开始,逐步把以、为根的子树排成堆,直到K-K.62以勺为根的树排成堆,就完成为了建堆的过程在归并排序中,若待排序记录的个数为则共需要进行趟归并,在第三趟归并中,
13.20,是把长度为的有序表归并为长度为的有序表应用题
9.3设待排序的排序码序列为试分别写出使用以下排序方法每趟排序后的14{12,2,16,30,28,10,16*,20,6,18},结果并说明做了多少次排序码比较起泡排序快速排序4基数排序堆排序直接选择排序67直接插入排序希尔排序增量为125,2,1对一个具有个记录的文件进行快速排序,请问157在最好情况下需进行多少次比较?并给出一个最好情况初始罗列的实例1在最坏情况下需进行多少次比较?为什么?并给出此时的实例2如果某个文件经内排序得到个初始归并段,试问1680若使用多路归并执行趟完成排序,那末应取的归并路数至少应为多少?13如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过个,则按多路归并至少需要几趟可以215完成排序?如果限定这个趟数,可取的最低路数是多少?。