下载文档原格式
数据结构考试题及答案一、选择题（每题2分，共20分）1. 以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 在一个单链表中，删除一个节点的操作需要知道该节点的：A. 地址B. 值C. 索引D. 前驱节点的引用3. 栈（Stack）是一种：A. 线性表B. 树状结构C. 图结构D. 散列表4. 哈希表解决冲突最常用的方法是：A. 排序B. 链地址法C. 再散列D. 除留余数法5. 以下哪个排序算法是稳定的？A. 快速排序B. 冒泡排序C. 选择排序D. 堆排序二、简答题（每题10分，共30分）1. 简述数组和链表的区别。
2. 解释二叉搜索树的基本概念及其优势。
3. 什么是递归？请给出一个简单的递归算法例子。
三、计算题（每题25分，共50分）1. 给定一个无序数组，请写出一个时间复杂度为O(n log n)的排序算法，并说明其工作原理。
2. 描述如何使用队列来实现一个简单的文本编辑器的撤销和重做功能。
四、编程题（共30分）编写一个函数，该函数接受一个整数数组作为参数，返回数组中所有元素的和。
如果数组为空，返回0。
答案一、选择题1. 答案：C（树和图都是非线性结构）2. 答案：D（需要前驱节点的引用来删除节点）3. 答案：A（栈是一种后进先出的特殊线性表）4. 答案：B（链地址法是解决哈希冲突的常用方法）5. 答案：B（冒泡排序是稳定的排序算法）二、简答题1. 数组和链表的区别：- 数组是连续的内存空间，链表是非连续的。
- 数组的索引访问速度快，链表需要遍历。
- 数组的大小固定，链表动态可变。
2. 二叉搜索树的基本概念及其优势：- 二叉搜索树是一种特殊的二叉树，左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 优势：支持快速的查找、插入和删除操作。
3. 递归是函数自己调用自己的过程。
例如，计算n的阶乘的递归算法： ```cint factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1);}```三、计算题1. 快速排序算法：- 选择一个元素作为“基准”（pivot）。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？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. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
数据结构试题及答案⼀、选择题（共10题，每题1分，共10分）1．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元D．线性表采⽤链接存储，便于插⼊和删除操作2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊s所指结点，则执⾏的操作是（）。
A. s->next=p->next;p->next=s;B. q->next=s;s->next=p;C. p->next=s->next;s->next=p;D. p->next=s;s->next=q;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素后，rear和front的值分别是( )。
A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。
A．⼆叉树就是度为2的树 B．⼆叉树中不存在度⼤于2的结点C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 6．在具有n个结点的⼆叉链表中，共有（）个空指针。
A. nB. n-1C. n+1D. 不确定7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。
A．1 B．log2n C. h/2 D. h8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。
A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。
A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。
数据结构考试试题题库一、选择题1. 在数据结构中，线性表是按照什么顺序存储数据的？A. 随机B. 无序C. 有序D. 连续2. 栈（Stack）是一种遵循哪种原则的数据结构？A. 先进先出（FIFO）B. 先进后出（LIFO）C. 后进先出（LILO）D. 随机访问3. 哈希表（Hash Table）的主要优点是什么？A. 存储空间大B. 访问速度快C. 易于排序D. 易于扩展二、简答题1. 请简述数组和链表的区别。
2. 什么是二叉树？请描述二叉树的几种遍历方法。
三、计算题1. 给定一个单链表，编写一个算法来删除链表中的重复元素。
2. 假设有一个数组，其中包含n个元素，编写一个算法来找到数组中的第k小的元素。
四、应用题1. 描述如何使用队列来实现一个打印任务调度系统。
2. 请解释二叉搜索树（BST）的插入操作，并给出相应的算法实现。
五、编程题1. 编写一个C++函数，实现对一个给定的整数数组进行排序。
2. 编写一个Python函数，实现对一个二叉树进行层次遍历。
六、论述题1. 讨论图的两种存储结构：邻接矩阵和邻接表，并比较它们的优缺点。
2. 解释什么是递归，并给出一个使用递归解决实际问题的例子。
结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。
通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。
请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。
考生应根据具体的课程内容和考试要求来准备。
数据结构期末考试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 数组C. 栈D. 队列答案：B2. 以下哪个是二叉树的性质？A. 每个节点最多有两个孩子B. 每个节点最多有三个孩子C. 每个节点最多有四个孩子D. 每个节点最多有五个孩子答案：A3. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的区别是什么？A. DFS使用队列，BFS使用栈B. DFS使用栈，BFS使用队列C. DFS和BFS都使用栈D. DFS和BFS都使用队列答案：B...20. 以下哪个排序算法的时间复杂度为O(n^2)？A. 冒泡排序B. 选择排序C. 插入排序D. 所有上述排序算法答案：D二、简答题（每题10分，共30分）1. 简述链表和数组的区别。
答案：链表和数组都是用来存储数据的线性数据结构。
数组是连续的内存空间，可以随机访问，但插入和删除操作效率较低；链表由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针，不支持随机访问，但插入和删除操作较为高效。
2. 什么是递归？请给出一个递归算法的例子。
答案：递归是一种算法设计技术，它允许函数调用自身来解决问题。
递归通常包含基本情况和递归情况。
例如，计算阶乘的递归算法：f(n) = n * f(n-1)，其中基本情况是f(1) = 1。
...三、算法设计题（每题25分，共50分）1. 给定一个整数数组，请设计一个算法找出数组中的第k大元素。
答案：可以采用快速选择算法，类似于快速排序的划分过程，通过随机选择一个元素作为基准，将数组分为两部分，一部分包含比基准大的元素，另一部分包含比基准小的元素。
然后根据k与基准元素的位置关系，决定是继续在左侧子数组还是右侧子数组中进行查找。
2. 描述如何使用哈希表解决字符串匹配问题。
答案：哈希表可以用于实现字符串匹配的KMP算法。
首先，构建模式字符串的前缀函数，该函数用于记录模式字符串中每个位置的最长相同前缀和后缀的长度。
数据结构期末考试题及答案一、选择题（每题2分，共10题）1. 数据结构是指（）A. 存储和组织数据的方式B. 对数据进行计算和处理的方法C. 数据的物理表示形式D. 数据的逻辑结构答案：A. 存储和组织数据的方式2. 在数据结构中，栈是一种（）A. 先进先出的数据结构B. 后进先出的数据结构C. 随机存取的数据结构D. 按键值查找的数据结构答案：B. 后进先出的数据结构3. 下列哪种数据结构不支持随机访问？（）A. 队列B. 栈C. 数组D. 链表答案：D. 链表4. 在二叉树中，每个节点最多可以有几个子节点？（）A. 0B. 1C. 2D. 无限多答案：C. 25. 在图的表示方法中，邻接矩阵适用于（）A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A. 稠密图6. 下列排序算法中，最坏情况时间复杂度为O(nlogn)的是（）A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C. 快速排序7. 广度优先搜索算法用于（）A. 求最短路径B. 求全排列C. 求最小生成树D. 求图的连通分量答案：A. 求最短路径8. 哈希表的查找时间复杂度为（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A. O(1)9. AVL树是一种（）A. 无序树B. 有序树C. 平衡树D. 非平衡树答案：C. 平衡树10. 以下哪个不属于基本的查找算法？（）A. 二分查找B. 插值查找C. 散列查找D. 顺序查找答案：C. 散列查找二、填空题（每题4分，共4题）11. 下列不是线性表的是（）答案：二叉树12. 在冒泡排序中，每一轮的比较次数是________答案：n-113. 在堆排序中，堆的建立时间复杂度为________答案：O(n)14. 从一个顶点到其余各顶点的最短路径算法是________答案：Dijkstra算法三、简答题（每题10分，共3题）15. 请简要说明栈的应用场景，并给出一个具体实例。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。
答案：线性表2. 队列是一种先进先出（____）的数据结构。
答案：线性表3. 链表是一种____数据结构，由一系列节点组成。
答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。
答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。
答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。
（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。
（）答案：错误3. 图是一种线性结构。
（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。
（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。
（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。
答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。
队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。
2. 请简述链表的优缺点。
答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。
缺点包括占用内存空间较大、不如数组支持随机访问。
数据结构考试题及答案一、选择题1. 以下哪种数据结构在实现栈时最为高效？A. 链表B. 数组C. 树D. 图答案：B2. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C3. 在二叉搜索树中，若要查找给定值的节点，应该按照以下哪种方式进行？A. 从根节点开始，向左或向右子树交替进行B. 从根节点开始，始终向左子树进行C. 从根节点开始，始终向右子树进行D. 从最底层节点开始向上进行答案：A4. 哈希表的主要优点是什么？A. 有序存储数据B. 高效的查找、插入和删除操作C. 动态扩容D. 消耗内存小答案：B5. 下面哪种数据结构通常用于实现高效的多对一映射？A. 数组B. 链表C. 哈希表D. 树答案：C二、填空题1. 在平衡树中，AVL树通过_________来保持树的平衡。
答案：旋转2. 堆数据结构通常用来实现_________等优先队列。
答案：最大/最小3. 拓扑排序是针对有向无环图(DAG)的一种排序算法，它能够反映出任务间的_________关系。
答案：依赖4. 广度优先搜索(BFS)算法使用_________数据结构来实现。
答案：队列5. 斐波那契数列可以通过递归算法、动态规划以及_________等方法来计算。
答案：矩阵快速幂三、简答题1. 请简述链表和数组的区别及各自的优缺点。
答案：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
它的优点是能够在常数时间内在任意位置插入或删除元素，但随机访问效率较低。
数组是一段连续的内存空间，可以存储一系列相同类型的元素。
它的优点是支持高效的随机访问，但插入和删除操作通常需要移动大量元素，且大小固定或调整大小成本较高。
2. 描述二分查找的工作原理及其适用条件。
答案：二分查找是一种在有序数组中查找特定元素的算法。
它的工作原理是将数组分为两半，比较中间元素与目标值，如果相等则查找结束；如果目标值较小，则在左半部分继续查找；如果目标值较大，则在右半部分继续查找。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
一、单项选择题（每小题2分，共计40分）1. 数据结构是指。
A. 一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为。
void fun(int n){ int i=1;while (i<=n)i++;}A. O(n)B. O(n)C. O(n log2n)D. O(log2n)3. 现要设计一个高效的算法，在一个长度为n的有序顺序表中删除所有元素值为x的元素（假设这样的元素是不唯一的），这样的算法时间复杂度为。
A. O(n)B. O(n log2n)C. O(n2)D. O(n)4. 在一个带头结点的循环双链表L中，要删除p所指结点，算法的时间复杂度为。
A. O(n)B. O(n)C. O(1)D. O(n2)5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针top为n，则以下元素x进栈的正确操作是。
++;s[top]=x; [top]=x;top++;;s[top]=x; [top]=x;top--;6. 中缀表达式“2*(3+4)-1”的后缀表达式是，其中#表示一个数值的结束。
A. 2#3#4#1#*+-B. 2#3#4#+*1#-C. 2#3#4#*+1#-D. -+*2#3#4#1#7. 设循环队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。
A. rear-frontB. rear-front-1C. (rear-front)％N+1D. (rear-front+N)％N8. 若用一个大小为6的数组来实现循环队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。
若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 1和5B. 2和4C. 4和2D. 5和19. 一棵高度为h（h≥1）的完全二叉树至少有个结点。
A. 2h-1B. 2hC. 2h+1D. 2h-1+110. 一棵含有n个结点的线索二叉树中，其线索个数为。
A. 2nB. n-1C. n+1D. n11. 设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对个字符进行编码。
A. 999B. 998C. 1000D. 100112. 一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是。
A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 稠密矩阵13. 设无向连通图有n个顶点e条边，若满足，则图中一定有回路。
A. e≥nB. e<nC. e=n-1D. 2e≥n14. 对于AOE网的关键路径，以下叙述是正确的。
A. 任何一个关键活动提前完成，则整个工程一定会提前完成B. 完成整个工程的最短时间是从源点到汇点的最短路径长度C. 一个AOE网的关键路径一定是唯一的D. 任何一个活动持续时间的改变可能会影响关键路径的改变15. 设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是。
A. 25B. 50C. 10D. 716. 在一棵m阶B-树中删除一个关键字会引起合并，则该结点原有个关键字。
A. 1B. m/2C. m/2-1D. m/2+117. 哈希查找方法一般适用于情况下的查找。
A. 查找表为链表B. 查找表为有序表C. 关键字集合比地址集合大得多D. 关键字集合与地址集合之间存在着某种对应关系。
18. 对含有n个元素的顺序表采用直接插入排序方法进行排序，在最好情况下算法的时间复杂度为。
A. O(n)B. O(n log2n)C. O(n2)D. O(n)19. 用某种排序方法对数据序列{24,88,21,48,15,27,69,35,20}进行递增排序，元素序列的变化情况如下：（1）{24,88,21,48,15,27,69,35,20}（2）{20,15,21,24,48,27,69,35,88}（3）{15,20,21,24,35,27,48,69,88}（4）{15,20,21,24,27,35,48,69,88}则所采用的排序方法是。
A. 快速排序B. 简单选择排序C. 直接插入排序D. 二路归并排序20. 以下排序方法中，不需要进行关键字的比较。
A.快速排序B.归并排序C.基数排序D.堆排序二、问答题（共4小题，每小题10分，共计40分）1. 如果一个含有n（n>1）个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构（所有链表均带有头结点），并简要说明理由。
（1）只有尾结点指针没有头结点指针的循环单链表（2）只有尾结点指针没有头结点指针的非循环双链表（3）只有头结点指针没有尾结点指针的循环双链表（4）既有头结点指针也有尾结点指针的循环单链表2. 对于图1所示的带权有向图，采用Dijkstra算法求从顶点0到其他顶点的最短路径，要求给出求解过程，包括每一步的S集合、dist和path数组元素。
图1 一个有向图3. 有一棵二叉排序树按先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)。
回答以下问题：（1）画出该二叉排序树。
（2）给出该二叉排序树的中序遍历序列。
（3）求在等概率下的查找成功和不成功情况下的平均查找长度。
4. 一个含有n个互不相同的整数的数组R[1..n]，其中所有元素是递减有序的，将其看成是一棵完全二叉树，该树构成一个大根堆吗？若不是，请给一个反例，若是，请说明理由。
三、算法设计题（每小题10分，共计20分）1. 设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。
设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。
给出你所设计的算法的时间复杂度和空间复杂度。
2. 假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点（假设这样的结点是唯一的）的双亲结点地址p，提示，根结点的双亲为NULL，若在b中未找到值为x的结点，p亦为NULL。
“数据结构”考试试题（A）参考答案要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共计40分）1. D2. A3. A4. C5. C6. B7. D8. B9. A10. C11. C 12. A 13. A 14. D 15. D 16. C17. D 18. A19. A20. C二、问答题（共4小题，每小题10分，共计40分）1. 答：本题答案为（3），因为实现上述4种运算的时间复杂度均为O(1)。
【评分说明】选择结果占4分，理由占6分。
若结果错误，但对各操作时间复杂度作了分析，可给2～5分。
2. 答：该图对应的邻接矩阵如下：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞0730202102960 在求最短路径时，S （存放顶点集），dist[]（存放最短路径长度）和path[]（存放最短路径）的变化如下：S dist[] path[]{0} {0, 4} {0, 1 ,4} {0,1,2,4} {0,1,2,3,4}最后得到的结果如下：顶点0到顶点1的最短距离为5，最短路径为：0、4、1 顶点0到顶点2的最短距离为6，最短路径为：0、4、1、2 顶点0到顶点3的最短距离为7，最短路径为：0、4、1、3 顶点0到顶点4的最短距离为2，最短路径为：0、4。
3. 答：（1）先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)，中序序列是一个有序序列，所以为：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以构造出对应的二叉树，如图2所示。
（2）中序遍历序列为：2,5,6,8,10,12,15,16,18,20。
（3）ASL 成功=(1×1+2×2+4×3+3×4)/10=29/10。
ASL 不成功=(5×3+6×4/11=39/11。
图2【评分说明】（1）小题占6分，（2）（3）小题各占2分。
4. 该数组一定构成一个大根堆。
当R是递减时，其数组元素为k1、k2、…、k n，从中看出下标越大的元素值越小，对于任一元素k i，有k i>k2i，k i>k2i+1（i<n/2），这正好满足大根堆的特性，所以构成一个大根堆。
【评分说明】回答是给5分，说明理由给5分。
三、算法设计题（每小题10分，共计20分）1. 设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。
设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。
给出你所设计的算法的时间复杂度和空间复杂度。
解：算法如下：void insertion(LinkList *A,LinkList *B,LinkList *&C){ LinkList *p=A->next,*q=B->next,*s,*t;C=(LinkList *)malloc(sizeof(LinkList));t=C;while (p!=NULL && q!=NULL){ if (p->data==q->data){ s=(LinkList *)malloc(sizeof(LinkList));s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;}else if (p->data<q->data)p=p->next;elseq=q->next;}t->next=NULL;}算法的时间复杂度为O(m+n)，空间复杂度为O(MIN(m,n))。
【评分说明】算法为8分，算法的时间复杂度和空间复杂度各占1分。
2. 假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p，提示，根结点的双亲为NULL，若未找到这样的结点，p亦为NULL。
解：算法如下：void findparent(BTNode *b,ElemType x,BTNode *&p){ if (b!=NULL){ if (b->data==x) p=NULL;else if (b->lchild!=NULL && b->lchild->data==x)p=b;else if (b->rchild!=NULL && b->rchild->data==x)p=b;else{ findparent(b->lchild,x,p);if (p==NULL)findparent(b->rchild,x,p);}}else p=NULL;}【评分说明】本题有多种解法，相应给分。
