北科大2004年《数据结构及软件工程》考研真题.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126北京科技大学2004年硕士学位研究生入学考试试题考试科目：468数据结构及软件工程(共3页)适用专业：计算机软件与理论说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效考试用具：第一部分：数据结构（共75分)一，(16分)设A、B分别为两个带头结点单链表的头指针，且两表中结点的数据集均为整数集合。下面算法产生两表中数据的交集，并以表C存储之（即C为结果表的头指针刘请填充算法中下画线的空白之处，完成其功能（填充的内容请写在答题纸土）Typedef struct nodeint data;struct node*next:Inode,*link;link andset(link A,link Blink C,r,p,q,s;C=-(link)malloc(sizeof(node)q=B-next;data-q-databreak;r-next=NULL;retum(C);二.(24分)设记录的关键字ky)集合：K=11,2,13,26,5,18,4,9l.描述Huffman树的结点形式，并以K为权集，构造一裸Huffian树，将树中各结点存入一维数组HTm+1中，其中m=15,为本树中的结点数；2.设Hash表表长m=16,选取的Hash函数H(key)=(key)%13,处理冲突的方法为“线性探测法”，请依次取K中各值，构造出满足所给条件的Hsh表结构，并在等概率条件下，求对该表的平均查找长度(ASL):3.设以K中第一个关键字(11).为枢轴，写出对K按“快速排序”方法排序时，第一趟排序结束时的结果（按升序排列），并将K调整成一个堆顶元素取最小值的堆。第1页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(wwww.e-);咨询QQ:2696670126三.(20分)设有向网G如下：V331.请写出网G的邻接矩阵画出网G的十字链表结构；来的风顶点，到顶京9的两条关健路统入4其路径长度。2.求出网G的3个拓扑序列；四(15分)算法设计设一棵叉树己用链式结构存储，根结点指针为七，结点的数据值和左、右孩子指针域分别为ata、Ichild和rchild。请采用按层次遍历二叉树的方法，用C语言函数形式写出将树中每个结点的左右子树宜换的算法：exchange(注J算法中可调用欧列”或“栈”操作的基本函数。)第二部分：软件工程（共75分)-、判断正误（共9分，每小题1分）生题号的左边画X(错)或V(对)1.概念模型常用ER模型来表示，它有实体和联系两个成份。2.软件设计阶段，把系统划分的模块越多越细，越有利于开发。3.集成测试一般采用非渐增式测试方法。4:边界值分析的方法属于白盒测试技术。5.自动测试方法中有一种是文件比较法。6.自顶向下的集成测试，是采用深度优先的方法。7.对象是面向对象软件的基本模块，独立性好，其动作是被动的。8.归纳关系（即“一般一特殊”关系），反映了一个类与若干个子类之间的分类关系。组合关系反映了类之间的构成关系，又称为聚集关系。9.软件重用主要有三种技术：软件组合、软件生成、面向对象。二、填空（共35分，每空1分)1.软件工程是指导计算机软件的和的工程学科。2.软件开发期包括系统设计和系统实现，系统设计包括和阶段，系统实现包括和阶段。3和共同定义了系统的逻辑模型。一般从以下方面验证软件需求的正确性：和第2页北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-studysky.con);咨询QQ:26966701265.经典的结构化程序设计只允许使用以及三种控制结构。6.Jackso如程序设计方法面向数据结构，采用了三种逻辑结构：测试包括测试和综合测试。综合测试包括集成测试和测试。集成测试又包括测试和测试。7.验收测试必须要有参加。8.维护是最多的软件维护活动，维护也是必要又经常的。9.主要从三个方面考查软件质量因素。10.面向对象方法通常需要建立三种模型：011.只有同时使用和才是真正面向对象的方法。三、简要回答（共21分)1.简述变换流与事务流的关系(3分)2.等价类划分与边界测试的关系？(3分)3.什么是预先指定的系统和用户驱动的系统？其开发模式有何不同(6分)4.请比较PO图和DD图的作用有何异同？(3分)烟一般情况下，在程序的哪两个部分写注释？各自的内容？(4分)6.什么是软件的可靠性？(2分)四、应用题（共10分）1.(共6分)画出下列程序的NS盘图和PAD图。START0名IF p THENBLOCKgEND BLOCKWHILE q DOEND DO-END IF【共4分在某项目中，共有C三个模块嚮要编程，各模块预计编程工期分别为2、1、】个月，各模STOP2.预计测试工期均为L个月，可用的程序员为甲、乙2人，可用的测试员为丙丁2人。请将下面的Gtt图中左边两列填充完普任务负责人C编程丙C测试了第3页