2009试卷a(研)评分标准

《2009试卷a(研)评分标准》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京航空航天大学研究生课程试卷A2009－2010学年第一学期期末试卷学号姓名成绩考试日期：2009年12月23日考试科目：《软件技术基础》（A卷）注意事项：1、考试时间120分钟题目：一、论述问题（本题共40分）1、在一个算法中，时间与空间往往构成一对矛盾体，论述并举例说明解决时间的有效方法。（本小题15分）(10分)论述解决时间的有效方法。答题点包括：1)(3分)增加存储空间是解决问题的一种方法2)(7分)有效的算法是解决问题的有效方法3)举(5分)例任何例子，能反映算法有效性都可以。2、论述并举例说明软件工程中的测试与调试之间的相同点与不同点？（本小题

2、10分）答题要点及分数：1)软件调试是编码过程中校正代码的过程2)软件测试是软件工程中一个评价软件的过程3)(4分)相同点在于试图考证程序的正确与否4)(6分，只要答对两点就给6分)不同点在于组织方式，实施方法以及结果处理等几个方面组织方式：调试工作由程序员完成，测试需要独立的小组-6-北京航空航天大学研究生课程试卷A实施方法：调试基于代码级，测试可以是白盒子也可以是黑盒子结果处理：调试中发现的错误要改正，测试中只记录测试结果3、阐述图与二叉树的相同点和不同点，在此基础上，阐述二叉树的前序遍历算法与图的深度优先遍历算法的相同点和不同点？（本小题15分）1)（

3、3分）图与二叉树都是非线性结构2)（4分）图与二叉树之间的不同点是：二叉树中不同点的后继集合不相交，而图则不然3)（4分）遍历算法中的相同点：访问当前结点，然后访问该结点的后继结点（邻结点）4)（4分）遍历算法中的不同点：对于图的访问，访问结点时需要记录已访问标志，访问结点的邻结点时需要判断是否已访问；对于二叉树而言，访问邻结点时，不需要记录与判断。二、假设在数组A[N]中存贮N个整数，设计算法change(int*A,int*B,intN),其中N为数组A中元素的个数，该算法将数组A中整数移动到数组B中，使得数组B中的元素呈现小、大、小、大间隔的形式，即B

4、[0]B[2],B[2]B[4],……,而且相邻两元素值之间的差的绝对值随下标值的增加呈现不增加趋势，例如

5、B[0]-B[1]

6、≥

7、B[1]-B[2]

8、≥

9、B[2]-B[3]

10、（本题20分）1、排序用冒泡排序法对数组A排序：数组A的元素两两比较，大的放在后面（即若前面的大于后面的，交换两元素的为止）。循环执行直到不交换为止。2、移动定义两个变量i，j。初始i=0；j=N-1。定义一个变量m，初值为0。循环执行以下操作：B[m]=A[i];-6-北京航空航天大学研究生课程试卷AB[m+1]=A[j];m+=2;i++

11、;j--;直到i>=j最后if(i==j)B[m]=A[i];算法的核心是对数组A实现从小到大的排序，然后从A数组的左右两端分别取数据，顺序放入B数组。分数安排如下：1)(10分)排序算法:任何排序算法都得分。如果没有给出排序算法，只说明要排序，得5分2)(10分)移动数据到B：任意的移动，只要结果正确便得分。三、假设每个人的信息仅包括姓名，年令和性别，在某信息管理系统中，经常需要查找同令人的姓名，设计物理存贮结构，使得查找过程方便快速，并给出相应的查找给定年令的算法，分析该算法的性能。（本题20分）存储结构的核心是：以年令age为关键字的hash散列，散列

12、函数是age-1；冲突的解决方法是链表。分数安排如下：1)存贮结构(5分)：画图，类C描述，文字描述都可以以年龄age为关键字，哈希散列函数为H=age–1；冲突解决办法为链表-6-北京航空航天大学研究生课程试卷A如图：2)查找算法(10分):函数原型描述(即假设的已知条件)，算法描述（包括根据年令访问数组，单向链表的访问）LPFIND（intage，CStringname）{H（age）=age–1；p=H（age）；if(p==NULL)returnNULL;while(p!=NULL){if(p->name==name)-6-北京航空航天大学研究生课程

13、试卷Aretutnp;p=p->next;}3)算法分析(5分):结出平均比较次数的概念根据age查找同龄人的姓名（由哈希查找的特点），不需要比较直接由哈希散列函数求出。假设某年龄age的人数为n，即有n人同龄。那么查找第i个人需要比较的次数为i次。又假设查找每个人的概率相同，均为1/n;那么平均比较次数为：，i=1,2，…,n;=(1+n)/2。四、假定二叉树存贮对象是整数，修改二叉树非递归前序遍历算法，使其能求得二叉树中最大元素。（本题20分）1)(10分)写出算法：包括函数原形，算法内容2)(10分)将遍历算法中访问结点的语句改为求最大值的比较语句in

14、tMax(BTREET){inttemp;BTREE