北航研究生课程期末试卷软件技术基础

北航研究生课程期末试卷软件技术基础 北京航空航天大学研究生课程试卷 A 2009,2010 学年 第一学期期末试卷 学号 姓名 成绩 考试日期:2009年12月 23 日 考试科目:《 软件技术基础 》(A卷) 注意事项:1、考试时间120分钟 题目: 一、论述问题(本题共 40 分) 1、在一个算法中，时间与空间往往构成一对矛盾体，论述并举例说明解决时间的有效方法。(本小题15分) (10分)论述解决时间的有效方法。答题点包括: 1) (3分)增加存储空间是解决问题的一种方法 2) (7分)有效的算法是解决问题的有效方法 3)举(5分)例任何例子，能反映算法有效性都可以。 2、论述并举例说明软件工程中的测试与调试之间的相同点与不同点,(本小题10分) 答题要点及分数: 1)软件调试是编码过程中校正代码的过程 2)软件测试是软件工程中一个评价软件的过程 3) (4分)相同点在于试图考证程序的正确与否 4) (6分，只要答对两点就给6分)不同点在于组织方式，实施方法以及结果处理等几个方面 组织方式:调试工作由程序员完成，测试需要独立的小组 - 1 - 北京航空航天大学研究生课程试卷 A 实施方法:调试基于代码级，测试可以是白盒子也可以是黑盒子 结果处理:调试中发现的错误要改正，测试中只记录测试结果 3、阐述图与二叉树的相同点和不同点，在此基础上，阐述二叉树的前序遍历算法与图的深度优先遍历算法的相同点和不同点,(本小题15分) 1)(3分)图与二叉树都是非线性结构 2)(4分)图与二叉树之间的不同点是:二叉树中不同点的后继集合不相交，而图则不然 3)(4分)遍历算法中的相同点:访问当前结点，然后访问该结点的后继结点(邻结点) 4)(4分)遍历算法中的不同点:对于图的访问，访问结点时需要记录已访问标志，访问结点的邻结点时需要判断是否已访问;对于二叉树而言，访问邻结点时，不需要记录与判断。 二、假设在数组A[N]中存贮N个整数，设计算法change(int *A, int *B, int N), 其中N为数组A中元素的个数，该算法将数组A中整数移动到数组B中，使得数组B中的元素呈现小、大、小、大间隔的形式，即B[0]B[2], B[2]B[4],……,而且相邻两元素值之间的差的绝对值随下标值的增加呈现不增加趋势，例如|B[0]-B[1]|?|B[1]-B[2]|?|B[2]-B[3]| (本题20分) 算法的核心是对数组A实现从小到大的排序，然后从A数组的左右两端分别取数据，顺序放入B数组。分数安排如下: 1)( 10分)排序算法:任何排序算法都得分。如果没有给出排序算法，只说明要排序，得5分 2) (10分)移动数据到B :任意的移动，只要结果正确便得分。 三、假设每个人的信息仅包括姓名，年令和性别，在某信息管理系统中，经常需要查找同令人的姓名，设计物理存贮结构，使得查找过程方便快速，并给出相应的查找给定年令的算法，分析该算法的性能。(本题 20 分) 存储结构的核心是:以年令age为关键字的hash散列，散列函数是age-1;冲突的解决方法是链

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

。分数安排如下: 1)存贮结构(5分):画图，类C描述，文字描述都可以 - 2 - 北京航空航天大学研究生课程试卷 A 2) 查找算法(10分):函数原型描述(即假设的已知条件)，算法描述(包括根据年令访问数组，单向链表的访问) 3)算法分析(5分):结出平均比较次数的概念 四、假定二叉树存贮对象是整数，修改二叉树非递归前序遍历算法，使其能求得二叉树中最大元素。(本题20 分) 1) (10分)写出算法:包括函数原形，算法内容 2)(10分)将遍历算法中访问结点的语句改为求最大值的比较语句 - 3 -