数据结构试卷(手动组卷).doc

题目部分，(卷面共有78题,523.0分,各大题标有题量和总分)一、简答题(78小题,共523.0分)(5分)1堆排序是否是一种稳定的排序方法？为什么？(10分)2简要叙述B(有些教材称为B-树)与B+ 树的区别(8分)3在多关键字排序时，LSD和MSD两种方法的特点是什么？(4分)4快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？(3分)5在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是哪种？(5分)6快速排序的最大递归深度是多少？最小递归深度是多少？ (7分)7在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？ (6分)8外排序中为何采用k-路（k2）合并而不用2-路合并？这种技术用于内排序有意义吗？为什么？ (7分)9以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。(5分)10设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。(6分)11快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？ (8分)12 在堆排序、快速排序和合并排序中： (1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？(8分)13简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。(6分)14以下概念的区别：拓扑排序与冒泡排序。 (5分)15在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ (7分)16对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？ (4分)17八皇后问题的最大递归深度是多少？(4分)18如果一棵Huffman树T有个叶子结点，那么，树T有多少个结点？(3分)19什么是循环队列？(8分)20简述数组与字符串属于线性表的理由。(4分)21试叙述一维数组与有序表的异同。(5分)22用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？(8分)23在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?(8分)24常用的存储表示方法有哪几种?(4分)25KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?(4分)26两个字符串相等的充要条件是什么？(3分)27两个串相等的充分必要条件是什么？(2分)28串的两种最基本的存储方式是什么？(5分)29试叙述一维数组与有序表的异同。(6分)30在什么条件下，MSD基数排序比LSD基数排序效率更高？(5分)31在顺序表中插入和删除一个结点需平均移动多少个结点？具体移动次数取决于哪几个因素？(6分)32为什么有序的单链表不能进行折半查找?(6分)33何时选用顺序表、何时选用链表作为线性表的存储结构为宜？简述线性表的相互许存储与链接存储的空间分配方式、存储结构特性和主要优缺点。(8分)34循环队列的优点是什么? 如何判别它的空和满?(6分)35链栈中为何不设置头结点?(4分)36试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？(5分)37算法的时间复杂度仅与问题的规模相关吗?(7分)38常用的存储表示方法有哪几种?(8分)39试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。(16分)40简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。(6分)41试问对于下列各种排序方法，哪些是稳定的？哪些是不稳定的？（1）直接插入排序； （2）希尔排序； （3）快速排序；（4）堆排序； （5）归并排序； （6）基数排序。(8分)42试问：对初始状态如下（长度为n）的各序列进行直接插入排序时，至多需进行多少次关键字间的比较（要求排序后的序列按关键字自小至大顺序有序）？（1）关键字（自小至大）顺序有序；（key1key2key2keyn）（3）序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序：(key1key3, key2key4)（4）前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序：(key1key=2keyn)(4分)43简述栈和线性表的差别。(7分)44对于循环向量中的循环队列，写出求队列长度的公式。(5分)45简述队列和栈这两种数据类型的相同点和差异处。(7分)46一个长度为n的序列，若去掉其中少数k个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。(6分)47 试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少场次的比赛（应考虑最坏的情况）？(7分)48不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。试问：当n为7时，在最好情况下需进行多少次比较？请说明理由。(6分)49假设我们把n个元素的序列a1, a2, , an中满足条件akaj(i Ai+1，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，如此反复，直到整个序列全部排好序为止。(1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。(3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？(6分)54在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?(15分)55线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？(10分)56如果待排序的排序码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。(7分)57在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？(9分)58什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? (8分)59在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。(7分)60数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？(8分)61什么是数据结构? 有关数据结构的讨论涉及哪三个方面?(8分)62什么是数据? 它与信息是什么关系?(6分)63为什么在单循环链表中设置尾指针比设置头指针更好?(9分)64在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?(6分)65何时选用顺序表、何时选用链表作为线性表的存储结构为宜?(6分)66试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。(12分)67在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。(6分)68若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定值K的记录；（2）查找成功，且表中只有一个关键字等于给定值K的记录；（3）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。(5分)69在结点个数为n (n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？(10分)70给出12个初始归并段，其长度分别为30, 44, 8, 6, 3, 20, 60, 18, 9, 62, 68, 85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。 (8分)71特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？(6分)72 试叙述一维数组与有序表的异同。(5分)73什么是广义表？请简述广义表和线性表的主要区别。(6分)74数组，广义表与线性表之间有什么样的关系？ (5分)75简述广义表属于线性结构的理由。(6分)76描述以下概念的区别：空格串与空串。(4分)77如果两个串含有相等的字符，能否说它们相等？(7分)78什么是前缀编码？举例说明如何利用二叉树来设计二进制的前缀编码。 =答案=答案部分，(卷面共有78题,523.0分,各大题标有题量和总分)一、简答题(78小题,共523.0分)(5分)1答案堆排序不是一种稳定的排序方法。因为在堆调整的过程中，关键字进行比较和交换的所走路线是沿着根结点到叶子结点，因此对于相同的关键字就可能存在后面的先被变换到前面。例如对于初始大J顶堆(2，1，)，第一遍堆调整为(,1)(2),因而堆排序不是稳定的。(10分)2答案 B树是一种平衡的多路查找树，通常用在文件系统中。B_树的定义为： 一棵m阶的B_树，或为空树，或为满足下列特性的m叉树： (1)树中每个结点至多有m 棵子树。 (2)若根结点不是叶于结点，则至少有两棵子树。 (3 除根之外的所有非终端结点至少有m/2棵子树。 (4)所有的非终端结点中包含下列信息数据： (n，)其中： (i=1，2，n)为关健字，且指针所指子树中所有结点的关键字均小于 (i=1，2，n)，所指子树中所有结点的关键字均大于，n(m/2 nm-1)为关键字的个数（或n+l为子树个数)。 (5)所有的叶结点都出现在同 一层次上，并且不带信息(可看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)， B+树是B-树的种变形树，常用于文件系统中：它与B_树的差异在于 （1）有n棵子树的结点中含有n个关键字。 （2)所有的叶结点中包含了全部关键字的信息以及指向含这些关键字记录的指针，且叶子结点本身关键字的大小由小到大的顺序进行链接。 (3)所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大(或最小)关键字。(8分)3答案最高位优先（MSD）法：先对最高位关键字K0进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K0值，然后，分别就每个子序列对关键字K1进行排序，按K1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先（LSD）法：先对最低位关键字Kd-1进行排序，然后对高一级关键字Kd-2进行排序，依次重复，直至对最高位关键字K0排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki (0=i2)是因为k越小，归并趟数越多，读写外存次数越多，时间效率越低，故，一般应大于最少的2路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。(7分)9答案内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。因为归并的趟数s=logkm,其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多（k）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。(5分)10答案对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序。(6分)11答案平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序、堆排序、希尔排序。(8分)12答案(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序(8分)13答案直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1=in)趟简单选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列。如此重复，经过log2n趟归并，最终得到一个长度为n的有序序列。最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是O(n)，是稳定排序。(6分)14答案拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶点连接的弧来确定顶点序列；冒泡排序是借助交换思想通过比较相邻结点关键字大小进行排序的算法。(5分)15答案这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。(7分)16答案从节省存储空间考虑：先选堆排序，再选快速排序，最后选择归并排序；从排序结果的稳定性考虑：选择归并排序。堆排序和快速排序都是不稳定排序；从平均情况下排序最快考虑：先选择快速排序。(4分)17答案八皇后问题是利用回溯法求解，而回溯法的一个很重要的特点就是：空间需求为O(从开始结点起最长路径的长度)。因此，八皇后问题的最大递归深度是8。(4分)18答案因为Huffman树没有度为1的结点，所以树T有2-1个结点(3分)19答案用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。(8分)20答案数组可以看成是线性表的扩展，也即此时线性表中的数据元素本身也是个数据结构，对n维数组来说，可以看作具有n个数据元素的线性表，而每一个数据元素本身又是一个数据结构，即由n-1维的数组构成。依此类推，也即，对于 n维数组中的每一个元素来说都受到n个关系(n维)的约束，在每个关系(每一维)中，数据元素都有一个直接后继(除去最后一个元素)和一个直接前驱(除去最前一个元素)因此，这n个(n维)关系中的任一关系，就其单个关系而言，仍是线性关系。串是取值范围受到限制的线性表，即只能取字符集合中的字符。因此，串仍然是线性表(4分)21答案一维数组是一种特殊的线性表结构，它与有序表的差异在于该结构中不存在元素值之间的递增或递减关系(5分)22答案用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。(8分)23答案可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。(8分)24答案（1）顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。（2）链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。（3） 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。（4）散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。(4分)25答案 KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。(4分)26答案两个串相等当且仅当这两个串的值相等，即只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等(3分)27答案两个串的长度相等且对应位置的字符相同。(2分)28答案顺序存储方式和链接存储方式。(5分)29答案一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。(6分)30答案由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。(5分)31答案在顺序表中插入和删除一个结点需平均移动表中近一半的结点。如果表长n,则插入运算时元素的平均移动次数为n/2；删除运算的平均移动次数为n-1/2。具体的取决于表长n和位置i。(6分)32答案因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。(6分)33答案顺序表的最大优点是可随机访问，因此，如果对线性表经常进行查找、排序等运算，则宜采用顺序表作为存储结构。 链表的最大优点是便于插入和删除(它不需要移动元素，只需要修改指针)。因此，如果对线性表经常进行插、删运算，则宜采用链表作为存储结构。(8分)34答案循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。(6分)35答案链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。(4分)36答案简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。(5分)37答案不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。(7分)38答案常用的存储表示方法有四种:顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：根据结点的关键字直接计算该结点的存储地址。(8分)39答案例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。(16分)40答案数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。逻辑结构：指各数据元素之间的逻辑关系。存储结构：就是数据的逻辑结构用计算机语言的实现。线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。(6分)41答案（1）（5）（6）是稳定的排序方法；（2）（3）（4）是不稳定的排序方法。(8分)42答案 (1)n-1(2)n(n-1)/2(3)n-1+(4)n/2-(4分)43答案栈是操作受限的线性表，栈的插入和删除操作都只能在栈顶端进行，因而相应的称为“入栈”和“出栈”。(7分)44答案公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSizeQueuelen=(QueueSize+rear-front)%QueueSize(5分)45答案队列和栈都是操作受限的线性表，都属于线性表的逻辑结构。区别在于，队列的插入是在对尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行。(7分)46答案对近似有序的序列可用直接插入排序法，其时间复杂度为O(kn)，当k远远小于n且n很大时，将比快速排序更有效。而起泡排序和简单选择排序的时间复杂度均为O(n2)，和k无关。(6分)47答案至少需编排17场比赛。(7分)48答案快速排序最好成绩的情况是指，排序所需的“关键字间的比较次数”和“记录的移动次数”最少的情况，在n为7的情况下，至少需进行2趟排序。(6分)49答案只要考虑序列中位于ai和aj之间的元素ak(ikaiaj时，有可能使ai由非逆元素变为逆序元素，但整个序列的“逆序对”不变。(10分)50答案(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = logkm = logk80 = 3得：k380。由此解得k3，即应取的归并路数至少为3。(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = logkm = log1480 = 2。即至少需2趟归并可完成排序。若限定这个趟数，由S = logk80 = 2，有80k2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。(6分)51答案由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。(12分)52答案(1) 希尔排序 512275 275* 061 增量为2 275*061 512 275 增量为1 061275* 275 512 (2) 直接选择排序 275 275* 512 061 i = 1 061275* 512 275 i = 2 061 275* 512 275 i = 3 061 275* 275 512 (3) 快速排序 512275 275* 275*275 512 (4) 堆排序 275 275* 061 170 已经是最大堆，交换275与170 170 275* 061 275 对前3个调整 275* 170 061 275 前3个最大堆，交换275*与061 061 170 275* 275 对前2个调整 170 061 275* 275 前2个最大堆，交换170与061 061 170 275* 275 (15分)53答案(1) 设有一个布尔变量exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若exchange = 0，表示刚才没有交换，可以结束排序。(2) 奇偶排序的算法template void dataList : odd-evenSort ( ) int i, exchange; do exchange = 0; for ( i = 1; i Vectori+1 ) /相邻两项比较, 发生逆序 exchange = 1;/作交换标记 swap ( Vectori, Vectori+1 );/交换 for ( i = 0; i Vectori+1 ) /相邻两项比较, 发生逆序 exchange = 1; /作交换标记 swap ( Vectori, Vectori+1 ); /交换 while ( exchange != 0 );(3) 设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有待排序对象序列中的对象按排序码从大到小初始排列时，执行m = (n+1)/2 趟奇偶排序。当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行1趟奇偶排序。在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较 (n-1)/2 次；对所有偶数项扫描一遍，排序码比较 n/2 次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次数为 (n-1)/2 + n/2 = n-1。(6分)54答案可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。(15分)55答案(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。(10分)56答案【证明】若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。对于这样的递归QuickSort( )算法，其时间代价为T(n) = (n-1) + T(n-1)= (n-1) + ( n-2) + T(n-2) = (n-1) + (n-2) + (n-3) + T(n-3) = = (n-1) + (n-2) + (n-3) + + 2 + T(1) = (n-1) + (n-2) + (n-3) + + 2 + 1= n(n-1)/2 = O(n2)(7分)57答案如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如， 57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75(9分)58答案内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“(或next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。(9分)64答案分别讨论三种链表的情况。 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。(6分)65答案在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 基于空