搜索
题目部分，(卷面共有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有0n个叶子结点，那么，树T有多少个结点？(3分)[19]什么是循环队列？(8分)[20]简述数组与字符串属于线性表的理由。(4分)[21]试叙述一维数组与有序表的异同。(5分)[22]用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？(8分)[23]在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈?为什么?(8分)[24]常用的存储表示方法有哪几种?(4分)[25]KMP算法(字符串匹配算法)较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）关键字（自小至大）顺序有序；（key1key2…keyn）（2）关键字（自大至小）逆序有序；（key2key2…keyn）（3）序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序：(key1key3…,key2key4…)（4）前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序：(key1key=2…keyn/2,key(n/2)+1…keyn)(4分)[43]简述栈和线性表的差别。(7分)[44]对于循环向量中的循环队列，写出求队列长度的公式。(5分)[45]简述队列和栈这两种数据类型的相同点和差异处。(7分)[46]一个长度为n的序列，若去掉其中少数k个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。(6分)[47]试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少场次的比赛（应考虑最坏的情况）？(7分)[48]不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。试问：当n为7时，在最好情况下需进行多少次比较？请说明理由。(6分)[49]假设我们把n个元素的序列{a1,a2,…,an}中满足条件ak}{max1lkla的元素ak称为“逆序元素”。若在一个无序序列有一对元素aiaj(ij)，试问当将ai和aj相互交换之后（即序列由{…ai...aj…}变为{…aj…ailll}），该序列中逆序元素的个数会有什么变化？为什么？(10分)[50]如果某个文件经内排序得到80个初始归并段，试问(1)若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？(2)如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？(6分)[51]在什么条件下，MSD基数排序比LSD基数排序效率更高？(12分)[52]希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。(15分)[53]奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i]A[i+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)，第一遍堆调整为(1,1)(2),因而堆排序不是稳定的。(10分)[2][答案]B树是一种平衡的多路查找树，通常用在文件系统中。B_树的定义为：一棵m阶的B_树，或为空树，或为满足下列特性的m叉树：(1)树中每个结