考研计算机－习题精炼和重点回顾 排序

考研计算机－习题精炼和重点回顾 排序内容摘要：

考研计算机－习题精炼和重点回顾 排序 1排序算法的稳定性是指 使值相同的数据保持原顺序中的相对位置不变 使值相同的数据保持原顺序中的绝对位置不变 您的答案是：【未答】 正确答案是：【A】解析：根据排序算法的稳定性概念可知选项 A 正确。 2对任意的 7 个关键字进行排序，至少要进行关键字之间的两两比较的次数是 您的答案是：【未答】 正确答案是：【A】解析：本题隐含了最坏情况这个条件，基于比较的排序算法在最坏情况下所需进行的比较次数至少为3对序列（49， 38，65，97，76 ，13，47，50 ）采用折半插入排序法进行排序，要把第 7 个元素 47 插入到已排序序列中，为寻找插入的合适位置需要进行（ ）次元素间的比较。 您的答案是：【未答】 正确答案是：【A】解析：具体进行折半插入排序可以得到结论。 4对有 n 个记录的表做直接插入排序，在最好的情况下需比较（ ）次关键字 D.n(2 您的答案是：【未答】 正确答案是：【A】解析：直接插入排序的最好情况是原表已经排好序，每插入一个元素的时候只需比较一个关键字，所以总的比较次数是 用直接插入排序方法对下面 4 个序列进行排序（由小到大），元素比较次数最少的是 A.（94，32，40，90，80 ，46，21，69） B.（32，40，21，46，69 ，94，90，80） C.（21，32，46，40，80 ，69，90，94） D.（90，69，80，46 ，21，32，94，40） 您的答案是：【未答】 正确答案是：【C 】解析：直接插入排序方法的最好情况为待排序表有序时，而且原表越接近有序，效率越高。 6起泡排序方法的排序趟数是一个区间范围1,当参加排序的序列是下列哪种情况时，要进行 n1 趟排序 您的答案是：【未答】 正确答案是：【C 】解析：一般情况下，起泡排序方法的排序趟数不同于其他排序方法，其排序趟数与参加排序的序列中元素分布的原始状态有关。 对于一个具有 n 个元素的任意序列，最多需要进行 n1 趟排序，至少也要进行 1 趟排序。 当原始序列号中值最小的元素处在序列的最后位置时，需要进行 n1 趟排序。 7对具有 n 个元素的任意序列采用简单选择排序法进行排序，排序趟数为 D. 您的答案是：【未答】 正确答案是：【A】解析：对具有 n 个元素的任意序列采用简单选择排序法进行排序，排序趟数为 n1。 8对序列（15， 9，7，8，20，4 ）用希尔排序方法排序，经一趟排序后序列变为（15， ，8， 20，9，7 ），则该次采用的增量是 您的答案是：【未答】 正确答案是：【D】解析：本题主要考查希尔排序算法的执行过程和增量的含义。 经一趟排序后序列的第二个元素原序列的位置是第 6 个位置，则它应该属于按照增量划分后的第二组元素，则元素 20 属于第一组元素，它在原序列的位置是 5，所以增量为4。 9快速排序法在下列哪种情况下最不利于发挥其长处 您的答案是：【未答】 正确答案是：【C 】解析：当参加排序的数据已经按值有序或者基本按值有序时，快速排序方法就成为了“慢速排序方法”，因为每一次被分成的各部分中的新的基准元素恰好是最大（或最小）值元素，对各个部分排序的过程中进行的比较次数将达到最多。 10下列序列中，哪一个是执行一趟快速排序后的结果 A.30，50，36 ，10，85，92，81，95 B.30，50，36 ，10，81，85，92 ， 95 C.36，10，81，85 ，30，50，92， 95 D.50，36，10，81，85 ，30，92 ， 95 您的答案是：【未答】 正确答案是：【B】解析：本题主要考查快速排序算法的执行过程和枢轴的含义。 经过一趟排序后，应该确定枢轴记录的最终位置，此时其左边的所有元素都不大于它，右边的所有元素都不小于它。 【归纳总结】快速排序算法并不产生一个有序区，但每一趟归位一个元素。 另外，快速排序与待排序数据的顺序有关，当正序和反序时效率都最低，只有当数据随机分布，每趟划分的子区间长度大致相等时效率最高。 11当 n 个整型数据有序时，对这 n 个数据用快速排序算法排序，则时间复杂度是X；当用递归算法求 n。 时，算法的时间复杂度是 Y；则 X 减 Y 的结果是 A.O(n) B. C. D. 您的答案是：【未答】 正确答案是：【B】解析：有序表的快速排序时间复杂度为 O(递归算法求 n。 算法的时间复杂度是O(n)，则 O(O(n)= O(12一组记录的关键字为（45，78 ，55，37，39 ，83），对其进行堆排序，所建的初始堆为 5 ， 55，37，39 ，83 8 ， 55，37，39 ，45 8 ，55，45，39 ，37 5 ， 78，39，35 ，37 您的答案是：【未答】 正确答案是：【B】解析：建堆的过程，即从最后一个非叶子结点，由下至上调整使得其满足堆的性质。 由此，可以得到初始堆为：83，78 ，55，37，39，45。 13构建 n 个记录的初始堆，其时间复杂度为 A.O(n) B. C. D. 您的答案是：【未答】 正确答案是：【A】解析：本题主要考查堆排序的性能分析。 设具有 n 个记录的原始序列所对应的完全二叉树的深度为 h，建立初始堆时，对每个非叶结点都要自上而下做“筛选”，由于第 i 层上的结点数小于等于 2第 i 层上的结点的最大下移深度为 下移一层要做两次比较，所以建初始堆时，有总的比较次数 所以建堆的时间复杂度是 O(n)。 14在含有 n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储的位置是 A. B. D. +2 您的答案是：【未答】 正确答案是：【D】解析：小根堆中，关键字最大的记录只可能在叶结点上，故不可能在小于等于 ën/2û 的结点上。 对于小根堆而言，每棵子树的根结点都是这棵子树上的最小的元素，而左右子树上的元素都比根结点元素大；对于小根堆中的结点，如果它存在子结点，则它必然不会是关键字最大的记录，由于堆在逻辑上是一棵完全二叉树，最大关键字只能存于其叶结点中，因此答案 D 有可能存储着最大关键字，其余答案都不可能。 15若要尽可能快地完成对实数数组的排序，则要求排序是稳定的，则应选择 您的答案是：【未答】 正确答案是：【C 】解析：快速排序和堆排序均为不稳定的排序，而基数排序不能对实数排序。 【归纳总结】基数排序的最大特点是不需要进行关键字的比较，算法中所产生的有序区不一定是全局有序的。 另外，基数排序的时间效率与待排序数据的顺序无关。 16设有 5 个初始归并段，每个归并段有 200 个记录，采用二路归并排序，总的比较次数是 您的答案是：【未答】 正确答案是：【D】解析：17下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序 您的答案是：【未答】 正确答案是：【D】解析：本题主要考查了选项中出现的几种树的结构特点。 对于选项 A，根据二叉排序树的结构特点我们可以知道，二叉排序树的中序遍历结果是一个有序序列，而在中序遍历中，父结点并不总是出现在孩子结点的前面（或后面）。 故该选项不正确。 例如，我们用关键字 3，1 ，2 建立一棵二叉排序树，则从结点 2 出发到根的路径上所经过的结点序列为 2，1，3 ，并不是一个有序的序列。 对于选项 B，根据哈夫曼树的结构特点我们可以知道，在哈夫曼树中所有的关键字只出现在叶子结点上，其非叶子结点上并没有关键字值，显然不正确。 对于选项 C，平衡二叉树其本质上也是一种二叉排序树，只不过是平衡化之后的二叉排序树，故该选项也是不正确的。 例如，我们用序列 5，1 ，8，6 ，9 建立一棵平衡二叉树，从结点 6 出发到根的路径上所经过的结点序列为6，8 ， 5，也不是一个有序的序列。 对于选项 D，根据建大根堆的过程，不断地把大值“上浮”，将小值“筛选”下去，最终得到的正是一个从任一结点出发到根的路径上所经过的结点序列按其关键字有序得树状结构，故 D 是正确的。 18下列的排序方法中，排序的比较次数与序列的初始排列状态无关的是 您的答案是：【未答】 正确答案是：【A】解析：无论参加排序的序列中的元素的位置初始如何排列，简单选择排序方法在整个排序过程中多进行的元素之间的比较次数都一样。 例如，对于具有 n 个元素的序列采用选择排序方法，整个排序过程中一共要进行 n*(2 次元素间的比较。 19下列排序方法中，整个排序过程中平均比较次数最少的是 您的答案是：【未答】 正确答案是：【D】解析：一般情况下，整个排序过程中平均比较次数最少的是快速排序。 20用某种排序方法对数据序列（24，88 ，21，48， 15，27，69，35，20 ）进行排序时，元素序列的变化情况如下：初态：24，88，21，48，15 ，27，69，35 ，20；第一趟：20， 15，21，24，48 ，27，69，35 ， 88；第二趟：15， 20，21，24，35 ，27，48，69 ， 88；第三趟：15， 20，21，24，27 ，35，48，69 ， 88。 则采用的排序方法是 您的答案是：【未答】 正确答案是：【A】解析：如果是选项 B 选择排序，则在 4 轮排序过程中无法得到最后的排序结果；如果是选项 C 希尔排序不可能在第一趟排序将 20 换到第一位；同理也不是归并排序。 题目中的排序过程是子序列同时进行的快速排序。 21数据序列（2，1，4 ，9，8，10，6 ，20）只能是下列（ ）排序算法中的两趟排序后的结果。 您的答案是：【未答】 正确答案是：【A】解析：对于选项 B、C、D 这三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 22欲求前 k 个最大元素，用下面（ ）排序方法好 您的答案是：【未答】 正确答案是：【C 】解析：求前 k 个最大元素选用堆排序比较好。 因为在建一个含有 n 个元素的堆时，共进行的关键字的比较次数不超过 4n，调整建新堆时的比较次数不超过 2 n 个元素中求前 k 个最大元素，在堆排序情况下，比较次数最多不超过4n+23有 n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。 （。