数据结构教程李春葆课后答案第10章内排序

李春葆《数据结构教程》（第4版）笔记和课后习题详解第8章图8.1复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。

采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。

抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。

（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。

②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。

③出度以顶点i为起点的出边的数目，称为该顶点的出度。

一个顶点的入度与出度的和为该顶点的度。

（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。

（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。

②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。

（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。

（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。

②路径长度路径长度是指一条路径上经过的边的数目。

（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。

数据结构（李春葆）习题与解析一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科。

1A.数据元素B.计算方法C.逻辑存储D.数据映像2A.结构B.关系C.运算D.算法2.数据结构被形式地定义为(K,R)，其中K是的有限集，R是K上的有限集。

1A.算法B.数据元素C.数据操作D.逻辑结构2A.操作B.映像C.存储D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是，算法分析的两个主要方面是。

1A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是，它必须具备输入、输出和等5个特性。

1A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法2A.可执行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。

第10章外排序一、单项选择题（1）以下关于外排序的叙述正确的是______。

A．外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花的时间完全由采用的内排序确定B．外排序所花的时间=内排序时间+外存信息读／写时间+内部归并所花的时间C．外排序并不涉及文件的读／写操作D．外排序完全可以由内排序来替代【答案】B【解析】外排序所花的时间由内排序时间、外存读写时间、内部归并时间三部分时间构成，因此AC两项错误，B项正确；外排序要将文件读取到内存中进行排序，但是由于文件大小可能会大于内存的最大容量，因此外排序不能完全由内排序替代。

（2）如果将一个由置换-选择排序得到的输出文件F1（含所有初始归并段）作为输入文件再次进行置换-选择排序，得到输出文件F2（含所有初始归并段），则F1和F2的差异是______。

A．F2中归并段的个数减少B．F2中归并段的最大长度增大C．F2和F1无差异D ．归并段个数及各归并段长度均不变，但F 2中可能存在与F 1不同的归并段【答案】C 【解析】当进行一次置换-选择排序后，文件的归并段即达到理想状态，无论再进行多少次排序，均不会发生变化，因此答案为C 项。

（3）采用败者树进行k 路平衡归并的外排序算法，其总的归并效率与k______。

A ．有关B ．无关【答案】A【解析】利用败者树进行k 路平衡归并不会影响总共需要的关键字比较次数，但是随着k 的增大，归并树的高度会减小，磁盘读/写的次数也就相应减少，从而提高总的归并效率，因此答案为A 项。

（4）对m 个初始归并段实施k 路平衡归并排序，所需的归并趟数是______。

A ．1B ．m/kC ．/m k ⎡⎤⎢⎥D ．log k m ⎡⎤⎢⎥【答案】D【解析】采用k 路归并，相应的归并树就有log k m ⎡⎤⎢⎥+1层，则需要归并的趟数为log k m ⎡⎤⎢⎥，答案为D 项。

（5）设有100个初始归并段，如果采用k 路平衡归并3趟完成排序，则k 值最小是______。

数据结构简明教程（第2版）配套练习题参考答案———————数据结构简明教程———————1.练习题1参考答案1.单项选择题（1）D （2）C （3）C （4）A （5）C （6）B （7）C （8）A （9）C （10）B 2.填空题（1）①逻辑结构 ②存储结构 ③运算（不限制顺序）（2）①线性结构 ②非线性结构（不限制顺序）（3）①数据元素 ②关系（4）①没有 ②没有（5）①前驱 ②一 ③后继 ④任意多个（6）任意多个（7）①顺序 ②链式 ③索引 ④哈希（不限制顺序）（8）①时间 ②空间（不限制顺序）（9）问题规模（通常用n 表示）。

（10）辅助或临时空间3.简答题（1）答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是处理步骤。

（2）答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2)，T 4(n )=O(n log 2n )。

（3）答：j =0，第1次循环：j =1，s =10。

第2次循环：j =2，s =30。

第3次循环：j =3，s =60。

第4次循环：j =4，s =100。

while 条件不再满足。

所以，其中循环语句的执行次数为4。

（4）答：语句s ++的执行次数2)2)(3(3)1()1(12121-+=++-+=+-=∑∑∑-=-==n n n n i n n i n i i nj。

（5）答：其中x ++语句为基本运算语句，∑∑∑=+==-=-==n i n i j ni n n i n n T 1112)1()(1)(=O(n 2)。

（6） 答：由于内循环j 的取值范围，所以i ≤n /2，则，该程序段的时间复杂度为O(n 2)。

∑∑∑-===--==2/122/124/))12((n i nij n i n i n m 3log 2n2.练习题2参考答案1.单项选择题（1）A （2）C （3）A （4）B （5）C（6）D （7）C （8）B （9）A （10）C（11）B （12）A （13）C （14）D （15）D（16）D （17）A （18）C （19）A （20）D2.填空题（1）L.length=0（2）O(1)（3）O(n)（4）n-i（5）①物理存储位置②指针域（6）①前驱　②O(n)（7）q=p->next; p->next=q->next; free(q);（8）s->next= p->next; p->next=s;（9）O(1)（10）L->next==L3.简答题（1）答：顺序存储结构中，逻辑上相邻元素的存储空间也是相邻的，无需额外空间表示逻辑关系，所以存储密度大，同时具有随机存取特性。

1．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。

A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

第九章查找一、填空题1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找) 。

2.线性有序表(a i，a2，a3,…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索_8 次。

设有100个结点，用二分法查找时，最大比较次数是_7_ ____________ 。

3•假设在有序线性表a[1..2O]上进行折半查找，则比较一次查找成功的结点数为1;比较两次查找成功的结点数为_2 ___________ ;比较四次查找成功的结点数为8 ,其下标从小到大依次是1,3,6,8,11,13,16,19 _ ，平均查找长度为 3.7 。

解：显然，平均查找长度二0( log 2n) <5次(25)。

但具体是多少次，则不应当按照公式ASL =U|°g2(n⑴来计算(即(21 X log 221) /20 = 4.6次并不正确！)。

因为这是在假设n = 2m-1 n 的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为=(1 + 2X 2+ 4X 3+ 8X 4+ 5X 5)= 74; ASL= 74/20=3.7 !!! 4•折半查找有序表(4, 6，12，20, 28, 38，50，70, 88，100)，若查找表中元素20,它将依次与表中元素28 , 6, 12, 20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。

6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n (n<m)个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n个关键码的散列地址都相同，贝U探测的总次数是n(n-1)/2= ( 1 土2+…+ n-1 )。

(而任一元素查找次数 < n-1)&设一哈希表表长M为100，用除留余数法构造哈希函数，即H( K) =K MOIP ( P<=M ,为使函数具有较好性能，P应选(97 )9、在各种查找方法中，平均查找长度与结点个数无关的是哈_______10、对线性表进行二分查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排列。

第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据与元素之间的关系是元素与集合之间的关系。

2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。

3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。

答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。

4．用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大和最小元素。

答：（1）算法如下：本算法的时间复杂度为O（n2）。

（2）算法如下：本算法的时间复杂度为O（1）。

（3）算法如下：本算法的时间复杂度为O（n）。

5．设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

第10章排序10.1 知识点分析1. 排序根本概念:〔1〕排序将数据元素的任意序列, 重新排列成一个按关键字有序〔递增或递减〕的序列的过程称为排序。

〔2〕排序方法的稳定和不稳定假设对任意的数据元素序列, 使用某个排序方法, 对它按关键字进展排序, 假设对原先具有一样键值元素间的位置关系, 排序前与排序后保持一致, 称此排序方法是稳定的；反之, 那么称为不稳定的。

〔3〕内排序整个排序过程都在内存进展的排序称为内排序, 本书仅讨论内排序。

〔4〕外排序待排序的数据元素量大, 以致内存一次不能包容全部记录, 在排序过程中需要对外存进展访问的排序称为外排序。

2. 直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中, 从而得到一个新的, 记录数增1的有序表。

3. 二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置, 然后挪动记录, 空出插入位置, 再进展插入的排序方法。

4. 希尔排序希尔排序的根本思想是: 先选取一个小于n的整数d1作为第一个增量, 把待排序的数据分成d1个组, 所有间隔为d1的倍数的记录放在同一个组内, 在各组内进展直接插入排序, 每一趟排序会使数据更接近于有序。

然后, 取第二个增量d2, d2< d1, 重复进展上述分组和排序, 直至所取的增量di=1〔其中di< di-1 < ……< d2< d1〕, 即所有记录在同一组进展直接插入排序后为止。

5. 冒泡排序冒泡法是指每相邻两个记录关键字比大小, 大的记录往下沉〔也可以小的往上浮〕。

每一遍把最后一个下沉的位置记下, 下一遍只需检查比拟到此为止；到所有记录都不发生下沉时, 整个过程完毕。

6. 快速排序快速排序法是通过一趟排序, 将待排序的记录组分割成独立的两局部, 其中前一局部记录的关键字均比枢轴记录的关键字小；后一局部记录的关键字均比枢轴记录的关键字大, 枢轴记录得到了它在整个序列中的最终位置并被存放好。

第10章内排序10.1 复习笔记一、排序的基本概念1．定义排序，就是整理表中的元素，使之按关键字递增或递减的顺序排列，本章仅讨论递增排序的情况。

其确切定义如下：输入：n个元素，R0，R1，…，R n-1，相应的关键字分别为k0，k1，…，k n-1。

输出：R i0，R i1，…，R in-1，使得k i0≤k i1≤…≤k in-1。

因此，排序算法就是要确定0，1，…，n-1的一种排列i0，i1，…，i n-1，使表中的元素依此排列整理后按关键字有序。

2．排序的稳定性（1）稳定如果待排序的表中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。

（2）不稳定若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意：排序算法的稳定性是针对所有输入实例而言的。

在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

3．内排序和外排序（1）内排序在排序过程中，若整个表都是放在内存中处理，排序时不涉及内、外存数据的交换，则称之为内排序。

内排序适用于元素个数不很多的小表。

（2）外排序若排序过程中要进行内、外存数据的交换，则称之为外排序。

外排序则适用于元素个数很多，不能一次将全部元素放入内存的大表。

内排序是外排序的基础。

（3）排序方法的其他分类①需要关键字比较的排序需要关键字比较的排序方法有插入排序、选择排序、交换排序和归并排序等。

②不需关键字比较的排序不需要关键字比较的排序方法有基数排序。

4．排序数据的组织在本章中，以顺序表作为排序数据的存储结构，假设关键字类型为整型。

待排序的顺序表中数据元素的类型定义如下：二、插入排序1．插入排序的思想及方法基本思想是：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止。

主要有两种插入排序方法，即直接插入排序和希尔排序。

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

数据结构简明教程（第2版）配套练习题参考答案———————数据结构简明教程———————1.练习题1参考答案1.单项选择题（1）D （2）C （3）C （4）A （5）C （6）B （7）C （8）A （9）C （10）B 2.填空题（1）①逻辑结构 ②存储结构 ③运算（不限制顺序）（2）①线性结构 ②非线性结构（不限制顺序）（3）①数据元素 ②关系（4）①没有 ②没有（5）①前驱 ②一 ③后继 ④任意多个（6）任意多个（7）①顺序 ②链式 ③索引 ④哈希（不限制顺序）（8）①时间 ②空间（不限制顺序）（9）问题规模（通常用n 表示）。

（10）辅助或临时空间3.简答题（1）答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是处理步骤。

（2）答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2)，T 4(n )=O(n log 2n )。

（3）答：j =0，第1次循环：j =1，s =10。

第2次循环：j =2，s =30。

第3次循环：j =3，s =60。

第4次循环：j =4，s =100。

while 条件不再满足。

所以，其中循环语句的执行次数为4。

（4）答：语句s ++的执行次数2)2)(3(3)1()1(12121-+=++-+=+-=∑∑∑-=-==n n n n i n n i n i i nj。

（5）答：其中x ++语句为基本运算语句，∑∑∑=+==-=-==n i n i j ni n n i n n T 1112)1()(1)(=O(n 2)。

（6） 答：由于内循环j 的取值范围，所以i ≤n /2，则，该程序段的时间复杂度为O(n 2)。

∑∑∑-===--==2/122/124/))12((n i nij n i n i n m 3log 2n2.练习题2参考答案1.单项选择题（1）A （2）C （3）A （4）B （5）C（6）D （7）C （8）B （9）A （10）C（11）B （12）A （13）C （14）D （15）D（16）D （17）A （18）C （19）A （20）D2.填空题（1）L.length=0（2）O(1)（3）O(n)（4）n-i（5）①物理存储位置②指针域（6）①前驱　②O(n)（7）q=p->next; p->next=q->next; free(q);（8）s->next= p->next; p->next=s;（9）O(1)（10）L->next==L3.简答题（1）答：顺序存储结构中，逻辑上相邻元素的存储空间也是相邻的，无需额外空间表示逻辑关系，所以存储密度大，同时具有随机存取特性。

第11章外排序一、选择题1．下列排序算法中，其中（）是稳定的。

A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。

不稳定排序有：快速排序、堆排序、shell排序。

时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。

3．在下面的排序方法中，辅助空间为O（n）的是（）。

A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。

A．归并排序B．快速排序C．希尔排序D．堆排序【答案】A【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。

5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A．NB．2N-1C．2ND．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。

最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序最好情况下的复杂度为O（n）。

6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。

插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。

将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。