数据结构答案第8章.pdf

  1. 1、本文档共12页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第 8 章 排序技术 2005-07-14 第 8 章 排序技术 课后习题讲解 1. 填空题 ⑴ 排序的主要目的是为了以后对已排序的数据元素进行( )。 【解答】查找 【分析】对已排序的记录序列进行查找通常能提高查找效率。 ⑵ 对 n 个元素进行起泡排序,在( )情况下比较的次数最少,其比较次数为( )。在( )情况下比较 次数最多,其比较次数为( )。 【解答】正序, n-1 ,反序, n(n-1)/2 ⑶ 对一组记录( 54, 38, 96, 23, 15, 72, 60, 45, 83 )进行直接插入排序,当把第 7 个记录 60 插入到有序 表时,为寻找插入位置需比较( )次。 【解答】3 【分析】当把第 7 个记录 60 插入到有序表时,该有序表中有 2 个记录大于 60 。 ⑷ 对一组记录( 54, 38, 96, 23, 15, 72, 60, 45, 83 )进行快速排序,在递归调用中使用的栈所能达到的最 大深度为( )。 【解答】3 ⑸ 对 n 个待排序记录序列进行快速排序,所需要的最好时间是( ),最坏时间是( )。 【解答】O(nlog2n) ,O(n2) ⑹ 利用简单选择排序对 n 个记录进行排序,最坏情况下,记录交换的次数为( )。 【解答】n-1 ⑺ 如果要将序列( 50 ,16 ,23 ,68 ,94 ,70 ,73 )建成堆,只需把 16 与( )交换。 【解答】50 ⑻ 对于键值序列( 12 ,13 , 11 ,18 ,60 , 15,7 , 18,25 ,100 ),用筛选法建堆,必须从键值为( ) 的结点开始。 【解答】60 【分析】60 是该键值序列对应的完全二叉树中最后一个分支结点。 2. 选择题 ⑴ 下述排序方法中,比较次数与待排序记录的初始状态无关的是( )。 A 插入排序和快速排序 B 归并排序和快速排序 C 选择排序和归并排序 D 插入排序和归并排序 【解答】C 【分析】选择排序在最好、最坏、平均情况下的时间性能均为 O(n2) ,归并排序在最好、最坏、平均情况 下的时间性能均为 O(nlog2n) 。 ⑵ 下列序列中,( )是执行第一趟快速排序的结果。 A [da ,ax ,eb ,de ,bb] ff [ha ,gc] B [cd ,eb ,ax ,da] ff [ha ,gc ,bb] C [gc ,ax ,eb ,cd ,bb] ff [da ,ha] D [ax ,bb ,cd ,da] ff [eb ,gc ,ha] 【解答】A 【分析】此题需要按字典序比较,前半区间中的所有元素都应小于 ff ,后半区间中的所有元素都应大于 ff 。 ⑶ 对初始状态为递增有序的序列进行排序,最省时间的是( ),最费时间的是( )。已知待排序序列中 每个元素距其最终位置不远,则采用( )方法最节省时间。 A 堆排序 B 插入排序 C 快速排序 D 直接选择排序 【解答】B,C,B 【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。 ⑷ 堆的形状是一棵( )。 A 二叉排序树 B 满二叉树 C 完全二叉树 D 判定树 【解答】C 【分析】从逻辑结构的角度来看,堆实际上是一种完全二叉树的结构。 ⑸ 当待排序序列基本有序或个数较小的情况下,最佳的内部排序方法是( ),就平均时间而言,( )最 佳。 A 直接插入排序 B 起泡排序 C 简单选择排序 D 快速排序 【解答】A ,D ⑹ 设有 5000 个元素,希望用最快的速度挑选出前 10 个最大的,采用( )方法最好。 A 快速排序 B 堆排序 C 希尔排序 D 归并排序 【解答】B 【分析】堆排序不必将整个序列排序即可确定前

文档评论(0)

tianya189 + 关注
官方认证
内容提供者

该用户很懒,什么也没介绍

认证主体阳新县融易互联网技术工作室
IP属地上海
统一社会信用代码/组织机构代码
92420222MA4ELHM75D

1亿VIP精品文档

相关文档