数据结构试题(答案)

吉首大学试题库 课程测试试题（ 卷） ----------------------以下为教师填写-------------------- I、命题院（部）： 数学与计算机科学学院 II、课程名称： 数据结构 III、测试学期：20 －20 学年度第 学期 IV、测试对象： 学院 专业 级 班 V、问卷页数（A4）： 页 VI、答卷页数（A4）： 页 VII、考试方式： 闭卷 （开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 单选题（每题 2 分，共20分） 以下数据结构中哪一个是线性结构？( ) A. 有向图 　　 B. 栈 C. 二叉树 　　 D. B树 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表 以下哪一个不是队列的基本运算？（ ） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？ A.15 B.14 　　 C.16 　　 D.21 由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.37 C. 19 D. 53 以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。 则该二叉树结点的前序遍历的序列为( ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 该二叉树有（ ）个叶子。 A．3 B.2 　　 C.5 D.4 该二叉树的按层遍历的序列为( ) A．E、G、F、A、C、D、B 　　　 B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D 　　　　 D. E、G、A、C、D、F、B 下面的二叉树中，( )不是完全二叉树。 设有关键码序列(q，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结果?( ) A. a，g ，m，q， z 　 B. a，g ，m，z,q C. g ，m，q，a，z D. g， m， a，q，z 填空题（每空1分，共26分） 数据结构是指数据及其相互之间的______________。当结点之间存在1对N（1：N）的联系时，称这种结构为_____________________。 一个广义表中的元素分为________元素和________元素两类。 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是_________________;删除一个结点时，需要执行的操作是___________________________（假设栈不空而且无需回收被删除结点）。 栈又称为_______________表，队列又称为___________表。 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。 若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、右子树皆非空的结点个数是________。 以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为________。 表示图的三种常用的存储结构为_____________、____________和_______________。 对于线性表（78，4，56，30，65）进行散列存储时，若选用H（K）=K %5作为散列函数，则散列地址为0的元素有________个，散列地址为4的有_______个。 在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。 在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。WPL称为_____________________。 在索引表中，若一个索引项对应主表的一个记录，则此索引为__________索引 ，若对应主表的若干条记录，则称此索引为________索引。 运算题（每题 6 分，共24分） 写出下列中缀表达式的后缀形式： 3X/(Y-2H)+1 2+X*(Y+3) 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。 先序： 中序： 后序： 按层：　　 a b c d e 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示  EMBED Equation.2 
 (1) 画出该图的图形； （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 已知一个图的顶点集V和边集E分别为： V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 阅读算法（每题7分，共14分） void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={2,5,8,22,15}; for(i=0;i<5;i++) Push(S,a[i]); while(!StackEmpty(S)) cout<