XX大学成人教育学院2022-2023学年度第二学期期末考试《数据结构》复习试卷1.docx
XX大学成人教育学院2022-2023学年度第二学期期末考试数据结构复习试卷1学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要 求，请在答题卡上正确填涂。）1.一棵高为k的二叉树最少有（B ）个结点。（2分）C. 2k1（2分）C. 3（2分）C. n（n+l）D. 2k-l2 .广义表（a, （b, （）,c）的深度为（C ）。A. 1B. 23 .含n个顶点的有向图最多有（B ）条弧。A. nB. n（n-l）4 .设对下图从顶点a出发进行深度优先遍历，则D.4D. n2（2分）A. acfgdebB. abcdefg（A ）是可能得到的遍历序列。C. acdgbefD. abefgcd5.具有n个顶点的有向强连通图最少有（B）条弧。（2分）A.n-1B.nC.n（n-l）D.n（n-l）26,下列叙述中错误的是（B）。（2分）A.树的度与该树中结点的度的最大值相等B.二叉树就是度为2的有序树C.有5个叶子结点的二叉树中必有4个度为2的结点D.满二叉树一定是完全二叉树7 .由树转换而得的二叉树，根结点（B）。（2分）A.没有左子树B.没有右子树C.左右子树都有D.视树的形态而定8 .一棵二叉树中第6层上最多有（C）个结点。（2分）A.2B.31C.32D.649.将一个AL.100,L.100的三对角矩阵,按行优先存入一维数组BL.298中，则A中的元素A66,65在数组B中的位置K=（八）。（2分）A.195B.196C.197D.198010"10110.设图G的邻接矩阵A=IIO1Oi,则图G中共有（B）个顶点。（2分）A.1B.3C.4D.9二多选题（共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。）11 .（ACD）二叉排序树不可以得到一个从小到大的有序序列。（2分）A.先序遍历；B.中序遍历；C.后序遍历；D.层序遍历12 .对线索二叉树叙述正确的是（ABCDE）o（2分）A.加上线索的二叉树称为线索二叉树B.指向前驱和后继的指针称为线索；C.若二叉树结点的左孩子指针为空，可用其指向其前驱；D.若二叉树结点的右孩子指针为空，可用其指向其后继；E.对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化13.以下说法中正确的是（ABC）O（2分）A.无向图中的极大连通子图称为连通分量；B.连通图的广度优先遍历中一般要采用队列来暂存刚访问过的顶点；C.图的深度优先遍历中一般要采用栈来暂存刚访问过的顶点；D.有向图的遍历不可采用广度优先遍历方法14.已知广义表L=（x,y,z）,a,（u,t）,W）,下列运算中结果为原子项的是（BD）。（2分）A.tail（head（tail（tail（L）B.head（tail（L）C.tail（head（L）D.head（head（tail（tail（L）15 .先序序列和中序序列相同的二叉树有（ACD）。（2分）A.空二叉树；B.左单支树；C.右单支树；D.根树三判断题（共9题，总分值9分正确的填涂“A”，错误的填涂"B"o）16 .最小生成树是指边数最少的生成树。（1分）（B）17 .二叉树中序线索化后，不存在空指针域。（1分）（B）18 .若图G有环，则G不存在拓扑排序序列。（1分）（八）19 .二叉树不是树的特殊情况。（1分）（八）20 .具有10个叶结点的二叉树中，有9个度为2的结点。（1分）（八）21 .如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G一定有2个连通分量。（1分）（八）22 .在有向图中，各顶点的入度之和等于各顶点的出度之和。（1分）（八）23 .完全二叉树中，若一个结点没有左孩子，则它必是树叶。（1分）（八）24 .二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的根结点是哪一个，则可以确定这棵二叉树。（1分）（B）四简答题（共2题，总分值20分）25 .试写出对如下无向图从顶点A出发进行广度优先遍历可能得到的所有遍历序列。（10分）答：AbcegiifdAbcehgfdAcbghedfcbhgedf26.试将下图中的树转化为二叉树。（10分）答:五综合题(共3题，总分值41分)27 .试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。(13分)答：intdepth(BiTreet)if(It)returnO;if(t->lchild)有左子树if(t->rchild)左、右子树均有hl=depth(t->lchild);求左子树高度hr=depth(t->rchild);求右子树高度returnhl>hr?hl+l:hr+l;)else只有左子树returndepth(t->1chi1d)+1;else无左子树returndepth（t->rchild）+l;有右子树，则返回右子树高度加1无右子树，即右子树高度为0,则返回11/depth28 .一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。若按层次顺序从1开始对全部结点编号，则：第i层上有多少个结点？编号为P的结点的第i个孩子结点（若存在）的编号是多少？（3）编号为P的结点的双亲结点（若存在）的编号是多少？（14分）答：第1层有1个结点，第i层结点数=第i-1层结点数*k（2WWH）个当根结点以及前面的P-I个结点的孩子都编了号之后，才开始为结点P的孩子编号。结点P的第i个孩子的编号为（1+（P-I）*k）+i0若P=1,则为根结点，无双亲，否则可设双亲结点编号为s,由可知结点s的孩子结点Zl,Z±ir的编号范围为（s1）*k+2（s1）*k+k+1,即kM,又：p÷A:-2：J=；：j由S为整数，可得-RJo29.设有向网如下，试用迪杰斯特拉算法求从顶点A出发到其余各顶点的最短路径。（14分）答:DPATHDPATHDPATHDPATHAO000B1OO1<x>110ACDB18ACDEBC22AC2AC2AC2ACD37AD35ACD3ACD3ACDE484846ACDE4ACDEF5<x>56ACF56ACF56ACFG6868613ACDG613ACDGDPATHDPATHDPATHAO00B18ACDEB1ACDEG1ACDEGC2AC2AC2ACD3ACD3/ACD3ACDE4ACDE4ACDE4ACDEF5ACF5ACF5ACFG612ACFG610ACFGE6ACFGE
