2023数据结构考试内部题库含答案解析

数据结构考试内部题库含答案解析（全考点）1、在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有元素都不在最终位置上。A：堆排序B：冒泡排序C：直接插入排序D：快速排序解析在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。答案：C2、对序列{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：以上都不对解析增量为4意味着所有相距为4的记录构成一组，然后在组内进行直接插入排序，经观察，只有选项A满足要求。答案：A3、用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（）。A：2B：3C：4D：5解析首先，第二个元素为1，是整个序列中的最小元素，因此可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，则第1+2个元素4明显比第1个元素9要小，A排除；若增量为3，则第i,i+3,i+6（i=1,2,3）个元素都为有序序列，符合希尔排序的定义；若增量为4，则第1个元素9比第1+4个元素7要大，C排除；若增量为5，则第1个元素9比第1+5个元素8要大，D排除。故选B。答案：B4、一组记录的关键码为（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）解析以46为基准元素，首先从后向前扫描比46小的元素，并与之进行交换，而后从前向后扫描比46大的元素并将46与该元素交换，得到（40,46,56,38,79,84）。此后，继续重复从后向前扫描与从前往后扫描的操作，直到46处于最终位置，答案选C。答案：C5、快速排序算法在（）情况下最不利于发挥其长处。A：要排序的数据量太大B：要排序的数据中含有多个相同值C：要排序的数据个数为奇数D：要排序的数据已基本有序解析当待排序数据为基本有序时，每次选取第n个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。答案：D6、对数据序列{8,9,10,4,5,6,20,1,2}采用冒泡排序（从后向前次序进行，要求升序），需要进行的趟数至少是（）。A：3B：4C：5D：8解析从后向前“冒泡”的过程为，第一趟{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。实际每趟冒泡发生交换后可以判断是否会导致新的逆序对，如果不会产生，则本趟冒泡之后序列全局有序，所以最少5趟即可。答案：C7、对下列4个序列，以第一个关键字为基准用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是（）。A：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，因此35移动到第一个位置，96移动到第六个位置，30移动到第二个位置，再将枢纽值移动到30所在的单元，即第五个位置，所以A中序列移动的次数是4。同样也可以分析出B中序列的移动次数为8，C中序列的移动次数为4，D中序列的移动次数为2。答案：B8、对n个关键字进行快速排序，最大递归深度为（）,最小递归深度为（）。A：1B：nC：D：解析快速排序过程构成一个递归树，递归深度即递归树的高度。枢纽值每次都将子表等分时，递归树的高为；枢纽值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为n。答案：B，C9、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。A：递归次数与初始数据的排列次序无关B：每次划分后，先处理较长的分区可以减少递归次数C：每次划分后，先处理较短的分区可以减少递归次数D：递归次数与每次划分后得到的分区的处理顺序无关解析递归次数与各元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若区分不平衡，递归次数多。递归次数与处理顺序是没有关系的。答案：D10、为实现快速排序算法，待排序序列宜采用的存储方式是（）。A：顺序存储B：散列存储C：链式存储D：索引存储解析绝大部分内部排序只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，又要从前向后查找，因此宜采用顺序存储。答案：A1、在开放定址法中散列到同一个地址而引起的“堆积”问题是由于（）引起的。A：同义词之间发生冲突B：非同义词之间发生冲突C：同义词之间或非同义词之间发生冲突D：散列表“溢出”解析在开放定址法中散列到同一个地址而产生的“堆积”问题，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列的效率。因此要选择好的处理冲突的方法来避免“堆积”。答案：C2、下列关于散列冲突处理方法的说法中，正确的有（）。Ⅰ、采用再散列法处理冲突时不易产生聚集Ⅱ、采用线性探测法处理冲突时，所有同义词在散列表中一定相邻Ⅲ、采用链地址法处理冲突时，若限定在链首插入，则插入任一个元素的时间是相同的Ⅳ、采用链地址法处理冲突易引起聚集现象A：Ⅰ和ⅢB：Ⅰ、Ⅱ和ⅢC：Ⅲ和ⅣD：Ⅰ和Ⅳ解析利用再散列法处理冲突时，按一定的距离，跳跃式地寻找“下一个”空闲位置，减少了发生聚集的可能，Ⅰ正确。散列地址i的关键字，和为解决冲突形成的某次探测地址为i的关键字，都争夺地址i，i+1，...，因此不一定相邻，Ⅱ错误。Ⅲ正确。同义词冲突不等于聚集，链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象，Ⅳ错误。答案：A3、设有一个含有200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表应能够容纳（）个表项（设查找成功的平均查找长度为ASL=，其中为装填因子）。A：400B：526C：624D：676解析若有200个表项要放入散列表，采用线性探测法解决冲突，限定查找成功的平均查找长度不超过1.5，则答案：A4、假定有K个关键字互为同义词，若用线性探测法把这K个关键字填入散列表，至少要进行（）次探测。A：K-1B：KC：K+1D：K(K+1)/2解析K个关键字在依次填入的过程中，只有第一个不会发生冲突，故探测次数为（1+2+3+...+K）=K(K+1)/2，即选D。答案：D5、对包含n个元素的散列表进行查找，平均查找长度（）。A：为B：为O(1)C：不直接依赖于nD：直接依赖于表长m解析在散列表中，平均查找长度与装填因子直接相关，表的查找效率不直接依赖于表中已有表项个数n或表长m。若散列表中存放的记录全部是某个地址的同义词，则平均查找长度为O(n)而非O(1)。答案：C6、采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（）。A：数据元素过多B：负载因子过大C：散列函数选择不当D：解决冲突的方法选择不当解析聚集是因为选取不当的处理冲突的方法，而导致不同关键字的元素对同一散列地址进行争夺的现象。用线性再探测法，容易引发聚集现象。答案：D7、在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值（）；若采用线性探测法，则（）。A：一定都是同义词B：不一定都是同义词C：都相同D：一定都不是同义词解析因为在链地址法中，映射到同一地址的关键字都会链到与此地址相对应的链表上，所以探测过程一定是在此链表上进行的，从而这些位置上的关键字均为同义词；但在线性探测法中出现两个同义关键字时，会把该关键字对应地址的下一个地址也占用掉，两个地址分别记为Addr、Addr+1，查找一个满足H(key)=Addr+1的关键字key时，显然首次探测到的不是key的同义词。答案：A，B8、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（）。A：存储效率B：散列函数C：装填（装载）因子D：平均查找长度解析产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选D。答案：D9、现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87,40,30,6，11,22,98,20依次插入HT后，HT查找失败的平均查找长度是（）。A：4B：5.35C：6D：6.29解析采用线性探查法计算每个关键字的存放情况如下表所示。请添加图片描述由于H(key)=0~6，查找失败时可能对应的地址有7个，对于计算出地址为0的关键字key0，只有比较完0~8号地址后才能确定该关键字不在表中，比较次数为9；对于计算出地址为1的