1、计算机专业基础综合数据结构（排序）模拟试卷 1（无答案）一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面给出的 4 种排序方法中，( )排序法是不稳定性排序法。（A）插入（B）冒泡（C）二路归并（D）堆2 下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（A）快速排序（B）直接插入排序（C）二路归并排序（D）冒泡排序3 下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。（A）冒泡排序（B）堆排序（C）直接插入排
2、序（D）二路归并排序4 下列排序算法中，( ) 每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（A）冒泡排序（B）希尔排序（C）简单选择排序（D）直接插入排序5 下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog2n)的是( )。（A）堆排序（B）冒泡排序（C）直接选择排序（D）快速排序6 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（A）选择排序（B）冒泡排序（C）归并排序（D）堆排序7 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（A）直接插入排序（B）归并排序（C）直接选择排序
3、（D）堆排序7 对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。8 (1)（A）堆排序（B）快速排序（C）插入排序（D）归并排序9 (2)（A）堆排序（B）快速排序（C）插入排序（D）归并排序10 如果只想得到 1 000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( ) 方法最快。（A）冒泡排序（B）快速排序（C）简单选择排序（D）堆排序11 数据表 A 中有 10 000 个元素，如果仅要求求出其中最大的 10 个元素，则采用( )方法最节省时间。（A）堆排序（B）希尔排序（C）快速排序（D）直接选择排序12 若对序
4、列(tang，deng ，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（A）an ，bai，deng，wang，tang，fang ，shi，liu（B） an，bai ，deng ，wang，shi，tang，fang，liu（C） an，bai ，deng ，wang，fang，shi，tang，liu（D）an，bai，deng，wang，shi，liu，tang，fang13 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法
5、。（A）插入（B）选择（C）希尔（D）二路归并14 若用冒泡排序方法对序列10，14，26，29，41，52 从大到小排序，需进行( )次比较。（A）3（B） 10（C） 15（D）2515 下列( ) 是一个堆。（A）19，75，34，26，97，56（B） 97，26，34，75，19，56（C） 19，56，26，97，34，75（D）19，34，26，97，56，7516 若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第 1 个记录为基准得到的一次划分结果为( )。（A）38，40，46，56，79，84（B） 40，38，46，79，56，84（
6、C） 40，38，46，56，79，84（D）40，38，46，84，56，79二、综合应用题41-47 小题，共 70 分。17 在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?18 设有 5 个互不相同的元素 a，b，c ，d，e，能否通过 7 次比较就将其排好序，7如果能，请列出其比较过程：如果不能，则说明原因。19 对一个由 n 个关键字不同的记录构成的序列，能否用比 2n 一 3 少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现? 在最坏的情况下至少要进行多少次比较?20 利用比较的方法
7、进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。21 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1key 2key n)； (2)关键字自大到小逆序(key1key 2 key n)； (3)奇数关键字顺序有序，偶数关键字顺序有序(key1key 3 ，key 2key 4)； (4) 前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1key 2key m， keym+1key m+2key n，m 为中间位置)。22
8、对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：(1)当 n=7 时，在最好情况下需进行多少次比较?请说明理由。(2)当 n=7 时，给出一个最好情况的初始排序的实例。(3)当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。(4)当 n=7 时，给出一个最坏情况的初始排序的实例。23 关于堆的一些问题：(1)堆的存储表示是顺序的，还是链接的?(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?(3)对 n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?
9、24 若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 Kn+1，请用文字简要说明如何在 log2n 的时间内将其重新调整为一个堆。25 冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。26 有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示) 进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。设计实现计数排序的算法。对于有 n 个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?27 某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。28 设有一个数组中存放了一个无序的关键字序列 K1，K 2，K n。现要求将 Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。
