数据结构第10章习题.ppt

第10章习题 一 选择题 1 下列内部排序算法中 北京工业大学2000一 1 10分每问2分 A 快速排序B 直接插入排序C 二路归并排序D 简单选择排序E 起泡排序F 堆排序 1 其比较次数与序列初态无关的算法是 dc 2 不稳定的排序算法是 adf 3 在初始序列已基本有序 除去n个元素中的某k个元素后即呈有序 k n 的情况下 排序效率最高的算法是 b 4 排序的平均时间复杂度为O n logn 的算法是 acf 为O n n 的算法是 bde 2 比较次数与排序的初始状态无关的排序方法是 d 北方交通大学2000二 2 2分 A 直接插入排序B 起泡排序C 快速排序D 简单选择排序3 数据序列 8 9 10 4 5 6 20 1 2 只能是下列排序算法中的 c 的两趟排序后的结果 合肥工业大学1999一 3 2分 A 选择排序B 冒泡排序C 插入排序D 堆排序4 数据序列 2 1 4 9 8 10 6 20 只能是下列排序算法中的 a 的两趟排序后的结果 快速排序B 冒泡排序C 选择排序D 插入排序5 对序列 15 9 7 8 20 1 4 进行排序 进行一趟后数据的排列变为 4 9 1 8 20 7 15 则采用的是 c 排序 南京理工大学1998一 8 2分 A 选择B 快速C 希尔D 冒泡 6 若上题的数据经一趟排序后的排列为 9 15 7 8 20 1 4 则采用的是 c 排序 南京理工大学1998一 9 2分 A 选择B 堆C 直接插入D 冒泡7 下列排序算法中 c 排序在一趟结束后不一定能选出一个元素放在其最终位置上 选择B 冒泡C 归并D 堆8 下列排序算法中 d 算法可能会出现下面情况 在最后一趟开始之前 所有元素都不在其最终的位置上 南开大学2000一 4 西北大学2001二 1 A 堆排序B 冒泡排序C 快速排序D 插入排序 9 用直接插入排序方法对下面四个序列进行排序 由小到大 元素比较次数最少的是 c A 94 32 40 90 80 46 21 69B 32 40 21 46 69 94 90 80C 21 32 46 40 80 69 90 94D 90 69 80 46 21 32 94 40 北方交通大学2001一 15 2分 10 在含有n个关键字的小根堆 堆顶元素最小 中 关键字最大的记录有可能存储在 d 位置上 A n 2 B n 2 1C 1D n 2 2 中科院计算所2000一 4 2分 11 在对n个元素的序列进行排序时 堆排序所需要的附加存储空间是 b 西安电子科技大学2001应用一 10 2分 A O log2n B O 1 C O n D O nlog2n 12 就排序算法所用的辅助空间而言 堆排序 快速排序 归并排序的关系是 a A 堆排序 快速排序 归并排序B 堆排序 归并排序 快速排序C 堆排序 归并排序 快速排序D 堆排序 快速排序 归并排序E 以上答案都不对 西安交通大学1996三 1 3分 13 将两个各有N个元素的有序表归并成一个有序表 其最少的比较次数是 a A NB 2N 1C 2ND N 1 二 判断题 1 在执行某个排序算法过程中 出现了排序码朝着最终排序序列位置相反方向移动 则该算法是不稳定的 f 上海交通大学1998一 18 2 中序周游 遍历 平衡的二叉排序树 可得到最好排序的关键码序列 t 中山大学1994一 4 2分 3 在任何情况下 归并排序都比简单插入排序快 f 北京邮电大学2000一 4 1分 4 在用堆排序算法排序时 如果要进行增序排序 则需要采用 大根堆 t 合肥工业大学2000二 10 1分 5 内排序要求数据一定要以顺序方式存储 f 南京理工大学1997二 2 2分 三 填空题 1 设用希尔排序对数组 98 36 9 0 47 23 1 8 10 7 进行排序 给出的步长 也称增量序列 依次是4 2 1则排序需 趟 写出第一趟结束后 数组中数据的排列次序 南京理工大学1997三 5 2分 2 若不考虑基数排序 则在排序过程中 主要进行的两种基本操作是关键字的 和记录的 北京邮电大学2001二 7 4分 3 分别采用堆排序 快速排序 冒泡排序和归并排序 对初态为有序的表 则最省时间的是 算法 最费时间的是 算法 福州大学1998二 10 2分 4 用链表表示的数据的简单选择排序 结点的域为数据域data 指针域next 链表首指针为head 链表无头结点 selectsort head p head while p q p r 2 while 3 if 4 q r r 5 tmp q data q data p data p data tmp p 6 南京理工大学2000三 2 6分 5 设有字母序列 Q D F X A P N B Y M C W 请写出按2路归并排序方法对该序列进行一趟扫描后的结果 北方交通大学2001二 7 四 应用题 1 我们知道 对于n个元素组成的线性表进行快速排序时 所需进行的比较次数与这n个元素的初始排序有关 问 西安电子科技大学2001计应用五 12分 中国矿业大学2000六 10分 1 当n 7时 在最好情况下需进行多少次比较 请说明理由 2 当n 7时 给出一个最好情况的初始排序的实例 3 当n 7时 在最坏情况下需进行多少次比较 请说明理由 4 当n 7时 给出一个最坏情况的初始排序的实例 1 在最好情况下 假设每次划分能得到两个长度相等的子文件 文件的长度n 2k 1 那么第一遍划分得到两个长度均为 n 2 的子文件 第二遍划分得到4个长度均为 n 4 的子文件 以此类推 总共进行k log2 n 1 遍划分 各子文件的长度均为1 排序完毕 当n 7时 k 3 在最好情况下 第一遍需比较6次 第二遍分别对两个子文件 长度均为3 k 2 进行排序 各需2次 共10次即可 2 在最好情况下快速排序的原始序列实例 4 1 3 2 6 5 7 3 在最坏情况下 若每次用来划分的记录的关键字具有最大值 或最小值 那么只能得到左 或右 子文件 其长度比原长度少1 因此 若原文件中的记录按关键字递减次序排列 而要求排序后按递增次序排列时 快速排序的效率与冒泡排序相同 其时间复杂度为O n2 所以当n 7时 最坏情况下的比较次数为21次 4 在最坏情况下快速排序的初始序列实例 7 6 5 4 3 2 1 要求按递增排序 快速排序在 的情况下最易发挥其长处 长沙铁道学院1998二 5 2分 最好每次划分能得到两个长度相等的子文件 设文件长度n 2k 1 第一遍划分得到两个长度 n 2 的子文件 第二遍划分得到4个长度 n 4 的子文件 以此类推 总共进行k log2 n 1 遍划分 各子文件长度均为1 排序结束 五 算法设计题 1 冒泡排序算法是把大的元素向上移 气泡的上浮 也可以把小的元素向下移 气泡的下沉 请给出上浮和下沉过程交替的冒泡排序算法 吉林大学2001二 3 9分 2 设待排序的文件用单链表作存储结构 其形式如下 TYPEpointer node node RECORDkey integer next pointer END 写出以head为头指针的选择排序算法 中山大学1999二 10分 3 非递归的快速排序算法