下载文档原格式
数据结构期末考试试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构是指（）。
A. 元素在存储空间中不连续B. 元素在存储空间中连续C. 元素在存储空间中随机分布D. 元素在存储空间中按照一定顺序排列答案：B2. 对于一个长度为n的顺序表，删除第i个元素（1≤i≤n）的时间复杂度为（）。
A. O(1)B. O(n)C. O(n^2)D. O(log n)答案：B3. 在二叉树中，度为2的节点数为x，度为1的节点数为y，度为0的节点数为z，则x，y，z之间的关系是（）。
A. x = y + 1B. x = y - 1C. x = zD. x = 2y答案：A4. 哈希表中，当发生冲突时，通常采用的方法是（）。
A. 链地址法B. 线性探测法C. 二次探测法D. 以上都是答案：D5. 在图的遍历中，深度优先搜索（DFS）使用的是（）。
A. 栈B. 队列C. 链表D. 数组答案：A6. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(n log n)C. O(n^2)D. O(2^n)答案：C7. 堆排序中，调整堆的过程称为（）。
A. 堆的建立B. 堆的调整C. 堆的插入D. 堆的删除答案：B8. 在数据库中，B树是一种（）。
A. 线性结构A. 树形结构B. 图形结构D. 散列结构答案：B9. 一个有n个顶点的无向完全图中，边的数目是（）。
A. n(n-1)/2B. n(n-1)C. n^2D. 2n答案：A10. 以下哪个算法不是动态规划算法（）。
A. 斐波那契数列B. 最长公共子序列C. 快速排序D. 背包问题答案：C二、填空题（每空2分，共20分）1. 在数据结构中，栈的基本操作包括入栈（）和出栈（）。
答案：push, pop2. 一个长度为n的链表，删除第i个元素的时间复杂度为（）。
答案：O(n)3. 在二叉搜索树中，对于任意节点，其左子树中的所有节点的值都（）该节点的值。
数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 编写代码的时间B. 代码的长度C. 执行代码所需的时间D. 执行代码所需的指令条数2. 下列关于队列的描述，错误的是（）。
A. 队列是先进先出（FIFO）的线性表B. 队列允许在一端进行插入操作C. 队列的插入操作称为入队D. 队列的删除操作称为出栈3. 对于长度为n的有序数组，使用二分查找法查找一个元素的平均时间复杂度是（）。
A. O(n)B. O(n^2)C. O(log n)D. O(1)4. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是（）。
A. 栈B. 队列C. 链表D. 数组5. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决冲突的方法？（）A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法6. 一个完全二叉树共有700个节点，它的最大节点数是（）。
A. 700B. 701C. 1400D. 14017. 快速排序算法的最坏情况发生在（）。
A. 每次选择的基准都是最大值B. 数据已经有序C. 数据已经完全逆序D. 所有数据元素相等8. 在一个具有n个节点的二叉搜索树中，最坏情况下查找一个元素的时间复杂度是（）。
A. O(n)B. O(log n)C. O(n^2)D. O(1)9. 堆排序算法中，将一个堆调整为最大堆或最小堆的过程称为（）。
A. 堆调整B. 堆构建C. 堆分解D. 堆维护10. 以下哪个不是B树的特性？（）A. 所有键值都存储在内部节点和叶子节点中B. 所有叶子节点都在同一层上C. 每个内部节点至多有m个子节点D. 每个内部节点的非叶子子节点都至少有m/2个子节点二、简答题（每题5分，共30分）1. 什么是递归？请举例说明递归算法的应用场景。
2. 请简述图的邻接矩阵和邻接表两种存储方式的优缺点。
3. 解释什么是平衡二叉树，并说明它为什么在实际应用中很重要。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）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.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。
《数据结构》试卷A一、选择题（20小题，每题2分）1、三个函数f,g,h分别为f(n)=100n3+n2+1000 , g(n)=25n3+5000n2, h(n)=n1.5+5000nlgn ，则下列关系不成立的是：A． f(n)=O(g(n)) B. g(n)=O(f(n))C. h(n)=O(n1.5)D. h(n)=O(nlgn)2、线性表是：A.一个有限序列，可以为空；B. 一个有限序列，不能为空；C. 一个无限序列，可以为空；D. 一个无序序列，不能为空。
3、线性表采用链式存储时，其地址：A.必须是连续的；B. 部分地址必须是连续的；C. 定是不连续的；D. 连续与否均可以。
4、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时大约要移动表中的（）个元素。
A.n/2B. n+1/2C. n-1/2D. n5、设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需修改指针的操作为（）。
A.p->next=(p->next)->nextB. p=p->nextC. p=(p->next)->nextD. p->next=p6、栈的特点是：A.先进先出B. 后进先出C. 进优于出D. 出优于进7、栈与队列都是：A.顺序存储的线性结构B. 链式存储的线性结构C. 限制存取点的线性结构D. 限制存取点的非线性结构8、若一个栈的输入序列是：1，2，3，...,n，输出序列的第一个元素是n，则第i个输出元素是：A.不确定B. n-iC. n-i+1D. i9、设字符串s1='ABCDEFG'，s2='PQRST'，则运算s=CONCAT(SUB(s1,2,LEN(s2)),SUB(s1,LEN(s2),2))后的串值为：A.‘BCDEF’B. ‘BCDEFG’C. ‘BCPQRST’D. ‘BCDEFEF’10、串的联结运算满足：A.分配律B. 交换律C. 结合律11、设有两个串p 和q ,求q 在p 中首次出现的位置的运算：A.连接B. 模式匹配C. 求子串D. 求串长12、设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A的终端结点a45的起始地位是A．1126 B. 1116 C. 1000 D. 103013、如果结点A有3个兄弟,而且B是A的双亲,则B的度是:A. 3B. 4C. 5D. 114、中序遍历的顺序是：A.根结点，左子树，右子树B. 左子树，根结点，右子树C. 右子树，根结点，左子树D. 左子树，右子树，根结点15、某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n.且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减一,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加一，这时按( )编号的.A.中序遍历序列B. 层次顺序C. 后序遍历序列D. 前序遍历序列16、在下图所示的各无向图中，哪个不是连通图：17、静态查找表与动态查找表的根本区别在于( )。
数据结构试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是元素之间存在一对一的线性关系。
以下哪个数据结构不属于线性结构？A. 栈B. 队列C. 树D. 链表答案：C2. 栈（Stack）是一种后进先出（LIFO）的数据结构，以下哪个操作不是栈的基本操作？A. PushB. PopC. TopD. Sort答案：D3. 在二叉树的遍历中，前序遍历的顺序是：A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表的冲突可以通过多种方法解决，以下哪个不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再散列法D. 排序法答案：D5. 以下哪个排序算法是稳定的？A. 快速排序B. 堆排序C. 归并排序D. 选择排序答案：C6. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B7. 以下哪个是图的存储方式？A. 顺序存储B. 链式存储C. 散列表D. 矩阵存储答案：D8. 动态数组（如C++中的vector）在插入元素时可能需要进行的操作是：A. 原地扩展B. 复制元素C. 重新分配内存D. 释放内存答案：C9. 以下哪个不是算法的时间复杂度？A. O(1)B. O(log n)C. O(n^2)D. O(n!)答案：D10. 在查找算法中，二分查找法要求被查找的数据必须是：A. 无序的B. 有序的C. 随机分布的D. 唯一元素答案：B二、简答题（每题5分，共30分）1. 简述链表和数组的区别。
答案：链表和数组都是存储数据的线性数据结构，但它们在内存分配、访问方式、插入和删除操作等方面存在差异。
数组在内存中是连续存储的，可以通过索引快速访问任意元素，但插入和删除元素时可能需要移动大量元素。
链表在内存中是非连续存储的，每个元素包含数据和指向下一个元素的指针，不支持通过索引快速访问，但插入和删除操作只需要改变指针，不需要移动其他元素。
数据结构期末试题及答案一、选择题（每题2分，共20分）1. 下列哪一项不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个直接前驱和一个直接后继C. 有多个根节点D. 有且只有一个叶子节点2. 在顺序存储结构中，数据元素之间的逻辑关系由（）表示。
A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置3. 在链式存储结构中，数据元素之间的逻辑关系由（）表示。
A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置4. 下列哪种排序算法的平均时间复杂度是O(nlogn)？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序5. 下列哪种数据结构属于非线性结构？A. 栈B. 队列C. 线性表D. 树二、填空题（每题2分，共20分）6. 一个栈的初始状态为空。
首先将元素1、2、3、4、5依次进栈，然后退栈一次，再让元素6、7依次进栈，此时栈顶元素的值为______。
7. 一个队列的初始状态为空。
首先将元素a、b、c、d、e依次入队，然后出队两次，再让元素f、g依次入队，此时队列的头部元素为______。
8. 在二分查找法中，每次查找都将查找区间分为______两部分。
9. 在顺序存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。
10. 在链式存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。
三、计算题（每题10分，共30分）11. 给定一个长度为8的数组A[8] = {5, 2, 9, 1, 5, 6, 3, 7}，请写出冒泡排序算法的实现过程，并计算排序后的数组。
12. 请手写一个递归函数，实现计算斐波那契数列的第n 项（n为非负整数）。
13. 请手写一个非递归函数，实现计算斐波那契数列的第n项（n为非负整数）。
数据结构期末试题答案一、选择题答案1. C2. C3. A4. B5. D二、填空题答案6. 77. b8. 相等9. n10. n-1三、计算题答案11. 冒泡排序算法实现过程：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j] A = [5, 2, 9, 1, 5, 6, 3, 7]bubble_sort(A)print(A) 输出排序后的数组```排序后的数组：[1, 2, 3, 5, 5, 6, 7, 9]12. 递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_recursive(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)n = 10 计算斐波那契数列的第10项print(fibonacci_recursive(n)) 输出结果```13. 非递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_iterative(n):a, b = 0, 1for _ in range(n):a, b = b, a + breturn an = 10 计算斐波那契数列的第10项print(fibonacci_iterative(n)) 输出结果```以上为数据结构期末试题及答案，希望对您有所帮助。
华清远见数据结构考试题A卷一、选择题1.下面哪种排序法对123456798在空间和时间上最优( )A.快速排序B.冒泡排序C.插入排序D.堆排序2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是( )A.堆排序<快速排序 <归并排序B.堆排序<归并排序<快速排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序E.以上答案都不对3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、G, .若该二叉树的根结点为E,则它的一种可能的前序遍历为___ ,相应的后序遍历为__A. ECBADFG, BDCAFGEB. ECBADFG, EFACDBGC. ECBADGF, EACBDGFD. EACBDGF, BDCAFGE(常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，推出二叉树)4.关于图和树，下面说法正确的是_A.树和图都允许有环B.图的深度遍历和广度遍历结果可能一样C.二叉树是每个节点都有两个孩子节点的树D.二叉树的前序遍历和后序遍历结果肯定不一样5.完成在双循环链表结点 p之后插入s的操作是( )A. p->next=s ; s->priou=p; p->next: >priou=s ;s->next=p->next;B. p->next->priou=s; p->next=s; s->priou=p; s->next=p->next;C. s->priou=p; s->next=p->next; p->next=s; p->next->priou=s ;D. s->priou=p; s->next=p->next; p->next->priou=s; p->next=s;二、填空题1. 用链表表示的数据的简单选择排序，结点的域为数据域data，指针域next :链表首指针为head，链表无头结点。
数据结构期末考试试题和标准答案及评分标准《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。
A.效率B.复杂度C.数据元素之间的关系??? ?D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。
A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大?B.插入运算方便?C.删除运算方便?D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。
>next=p->next->next >next=p->next=p->next;p->next=p->next->next =p->next->next6.带头结点的单链表head为空的判定条件是（）。
==NULL >next==NULL >next==head !==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。
>head==NULL ==NULL >next==head ==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
9.队列操作的原则是（）。
A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。
数据结构考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么类型的数据结构来实现？A. 栈B. 队列C. 数组D. 链表答案：C2. 下列选项中，哪一个不是二叉树的性质？A. 任意节点的左子树和右子树的深度可能不同B. 任意节点的左子树和右子树的深度相同C. 任意节点的左子树和右子树的节点数可能不同D. 任意节点的左子树和右子树的节点数相同答案：B3. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D4. 以下哪种排序算法的时间复杂度最低？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B5. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：B6. 以下哪种数据结构可以有效地实现稀疏矩阵的存储？A. 顺序存储B. 链表C. 散列D. 邻接矩阵答案：C7. 在二叉搜索树中，插入一个新节点后，树的平衡因子可能为：A. -2B. 0C. 2D. 3答案：A8. 堆数据结构中，父节点的值总是大于其子节点的值，这种堆被称为：A. 最小堆B. 最大堆C. 完全二叉树D. 满二叉树答案：B9. 以下哪个算法不是动态查找表的算法？A. 直接查找B. 二分查找C. 斐波那契查找D. 哈希查找答案：A10. 在图的遍历算法中，广度优先搜索（BFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______结构，遵循后进先出（LIFO）的原则。
答案：线性2. 一个具有n个顶点的无向图的边数最多为______。
答案：n*(n-1)/23. 快速排序算法的时间复杂度在最坏情况下为______。
答案：O(n^2)4. 在哈希表中，如果一个关键字的哈希地址已经被占用，则需要进行______。
一、 单项选择题（在每小题的4个备选答案中，选出1个正确的答案，并将其号码填在题干的括号内。每小题2分，共30分）
1． 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（ D）存储方式最节省时间。 A)单链表 B)双链表 C)单向循环链表 D)顺序表 2．串是任意有限个（ C ） A)符号构成的序列 B)符号构成的集合 C)字符构成的序列 D)字符构成的集合
3．设矩阵A的任一元素)10,1(jiaij满足：
)10,1,(;0)10,1,(;0jijiajijia
ijij
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（ D ）。 A)2340 B)2336 C)2164 D)2160 4．如果以链表作为栈的存储结构，则退栈操作时（ C） A)必须判别栈是否满 B)对栈不作任何判别 C)必须判别栈是否空 D)判别栈元素的类型 5．设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ D ） A)front=front+1 B)front=(front+1)%m C)rear=(rear+1)%m D)front=(front+1)%(m+1) 6．深度为6（根的层次为1）的二叉树至多有（ D）结点。 A)64 B)32 C)31 D)63 7．将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。则编号为49的结点X的双亲的编号为（ A）。 A)24 B)25 C)23 D)无法确定 8．设有一个无向图G=(V,E)和G’=(V’,E’)，如果G;G的生成树，则下面不正确的说法是（B ）。 A)G’为G的子图 B) G’为G的连通分量 C) G’为G的极小连通子图且V’=V D) G’为G的一个无环子图 9．下列序列中，( A )是执行第一趟快速排序后得到的序列。(排序的关键字类型是字符 串) A)[da，ax，eb，cd，bb]ff[ha，gc] B) [ge，ax，eb，cd，bb] ff [da，ha] C)[cd，eb，ax，da] ff [ha，gc，bb] D) [ax，bb，cd．da] ff [eb，gc，ha] 10．二分查找要求被查找的表是( C )。 A)键值有序的链接表 B)链接表但键值不一定有序 C)键值有序的顺序表 D)顺序表但键值不一定有序 11．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( D )。 A)n2 B)nlog2n c)log2n D)n-1
12．堆是一个键值序列(k1，k2，…，kn)，对i=1，2，…，/2n，满足( C)。 A)ki≤k2i≤k2i+1 B)kiC) ki≤k2i且ki≤k2i+1 (2i+l≤n) D) ki≤k2i或ki≤k2i+1 (2i+1≤n) 13．使用双向链表存储数据，其优点是可以( A )。 A)提高检索速度 B)很方便地插入和删除数据 C)节约存储空间 D)很快回收存储空间 14．设计一个判别表达式中左右括号是否配对出现的算法，采用( B )数据结构最佳。 A)线性表的顺序存储结构 B)栈 C)队列 D)线性表的链式存储结构 15．设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为( C )。 A)k+l B)2k C)2k-1 D)2k+1
二、填空题(每空2分，共28分) 1．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 r->next=s r=s；r->next=NULL。 2．在单链表中，指针p所指结点为最后一个结点的条件是 p->next==NULL 。
3．设一个链栈的栈顶指针是ls，栈中结点格式为 ，栈空的条件是 ____ ls==NULL， _______。如果栈不为空，则退栈操作为p=ls； ls=ls->link _ ；free(p)。 4．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 12 个叶子结点。 5．树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 双亲表示法 。 6．n个顶点的连通图的生成树有 n-1 条边。 7．一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi，vj和vk的相对位置为 ________ i，j，k 。 8．设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，__ 冒泡排序、 最省时间， __ 快速排序 最费时间。 9．下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct node { int key； struct node *left, *right； } void searchinsert( int x; pnode t) /* t为二叉排序树根节点的指针*/ { if （ t==NULL, _____ ） { p= malloc(suze)； p->key=x; p->left = NULL； p->right=NULL； t=p； } else if(xkey) searchinsert (x, t->left) else searchinsert(x,t->right) _____ } 10.线性表的 _循环链表、_ 主要有点是从表中任一结点出发能访问到所有结点。而使用___________双向链表__ ，可根据需要在前后两个方向上方便地进行查找。
三、应用题（本题共28分） 1.树的后根遍历方法是： 若树非空，则 1）依次后根遍历根的各个子树T1，T2，……，Tm； 2）访问根节点。 对图1所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。（4分）
图1 树 EBFGCKHIJDA 2.将图2的森林转换成二叉树。（4分）
A B C D E F G H I J K 图2 森林 分析：先将每棵树转换成二叉树，然后再将各二叉树的根结点作为兄弟连接在一起。而树转换成二叉树的方法是，先将兄弟结点连在一起，然后除最左边的孩子外，断开其它双亲到孩子的连线。
答案：如图6所示。
（a）先将各树转换成二叉树
（b）以结点为中心旋转45° A B C D E F G I J
A B C D E F G I J
A B C D E F G I J （c）将各二叉树组合在一起 图6 森林转换成二叉树
3.图3表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修
图建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。（4分） 3网
分析：本题实际上是求最小生成树问题。由于图中有两条权值为6的边，故可以得到两种方案。
答案：如图7所示。
6 14 33 21 18 11 6 5
16 2 4 3 6 1
5 19
A B C D E F G I
J 图7 由网络得到的最小生成树
4．已知一个无向图的邻接表如图4所示。
图4邻连表 1)画出这个图。 2)以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。(本题4分，每小题2分)
1）如图8所示。
图8 图4所示邻接表所对应的图 （2）v1v2v4v5v3和v1v4v2v3v5。
5．设n个元素的有序表为R，K为一个给定的值，二分查找算法如下： int binswarth(sqlist R；keytype K) { L=1； h=n；suc=0； while((L<=h)＆＆(!suc)
2 5 3 1 4
18 18
11 11 6 6 5 5 16 16 2 4 3 6 1 5 2 4 3 6 1
5 V1 2 4 ∧ V2 5 4 1 ∧
V3 4 5 ∧ V4 3 2 1 ∧
V5 3 2 ∧ { mid=(L+h)／2； switch { K=R[mid].key：suc=L；break； kK>R[mid].key：L=mid+1 } } if(suc) return(mid) else return(0)； } 将上述算法中划线语句改为：K1)改动后，算法能否正常工作?请说明原因。 2)若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。(本题6分，每小题3分)
分析：经过改动以后，有可能出现死循环，比如当查找的键值k小于有序表中的最小键值时，就会出现死循环。
答案：(1)算法不能正常运行。 (2)假设有序表的查找序列为(7，10，12，16，24，39，42)，当待查的键值为k=5时，出现死循环。
6．有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。(本题6分)
25 84 2l 47 15 27 68 35 20 第一趟 [20 15 21] 25 [47 27 68 35 84] 第二趟 [15] 20 [21] 25 [35 27] 47 [68 84] 第三趟 15 20 21 25 [27] 35 47 68 [84] 得到： 15 20 2l 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如图9所示。
四、设计题（共14分） 1. 设一颗二叉树以二叉链表为存储结构，结点结构为 。设计一个算法，
① x 25 84 2l 47 15 27 68 35 20 ② ③ ④
