真题_2013年_数据结构

《真题_2013年_数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2013年全国硕士研究生入学统一考试计算机学科专业基础综合试卷数据结构部分一、单项选择题：1~40小题。每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是A.O(n)B.O(m*n)C.O(min(m,n))D.O(max(m,n))2.一个栈的入栈序列是1,2,3,...,n，其出栈序列是p1,p2,p3,...,pn。若p2=3，则p3可能取值的个数是A.n-3B.n-2C.n-1D.不确定参考答案：D参考答案：C3.

2、若将关键字1,2,3,4,5,6,7依次插入初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是A.0B.1C.2D.34.已知三叉树T中有6个叶结点的权分别是2,3,4,5,6,7，T的带权（外部）路径长度最小是A.27B.46C.54D.56参考答案：B参考答案：D5.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是A.X的父结点B.以Y为根的子树的最左下结点C.X的左兄弟结点YD.以Y为根的子树的最右下结点参考答案：A6.在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排

3、序树T3。下列关于T1与T3的叙述中，正确的是(1)若v是T1的叶结点，则T1与T3不同(2)若v是T1的叶结点，则T1与T3相同(3)若v不是T1的叶结点，则T1与T3不同(4)若v不是T1的叶结点，则T1与T3相同A.仅(1)(3)B.仅(1)(4)C.仅(2)(3)D.仅(2)(4)参考答案：C7.设图的邻接矩阵A如下所示。各顶点的度依次是A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,2参考答案：C8.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,

4、c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g参考答案：Dbdchafge9.下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度，可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是A.c和eB.d和cC.f和dD.f和h参考答案：C10.在一棵高度为2的5阶B树中，所含关键字的个数最少是A.5B.7C.8D.14参考答案：A11.对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是007，110，119，114，911，12

5、0，122007，110，119，114，911，122，120C.007，110，911，114，119，120，122D.110，120，911，122，114，007，119参考答案：C二、综合应用题：41~47小题，共70分。二、综合应用题：41~47小题，共70分。41.（13分）参考答案(1)给出算法的基本设计思想。利用计数排序的思想，先求出原序列中每个元素的出现次数并保存在另一计数数组中然后检查计数数组中每个元素的值，返回值大于n/2的计数数组值。否则返回-1(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)

6、说明你所设计算法的时间复杂度和空间复杂度T(n)=O(n)S(n)=O(n)二、综合应用题：41~47小题，共70分。41.（13分）参考答案(2)参考算法：intMajority(intA[],intn){int*C;C=newint[n];for(inti=0;in/2)returni;//找到了主元素return-1;//没有找到主元素}42.（10分）设包含4个数据元素的集合S={“do”,“for”,“repeat”,

7、“while”}，各元素的查找概率依次为：p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答。(1)若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应当如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？(2)若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？42.（10分）设包含4个数据元素的集合S={“do”,“for”,“repeat”,“while”}，各元

8、素的查找概率依次为：p1=0.35,p2=0.15,p3=0.15,p4=0.3