还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)在下列算法中,()算法可能出现下列情况在最后一趟开
1.始之前,所有元素都不在最终位置上.A:堆排序・B:冒泡排序.C:直接插入排序:快速排序.D解析在直接插入排序中,若待排序列中的最后一个元素应插入表中的第一个位置,则前面的有序子序列中的所有元素都不在最终位置上答案C对序列采用希尔排序,下列序
2.{98,36,-9,0,47,23,1,8,10,7}列()是增量为的一趟排序结果4・A:{98,7,-9,0,47,23,1,8,98,36}・B:{-9,0,36,98,1,8,23,47,7,10}・C:{36,98,-9,0,23,47,1,8,7,10}・以上都不对D:同义词冲突不等于聚集,链地址法处理冲突时将同义词放在同一个链表中,不会引起聚集现象,IV错误答案A设有一个含有个表项的散列表,用线性探测法解决冲突,
3.200按关键字杳询时找到一个表项的平均探测次数不超过,则散L5列表应能够容纳()个表项(设直找成功的平()》一〜[1+1/1—a]/2均蛰找长度为刀/,其中ASL=L/a为装填因子)・A:400・B:526・C:624・D:676解析若有个表项要放入散列表,采用线性探测法解决冲突,限200定查找成功的平均查找长度不超过
1.5,则答案A、假定有个关键字互为同义词,若用线性探测法把这个4K K关键字填入散列表,至少要进行次探测・A:K-1・B:K・C:K+1・D:KK+l/2解析K个关键字在依次填入的过程中,只有第一个不会发生冲突,故探测次数为即选1+2+3+…+K=KK+l/2,Do答案D对包含个元素的散列表进行直找,平均直找长度
5.n为鸣九.A・:为B01・:不直接依赖于C n・:直接依赖于表长D m解析a在散列表中,平均查找长度与装填因子直接相关,表的查找效率不直接依赖于表中已有表项个数n或表长m若散列表中存放的记录全部是某个地址的同义词,则平均查找长度为而0n非01答案C采用开放定址法解决冲突的散列查找中,发生聚集的原因主
6.要是:数据元素过多.A:负载因子过大.B・:散列函数选择不当C・:解决冲突的方法选择不当D解析聚集是因为选取不当的处理冲突的方法,而导致不同关键字的元素对同一散列地址进行争夺的现象用线性再探测法,容易引发聚集现象答案D、在采用链地址法处理冲突所构成的散列表上查找某一关键字,7则在蛰找成功的情况下,所探测的这些位置上的键值();若采用线性探测法,则()・A:一定都是同义词・不一定都是同义词B::都相同.C・:一定都不是同义词D解析因为在链地址法中,映射到同一地址的关键字都会链到与此地址相对应的链表上,所以探测过程一定是在此链表上进行的,从而这些位置上的关键字均为同义词;但在线性探测法中出现两个同义关键字时,会把该关键字对应地址的下一个地址也占用掉,两个地址分别记为、查找一个满足Addr Addr+1,()H key=Addr+l的关键字key时,显然首次探测到的不是key的同义词()(答案、用哈希散列方法处理冲突碰撞)时可A,B8能出现堆积(聚集)现象,下列选项中,会受堆积现象直接影响的是():存储效率.A・B:散列函数・:装填(装载)因子C.:平均查找长度D解析产生堆积现象,即产生了冲突,它对存储效率、散列函数和装填因子均不会有影响,而平均查找长度会因为堆积现象而增大,选Do答案D、现有长度为且初始为空的散列表,散列函数是911HT()二采用线性探直(线性探测再散列)法解决H keykey%7,冲突将关键字序列依次插入87,40,30,6,11,22,98,20后,查找失败的平均查找长度是()HT HTA:4B:
5.35C:6D:
6.29解析采用线性探查法计算每个关键字的存放情况如下表所示请添加图片描述由于二,查找失败时可能对应的地Hkey0~6址有个,对于计算出地址为的关键字只有比较完70keyO,号地址后才能确定该关键字不在表中,比较次数为;对于89〜计算出地址为1的关键字keyl,只有比较完1〜8号地址后才能确定该关键字不在表中,比较次数为以此类推需要特别注8;意的是,散列函数不可能计算出地址因此有7,请添加图片描述答案C对任意个关键字进行基于比较的排序至少要进行10,7次关键字之间的两两比较A:13B:14C:15D:6解析对于任意序列进行基于比较的排序,求最少的比较次数应考虑最坏情况对于任意个关键字排序的比较次数至少为口n理?)将代入公式,答案为n=713o答案A解析增量为意味着所有相距为的记录构成一组,然后在组44内进行直接插入排序,经观察,只有选项满足要求A答案A、用希尔排序方法对一个数据序列进行排序时,若第趟排序31结果为,则该趟排序采用的增量(间隔)9,1,4,13,7,8,20,23,15可能是()・A:2・B:3・C:4・D:5解析,首先第二个元素为1,是整个序列中的最小元素,因此可知该希尔排序为从小到大排序然后考虑增量问题,・若增量为2,则第1+2个元素4明显比第1个元素9()要小,排除;若增量为,则第个元A3i,i+3,i+6i=l,2,3素都为有序序列,符合希尔排序的定义;・若增量为4,则第1个元素9比第1+4个元素7要大,C排除;・若增量为5,则第1个元素9比第1+5个元素8要大,D排除故选Bo答案B、一组记录的关键码为则利用快速排序446,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解析以为基准元素,首先从后向前扫描比小的元素,并与之进4646行交换,而后从前向后扫描比46大的元素并将46与该元素交换,得到此后,继续重复从后向前40,46,56,38,79,84o扫描与从前往后扫描的操作直到处于最终位置,46答案选Co答案C)、快速排序算法在(情况下最不利于发挥其长处5:要排序的数据量太大.A.B:要排序的数据中含有多个相同值.C:要排序的数据个数为奇数:要排序的数据已基本有序.D解析当待排序数据为基本有序时,每次选取第个元素为基准,n会导致划分区间分配不均匀,不利于发挥快速排序算法的优势相反,当待排序数据分布较为随机时,基准元素能将序列划分为两个长度大致相等的序列,这时才能发挥快速排序的优势答案D{}对数据序列采用冒泡排序(从后
6.8,9,10,4,5,6,20,1,2向前次序进行,要求升序),需要进行的趟数至少是()O・B:4・C:5・D:8r=i从后向前泡〃的过程为,第一趟解析,第二趟第三趟{1,8,9,10,4,5,6,20,2}{1,2,8,9,10,4,5,6,20},{1,2,4,8,9,10,5,6,20},第四趟,第五趟经过第五{1,2,4,5,8,9,10,6,20}{1,2,4,5,6,8,9,10,20},趟冒泡后,序列已经全局有序,故选C实际每趟冒泡发生交换后o可以判断是否会导致新的逆序对,如果不会产生,则本趟冒泡之后序列全局有序,所以最少5趟即可答案C、对下列个序列,以第一个关键字为基准用快速排序算74法进行排序,在第一趟过程中移动记录次数最多的是()OA:92,96,88,42,30,35,110,100B:92,96,100,110,42,35,30,88C:100,96,92,35,30,110,88,42D:42,30,35,92,100,96,88,110解析对各序列分别执行一趟快速排序,可做如下分析(以为例):A,由于枢纽值为因此移动到第一个位置移动到第六92,3596,个位置移动到第二个位置,再将枢纽值移动到所在的3030单元,即第五个位置,所以中序列移动的次数是A4O同样也可以分析出中序列的移动次数为中序列的移动次B8,C数为4,D中序列的移动次数为20答案B、对个关键字进行快速排序,最大递归深度为(),最小递8n归深度为()・A:1・B:n.晦nc・L•n.^log2n解析快速排序过程构成一个递归树,递归深度即递归树的高度n枢纽值每次都将子表等分时,递归树的高为logo;枢纽值每次都是子表的最大值或最小值时,递归树退化为单链表,树高为no答案B,C、采用递归方式对顺序表进行快速排序,下列关于递归次数的9叙述中,正确的是・A:递归次数与初始数据的排列次序无关:每次划分后,先处理较长的分区可以减少递归次数.B.C:每次划分后,先处理较短的分区可以减少递归次数・D:递归次数与每次划分后得到的分区的处理顺序无关解析递归次数与各元素的初始排列有关若每次划分后分区比较平衡,则递归次数少;若区分不平衡,递归次数多递归次数与处理顺序是没有关系的答案D为实现快速排序算法,待排序序列宜采用的存储方式是
10.o・A:顺序存储:散列存储.B・C:链式存储索引存储.D:解析绝大部分内部排序只适用于顺序存储结构快速排序在排序的过程中,既要从后向前查找,又要从前向后查找,因此宜采用顺序存储答案A、在开放定址法中散列到同一个地址而引起的“堆积〃问题是1由于()引起的・A:同义词之间发生冲突:非同义词之间发生冲突.B・C:同义词之间或非同义词之间发生冲突:散列表〃溢出〃.D解析在开放定址法中散列到同一个地址而产生的〃堆积〃问题,是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起,导致关键字查询需要经过较长的探测距离,降低了散列的效率因此要选择好的处理冲突的方法来避免〃堆积〃答案C)、下列关于散列冲突处理方法的说法中,正确的有(2工、采用再散列法处理冲突时不易产生聚集口、采用线性探测法处理冲突时,所有同义词在散列表中一定相邻、采用链地址法m处理冲突时,若限定在链首插入,则插入任一个元素的时间是相同的IV、采用链地址法处理冲突易引起聚集现象和・A Im・BI、口和m・c:m和iv・DI和IV解析.利用再散列法处理冲突时,按一定的距离,跳跃式地寻找〃下一个〃空闲位置,减少了发生聚集的可能,I正确散列地址的关键字,和为解决冲突形成的某次探测地址为・i i的关键字,都争夺地址i,i+1,…,因此不一定相邻,口错误in正确。