2018年山东省中国海洋大学数据结构和软件工程考研真题.doc

《2018年山东省中国海洋大学数据结构和软件工程考研真题.doc》由会员分享，可在线阅读，更多相关《2018年山东省中国海洋大学数据结构和软件工程考研真题.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2018年山东省中国海洋大学数据结构和软件工程考研真题数据结构部分：要求：算法描述用C语言，对算法中用到的数据结构加以说明描述。一、选择题(共10题，每题2分，共20分)1.在存储结构上，必须占一片连续空间的是哪种结构?(1)图(2)栈(3)队列(4)数组2.设输入元素序列为1,2,3,4,5,利用两个队列，下面哪种排序不可能得到?(1)1,2,3,4,5(2)5,2,3,4,1(3)1,3,2,4,5(4)4,1,5,2,33.在线索二叉树上，线索是什么?(1)两个标志域(2)数据域(3)指向结点前驱和后继的指针(4)指向左、右子树的指针4.已给如图所示哈夫曼树，那么电文CDAA的编码是什么

2、?(1)110100(2)11011100(3)010110111(4)111111005.在N个结点的完全二叉树中，对任一结点I(1=I=N),那么I的左孩子可能是哪一个?(1)1/2(2)2I+1(3)2I(4)都不是6.已给如图所示二叉树，A,B,C,D分别带权值为7,5,2,4,则该树的带权路径长度是多少?(1)46(2)36(3)35(4)都不是7.在图的表示中，哪一种是一种顺序表示法?(1)数组(2)邻接表(3)十字链表(4)邻接多重表8.平衡二叉树上结点的平衡因子不能是哪一个值?(1)-1(2)0(3)1(4)29.堆排序在最坏情况下，其时间复杂度是多少?(1)0(n2)(2)0

3、(nlogn)(3)0(n)(4)都不是10.m阶B-树中的m是指。(1)每个结点至少有m棵子树(2)每个结点至多有m棵子树(3)非终端结点中关键字的个数(4)m阶B-树的深度(或高度)二、解答题(共5题，每题7分，共35分)1.折半查找适不适合链表结构的序列，为什么?用二分查找的查找速度必然比线性查找的速度快，这种说法对吗?2.给出一组关键字(12,2,16,30,8,28,4,10,20,6,18),按从小到大顺序，写出对其进行希尔排序的排序过程(第一趟排序的增量为5)。3.已知序列503,87,512,61,908,170,897,275,653,462将其调整为堆(大堆顶，即)4.已知

4、一棵3阶B-树如下图所示。(1)画出插入(18)后的3阶B-树；(2)画出在插入(18)后的3阶B-树中删除(78)后的3阶B-树。5.利用普里姆(Prim)算法求下图的最小生成树，写出执行算法过程中各步的状态。三、证明：(10分)设与记录R1,R2,Rn对应的关键词分别是K1,K2,Kn。如果存在Ri和Rj使得ji且KiKj成立，试证明经过一趟起泡后，一定有记录与Ri进行交换。四、(10分)设计算法：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。五、(15分)已知无向图G,设计算法求距离顶点vO的最短路径长度为K的所有顶点，要求尽可能节省时间。(1)用文字写出实现上述过程

5、的基本思想；(5分)(2)写出算法。(10分)软件工程部分：一、填空题(每空1分，共10分)1、软件生命周期包括(1)、可行性研究、(2)、(3)、(4)、(5)、综合测试、软件维护8个阶段。2、可行性研究主要是从技术可行性、(6)和(7)三个方面研究可行性。3、软件能力成熟度模型包括(8)、(9)、(10)、已管理级、优化级5个级别。二、判断题(每题2分，共20分，正确的打,错误的打)1、在系统中软件成本所占的比重越来越少导致软件危机。2、螺旋模型的主要优势在于它是风险驱动的。3、软件测试的目的是证明软件中没有错误。4、白盒测试又称为功能测试。5、程序设计中，应避免数据耦合。6、可通过访谈获取用户的需求。7、向已经延期的项目增加人力，会使它更加延期。8、软件模块间应尽可能紧耦合。9、软件维护过程中，把诊断和改正错误的过程称为改正性维护。10、面向对象方法学认为任何事物都是对象。三、简答题(每题5分，共20分)1、请说明软件能力成熟度模型第1级、第2级两个级别的特征。2、什么是关键路径?3、请说明面向对象方法学的优点。4、请解释什么是判定覆盖。四、分析题(共1题，共10分)如图所示的程序流程图，请画出对应的流图，并用三种方法计算其环形复杂度，并给出求解过程。