1、北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(ww.e-);咨询QQ:2696670126468-1北京科技大学2005年硕士学位研究生入学考试试题试题编号：468试题名称：数据结构及软件工程（共4页）适用专业：计算机系统结构、计算机软件与理论、计算机应用技术说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效第一部分：数据结构（共75分）注：统考生做第一、二、三、四题；单考生做第一、二、三、五题。一.（15分)回答下列各题1.简述数据结构中“层次结构”的特点。2.设pre、next分别为双向循环链表中结点的前驱和后继指针域，p为链表中某结点的指针，
2、写出在p所指结点之后插入指针s所指结点的C语言描述语句。3.一棵度为4的树中，若叶结点数为n0,出度为2、3、4的结点数分别为n2、3n4,指出n0与n2、n3、n4之间的关系，即n0=?4.无向图的“连通分量”和有向图的“强连通分量”分别表示什么？5.设待查找及待排序文件的记录数均为，“折半查找”及“堆排序”算法的时间复杂度分别如何？二.(16分)算法填空设Huffman树已采用二叉链表结构存储，求树的带权路径长度(WPL)的算法如下。其中ht为树根结点的指针，S为指针类型的栈（栈类型说明符为stpe,clearstack(S)、push(Spop(S)和emptystack(S)分别为置栈
3、空、指针P进线、州栈和判栈是否为空的函数。请填写算法中下画线的空白之处，完成其功能。typedef float weight;typedef struct hnodeE盖ada*ehaid;htnode,*htptr,weight HWPL(htptr ht)tptr p:stype S;e-studysky*if(ht-NULL)retum(cwplclearstack(S)while(p!emptystack(S)while(push(S,p);p-pop(S);f第1页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-)；咨询QQ:269
4、6670126W0:468-38.程序效率主要指处理机时间和两个方面。9.综合测试包括测试和测试。10.通常根据来评价软件维护活动。11.对象的状态，是对对象的一种抽象。12.在面向对象方法中，动态模型是基于事件共享而互相关联的一组的集合。13.软件质量因素分为三组：产品运行、和014.软件重用有三个层次，即知识重用、方法和标准重用和重用。15.软件开发过程中保证质量，主要有以下措施：审查、和二、选择题（共10分）1、原型化方法是用户和设计者之间执行的一种交互过程，适合于(A)系统。它从用户界面设计开始，首先形成(B),用户(C)并就提出意见。它是一种(E)型的设计过程。供选择的答案：A:需求
5、不确定性高的需求确定的管理信息决第B:用户界面使用手册界面需求分析说系统界面原型完善的用户界面C:改进界面的设计使用和不使用娜种编程语言程序的结构运行界面原型D:同意什么和不同意什么使用和不使用哪种编程语言程序的结构名执行速度是否清起要求E:自外向内自项向下自内向外2、结构化分析方法SA、结构化设计方祛SD和Jackson方法是软件开发过程中常用的方法。使用SA方法可以得到(，这种方法采用的基本毛段是(B)；使用$D方法可得到(C),并可实现(D):而使用Jackson方法可得到(E程序流程图模块结构图与模块功能说明书具体的语言分层数据流图和数据字典B:分解与抽象分解与综含归纳与推导试深与回溯
6、D、E:从数据结构导出程序结构从数据流图导出初始结构图从模块结构导出程序结构从PAD图导出N-S图三、判断题（共14分每小题1分）1、软件的发展依次经历了程序系统阶段、程序设计阶段和软件工程阶段。2.软件工程学家提出了软件工程的七条基本原理，其中承认了不断改进软件工程实践的必要性。3.软件的总体设计属于软件定义时期。4.尽可能推迟程序的物理实现，是按照瀑布模型开发软件的一条重要思想。5.管理复审的主要任务是，在软件生命周期每个阶段开始时，对成本、经费、进度等因素从管理角度进行审查。6.概念模型包括数据流图和数据字典。7.任何系统的数据流图基本模型都由若干个数据源点/终点、一个处理和一个数据存储组成。8.对“数据处理”的定义一般采用PO图描述，而数据字典主要由对数据的定义组成。9.结构化分析方法就是面向数据流自顶向下逐步求精进行需求分析的方法。通常从数据流图的输出端着手分析。10.在ER模型中，属性是实体所具有的性质。11.验证需求完整性和有效性的一个比较现实的方法，就是使用原型系统。12.总体设计阶段的任务包括结构设计和过程设计。13.软件模块的独立程度可以由内聚和耦合这两个标准来度量。14.扇入大一般是因为缺乏中间层次，需要适当增加中间层次的控制模块。第3页