第八章 排序练习答案

《数据结构（C语言版第2版）》（严蔚敏著）第八章练习题答案第8章排序1．选择题（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。

A．归并排序B．冒泡排序C．插入排序D．选择排序答案：C（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

A．归并排序B．冒泡排序C．插入排序D．选择排序答案：D（3）对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序答案：B解释：对关键字进行冒泡排序，关键字逆序时比较次数最多。

（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。

A．n+1B．n C．n-1D．n(n-1)/2答案：D解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1次，即(n-1)+(n-2)+…+1=n(n-1)/2。

（5）快速排序在下列（）情况下最易发挥其长处。

A．被排序的数据中含有多个相同排序码B．被排序的数据已基本有序C．被排序的数据完全无序D．被排序的数据中的最大值和最小值相差悬殊答案：C解释：B选项是快速排序的最坏情况。

（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)答案：B解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。

（7）若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，79答案：C（8）下列关键字序列中，（）是堆。

数据结构第八章习题及答案习题八查找一、单项选择题1．顺序查找法适合于存储结构为（）的线性表。

A．散列存储 B. 顺序存储或链式存储C. 压缩存储D. 索引存储2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n3．适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法（）。

A．正确 B. 错误7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。

(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分快查找B. 顺序查找C. 折半查找D. 基于属性9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D. (100，80， 60， 90，120，130，110)10．下图所示的4棵二叉树,( )是平衡二叉树。

A. 3, 5, 7, 9, 12, 10, 15, 1B. 3, 5, 9, 7, 12, 10, 15, 1单项选择题若对 n 个元素进行直接插入排序，在进行第 i 趟排序时， 则需要移动元素的次数为(在对 n 个元素进行直接插入排序的过程中， A. O(1) B. O(log 2n)算法的空间复杂度为( )。

2C. O(n 2)D. O(nlog 2n)对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中 需要移动元素次数最多的序列为( )。

排序》练习题1.2.3.4.5.6.7.8.9.10.11.12. A. j-i B. i-j-1 C. i-j D. i-j+1在对 n 个元素进行直接插入排序的过程中，共需要进行( A. n B. n+1 C. n-1 )趟。

D. 2n在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为( 2A. O(1)B. O(log 2n)C. O(n 2) D. O(n))。

在对 n 个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等 或只差一个，则排序的时间复杂度为( A. O(1) B. O(nlog 2n) )。

2C. O(n 2)D. O(n) 设一组初始记录关键字序列 (5，2，6， 进行比较，则第一趟冒泡排序的结果为( (A) 2 ，5，3，6， 8(C) 2 ，3，5，6， 8 3，8)，利用冒泡排序进行升序排序，且排序中从后往前 )。

(B) 2 ，5，6，3，8(D) 2 ，3，6，5，8)。

假定元素 r[i+1] 的插入位置为 r[j] ， A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1C. 5, 1, 3, 7, 9D. 5, 7, 9, 3, 1在对 n 个元素进行堆排序的过程中，时间复杂度为(2A. O(1)B. O(log 2n)C. O(n 2))。

第八章排序〔答案〕一、选择题1．一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为。

A).78,47,57,39,41,85 B).85,78,57,39,41,47C).85,78,57,47,41,39 D).85,57,78,41,47,392．一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为。

A).38,40, 48, 52,79,84 B).40,38, 48,79, 52,84C).40,38, 48, 52,79,84 D).40,38, 48,84, 52,793．一组记录的排序码为26,48,16,35,78,82,22,40,37,72.,其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为。

A).16, 26,35,48, 22,40, 78,82, 37,72B).16, 26,35,48, 78,82, 22, 37,40,72C).16, 26,48,35, 78,82, 22, 37,40,72D).16, 26,35,48, 78, 22, 37,40,72,824.以下序列不是堆的是A.105,85,98,77,80,61,82,40,22,13,66B.105,98,85,82,80,77,66,61,40,22,13C.13,22,40,61,66,77,80,82,85,98,105D.105，85,40,77,80,61,66,98,82,13,225、下列四种排序方法中，不稳定的方法是A.直接插入排序B.冒泡排序C.归并排序D. 简单选择排序6、对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。

在第1趟划分过程中，元素移动次数最多的是序列A.71,75,82,90, 24,18,10,68B.71,75,68,23,10,18,90,82C.82,75,71,18,10,90,68,24D.24,10,18,71,82,75,68,907.下列排序算法中，___________算法可能在初始数据有序时，花费的时间反而最多。

Java语言程序设计（郑莉）第八章课后习题答案1.进程和线程有何区别，Java是如何实现多线程的。

答：区别：一个程序至少有一个进程,一个进程至少有一个线程；线程的划分尺度小于进程；进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

Java程序一般是继承Thread类或者实现Runnable接口，从而实现多线程。

2.简述线程的生命周期，重点注意线程阻塞的几种情况，以及如何重回就绪状态。

答：线程的声明周期：新建-就绪-（阻塞）-运行--死亡线程阻塞的情况：休眠、进入对象wait池等待、进入对象lock池等待；休眠时间到回到就绪状态；在wait池中获得notify（）进入lock池，然后获得锁棋标进入就绪状态。

3.随便选择两个城市作为预选旅游目标。

实现两个独立的线程分别显示10次城市名，每次显示后休眠一段随机时间（1000毫秒以内），哪个先显示完毕，就决定去哪个城市。

分别用Runnable接口和Thread类实现。

（注：两个类，相同一个测试类）//Runnable接口实现的线程runable类publicclarunnableimplementRunnable{privateStringcity;publicr unnable(){}publicrunnable(Stringcity){thi.city=city;}publicvoidrun(){for(inti=0;i<10;i++){Sytem.out.println(city);try{//休眠1000毫秒。

Thread.leep(1000);}catch(InterruptedE某ceptione){e.printStackTrace();}}}}//Thread类实现的线程thread类publicclarunnablee某tendThread{privateStringcity;publicrunnable(){}publicrunnable(Stringcity){thi.city=city;}publicvoidrun(){for(inti=0;i<10;i++){Sytem.out.println(city);try{//休眠1000毫秒。

2017年智慧树选修课《职业生涯规划—体验式学习》课后练习答案?对应章节第一章1、【多选题】(20分)生涯可不可以规划？（C、D）A.可以规划B.不可以规划C.职业生涯规划提供信息、资料和经验的分享D.职业生涯规划是对于整个生涯的了解和投入正确2、【多选题】(20分)职业生涯规划涵盖什么？（A、B）A.职业生涯前、职业生涯中和职业生涯后B.人一生的规划C.企业的人力资源职业生涯规划D.对他人的职业生涯规划正确3、【判断题】(20分)职业生涯规划随着时空变化而调整，不同的时段不同的地方有不一样的职业生涯规划。

（对）A.对B.错正确4、【判断题】(20分)我们不仅是中国的大学生，也是世界中的大学生。

但我们只要关心自己、自己的国家即可。

（错）A.对B.错正确5、【判断题】(20分)职业生涯规划这门课老师和学生的关系不是以老师为主体的，是双主体。

（对）A.对B.错正确名称职业生涯规划——体验式学习对应章节第二章1、【判断题】(20分)体验式学习具有高峰体验的经验。

（对）A.对B.错正确2、【判断题】(20分)体验式学习在学习态度上，接纳、欢迎、尊重和诚实，不仅要帮助自己，还要学习怎样帮助别人才能解决问题。

（对）A.对B.错正确3、【判断题】(20分)体验式学习是以内容为本的。

（错）A.对B.错正确4、【判断题】(20分)体验式学习是每一个人主动的，参与的，投入的，互动的。

（对）A.对B.错正确5、【判断题】(20分)传统式学习在遇到问题时，习惯性的理由化和合理化。

（对）A.对B.错正确?名称职业生涯规划——体验式学习?对应章节第三章1、【多选题】(20分)活在当下是什么？（A、C）A.不要为倒翻的牛奶去哭泣B.说了要做，但是可以缓一缓C.把每一天都当做余生的第一天去过D.不能服从你的冲动正确2、【单选题】(20分)濒死五阶段是哪位提出的？（A）A.库柏勒·罗斯B.卡尔·罗杰斯C.乔治·莱尔D.桑德斯正确3、【单选题】(20分)4、濒死五阶段的顺序是什么？（C）A.沮丧、否认、妥协（讨价还价）、愤怒、接受B.沮丧、愤怒、否认、妥协（讨价还价）、接受C.愤怒、否认、妥协（讨价还价）、沮丧、接受D.否认、愤怒、妥协（讨价还价）、沮丧、接受正确4、【多选题】(20分)下面哪句话是正确的？（C、D）A.活人的事情都还没照顾好，没必要去管死人的事情。

第八章查找1．若为大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定值K的记录；（2）查找成功，且表中只有一个关键字等于给定值K的记录；（3）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。

此时平均查找长度应考虑找到所有记录时所用的比较次数。

【解答】在已知的有序表进行顺序排序，可对顺序查找算法进行改进。

（1）不相同；（2）相同；（3）不相同。

2．画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

【解答】等概率时查找成功的平均查找长度=(1+2*2+3*4+4*3)/10=2.93．已知下列长度为7的表（50, 40, 30, 60, 55, 58, 59）。

（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，求其在等概率情况下查找成功的平均查找长度。

（2）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。

【解答】(1)等概率情况下查找成功的平均查找长度=(1+2*2+3*2+4+5)/7=20/7(2)等概率情况下查找成功的平均查找长度=(1+2*2+3*4)/7=17/74．在地址空间为0~16的散列区中，自己构造哈希函数，对以下关键字序列构造哈希表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）（1）用线性探测开放定址法处理冲突；（2）用链地址法处理冲突。

并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。

【解答】略。

第8 章查找课后习题解答一、选择题1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（）次比较后查找成功。

A 2B 3C 4D 5【解答】A2．已知10个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为62的结点所需比较次数为（）。

A 2B 3C 4D 5【解答】B3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。

A 4B 5C 6D 7【解答】B4．按（）遍历二叉排序树得到的序列是一个有序序列。

A 前序B 中序C 后序D 层次【解答】B5一棵高度为h的平衡二叉树，最少含有个结点。

A 2hB 2 h -1C 2 h +1D 2 h -1【解答】D6．在散列函数H(k)= k mod m中，一般来讲，m应取（）。

A 奇数B 偶数C 素数D 充分大的数7.静态查找与动态查找的根本区别在于（）。

A 它们的逻辑结构不一样B 施加在其上的操作不同C 所包含的数据元素的类型不一样D 存储实现不一样【解答】B【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。

8. 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。

A 37/12B 62/13C 3 9/12D 49/13【解答】A，B9. 用n个键值构造一棵二叉排序树，其最低高度为（）。

A n/2B nC log2nD log2n+1【解答】D【分析】二叉排序树的最低高度与完全二叉树的高度相同10. 二叉排序树中，最小值结点的（）。

A 左指针一定为空B 右指针一定为空C 左、右指针均为空D 左、右指针均不为空【解答】A【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。

数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。

第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。

A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。

A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。