下载文档原格式
数据结构试卷B试题B⼀、填空题（18⼩题，40个空，每空分，共20分）1、数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。
2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
3、在顺序表中插⼊或删除⼀个元素，需要平均移动，具体移动的元素个数与有关。
4、在顺序表中访问任意⼀结点的时间复杂度均为，因此，顺序表也称为的数据结构。
5、顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置相邻。
6、若n为主串长，m为⼦串长，则串的古典（朴素）匹配算法最坏的情况下需要⽐较字符的总次数为。
7、求下列⼴义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ; //头元素不必加括号—（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、⼀棵具有２５７个结点的完全⼆叉树，它的深度为。
9、设⼀棵完全⼆叉树具有1000个结点，则此完全⼆叉树有个叶⼦结点，有个度为2的结点，有个结点只有⾮空左⼦树，有个结点只有⾮空右⼦树。
10、图有、等存储结构，遍历图有、等⽅法。
11、n个顶点e条边的图采⽤邻接矩阵存储，⼴度优先遍历算法的时间复杂度为；若采⽤邻接表存储，该算法的时间复杂度为。
12、⽤Dijkstra算法求某⼀顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。
13、假设在有序线性表a[20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为；⽐较四次查找成功的结点数为；平均查找长度为。
14、在各种查找⽅法中，平均查找长度与结点个数n⽆关的查找⽅法是。
⼤多数排序算法都有两个基本的操作：和。
一、单选题1、逻辑上通常可以将数据结构分为( )A.初等结构和组合结构B.顺序结构和链式结构C.线性结构和非线性结构D.动态结构和静态结构正确答案：C2、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。
A.栈B. 队列C.图D.树正确答案：D3、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（）A.n-iB.i-1C.n-i+1D.i正确答案：C4、在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（）A.q->next=p；p->next=q；B.p->next=q；q->next=p；C.q->next=p->next；p->next=q；D.q->next=p->next；p=q；正确答案：C5、已知栈的最大容量为4。
若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.2，3，5，6，1，4B.1，4，6，5，2，3C.5，4，3，2，1，6D.3，2，5，4，1，6正确答案：D6、设栈S和队列Q初始均为空，若6个元素入栈的顺序为1、2、3、4、5、6，一个元素出栈以后立即入队列Q，若6个元素出队的顺序为2、4、3、6、5、1，则栈S的容量至少为（）A.3B.5C.4D.2正确答案：A7、在计算机内实现递归算法时所需的辅助数据结构是（）A.队列B.栈C.图D.树正确答案：B8、循环队列存储在数组A[0..m-1],则出队时的操作为（）A.front=(front mod m)+1B.ront=(front+1)mod mC.front=front+1D.front=(front+1)mod (m-1)正确答案：B9、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（)A.SXXSXSSXB.SSSXXSXXC.SXSSXXXXD.SXSXXSSX正确答案：B10、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A.(front+1)%m==rearB.(rear+1)%m==frontC.front==rearD.rear+1==front正确答案：B11、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.nC.n/3D.n/2正确答案：D12、元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.E，D，C，B，AB.A，B，C，D，EC.E，A，B，C，DD.B，C，D，E，A正确答案：C13、下述二叉树中，（）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
一、单项选择题1．算法必须具备的三个特性是( )。
A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性2．下列数据中，( )是非线性数据结构。
A．栈B．队列C．完全二叉树D．顺序表3．算法分析的两个方面是( )。
A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性4．非空的循环单链表head的尾结点p满足( )。
A．p->next==head B．p->next==NULLC．p==NULL D．p==head5．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( )。
A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s;6．按照二叉树的定义，具有3个结点的二叉树有( )种。
A．3 B．4C．5 D．67．在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的( )倍。
A．1/2 B．1C．2 D．48．二叉排序树是( )。
A．每一分支结点的度均为2的二叉树B．中序遍历得到一升序序列的二叉树C．按从左到右顺序编号的二叉树D．每一分支结点的值均小于左子树上所有结点的值，大于右子树上所有结点的值9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( )。
A．1和 5 B．2和4C．4和2 D．5和110．下列说法中正确的是( )。
A．堆栈是在两端操作、先进后出的线性表B．堆栈是在一端操作、先进先出的线性表C．队列是在一端操作、先进先出的线性表D．队列是在两端操作、先进先出的线性表11．不带头结点的单链表head为空的判定条件是( )。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）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. 编写一个函数，实现链表的插入操作。
一、单选题（每题 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）的联系时，称这种结构为_____________________。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷B专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。
（正确的打√，错的打×）1、空串和空格串是相同的。
( )2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。
( )3、大顶堆（最大堆）中，最大值一定为根结点。
( )4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。
( )5、稀疏矩阵一般采用三元组顺序表方法压缩存储。
( )6、 若二叉排序树（搜索树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。
( )7、有向图用邻接表表示后，顶点i 的出度等于邻接表中顶点i 后链表的长度。
( ) 8、链接线性表是顺序存取的线性表。
( )9、哈希函数进行模除取余时，最好取素数进行模除。
（ ） 10、归并排序是一种稳定的排序算法。
（ ）二、填空题（本题共10小题，每小题 2 分，共计 20分）。
（请将正确答案填入空格内，答案是确定和唯一的）1、在数据结构中，从逻辑上可以把数据结构分成 和 。
2、限在表尾进行插入和删除操作的线性表称为 。
3、实现二分查找（对半搜索）的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的。
4、在拓扑排序中，拓扑序列的第一个顶点必须是 的顶点。
5、在一个长度为n 的顺序表中删除第i 个元素，则需要移动 个元素。
6、二维数组A[6，7]，按列优先存储，每个元素占4个字节,A 基址为500,则元素A[4,6]的存储地址是 。
7、深度为k二叉树中最多可有个结点。
8、任意写出二叉树的两种存储结构，分别是和。
9、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是。
10、快速排序平均时间复杂性为，平均空间复杂性。
三、选择题（本题共18小题，每小题 1分，共计 18 分）。
（从下列答案中选出一个正确答案，并将对应的字母填入括号内）1．线性表的顺序存储结构是一种( )的存储结构。
安徽大学2010—2011学年第2学期《 数据结构 》考试试卷（B 卷） （闭卷 时间120分钟）考场登记表序号一、填空题（每小题1.5分，共15分） 1．含有36个元素的有序表，进行二分查找时的判定树的深度为 6 。
2．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍。
3． 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 44 。
4．由a ，b ，c 三个结点构成的二叉树，共有 5 种不同形态。
5．二维数组A[0‥5][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[0][5]的存储地址是1000，则A[3][9]的地址是 1088 。
6．若串s=''soft ，则其子串个数是 11 。
7. 设循环队列的空间大小为M ，入队时修改队尾指针rear 的语句为 rear=(rear+1)%M 。
8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中 一半 元素。
9．下列程序段的时间复杂度是 O(m*n) 。
for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]+=5;10. 在数据结构中，与所使用的计算机无关的是数据的 逻辑 结构。
二、单项选择题（每小题2分，共20分）1. 数据结构可以用二元组来表示，它包括（ A ）集合D 和定义在D 上的（ C ）集合R 。
A 、数据元素B 、存储结构C 、元素之间的关系D 、逻辑结构2． 已知L 是一个不带头结点的单链表，p 指向其中的一个结点，选择合适的语句实现在院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------p结点的后面插入一个结点s的操作（B）。
数据结构考试题及答案一、选择题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分×10=20分）1．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ D ）存储方式最省时间。
A.单链表B.双链表C.单向循环链表D.顺序表2．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ A ）。
A. 34B. 35C. 33D. 无法确定3. 单循环链表的主要优点是（D ）。
A. 不再需要头指针了B. 已知某结点的位置后，很容易找到其前驱C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表4. 在长为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（ B ）个元素。
A. n-iB. n-i+1C. n-i-1D. i5. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ C ）。
A. 5、4、3、2、1B. 4、5、3、2、1C. 4、3、5、1、2D. 1、2、3、4、56. 串是一种特殊的线性表，其特殊性表现在（ B ）。
A. 可以顺序存储B.数据元素是一个字符C可以链式存储 D.数据元素是多个字符7. 一棵5层满二叉树中，结点总数为（C ）个。
A. 33B.32C.31D.308. 下列4棵二叉树，（ B ）是平衡树。
A. B. C. D.9. n个顶点的无向图中最多有（A ）条边。
A. n(n-1)/2B. n(n-1)C. n(n+1)D. n(n+1)/210. 6个顶点的无向图中，至少有（A ）条边才能保证是一个连通图。
A. 5B. 6C. 7D. 8二、判断题（1分×10=10分）（F ）1. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。
（F ） 2. 二叉树是树的特殊情形。
（T ）3. 存在这样的二叉树，其先序遍历与中序遍历得到的访问序列相同。
（ F ） 4.用一维数组存储二叉树时，总是以先序遍历的顺序存储结点。
（F ） 5. 空串就是由空格组成的串。
（ F ） 6. 在AOE网中，一定只有一条关键路径。
（T ）7. m阶B-树每一个结点的子树个数都小于或等于m.（T ）8. 插入排序是稳定的。
（T ）9. 顺序存储的线性表可以实现随机存取。
（ F ）10.二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。
三、填空题（2分×8=16分）1．在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s->next=p->next；p->next=s ；2. 在有头结点的单链表L中，指针p所指结点是第一个结点的条件是p=L->next 。
3. 栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是后进先出。
4. 对于队，只能在队尾插入元素，只能在队头删除元素。
5. 抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示：数据对象、数据关系和基本操作。
四、简答和应用题（38分）1. （8分）某二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE.（1）画出此二叉树；（2）写出其后先序遍历的结果。
AB EC D FG (5分)CDBGFEA (3分)2. （9分）已知如图所示有向图，（1）求各点的入度和出度；（2）给出该图的邻接矩阵；（3）给出该图的邻接表。
(1)1: 0,3 2:2,1 3:3,0 4:1,1 5:1,2(3) 0 1→1→3→4 ^1 2 →2 ^2 3 ^3 4 →2 ^4 5→1→2^(2) 0 1 0 1 10 0 1 0 00 0 0 0 00 0 1 0 00 1 1 0 0(各3分)3. 给出下面稀疏矩阵的三元组。
（5分）5行6列:(1,2,12),(2,1,9),(4,1,-1),(4,5,10),(5,4,11) (5分)4. （8分）已知序列5，3，4，8，6。
（1）以该序列为权构造一棵有5个叶子结点的Huffman树。
（2）求上边构造的Huffman树的带权路径长度WPL.2615 117 8 5 63 4 (6分)WPL=(3+4)*3+(8+5+6)*2=21+38=59 (2分)5. （8分）已知如图所示的AOE网。
（1）求每项活动的最早开始时间e(ai)和最迟时间l(ai); （2）V1V2V4V5V6a1=3a3=2a5=4a4=3a6=1a7=2求其关键路径。
V3a2=2a8=3(见最后)ve vl e l l-e v1 0 0 a1 0 1 1 v2 3 4 a2 0 0 0v3 2 2 a3 3 4 1v4 6 6 a4 3 4 1v5 6 7 a5 2 2 0v6 8 8 a6 6 7 1a7 6 6 0a8 2 5 3(2分) (4分)a2 a5 a7关键路径: v1 →v3 →v4 →v6 (2分)五、设计题（16分）1. 编写实现“起泡排序”的子函数，入口参数是整形数组L[ ]和数组长度n.void sort(int L[],int n){ int i,j,t;for(i=n;i>1;i--)for(j=1;j<i;j++){if(L[j]>=L[j+1]){t=L[j];L[j]=l[j+1],l[j+1]=t;}2. 写出先序遍历二叉树的子函数，入口参数是其根结点指针BiTree型指针T，其中BiTree 定义为：typedef struct BiTNode {char data;struct BiTNode *LChild,*RChild;} BiTNode,*BiTree;void PreOrderTran(BiTree T){ if(!T){printf(“%c”,T->data);PreOrderTran(T->Lchild);PreOrderTran(T->Rchild);}一、选择题(每小题1分，共20分)1．以下数据结构中， a 是线性结构。
A）栈B）树C）二叉树D）图2．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 a 。
A、选择排序B、冒泡排序C、插入排序D、希尔排序3．下面 c 是顺序存储结构的优点。
A）存储密度大B）插入运算方便C）查找方便D）适合各种逻辑结构的存储表示4．用链式方式存储的队列，在进行插入运算时， b 。
A）仅修改头指针B）仅修改尾指针C）头、尾指针都要修改D）头、尾指针可能都要修改5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 a 排序法。
A）插入B）选择C）冒泡D）都不是6．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是 c 。
先序序列：EFHIGJK 中序序列：HFIEJKGA）E B）F C）G D）H7．下面 a 方法可以判断出一个有向图中是否有环。
A）深度优先遍历 B）拓朴排序 C）求最短路径 D）求关键路径8．下面关于串的叙述中， b 是不正确的。
A）串是字符的有限序列B）空串是由空格构成的串C）模式匹配是串的一种重要运算D）串既可以采用顺序存储，也可以采用链式存储9． b 的邻接矩阵是对称矩阵。
A）有向图B）无向图C）AOV网D）AOE网10．若在线性表中采用折半查找法查找元素，该线性表应该 c 。
A）元素按值有序B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构D）元素按值有序，且采用链式存储结构11．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移 c 个元素。
A、n-iB、n-i-1C、n-i+1D、i12．一个栈的入栈序列是12345，则栈的不可能的输出序列是 b 。
A、23415B、54132C、23145D、1543213．从邻接矩阵可以看出，该图共有 b 顶点。
A、9B、3C、6D、114．上题中，若是无向图，则有 d 条边。
A、5B、4C、3D、215．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 d 。
A、i<nB、2*i<=nC、2*i+1>nD、2*i>n16．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 b个元素。
A、64.5B、64C、63D、6517．5个顶点的有向图最多有 b 条弧。
A、5B、20C、30D、2518．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行d 。
A、q->next=p->next; p->next=q;B、p->next=q->next; q=p;C、p->next=p->next; q->next=q;D、p->next=q->next; q->nxet=p;19．对一个满二叉树，m个树叶，n个结点，深度为h，则有 d 。
A、n=h+mB、h+m=2nC、m=h-1D、n=2h-120．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为 d 。
A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL二、判断题：（判断下列各题正误，正确的在题目后面的括号内写“对”，错误的在题目后面的括号内写“错”。
每小题2分，共10分）（ t ）1. 含尾指针的单链循环表可以被用于队列操作。
（ f ）2. 栈和队列都不是线性数据结构。
（ t ）3. 数据项是数据的最小单位。
（ t ）4. 数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。
（ f ）5. 完全二叉树不可以用顺序存储结构进行存储。
三、填空题（每空2分，共10分）1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。
2、队列的插入操作在进行，栈的删除操作在进行。
3、设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为。
四、回答下列问题（每小题8分，共40分）1．分别给出对下图进行深度优先和广度优先遍历的结果。
2541368972．已知序列（12，4，17，10，7，30），用冒泡排序法对其进行递增排序，写出每一趟的排序结果。
3．一批数据有如下的逻辑结构B=(K ,R),其中K={ }, R={r}, r={ } ,试用图示法表示其逻辑结构。
4．已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。
