数据结构第八章参考答案.doc

习题81. 填空题(1) 排序的主要目的是为了以后对已排序的数据元素进行（_）。答案：查找(2) 对n个元素进行起泡排序，在（_）的情况下比较的次数最少，其比较次数为（_）；在（_）的情况下比较次数最多，其比较次数为（_）。答案：原始序列有序 n-1 原始序列逆序 n(n-1)/2(3) 对一组元素54,38,96,23,15,72,60,45,83进行直接插入排序，当第7个元素60插入到有序表时，寻找插入位置需比较（_）次。答案：3(4) 对一族元素54,38,96,23,15,72,60,45,83进行快速排序，在递归调用中使用的栈所能达到的最大深度为（_）答案：4(5) 对n个待排序元素序列进行快速排序，所需最好时间是（_），最坏时间是（_）。答案：O(nlogn) O(n2)(6) 利用简单选择排序对n个元素进行排序，最坏情况下，元素交换的次数为（_）。答案：n-1(7) 如果将序列50,16,23,68,94,70,73建成堆，只需把16与（_）交换。答案：50(8) 对于键值序列12,13,11,18,60,15,7,18,25,100，用筛选法建堆，必须从键值为（_）的结点开始。答案：60(9) 采用改进的冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为（_）。若A的初始状态为递减排序，则记录的交换次数为（_）。答案：n-1 n(n-1)/22. 单选题(1) 从未排序序列中依此取出一个元素与已排序序列中的元素依此进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。A.插入排序B. 选择排序C. 希尔排序D. 二路归并排序(2) 一个对象序列的排序码为46,79,56,38,40,84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。A. 38,46,79,56,40,84 B. 38,79,56,46,40,84C. 40,38,46,56,79,84 C. 38,46,56,79,40,84(3) 对二叉排序树进行（ ）遍历，可以得到该二叉树所有节点构成的排序序列。A. 前序B. 中序C. 后序D. 按层序(4) 当待排序列基本有序时，下列排序方法中（ ）最好。A. 直接插入排序B. 快速排序C. 堆排序D. 归并排序(5) 在下列排序算法中，在待排序的数据表已经为有序时，比较操作花费时间反而最多的是（ ）。A. 快速排序B. 希尔排序C. 冒泡排序D. 堆排序(6) 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。A. 堆排序B. 冒泡排序C. 快速排序D. 直接插入排序(7) 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ ）。A. 堆排序B. 冒泡排序C. 快速排序D. 希尔排序(8) 已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时间。A. 堆排序B. 插入排序C. 快速排序D. 直接选择排序(9) 下面给出的4种排序法中（ ）排序法是不稳定排序法。A. 插入B. 冒泡C. 二路归并D. 堆(10) 就平均性能而言，最快的排序方法是（ ）。A. 冒泡排序B. 希尔排序C. 快速排序D. 插入排序3. 判断以下序列是否为小（顶）根堆？若否，则以最少的移动次数将他们调整为小（顶）根堆。（要求画出最后的堆结构和线性序列）(1) (19,78,32,66,26,58,46,95,89,31)；(2) (113,98,69,35,68,25,43,19,31,55,16,29)。答案：(1) (19,26,32,66,31,58,46,95,89,78)(2) (16,19,25,31,55,29,43,35,113,98,68,69)4. 设有关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要求按照关键码值递增的次序进行排序。(1) 若采用初时步长为4的Shell（希尔）排序法，写出一趟排序的结果；(2) 若采用以第一个元素为分界元素（枢轴）的快速排序法，写出一趟排序的结果。答案：(1) (Q,A,C,S,Q,D,F,X,R,H,M,Y)(2) (F,H,C,D,Q,A,M,Q,R,S,Y,X)5. 试编写一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。6. 编写算法，实现将整形数组中的元素按照奇数和偶数分开，使奇数在原数组的前面，偶数在原