数据结构第9章测试题B.docx
A.插入B.冒泡3 .以下排序算法中，其中（）A.堆排序，冒泡排序C.直接选择排序，归并排序4 .稳定的排序方法是（）A.直接插入排序和快速排序C.简单项选择择排序和四路归并排序第9章测试题B卷一、填空题.某内排序方法的稳定性是指（）oB.该排序算法允许有相同A.该排序算法不允许有相同的关键字记录的关键字记录C.平均时间为0 （n log n）的排序方法D.以上都不对.下面给出的四种排序法中（）排序法是不稳定性排序法。 米 C.二路归并D.堆积是稳定的。 B.快速排序，堆排序 D.归并排序，冒泡排序B.折半插入排序和起泡排序 D.树形选择排序和shell排序.以下排序方法中，哪一个是稳定的排序方法？（）A.直接选择排序 B.二分法插入排序 C.希尔排序 D.快 速排序.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，那么称该排序算法是不稳定的。（）就是不稳定的排序方法。A.起泡排序 B.归并排序C. Shell排序 D.直接插入排序E.简单项选择择排序 7.假设要求排序是稳定的，且关键字为实数，那么在以下排序方法中应选（）排序为宜。A.直接插入B.直接选择C.堆D.快速E.基数.假设需在O（nlogg）的时间内完成对数组的排序，且要求排序是稳定的，那么可选择 的排序方法是（ ）oA.快速排序B.堆排序 C.归并排序D.直接插入排序 9.下面的排序算法中，不稳定的是（）A.起泡排序B.折半插入排序 C.简单项选择择排序D.希尔排序E.基数排序F.推排序。 10.以下内部排序算法中：A.快速排序 B.直接插入排序C.二路归并排序I）.简单项选择择排序E.起 泡排序 F.堆排序 （1）其比拟次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k«n）的 情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为0（nlogn）的算法是（）为0（nn）的算法是（）.排序越数与序列的原始状态有关的排序方法是（）排序法。A.插入B.选择C.冒泡D.快速11 .下面给出的四种排序方法中，排序过程中的比拟次数与排序方法无关的是。）A.选择排序法B.插入排序法C.快速排序法D.堆积排序法13.对以下四种排序方法,在排序中关键字比拟次数同记录初始排列无关的是（）。 A.直接插入B.二分法插入C.快速排序D.归并排序14 .在以下排序算法中，哪一个算法的时间复杂度与初始排序无关（A.直接插入排序B.气泡排序 C.快速排序 D.序15 .在以下排序算法中，哪一个算法的时间复杂度与初始排序无关（A.直接插入排序B.气泡排序 C.快速排序 D.）, 直接选择排序16 .比拟次数与排序的初始状态无关的排序方法是（A.直接插入排序 排序16.数据序列（8, 9, 两趟排序后的结果。A.选择排序 17.数据序列（2, 1, 趟排序后的结果。 A.快速排序序18.对一组数据（84,A.直接插入排序 排序16.数据序列（8, 9, 两趟排序后的结果。A.选择排序 17.数据序列（2, 1, 趟排序后的结果。 A.快速排序序18.对一组数据（84,A.直接插入排序 排序16.数据序列（8, 9, 两趟排序后的结果。A.选择排序 17.数据序列（2, 1, 趟排序后的结果。 A.快速排序序18.对一组数据（84,10,B.起泡排序4, 5, 6, 20,B.冒泡排序4, 9, 8, 10, 6,B.冒泡排序47, 25, 15, 21)1,20)C.快速排序D.简单项选择择2）只能是以下排序算法中的（）的C.插入排序D.堆排序只能是以下排序算法中的（）的两C.选择排序D.插入排排序,数据的排列次序在排序的过程中的变化为(1) 8421 25 47 A.47 25 15 21(2) 15 47 2584那么采用的排序是（选择B.冒泡84 21(3) 15 21 25 84 47(4) 15)oC.快速D.插入19.对序列15, 9, 7, 8, 20, T, 4进行排序，进行一趟后数据的排列变为4, 9,-1, 8, 20, 7, 15）；那么采用的是（-1, 8, 20, 7, 15）；那么采用的是（-1, 8, 20, 7, 15）；那么采用的是（A.选择B.快速）排序。C.希尔D.冒泡20.假设上题的数据经一趟排序后的排列为9, 15, 7, 8, 20, -1, 4,那么采用的是（）排序。C.直接插入 I）.冒泡A.选择 B.堆二、填空题1.假设不考虑基数排序，那么在排序过程中，主要进行的两种基本操作是关键字的和记录的 O【北京邮电大学2001二、7 （4分）】2.外排序的基本操作过程是2.外排序的基本操作过程是2.外排序的基本操作过程是。【西安电子科技大学1998二、3 （3 米 米 米 分）】.直接插入排序用监视哨的作用是 o.对n个记录的表rl.n进行简单项选择择排序，所需进行的关键字间的比拟次数为O3 .设用希尔排序对数组98, 36, -9, 0, 47, 23, 1, 8, 10, 7进行排序，给出的 步长（也称增量序列）依次是4, 2, 1那么排序需趟，写出第一趟结束后,数组中数据的排列次序O.对于7个元素的集合H, 2, 3, 4, 5, 6, 7进行快速排序，具有最小比拟和交 换次数的初始排列次序为 O.堆是一种有用的数据结构.堆排序是一种（1）排序,堆实质上是一棵42_结点 的层次序列。对含有n个元素的序列进行排序时，堆排序的时间复杂度是g_,所 需的附加存储结点是关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满 足堆的性质（5） ° 【山东工业大学1996三、1 （5分）】三、综合题1、设有5个互不相同的元素a、b、c、d、e,能否通过7次比拟就将其排好序？如 果能，请列出其比拟过程；如果不能，那么说明原因。2、对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动 情况。（125, 11, 22, 34, 15, 44, 76, 66, 100, 8, 14, 20, 2, 5, 1）。3、借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的 记录。设此组记录存放于数组中。假设查找成功，那么输出该记录在r数组中的 位置及其值，否那么显示“not find”信息。请编写出算法并简要说明算法思想。
