搜索
《数据结构B》期末试卷（A）第1页共6页《数据结构B》期末试卷（A）本试卷共4页；考试时间110分钟；专业班级学号姓名一、填空题（20分，共10题）1.数据结构主要研究数据的______结构，数据的存储结构以及在数据上执行的运算。2.设顺序表长度为100，若下标从0开始计，则删除元素a10需要移动______个元素。3.一棵二叉树中，若叶结点的个数为2011，则度为2的结点个数为______。4.有向图进行拓扑排序时，没有输出图中所有顶点，说明图中存在______。5.线性表采用二分搜索必须满足两个条件：线性表关键字必须是______；存储结构必须采用顺序存储结构。6.二叉搜索树的______序遍历序列是一个按关键字递增排列的有序序列。7.设有一组记录的关键字为{19,14,1,69,20,27,55,79}，散列函数为h(key)=key%11，散列函数值为3的有______个。8.快速排序算法平均情况下的渐近时间复杂度为O(______)。9.采用二次探查法解决冲突可能产生_______聚集。10.图常见的两种存储结构有邻接矩阵和_______。二、选择题（20分，共10题）1.一个算法必须在执行有穷步之后结束。这是算法的_______。A.有穷性B.正确性C.确定性D.可行性2.在指针p所指示的结点之后插入新结点s的操作是_______。A.s-link=p;p-link=s;B.s-link=p-link;p-link=s;C.s-link=p-link;p=s;D.p-link=s;s-link=p;3.栈和队列的共同点是_______。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点4.后缀表达式：532*3+3/+的值为_______。A.18B.7C.9D.8装订线内不要答题自觉遵守考试规则，诚信考试，绝不作弊《数据结构B》期末试卷（A）第2页共6页5.高度为5的二叉树至多有_______个结点。A.5B.10C.31D.326.采用对半查找方法查找长度为n的线性表时，时间复杂度为_______。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)7.n个顶点的无向图采用邻接矩阵表示，则该矩阵的大小是_______。A.nB.(n-1)2C.n2D.n–18.一个无向连通图的生成树是一个_______连通子图。A.极大B.极小C.有时极大D.有时候极小9.下列排序方法中，排序过程中的比较次数与排序方法无关的是_______。A.简单选择排序法B.直接插入排序法C.快速排序法D.冒泡排序法10.散列表的长度为11，下标范围是[0，10]，散列函数为h(key)=key%11。采用线性探查法解决冲突，依次将关键字7，38，5，16插入空的散列表中。则关键字16在散列表中存放的下标是_______。A.5B.6C.7D.8三、简答题（30分，共5题）1．有二叉树如图1所示，写出该二叉树的前序遍历序列和中序遍历序列。BEACDBAECD图1图22．写出图2所有可能的拓扑排序。3．设有向图的邻接表表示如图3所示，请给出每个顶点的入度。0∧0∧132434550∧11∧42∧0∧图3《数据结构B》期末试卷（A）第3页共6页4．空二叉搜索树中依次插入33，44，99，22，11，55，画出最终所构建二叉搜索树。5．设W={5,6,7,8,9}，（1）画出由权值集合W构造的哈夫曼树。（2）计算加权路径长度。四、判断题（10分，共5题）1．线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2．简单选择排序是稳定的排序算法。3．散列函数越复杂越好，因为这样随机性好，冲突概率小。4．完全二叉树一定存在度为1的结点。5．在一非空二叉树的中序遍历中，根结点的右边是其右子树上的所有结点。五、程序填空题（10分，共1题）1.以下程序是对半搜索的迭代实现，请填写完整。BOOLBSearch2(Listlst,KeyTypek,T*x){intmid,low=(1)_________,high=lst.Size－1;while((2)__________){mid=(low+high)/2;if(klst.Elements[mid].Key)high=(3)___________;elseif((4)_______________)low=mid+1;else{*x=lst.Elements[mid];returnTRUE;}}(5)_____________}《数据结构B》期末试卷（A）答案第4页共6页六、编程题（10分，共1题）1.用二叉链表方式存储二叉树。试编写函数Count1，求一棵二叉树的结点总数。并编写Count接口函数，让其调用Count1函数。typedefintK;typedefstructbtnode{KElement;structbtnode*LChild,*RChild;}BTNode;typedefstructbtree{structbtnode*Root;}BTree;《数据结构B》期末试卷（A）答案一、填空题（20分，共10题）12345678910逻辑892010有向回路有序中2nlog2n二次邻接表二、选择题（20分，共10题）12345678910ABCDCDCBAD三、简答题（30分，共5题）1．前序遍历序列：BADCE（3分）装订线内不要答题自觉遵守考试规则，诚信考试，绝不作弊《数据结构B》期末试卷（A）答案第5页共6页中序遍历序列：ABCDE（3分）2．每个1分，全对再加2分BACDEBACEDBCADEBCAED3．每个1分顶点入度0312213142514．9922115544335．1587201196535（4分）WPL=(5+6)*3+(7+8+9)*2=33+48=81（2分）四、判断题（10分，每题2分）12345××××√五、程序填空题（10分，每空2分）(1)0(2)low=high《数据结构B》期末试卷（A）答案第6页共6页(3)mid－1(4)klst.Elements[mid].Key(5)returnFALSE;六、编程题（10分，共1题）1．intCount(BTreeBt){returnCount1(Bt.Root);}intCount1(BTNode*p){if(!p)return0;elsereturnCount1(p-LChild)+Count1(p-RChild)+1;}