数据结构改错题(数据结构题目解析)
导语：数据结构错题收录（二十二）
在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。
答案：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：2• B：3• C：4• D：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：3• B：4• C：5• D：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,100• B：92,96,100,110,42,35,30,88• C：100,96,92,35,30,110,88,42• D：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：1• B：n• C：• D：解析快速排序过程构成一个递归树，递归深度即递归树的高度。枢纽值每次都将子表等分时，递归树的高为；枢纽值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为n。
答案：B，C9、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。• A：递归次数与初始数据的排列次序无关• B：每次划分后，先处理较长的分区可以减少递归次数• C：每次划分后，先处理较短的分区可以减少递归次数• D：递归次数与每次划分后得到的分区的处理顺序无关解析递归次数与各元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若区分不平衡，递归次数多。递归次数与处理顺序是没有关系的。
答案：D10、为实现快速排序算法，待排序序列宜采用的存储方式是（）。• A：顺序存储• B：散列存储• C：链式存储• D：索引存储解析绝大部分内部排序只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，又要从前向后查找，因此宜采用顺序存储。
答案：A本文内容由小迪整理编辑！