发布时间 : 星期五 文章校本教材各章习题及答案更新完毕开始阅读
练习题目
一、单选题
1．内部排序方法的稳定性是指( )。
A．该排序算法不允许有相同的关键字记录 B ．该排序算法允许有相同的关键字记录 C．平均时间为0（nlogn）的排序方法 D．以上都不对 2. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方
法是（ ）。
A. 快速排序 B . 堆排序 C. 归并排序 D. 直接插入排序 3. 12．排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B . 选择 C. 冒泡 D. 快速
4. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 ，则采用的排序是 ( )。
A. 选择 B . 冒泡 C. 快速 D. 插入
5. 有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。
A．下面的B ，C，D都不对。 B ．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
6. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）
方法最快。
A．起泡排序 B ．快速排列 C．Shell排序 D．堆排序 E．简单选择排序
7. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A. 插入 B . 选择 C. 希尔 D. 二路归并
8. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ ）。
A. 选择 B . 冒泡 C. 插入 D. 堆 9. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
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) 10. 归并排序中，归并的趟数是( )。
A．O（n） B ．O(logn) C．O(nlogn) D．O(n*n) 二、判断题：
1．内部排序要求数据一定要以顺序方式存储。 （ ）
2．排序算法中的比较次数与初始元素序列的排列无关。（ ）
3．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 4．堆肯定是一棵平衡二叉树。（ ） 5．堆排序是稳定的排序方法。（ ） 6．归并排序辅助存储为O（1）。（ ）
7．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ） 三、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。
2. 直接插入排序用监视哨的作用是_______。
3. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。
4. 设有字母序列{Q,D,F,X,A,P,N,B ,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。
实验题目
1、给出关键字序列(27，18，21，77，26，45，66，34)，采用快速排序方法将其由小到大排序。
2、采用冒泡排序对关键字序列(18,16,14,12,10,8),进行从小到大的排序。 3、对关键字序列(50,72,43,85,75,20,35，45，65，30)进行简单选择排序。
练习题目答案
一、单选题 1 D 1 × 2 C 2 × 3 C 4 A 3 × 5 A 4 × 6 D 7 A 5 × 8 A 6 × 9 B 10 B 7 × 二、判断题
三、填空题 1. 比较，移动
2. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 3. 3，(10，7，-9，0，47，23，1，8，98，36) 4. {D，Q，F，X，A，P，B，N，M，Y，C，W}
第十章外部排序
10.5总结与提高
10.5.1主要知识点
1．外部排序的两个阶段，归并过程。
2．外部排序过程中进行外存读/写次数的计算方法。 3．实现多路归并败者树的方法。 4．置换—选择排序的过程。 5．最佳归并树的构造方法。
10.5.2典型例题
以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。 内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。因为归并的趟数s=?logkm?,其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多（k）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。
练习题目
一、单选题
1. 采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （）
A． 有关 B ．无关
2. 文件经过内部排序得到100个初始归并段，若要是多路归并3趟完成，则应取归并的路数至少为（）。
A．3 B ．4 C．5 D．6 二、判断题
1．外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( )
2．在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。( )
3．为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。( )
4．排序速度，进行外排序时，必须选用最快的内排序算法。( ) 5．在完成外排序过程中，每个记录的I/O次数必定相等。( )
6．影响外排序的时间因素主要是内存与外设交换信息的总次数。( ) 三．填空题
1． 外部排序的基本操作过程是_______和_______。
2．设输入的关键字满足k1>k2>?>kn，缓冲区大小为m，用置换-选择排序方法可产生____个初始归并段。
实验题目
设输入文件包含以下记录：14, 22, 7, 24, 15, 16, 11, 100, 10, 9, 20, 12, 90, 17, 13, 19, 26, 38, 30, 25, 50, 28, 110, 21, 40。现采用败者树生成初始归并段，请将其排序。
练习题目答案
一、单选题 1 A 1 × 2 C 2 √ 3 × 4 × 5 × 6 √ 二、判断题 三、填空题
1．生成有序归并段（顺串），归并 2．?n/m?
附录
数据结构试卷Ⅰ
一、选择题（每空2分，共30分）
1．一个完整的算法应该具有的特性是????????（B）
A．确定性、有穷性和稳定性
B．输入、输出、可行性、确定性和有穷性 C．易读性、稳定性和安全性 D．可行性、确定性和有穷性
2．分析以下程序段的时间复杂度??????????（C） i=1;j=0;
while(i+j<=n) if(i>j) j++; else i++;
A．O(n/2) B．O(nlogn) C．O(n) D．O(n2) 3．单链表中，增加一个头结点的目的是为了?????（C）
A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现
D．说明单链表是线性表的链式存储
4．以下数据结构中，是线性数据结构?????????（D）
A．树B．图
C．散列 D．栈