数据结构试卷（手动组卷）

《数据结构试卷（手动组卷）》由会员分享，可在线阅读，更多相关《数据结构试卷（手动组卷）（16页珍藏版）》请在金锄头文库上搜索。

1、题目部分，(卷面共有 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在执行某个排序算法过程

2、中，出现了排序关键字朝着最终排序序列相反的方向的移 动，从而认为该算法是不稳定的。这种说法对么？为什么？ (6 分)8外排序中为何采用 k-路（k2）合并而不用 2-路合并？这种技术用于内排序有意义 吗？为什么？ (7 分)9以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。 (5 分)10设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。 (6 分)11快排序、堆排序、合并排序、Shell 排序中哪种排序平均比较次数最少，哪种排序 占用空间最多，哪几种排序算法是不稳定的？ (8 分)12 在堆排序、快速排序和合并排序中： (1)若只从存储空间考虑，则应

3、首先选取哪种排序方法，其次选取哪种排序方法，最后选 取哪种排序方法？ (2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ (8 分)13简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度 和排序稳定性上的差别。 (6 分)14以下概念的区别：拓扑排序与冒泡排序。 (5 分)15在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗？为什么？ (7 分)16对于堆积排序法，快速

4、排序法和归并排序法，若仅从节省存储空间考虑，则应该 首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其 中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？ (4 分)17八皇后问题的最大递归深度是多少？(4 分)18如果一棵 Huffman 树 T 有0n个叶子结点，那么，树 T 有多少个结点？(3 分)19什么是循环队列？ (8 分)20简述数组与字符串属于线性表的理由。 (4 分)21试叙述一维数组与有序表的异同。 (5 分)22用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相 关？ (8 分)23在使用非递归方法实现

5、快速排序时, 通常要利用一个栈记忆待排序区间的两个端 点。那么能否用队列来代替这个栈? 为什么? (8 分)24常用的存储表示方法有哪几种? (4 分)25KMP 算法(字符串匹配算法)较 Brute(朴素的字符串匹配)算法有哪些改进?(4 分)26两个字符串相等的充要条件是什么？ (3 分)27两个串相等的充分必要条件是什么？ (2 分)28串的两种最基本的存储方式是什么？ (5 分)29试叙述一维数组与有序表的异同。 (6 分)30在什么条件下，MSD 基数排序比 LSD 基数排序效率更高？ (5 分)31在顺序表中插入和删除一个结点需平均移动多少个结点？具体移动次数取决于哪 几个因素？

6、(6 分)32为什么有序的单链表不能进行折半查找? (6 分)33何时选用顺序表、何时选用链表作为线性表的存储结构为宜？ 简述线性表的相互许存储与链接存储的空间分配方式、存储结构特性和主要优缺点。 (8 分)34循环队列的优点是什么? 如何判别它的空和满? (6 分)35链栈中为何不设置头结点? (4 分)36试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？ (5 分)37算法的时间复杂度仅与问题的规模相关吗? (7 分)38常用的存储表示方法有哪几种? (8 分)39试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 (16 分)40简述下列概念：数

7、据、数据元素、数据类型、数据结构、逻辑结构、存储结构、 线性结构、非线性结构。 (6 分)41试问对于下列各种排序方法，哪些是稳定的？哪些是不稳定的？ （1）直接插入排序； （2）希尔排序； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。 (8 分)42试问：对初始状态如下（长度为 n）的各序列进行直接插入排序时，至多需进行 多少次关键字间的比较（要求排序后的序列按关键字自小至大顺序有序）？ （1）关键字（自小至大）顺序有序；（key1key2keyn） （3）序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序： (key1keyn)(4 分)43简述栈和线性表的差别

8、。 (7 分)44对于循环向量中的循环队列，写出求队列长度的公式。 (5 分)45简述队列和栈这两种数据类型的相同点和差异处。 (7 分)46一个长度为 n 的序列，若去掉其中少数 k 个记录后，序列是按关键字有序的，则 称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。 (6 分)47 试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少 场次的比赛（应考虑最坏的情况）？ (7 分)48不难看出，对长度为 n 的记录序列进行快速排序时，所需进行的比较次数依赖于 这 n 个元素的初始排列。试问：当 n 为 7 时，在最好情况下需进行多少次比较？请说明理 由。(6

9、 分)49假设我们把 n 个元素的序列a1, a2, , an中满足条件 akaj(i Ai+1，则交换它们。第三趟有对所有的奇数 项，第四趟对所有的偶数项，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交 换排序过程中的排序码比较次数是多少？ (6 分)54在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端 点。那么能否用队列来代替这个栈? 为什么? (15 分)55线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪

10、些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也 可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素， 这时，应采用哪种存储表示？为什么？ (10 分)56如果待排序的排序码序列已经按非递减次序有序排列，试证明函数 QuickSort( ) 的计算时间将下降到 O(n2)。 (7 分)57在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说 明。在快速排序过程中有这种现象吗？ (9 分)58什么是内排序? 什么是外排序? 什么排序方法是

11、稳定的? 什么排序方法是不稳定 的? (8 分)59在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为 两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需 要的栈的深度为 O(log2n)。 (7 分)60数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ (8 分)61什么是数据结构? 有关数据结构的讨论涉及哪三个方面? (8 分)62什么是数据? 它与信息是什么关系? (6 分)63为什么在单循环链表中设置尾指针比设置头指针更好? (9 分)6

12、4在单链表、双链表和单循环链表中，若仅知道指针 p 指向某结点，不知道头指针， 能否将结点*p 从相应的链表中删去?若可以，其时间复杂度各为多少? (6 分)65何时选用顺序表、何时选用链表作为线性表的存储结构为宜? (6 分)66试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 (12 分)67在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。 基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count，用于存放在已排好序的序列中该对象前面的对象数目，最后依 count 域的值，将序 列重新排列，就可完成排序。试编写一个算法

13、，实现计数排序。并说明对于一个有 n 个对 象的序列，为确定所有对象的 count 值，最多需要做 n(n-1)/2 次排序码比较。(6 分)68若对大小均为 n 的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三 种情况下分别讨论两者在等概率时的平均查找长度是否相同？ （1）查找不成功，即表中没有关键字等于给定值 K 的记录； （2）查找成功，且表中只有一个关键字等于给定值 K 的记录； （3）查找成功，且表中有若干个关键字等于给定值 K 的记录，一次查找要求找出所有记录。 此时的平均查找长度应考虑找到所有记录时所用的比较次数。 (5 分)69在结点个数为 n (n1)的各棵树中，高度

14、最小的树的高度是多少？它有多少个叶结 点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？(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数组，广义表与线性表之间有什么样的关

15、系？ (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)树中每个结点至多有 m 棵子树。(2)若根结点不是叶于结点，则至少有两棵子树。(3 除根之外的所有非终端结点至少有m/2棵子树。(4)所有的非终端结点中包含下列信息数据：(n，0,1,122,.,nnA K A KAKA)0,1,1221,.,nniA K A KAKAK其中：iK(i=1，2，n)为关