当前位置：文档之家 › 第十章排序答案

第十章排序答案

  • 格式：doc
  • 大小：71.00 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

数据结构-第十章-内部排序

数据结构-第十章-内部排序

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

第十章内部排序

第十章内部排序

10.2 插入排序
1、直接插入排序:续 •实现算法
Status InsertSort ( SqList &L ) { for ( i = 2; i <= L.length ; ++i ) if ( LT( L.r[i].key, L.r[i-1].key ) ) { L.r[0].key = L.r[i].key; //复制为哨兵 for ( j=i-1; LT( L.r[0].key, L.r[j].key ) ; - -j ) L.r[j+1] = L.r[j]; //后移记录 L.r[j+1] = L.r[0]; } } //InsertSort
1 物料管理
第十章 内部排序
学习内容
10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序
SORT
2 物料管理
第十章 内部排序
10.1 概述
•定义
设有记录序列：{ R1、R2 ……….. Rn } 其相应的关键字序列为： { K1、K2 ……….. Kn }; 若存在一种确定的关系： Kx <= Ky <= … <= Kz，则将记录序列 { R1、R2 ……….. Rn } 排成按 该关键字有序的序列：{ Rx、Ry ……….. Rz } 的操作，称之为排序。
•性能分析 减少了查找比较次数，但并未降低时间复杂度，仍为O(n2)。 7
SORT
8 物料管理
第十章 内部排序
10.2 插入排序
3、 希尔(shell) 排序 •基本思想 先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列 中的记录基本有序时，再对全体记录进行一次直接插入排序。

第十章_排序方法(数据结构ppt-严蔚敏)

第十章_排序方法(数据结构ppt-严蔚敏)

第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量

第十章排序答案

第十章排序答案

第10章排序一、选择题1．某内排序方法的稳定性是指( D )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( D )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3．下列排序算法中，其中（D ）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6. 快速排序方法在（ D ）情况下最不利于发挥其长处。

【燕山大学 2001 一、3 （2分）】A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序7. 以下序列不是堆的是( D )。

【西安电子科技大学 2001应用一、5 （2分）】A. (100,85,98,77,80,60,82,40,20,10,66)B. (100,98,85,82,80,77,66,60,40,20,10)C. (10,20,40,60,66,77,80,82,85,98,100)D. (100,85,40,77,80,60,66,98,82,10,20)8．下列四个序列中，哪一个是堆（ C ）。

【北京工商大学 2001 一、8 （3分）】A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,159．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

第十章 内部排序

第十章 内部排序

(38) (65) (97) (76) (13) (27) (49)
直接插入排序算法
Void InsertSort(SqList &L) { //对顺序表L作直接插入排序 for (i=2; i<=L.length; ++i) if LT(L.r[i].key, L.r[i-1].key) { L.r[0]=L.r[i]; //复制为哨兵 for (j=i-1; LT(L.r[0].key, L.r[j].key); --j) L.r[j+1]=L.r[j]; //记录后移 L.r[j+1]=L.r[0]; //插入到正确位置 } }//InsertSort
改写上述算法：将枢轴暂存在r[0]的位置上，直至一趟排 序结束后再将枢轴记录移至正确位置上， 算法10.6(b)： Int Partition(SqList &L, int low, int high) { L.r[0]=L.r[low]; Pivotkey=L.r[low].key; while (low<high) { while(low<high && L.r[high].key>=pivotkey) --high;
10。3交换排序
起泡排序思想： 依次对未排序部分相邻的两个元素进行比较,若逆序则 交换位置,每一趟可以使一个最大(最小)元素从这个序列 中冒出来,经过n-1趟,就可以排好序 例：
起泡排序示例
初始关键字 第一趟排序后 第二趟排序后 第三趟排序后 第四趟排序后 第五趟排序后 12 12 12 12 12 4 23 23 18 14 4 18 18 14 4 14 14 14 4 18 4 4 23 90 90
快速排序

第10章 排序

第10章 排序

第十章排序一、单项选择题1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。

A. (24 28 36) 48 (52 68 75 99)B. (28 36 24) 48 (75 99 68 52)C. (36 68 99) 48 (75 24 28 52)D. (28 36 24) 48 (99 75 68 52)2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。

A. 希尔排序B. 二分插入排序C. 合并排序D. 冒泡排序3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。

A. 快速排序是稳定的排序方法B. 堆排序是不稳定的排序方法C. 希尔排序是稳定的排序方法D. 冒泡排序是不稳定的排序方法4. 下列排序方法中，____方法是不稳定的。

A. 冒泡排序B. 希尔排序C. 冒泡排序D. 直接插入排序5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。

A.快速排序B. 希尔排序C. 冒泡排序D. 堆排序6. 快速排序方法在最好情况下的时间复杂度为______。

A. O(n)B. O(n2)C. O(nlog2n)D.(log2n)7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。

A. 堆排序B.冒泡排序C. 直接选择排序D.快速排序8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。

A. 快速排序B.插入排序C. 冒泡排序D. 堆排序9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 选择排序10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。

A. 堆排序B. 冒泡排序C. 快速排序D. 直接选择排序11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。

有机化学答案

有机化学答案

第十章 羧酸及其衍生物习题答案1. 命名下列化合物（1）三氟乙酸 （2）3-丁烯酸 （3）4-戊酮酸 （4）1-羟基环己基甲酸 （5）2,4-二氯苯氧乙酸 （6）1,3-环己基二甲酸 （7）2,2-二甲基丙二酸 （8）丁二酸单酰氯 （9）2-甲基顺丁烯二酸酐 （10）N-溴丁二酰亚胺 （11）2-环戊酮基甲酸甲酯 （12） -丁内酯 （13）N-苯基-4-甲氧基苯甲酰胺 （14）N-苯基氨基甲酸甲酯 （15）2-乙酰氧基苯甲酸（乙酰水杨酸） （16）2-乙基-3-丁酮酸乙酯 2. 写出下列化合物的结构式CH 3CH 2CHCCHOOHCH 3CH 3COOH COOH CH CHCOOHHOOCCH 2CCH 2COOH COOH CH 3CHCOOH CH 3ONHCOCH 3H C ON(CH 3)2CH 2CCOOCH 33C C O OO NHC O (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)3. 比较下列化合物的酸性大小（1）甲酸 ＞ 碳酸 ＞ 苯酚 ＞ 水 ＞ 环己醇（2）氯乙酸 ＞ 羟基乙酸 ＞ 乙酸 ＞ 丙酸 （3）草酸 ＞ 丙二酸 ＞ 苯甲酸 ＞ 乙酸（4）邻硝基苯甲酸 ＞ 对硝基苯甲酸 ＞ 间硝基苯甲酸 ＞ 苯甲酸（5）对溴苯甲酸 ＞ 对甲基苯甲酸 ＞ 对甲氧基苯甲酸 ＞ 对氨基苯甲酸 4.按要求排序（1）按水解活性大小排序:丙酰氯 ＞ 丙酸酐 ＞ 丙酸乙酯 ＞ 丙酰胺 （2）与乙醇酯化的速度：乙酸 ＞ 丙酸 ＞ 2-甲基丙酸 ＞ 苯甲酸 （3）与丙酸酯化的速度：乙醇 ＞ 丙醇 ＞ 异丙醇 ＞ 苯甲醇（4）碱性水解的速度：甲酸甲酯 ＞ 乙酸甲酯 ＞ 乙酸乙酯 ＞ 乙酸异丙酯（5）碱性水解的速度：对硝基苯甲酸乙酯 ＞ 对氯苯甲酸乙酸 ＞ 对甲基苯甲酸乙酯 5.写出下列化合物加热后生成的主要产物。

(2)(3)(4)(1)CH 3CH O C OOCHCCH 3OCH 3CH CHCOOH C O OCH 3COCH 3O(5)(6)CH 3CHO C C O O OHCOOH (7)(8)(9)CH 3COOH6.写出丙酸与下列试剂反应的主要产物(2)(3)(4)(1)(5)(6)CH 3CH 2COONa CH 3CH 2COCl CH 3CH 2COOCH 2CH 3CH 3CH 2CH 2OHCH 3CHCOOHCH 3CH 2CONH 27.写出乙酰氯与下列试剂反应的主要产物。

FORTRAN95第十章 排序、查找算法

FORTRAN95第十章 排序、查找算法
要求线性表中的所有元素按照关键字有序(递增或递减)排列。 假设线性表中元素按关键字递增排列，那么二分查找方法是:将
给定值与处于顺序表“中间位置”上的元素的关键字进行比较键字则在表的后半部分继续进行二 分查找。否则在表的前半部分继续进行二分查找, 如此进行下去直 至找到满足条件的元素，或当前查找区为空。
10.1.4 直接插入排序 直接插入排序的方法是将待排记录分成两部分,初始第
一部分只含1个记录,在排序进程中把第二部分的全部记 录逐步插入到第一部分,并使该部分每次插入记录后是有 序的。直接插入排序算法步骤：
(1)将n个待排的记录数据存一维数组A中,默认A(1)为第 一部分的记录,2=>I；
(2）若I<=n, 则第二部分的一个记录A(I)与第一部分记 录进行比较, 找出在第一部分插入这个记录的位置，然后 将该位置上原来的记录及其后面所有的记录顺序后移一 个位置，在空出的位置上插入这个记录；若I>n (表示把 第二部分的记录全部插入到第一部分) ,则结束排序；
10.1.2 冒泡排序 冒泡排序是通过相邻两个排序记录的关键字的比
较,按一定次序互换逐步实现有序排序。 冒泡排序的实现过程是:第一次冒泡排序,首先将第
一个记录的关键字和第二个记录的关键字进行比较, 若不满足顺序的要求，则将两个记录进行交换，然
后比较第二个记录和第三个记录的关键字并做同样
处理，依次类推，直至对第n-1个记录和第n个记录 进行比较并处理完, 使得关键字值最大的记录被交换 到了最后一个记录的位置上。第二次冒泡排序只需
integer::low,high,key,ix,mid integer,dimension(low:high):: a do while(low<=high)

数据结构第10章排序练习及答案

数据结构第10章排序练习及答案

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

数据结构Ch10习题答案

数据结构Ch10习题答案

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

数据结构1800试题-第10章 排序 - 答案

数据结构1800试题-第10章 排序 - 答案

第10章排序（参考答案）部分答案解释如下：18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。

20. 本题为步长为3的一趟希尔排序。

24.枢轴是73。

49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。

64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。

二、判断题5. 错误。

例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。

12. 错误。

堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。

22. 错误。

待排序序列为正序时，简单插入排序比归并排序快。

三、填空题1. 比较,移动2.生成有序归并段（顺串）,归并3.希尔排序、简单选择排序、快速排序、堆排序等4. 冒泡,快速5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时）6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

7. n(n-1)/28.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。

(1)!=null (2)p->next (3)r!=null (4)r->data<q->data(5)r->next (6)p->next9. 题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。

(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link10.(1)i<n-i+1 (2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i(6)r[max]<-->r[n-i+1]11.(1)N (2)0 (3)N-1 (4)1 (5)R[P].KEY<R[I].KEY (6)R[P].LINK(7)(N+2)(N-1)/2(8)N-1 (9)0 (10)O(1)(每个记录增加一个字段) (11)稳定（请注意I的步长为-1）12. 3,(10,7,-9,0,47,23,1,8,98,36) 13.快速14.(4,1,3,2,6,5,7)15.最好每次划分能得到两个长度相等的子文件。

第十章 第三节 排列与组合的综合应用

第十章 第三节 排列与组合的综合应用

同步检测训练一、选择题1．(2008·湖南)某市拟从4个重点项目和6个一般项目中各选2个项目作为本年度要启动的项目，则重点项目A和一般项目B至少有一个被选中的不同选法的种数是() A．15B．45C．60 D．75答案：C解析：依题意得重点项目A和一般项目B至少有一个被选中的不同选法的种数是C24·C26－C23·C25＝60(其中C23·C25表示所选的2个重点项目中没有A且所选的2个一般项目中没有B的选法数)，选C.2．(2008·宁夏、海南)甲、乙、丙3位志愿者安排在周一至周五的5天中参加某项志愿者活动，要求每人参加一天且每天至多安排一人，并要求甲安排在另外两位前面．不同的安排方法共有()A．20种B．30种C．40种D．60种答案：A解析：由题意，从5天中选出3天安排3位志愿者的方法数为C35＝10(种)，甲安排在另外两位前面，故另两位有两种安排方法，根据乘法原理，不同的安排方法数共有20种，故选A.3．设集合I＝{1,2,3,4,5}，选择Ⅰ的两个非空子集A和B，要使B中最小的数大于A中最大的数，则不同的选择方法共有()A．50种B．49种C．48种D．47种答案：B解析：集合A、B中没有相同的元素，且都不是空集：从5个元素中选出2个元素，有C25＝10种选法，小的给A集合，大的给B集合；从5个元素中选出3个元素，有C35＝10种选法，将选出的3个元素从小到大排序，再分成1、2或2、1两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有2×10＝20种方法；同理，从5个元素中选出4个元素分给A、B，共有3C45＝15种方法；从5个元素中选出5个元素分给A、B，共有4C55＝4种方法。

总计为10＋20＋15＋4＝49种方法。

故选B.4．已知直线xa＋yb＝1(a，b是非零常数)与圆x2＋y2＝100有公共点，且公共点的横坐标和纵坐标均为整数，那么这样的直线共有()A．60条B．66条C．72条D．78条答案：A解析：在第一象限内圆x2＋y2＝100上的整数点只有(6,8)，(8,6)，而点(±10,0)，(0，±10)在圆上，∴圆x2＋y2＝100上横、纵坐标的为整数的点共12个点．过这12个点的圆x2＋y2＝100的切线和割线共12＋C212＝78，而不合题意的过原点、斜率为0、斜率不存在的各6条．∴共有78－3×6＝60条，故选A.评析：考查排列组合的基础知识及分类讨论的思想.5．(2006·南通)4位同学参加某种形式的竞赛，竞赛规则规定：每位同学必须从甲、乙两道题中任选一题作答，选甲题答对得21分，答错得－21分；选乙题答对得7分，答错得－7分．若4位同学的总分为0，则这4位同学不同得分情况的种数是()A．48 B．44C．36 D．24答案：B解析：4位同学的总分为0，分以下几种情形：(1)4位同学都选甲题，其中二人答对二人答错，则这4位同学不同得分情况的种数为把这4位同学平均分成2组的种数有C24种；(2)4位同学都选乙题，其中二人答对二人答错，同(1)的情况也有C24种；(3)4位同学中有一位同学选甲题并且答对，其余3位同学选乙题并且答错有C14C33种；(4)4位同学中有一位同学选甲题答错，其余3位同学选乙题并且答对有C14C33种；(5)4位同学中有2位同学选甲题一人答对另一人答错，其余2位同学选乙题一人答对另一人答错，共有A24·A22种，由分类计数原理，共有2C24＋2C14C33＋A24A22＝44种，故选B.6．(2009·东北三校模拟)某教师一个上午有3个班级的课，每班一节．如果上午只能排四节课，并且教师不能连上三节课，那么这位教师上午的课表的所有排法为() A．2 B．4C．12 D．24答案：C解析：本题属于部分元素不相邻问题，可采用插空法解答．先把教师上的三节课进行排列，然后将不上的一节课排在三节课形成的2个空中的一个空中即可，故共有A33C12＝12种课程表的排法．7．(2009·武汉5月)三个学校分别有1名、2名、3名学生获奖，这6名学生排成一排合影，要求同校的任两名学生不能相邻，那么不同的排法有()A．36种B．72种C．108种D．120种答案：D解析：解答本题的关键是正确的分类和分步；据题意可先让同校的3名学生排列，然后同校的2名学生的站法可以是：□×□××，××□×□，□××□×，×□××□，最后让只有一个获奖的学校的那名学生去站此时只有一种方法，此时共有4A33A22种不同的排法；若先让同校的3名学生排列，然后同校的2名学生的站法是×□×□×，则只有一个获奖的学校的那名学生可以去任意排，其有6种站法，故此时有6A33A22种不同的站法，综上共有4A33 A22＋6A33A22＝120种不同的站法．故选D.8．(2009·江西重点中学联考)将4个相同的红球和4个相同的蓝球排成一排，从左到右每个球依次对应序号为1,2，…，8，若同色球之间不加区分，则4个红球对应序号之和小于4个蓝球对应序号之和的排列方法种数为()A．31 B．27C．54 D．62答案：A解析：用●代表红球，○代表蓝球，则8个球不同的排列方法共有C212=70种，其中红球对应序号不小于蓝球与蓝球对应序号不小于红球排列方法种数相同，如图所示的4种排列红蓝球的对应序号之和相等(将红蓝球相互交换位置同样可得另4种排列)，故4个红球序号之和小于4个蓝球序号之和的排列方法种数为35-4=31，故应选A.二、填空题9．(2008·浙江)用1,2,3,4,5,6组成六位数(没有重复数字)，要求任何相邻两个数字的奇偶性不同，且1和2相邻．这样的六位数的个数是________(用数字作答)．答案：40解析：由题意得，奇数位上全为奇数或全为偶数．若全为奇数，方法有A22A22＋C12A22C12A22＝20.若全为偶数，方法有A22A22＋C12A22C12A22＝20.故共有20＋20＝40(种)．10．安排7位工作人员在5月1日至5月7日值班，每人值班一天，其中甲、乙二人都不安排在5月1日和2日．不同的安排方法共有__________种．(用数字作答) 答案：2400解析：由甲、乙两人都不安排在1日和2日，则只能安排在3日到7日这五天中，则有C 25A 22，其余5人均没限制，则有A 55；故这样的不同安排方法共有C 25A 22A 55＝2400种．11．(2008·武汉二调)从4双不同鞋子中取出4只鞋，其中至少有2只鞋配成一双的取法种数为________．(将计算的结果用数字作答)答案：54解析：依题意，分以下两类，第一类从4双中选2双有C 24＝6种，第二类，第一步从4双中选1双有C 14种，第二步从剩余的3双中选2双，每双中选1只有C 23×2×2种，共有C 14C 23×2×2＝48种，共48＋6＝54种．三、解答题12．4个不同的球，4个不同的盒子，把球全部放入盒内．(1)恰有1个盒不放球，共有几种放法？(2)恰有1个盒内有2个球，共有几种放法？(3)恰有2个盒不放球，共有几种放法？分析：把不放球的盒子先拿走，再放球到余下的盒子中并且不空．解：(1)为保证“恰有1个盒不放球”，先从4个盒子中任意取出去一个，问题转化为“4个球，3个盒子，每个盒子都要放入球，共有几种放法？”即把4个球分成2,1,1的三组，然后再从3个盒子中选1个放2个球，其余2个球放在另外2个盒子内，由分步计数原理，共有C 14C 24C 13×A 22＝144种．(2)“恰有1个盒内有2个球”，即另外3个盒子放2个球，每个盒子至多放1个球，也即另外3个盒子中恰有一个空盒，因此，“恰有1个盒内有2个球”与“恰有1个盒不放球”是同一件事，所以共有144种放法．(3)确定2个空盒有C 24种方法．4个球放进2个盒子可分成(3,1)、(2,2)两类，第一类有序不均匀分组有C 34C 11A 22种方法；第二类有序均匀分组有C 24C 22A 22·A 22种方法． 故共有C 24(C 34C 11A 22＋C 24C 22A 22·A 22)＝84种． 13．课外活动小组共13人，其中男生8人，女生5人，并且男、女各指定一名队长，现从中选5人主持某种活动，依下列条件各有多少种选法？(1)只有一名女生；(2)两队长当选；(3)至少有一名队长当选；(4)至多有两名女生当选.分析：解组合问题常从特殊元素入手．解：(1)一名女生，四名男生，故共有C 15·C 48＝350(种)．(2)将两队长作为一类，其他11人作为一类，故共有C 22·C 311＝165(种)．(3)至少有一名队长含有两类：有一名队长和两名队长．故共有：C 12·C 411＋C 22·C 311＝825(种)．或采用间接法：C 513－C 511＝825(种)．(4)至多有两名女生含有三类：有两名女生、只有一名女生、没有女生．故选法为C 25·C 38＋C 15·C 48＋C 58＝966(种)．14．已知平面α∥β，在α内有4个点，在β内有6个点．(1)过这10个点中的3点作一平面，最多可作多少个不同平面？(2)以这些点为顶点，最多可作多少个三棱锥？(3)上述三棱锥中最多可以有多少个不同的体积？解：(1)所作出的平面有三类：①α内1点，β内2点确定的平面，有C 14·C 26个；②α内2点，β内1点确定的平面，有C 24·C 16个；③α，β本身．∴所作的平面最多有C 14·C 26＋C 24·C 16＋2＝98(个)．(2)所作的三棱锥有三类：①α内1点，β内3点确定的三棱锥，有C 14·C 36个；②α内2点，β内2点确定的三棱锥，有C 24·C 26个；③α内3点，β内1点确定的三棱锥，有C 34·C 16个．∴最多可作出的三棱锥有：C14·C36＋C24·C26＋C34·C16＝194(个)(3)∵当等底面积、等高的情况下三棱锥的体积相等．且平面α∥β，∴体积不相同的三棱锥最多有C36＋C34＋C26·C24＝114(个)15．有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，共有多少种不同排法？解：∵前排中间3个座位不能坐，∴实际可坐的位置前排8个，后排12个．(1)两人一个前排，一个后排，方法数为C18·C112·A22种；(2)两人均在后排左右不相邻，共A212－A22·A111＝A211种；(3)两人均在前排，又分两类：①两人一左一右，共C14·C14·A22种；②两人同左同右，有2(A24－A13·A22)种．综上可知，不同排法种数为C18·C112·A22＋A211＋C14·C14·A22＋2(A24－A13·A22)＝346种．。

第十章 内部排序1

第十章 内部排序1

0 1 2 3 4 5 6 i=1 7 (49 38 65 97 76 13 27 ) i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27
k’1≤k’2≤···≤k’n 或 k’1≥k’2≥···≥k’n
• 稳定与不稳定：若记录序列中的任意两个记录 Rx , Ry 的排序码 Kx= Ky ；如果在排序之前和排 序之后，它们的相对位置保持不变，则这种排序 方法是稳定的，否则是不稳定的 • 排序中的两种基本操作：
– 两个排序码的比较（通常是必须的）
n
0
1 2 3 4 97 76 65 49
5 6 7 38 27 13
若待排序记录是随机的，取平均值
排序码比较次数：
n2 4
n2 记录移动次数： 4
时间复杂度：T(n)=O(n² ) 空间复杂度：S(n)=O(1)
10.1.2 折半插入排序
• 对直接插入排序，在插入记录Ri时，改用折半查找 方法确定插入的位置 • 算法思想：在插入Ri时，前面的记录R1, R2 ,·· Ri -1 ·, 已经排好序，因此可用折半查找找到Ri的插入位置
算法描述 #define M 100 //最大记录个数 typedef struct { int key; //排序码域 ···· //其他域 · ·; }RcdType; //记录类型 typedef RcdType Rcdlist[M+1];
//用顺序表存放，记录0下标不用 假设Rcdlist R；排序前待排序的记录已顺序存放在 R中，记录个数为n i：排序趟数，j：移动次数，直接插入排序算法如下：

实用数据结构基础(第四版)课后习题

实用数据结构基础(第四版)课后习题

一、判断题(第一章绪论)1、数据元素就是数据得最小单元。

答案:错误2.一个数据结构就是由一个逻辑结构与这个逻辑结构上得基本运算集构成得整体。

答案:错误3.数据得存储结构就是数据元素之间得逻辑关系与逻辑结构在计算机存储器内得映像。

答案:正确4.数据得逻辑结构就是描述元素之间得逻辑关系,它就是依赖于计算机得。

答案:错误5、用语句频度来表示算法得时间复杂度得最大好处就是可以独立于计算机得软硬件,分析算法得时间答案:正确(第二章线性表)6、取顺序存储线性表得第i个元素得时间同i得大小有关。

答案:错误7、线性表链式存储得特点就是可以用一组任意得存储单元存储表中得数据元素。

答案:正确8、线性链表得每一个节点都恰好包含一个指针域。

答案:错误9、顺序存储方式得优点得存储密度大,插入与删除效率不如练市存储方式好。

答案:正确10、插入与删除操作就是数据结构中最基本得两种操作,所以这两种操作在数组中也经常使用。

答案:错误(第三章栈)11、栈就是一种对进栈与出栈作了限制得线性表。

答案:错误12、在C(或C++)语言中设顺序栈得长度为MAXLEN,则top=MAXLEN表示栈满。

答案:错误13、链栈与顺序栈相比,其特点之一就是通常不会出现满栈得情况。

答案:正确14、空栈就就是所有元素都为0上得栈。

答案:错误15、将十进制数转换为二进制数就是栈得典型应用之一。

答案:正确(第四章队列)16、队列式限制在两端进行操作得线性表。

答案:正确17、判断顺序队列为空得标准就是头指针与尾指针都指向同一结点。

答案:错误18、在循环链列队中无溢出现像。

答案:错误19、在循环队列中,若尾指针rear大于头指针front,则元素个数为rear-front。

答案:正确20、顺序队列与循环队列关于队满与队空得判断条件就是一样得。

答案:错误(第五章串)21、串就是n个字母得有限序列。

答案:错误22、串得堆分配存储就是一种动态存储结构。

答案:正确23、串得长度就是指串中不同字符得个数。

第10章排序答案

第10章排序答案

第10章排序习题答案一、填空题1. 大多数排序算法都有两个基本的操作：比较（两个关键字的大小）和移动（记录或改变指向记录的指针）。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3次。

(可约定为，从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）；若初始数据基本反序，则选用选择排序。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。

若对其进行快速排序，在最坏的情况下所需要的时间是O(n2) 。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是O(n) 。

7．【计研题2000】对于n个记录的表进行2路归并排序，整个归并排序需进行 log2n 趟（遍），共计移动 n log2n次记录。

(即移动到新表中的总次数！共log2n趟，每趟都要移动n个元素)8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 H, C, Q, P, A, M, S, R, D, F, X ,Y；初始步长为4的希尔（shell）排序一趟的结果是P, A, C, S, Q, D, F, X , R, H,M, Y；二路归并排序一趟扫描的结果是H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟扫描的结果是F, H, C, D, P, A, M, Q, R, S, Y，X；堆排序初始建堆的结果是A, D, C, R, F, Q, M, S, Y，P, H, X。

9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

数据结构第十章 排序

数据结构第十章 排序
7
10.2 插入排序 插入排序
直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序
10.2.1 直接插入排序
基本操作：将一个记录插入到已排好序的有序表中， 从而得到一个新的、记录数增1的有序表。
例:有一组待排序的记录的关键字初始序列如下:
(49,38,65,97,76,13,27,49`)
（4）归并排序 （5）基数排序
按内排过程中所需的工作量分类：
（1）简单的排序方法，其时间复杂度为O(n×n)
（2）先进的排序方法，其时间复杂度为O(nlogn);
（3）基数排序，其时间复杂度为O(d(n+rd))
排序算法的两种基本操作：
（1）比较两个关键字的大小； （2）将记录从一个位置移至另一个位置；
算法实现的关键设计:
将d看成是一个循环数组,并设两个指针first和final分别指示排序过 程中得到的有序序列中的第一个记录和最后一个记录在d中的位置.
例:有一组待排序的记录的关键字初始排列如下:
(49,38,65,97,76,13,27,49`) 16
[初始关键字] 49 38 65 97 76 13 27 49`
18
10.2.3 希尔排序 从直接插入排序
待排序序列基本有序可提高效率 回顾 待排序序列的记录数n很小时可提高效率
希尔排序的基本思想:
先将整个待排记录序列分割成为若干子序列分别进行
直接插入排序,待整个序列中的记录“基本有序”时,再对 全
体记例录:有进一行组一待次排直序接的插记入录排的序关. 键字初始排列如下: (49,38,65,97,76,13,27,49`)
} 12
直接插入排序的性能分析: 10. 3
(1)空间:只需一个记录的辅助空间r[0].

第10章 排序(3)-数据结构教程(Java语言描述)-李春葆-清华大学出版社

第10章 排序(3)-数据结构教程(Java语言描述)-李春葆-清华大学出版社
11/41
12/41
排序区间是R[s..t]（为大问题），当其长度为0或者1时，本身就是有 序的，不做任何处理。
否则，其中间位置m，采用相同方法对R[s..m]和R[m+1..t]排好序（分 解为两个小问题），再调用前面的二路归并算法Merge(s，m，t)得到整 个有序表（合并）。
f(R，s，t) ≡ 不做任何事情
int i=low,j=mid+1,k=0;
//k是R1的下标,i、j分别为第1、2段的下标
while (i<=mid && j<=high)
//在第1段和第2段均未扫描完时循环
if (R[i].key<=R[j].key) //将第1段中的元素放入R1中
{ R1[k]=R[i];
i++; k++; }
空间复杂度为O(high-low+1)
else
//将第2段中的元素放入R1中
{ R1[k]=R[j];
j++; k++;
}
while (i<=mid)
//将第1段余下部分复制到R1
{ R1[k]=R[i];
i++; k++;
}
while (j<=high)
//将第2段余下部分复制到R1
{ R1[k]=R[j];
j++; k++;
}
for (k=0,i=low;i<=high;k++,i++)
//将R1复制回R中
R[i]=R1[k];
}
5/41

生态学：第10章 群落的分类与排序

生态学：第10章 群落的分类与排序

40 37 60 似
D 70 50 60
87 50 系
数
E 73 53 63 13
F 40 60 40 50 47
相异系数
1、计算样方间相异系数矩阵，Bray & Curtis (1975) 距离公式如下：
2、选择 x 轴的端点，即选择相异系数最大的两个样方（A、E）作为第一排序轴的端 点，其中一个坐标值记为0，另一个坐标值等于两端点的相异系数。
根据上述系统，中国植被分为： 10个植被型组、29个植被型、560多个群系、几千个群丛。
一、针叶林（植被型组） 1. 寒温性针叶林（植被型） 2. 温性针叶林 3. 温性针阔叶混交林 4. 暖性针叶林 5. 热性针叶林
二、阔叶林
落
6. 落叶阔叶林
叶
阔
7. 常绿、落叶阔叶混交林
叶
林
8. 常绿阔叶林
样方2
0
5.866
3′″
0
由此已将全部样方合成一组，得到整个聚合过程的树状图为：
6个样方组平均法的聚合分类结果
10.2 群落排序 (ordination) 10.2.1 排序的概念 ✓ 定义：把一个地区内所调查的群落样地，按照相似度 (similarity) 来排定各样地的
位序，从而分析各样地之间以及与生境之间的相互关系。
草甸
沼泽
水生植被
10.1.2 植物群落的命名 联名法（中国）：将各个层中的建群种或优势种和生态指示种的学名按顺序排列。 • 在前面冠以Ass. • 不同层的优势种用“－”相连（如：“马尾松 - 桃金娘 - 芒萁”群丛） • 某一层具共优种时，用“＋”相连（如：“马尾松 + 藜蒴 - 桃金娘 - 芒萁”群丛） • 当最上层的植物不是群落的建群种，而是伴生种或景观植物，这时用“＜”来表
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第10章排序一、选择题1．某内排序方法的稳定性是指( D )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( D )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3．下列排序算法中，其中（D ）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6. 快速排序方法在（ D ）情况下最不利于发挥其长处。

【燕山大学 2001 一、3 （2分）】A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序7. 以下序列不是堆的是( D )。

【西安电子科技大学 2001应用一、5 （2分）】A. (100,85,98,77,80,60,82,40,20,10,66)B. (100,98,85,82,80,77,66,60,40,20,10)C. (10,20,40,60,66,77,80,82,85,98,100)D. (100,85,40,77,80,60,66,98,82,10,20)8．下列四个序列中，哪一个是堆（ C ）。

【北京工商大学 2001 一、8 （3分）】A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,159．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

【北京航空航天大学 1999 一、8（2分）】A. 插入B. 选择C. 希尔D. 二路归并10．比较次数与排序的初始状态无关的排序方法是( D )。

【北方交通大学 2000 二、2（2分）】A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序11．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。

A. (2,5,12,16)26(60,32,72)B. (5,16,2,12)28(60,32,72)C. (2,16,12,5)28(60,32,72)D. (5,16,2,12)28(32,60,72) 【青岛大学 2000 三、4 （2分）】12．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序B. shell排序C. 堆排序D.冒泡排序【合肥工业大学 2001 一、3（2分）】13．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

【南京理工大学 1996 一、4 （2分）】A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，2014．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

【燕山大学 2001 一、4（2分）】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)15．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。

A．冒泡 B. 希尔 C. 快速 D. 堆【南京理工大学 2001 一、12 （1.5分）】16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ C ）算法，最费时间的是（ B ）算法。

A. 堆排序B. 快速排序C. 插入排序D. 归并排序【南开大学 2000 一、5】17. 就平均性能而言，目前最好的内排序方法是( D )排序法。

【西安电子科技大学 1998 一、9 (2分）】A. 冒泡B. 希尔插入C. 交换D. 快速18．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序【清华大学 1998 一、2 （2分）】19．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ A ）A．直接插入排序 B．冒泡排序 C．简单选择排序【山东工业大学 1995 二、1 （2分）】20．下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

【南开大学 2000 一、4】【西北大学 2001 二、1】A. 堆排序B. 冒泡排序C. 快速排序D. 插入排序三、填空题1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动__。

【北京邮电大学 2001 二、7 （4分）】2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡_算法，最费时间的是_快速_算法。

【福州大学 1998 二、10 (2分)】3. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是简单选择_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是(2)直接插入排序（最小的元素在最后时）_。

【中国人民大学 2001 一、3 （2分）】4．直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

【南京理工大学 2001 二、8 （2分）】5 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__3___趟，写出第一趟结束后，数组中数据的排列次序(10,7,-9,0,47,23,1,8,98,36)。

【南京理工大学 1997 三、5 （2分）】6．堆是一种有用的数据结构。

试判断下面的关键码序列中哪一个是堆___4_____。

①16，72，31，23，94，53 ②94，53，31，72，16，23 ③16，53，23，94，31，72④16，31，23，94，53，72 ⑤94，31，53，23，16，727．堆是一种有用的数据结构. 堆排序是一种_(1)选择_排序，堆实质上是一棵_(2)完全二叉树_结点的层次序列。

【山东工业大学 1996 三、1 （5分）】8．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_（Q,A,C,S,Q,D,F,X,R,H,M,Y）_；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_(F,H,C,D,Q,A,M,Q,R,S,Y,X)_。

【北京大学 1997 一、4 （4分）】四、应用题1. 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。

【大连海事大学 1996 七、3 (４分)】2. 对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。

（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。

【合肥工业大学 1999 四、4 （5分）】125，11，设D=7D=31，11，2，5，15，8，14，34，20，22，66，100，44，76，125D=1 1，2，5，8，11，14，15，20，22，34，44，66，76，100，1253．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 【武汉交通科技大学 1996 二、5 (6分)】初始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84该排序方法为快速排序。

4．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80， 82，85，98，100【山东大学 1998 四 (5分)】【山东工业大学 2000 四（5分）】答案: (1)是大堆； (2)是大堆；（4）是小堆；(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，205．给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；(1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔））【上海交通大学 1999 八（9分）】(1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 （ D=5）(2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,186. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：【南开大学 1998 八 (12分)】(1) 归并排序每归并一次书写一个次序。

(2) 快速排序每划分一次书写一个次序。

(3) 堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

(1)2路归并第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88(3)堆排序建大堆:58,47,51,29,18,12,25,10；①51,47,25,29,18,12,10,58；②47,29,25,10,18,12,51,58；③29,18,25,10,12,47,51,58；④25,18,12,10,29,47,51,58；⑤18,10,12,25,29,47,51,58；⑥12,10,18,25,29,47,51,58；⑦10,12,18,25,29,47,51,58。