第八章 排 序

第八章排序：习题习题一、选择题1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序2．设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。

A.冒泡排序B.快速排序C.堆排序D.基数排序3．在待排序的记录序列基本有序的前提下，效率最高的排序方法是( )。

A.插入排序B.选择排序C.快速排序D.归并排序’4．不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。

A.保持不变B.保持相反C.不定D.无关5．内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。

A. 内存储器B.外存储器C.内存储器和外存储器D.寄存器6．用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。

A.1B.2C.n-lD.n7．直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。

A.1B.2C.3D.n8．用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。

A.1B.2C.n-lD.n9．归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。

A.1B.2C.n-lD.n10．直接插入排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树11．冒泡排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树12．快速排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树13．排序方法中，从未排序序列中依次取出记录与已排序序列（初始时为空）中的记录进行比较，将其放入已排序序列的正确位置上的方法，称为( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序14．每次把待排序的记录划分为左、右两个子序列，其中左序列中记录的关键字均小于等于基准记录的关键字，右序列中记录的关键字均大于基准记录的关键字，则此排序方法叫做( )。

第一章绪论1. 从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2. 在下面的程序段中，对x的赋值语句的频度为（).For（k=1；k〈=n;k++)For（j=1；j〈=n；j++）x=x＋1；A．O(2n) B．O（n）C．O（n2) D．O（log2n)3。

采用顺序存储结构表示数据时，相邻的数据元素的存储地址( ).A．一定连续B．一定不连续C．不一定连续D．部分连续、部分不连续4. 下面关于算法的说法,正确的是（）.A．算法的时间复杂度一般与算法的空间复杂度成正比B．解决某问题的算法可能有多种，但肯定采用相同的数据结构C．算法的可行性是指算法的指令不能有二义性D．同一个算法,实现语言的级别越高，执行效率就越低5。

在发生非法操作时,算法能够作出适当处理的特性称为（）.A．正确性B．健壮性C．可读性D．可移植性第二章线性表1. 线性表是（）。

A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列,可以为空D．一个无限序列，不能为空2．对顺序存储的线性表,设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

A．n/2 B．(n＋1）/2 C．（n－1)/2 D．n3．线性表采用链式存储时，其地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4．用链表表示线性表的优点是( ）。

A．便于随机存取B．花费的存储空间较顺序存储少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ )存储方式最节省运算时间。

A．单链表B．双链表C．单循环链表D．带头结点的双向循环链表6．下面关于线性表的叙述，错误的是（）.A．线性表采用顺序存储，必须占用一片地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储,不必占用一片地址连续的单元D．线性表采用链式存储，不便于进行插入和删除操作7．单链表中，增加一个头结点的目的是为了( ）.A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储8．在单链表指针为p的结点之后插入指针为s结点，正确的操作是（）。

《数据结构（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．知识结构：2．基本要求：理解乘法原理与加法原理；理解排列与组合的概念；掌握将实际问题抽象为排列或组合模型；能应用排列数与组合数公式进行计算．理解二项式定理的概念，掌握二项式定理的通项公式，能解决二项式展开式的特定项问题及系数问题。

3．重点问题：（1）实际问题中的排列与组合模型的建立、排列数与组合数的计算公式；（2）求解二项式展开式的特定项问题及系数问题4．思想方法与能力：（1）将实际问题抽象为数学模型的建模思想；（2）应用两个基本计数原理时，形成思辨的品质。

8.1 排列与组合知识梳理1． 两个基本原理： （１）乘法原理：分步 （２）加法原理：分类 2．排列与排列数公式!(1)(2)21()!m n n P n n n n m =⋅-⋅-⋅⋅⋅=-（*n m N m n ∈≤、，）四种排列（１）优待排列：先考虑特殊元素或特殊位置，再考虑一般元素（２）集团排列：把相邻的元素看成一个元素进行排列，再集团内部作全排列 （３）间隔排列：先排其它元素，再在其形成的空挡中选择插入 （４）定序排列：把总的排列数除以需定序的元素全排列 ３．组合与组合数公式及其性质(1)(2)(1)!(1)21!()!m n n n n n m n C m m m n m ⋅-⋅-⋅⋅-+==⋅-⋅⋅⋅-（*n m N m n ∈≤、，）三种组合（１）优待组合：先考虑特殊元素，再考察一般元素 （２）分类组合：至少、至多问题进行分类讨论 （３）先选再排：先组合再排列4．乘法原理与加法原理的区分，关键是“分步”与“分类” 排列问题与组合问题的区分，关键是“有序”与“无序”典型例题【例１】（1）6名同学报名参加数学、物理、英语竞赛，每人报且仅报一科，则不同的报名方法共有多少种？（2）从1到40的正整数中每次取出2个数，使它们的和大于40，则不同的取法共有多少种？解 （1）6名同学每人报一科竞赛，可以分成6个步骤完成：先确定第一位同学报名，有3种方法；再确定第二位同学报名，也有3种方法；依此类推，最后一位同学报名，也有3种方法．根据分步计数原理，不同的报名方法种数是333333729N =⨯⨯⨯⨯⨯=． 答：不同的报名方法共有729种．（2）设{}{}1232021222340A ,,,,,B ,,,,==，符合题设要求的取法可分为两类：第一类是从B 中任取两个数，有220C 种；第二类是从A 中取一个数，B 中取一个数，若A 中取数1，则B 中只有取数40这1种取法，若A 中取数2，则B 中对应的有取数39或取数40这2种取法，类似地，在A 中分别取数3420,,,，则在B 中分别有3420,,,种取法，故共有12320210++++=种取法．根据分类计数原理，不同的取法种数为220210400N C =+=．答：不同的取法共有400种．说明 解决计数问题，首先要明确“完成一件事”是需分类还是分步，再合理地选用分类计数原理与分步计数原理使问题获解．分类时要注意选好分类标准，设计好分类方案，防止重复和遗漏．【例2】让6名学生排成一排，按下列条件，分别求排法种数： （1）甲必须在排头；（2）甲不在排头也不在排尾； （3）甲不在排头，乙不在排尾；（4）甲、乙必须相邻； （5）甲、乙、丙在一起；（6）甲、乙不相邻；（7）甲、乙、丙两两不相邻；（8）甲在乙的左边；（9）甲在乙的左边，乙在丙的左边 解：（1）120；（2）480；（3）504；（4）240；（5）144； （6）480；（7）144；（8）360；（9）120说明 主要掌握排列的四种形式，即优待排列、集团排列、间隔排列、定序排列【例3】从6名女同学和4名男同学中选出4名组建小组，按下列条件，分别求选法种数： （1）甲必须参加；（2）甲必须参加，而乙不参加；（3）甲、乙至少有一人参加； （4）甲、乙至多有一人参加； （5）至少有两名女同学（6）担任不同的职务（7）甲担任组长，其余3人担任不同的职务 解：（1）84；（2）56；（3）140；（4）182；（5）185；（6）5040；（7）504说明 主要掌握三种组合形式，即含特殊元素的组合、有关分类讨论的问题（至少、至多问题）、先选再排问题【例4】由０～９这十个数字组成没有重复数字的五位数，根据下列条件求五位数的个数： （１）五位数； （２）五位奇数； （３）五位偶数（4）个位数字比十位数字大的五位数； （5）比51637大的五位数（6）从5个偶数中选出3个，从5个奇数中选出2个组成五位数 解：（1）27216；（2）13440；（3）13776；（4）13608；（5）14600；（6）10560【备用1】一天要排语文、数学、英语、生物、体育、班会六节课（上午四节，下午二节），要求上午第一节不排体育，数学课排在上午，班会课排在下午，问共有多少种不同的排课方法？解法一:（从数学课入手）（第一类）数学排在第一节，班会课排在下午，其余四科任排，得4844121==A A N （第二类）数学排在上午另三节中的一节，班会排在下午，体育排在余下（不会第一节）三节中的一节，其余三科任排，得11133233108A A A A =∴ 共有排法1561084821=+=+=N N N （种）解法二（从体育课入手）（第一类）体育课在上午 1111313323108N A A A A =⋅⋅⋅=（第二类）体育课在下午 2422448N A A =⋅=共有排法1564810821=+=+=N N N （种） 【备用】2160的正因数有多少个？解：432160235=，235p αβγ=，所有有54240N =⋅⋅=个。

第八章序列图和协作图本章要点⏹基础内容：序列图和协作图的激活和链⏹重点掌握：序列图和协作图中的对象、消息⏹一般了解：序列图中的分支和从属流导读⏹在标识出系统的类图之后，除了显示了实现用例的组成结构外，还需要描述这些类的对象是如何交互来实现用例功能的，即不但需要类图模型，还需要将它转化为交互图模型。

⏹交互图为基于交互的对象行为建模，是UML用于描述对象之间信息的交互过程的方法，是描述对象间协作关系的模型。

交互图指出对象如何通过协作来完成用例中捕获的业务流程。

⏹UML中的交互图以图形的形式表示方法调用的具体过程，主要有顺序图和协作图两种形式。

UML提供了一系列的图支持面向对象的分析和设计，顺序图和协作图都输描述系统动态视图的交互图。

其中顺序图描述了以时间顺序组织的对象之间的交互活动，协作图强调收发消息的对象的组织结构。

8.1 顺序图概述⏹顺序图由类角色、生命线、激活期和消息组成。

⏹顺序图用于表示一个交互，该交互是协作中各种类元角色间的一组消息交换，侧重于强调时间顺序。

顺序图捕获系统运行中对象之间有顺序的交互，强调的是消息交互的时间顺序。

⏹顺序图用于表示用例中的行为顺序。

顺序图将交互关系表示为一个二维图。

横向轴代表了在协作中各独立对象的类元角色。

纵向轴是时间轴，时间沿竖线向下延伸。

所谓交互是指在具体语境中由为实现某个目标的一组对象之间进行交互的一组消息所构成的行为。

交互——语境对象相互链接的地方就有交互（1）具有对象协作的系统、子系统语境中如：Web商务系统，客户对象、服务器对象间交互（2）操作实现语境中如：操作的参数、局部变量、全局对象相互交互完成操作的实现算法（3）类语境中如：通过交互显示类的属性是如何相互协作的交互——对象和角色⏹交互中的对象可以是具体事物⏹也可以是原型化事物⏹可以是类、构件、节点、用例的实例，也可以是抽象类、接口的间接实例UML提供的交互机制通常用于为以下两种情况进行建模：（1）控制流方面进行建模可针对一个用例、一个业务操作过程或系统过程，也可针对整个系统。