1年全国硕士研究生入学考试计算机统考试题参考答案

《1年全国硕士研究生入学考试计算机统考试题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011年全国硕士研究生入学考试计算机统考试题参考答案　　一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。请在答题卡上将所选项的字母涂黑。　　1.　　【答案】A　　2.　　【答案】B　　3.　　【答案】B　　4.　　【答案】C　　5.　　【答案】C　　6.　　【答案】D　　7.　　【答案】A　　8.　　【答案】C　　9.　　【答案】B　　10.　　【答案】A　　11.　　【答案】B　　12.　　【答案】D　　13.　　【答案】A　　14.　　【答案】B　　15.　　【答案】D　　16.　　【答案】A　　17.　　【答案

2、】C　　18.　　【答案】D　　19.　　【答案】C　　20.　　【答案】C　　21.　　【答案】D　　22.　　【答案】C　　23.　　【答案】B　　24.　　【答案】A　　25.　　【答案】D　　26.　　【答案】B　　27.　　【答案】D　　28.　　【答案】D　　29.　　【答案】A　　30.　　【答案】B　　31.　　【答案】B　　32.　　【答案】C　　33.　　【答案】A　　34.　　【答案】B　　35.　　【答案】B　　36.　　【答案】D　　37.　　【答案】D　　38.　　【答案】C　　39.　　【答案】C　　40.　　【答案】B二、综合应用题：41～47小题

3、，共70分。请将答案写在答题纸指定位置上。41．【答案解析】此题考察的知识点是图的存储以及关键路径求解的综合知识。（1）由题可以画出待定上三角矩阵的结构图如下（图中“？”待定元素）可以看出，第一行至第五行主对角线上方的元素分别5、4、3、2、1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：46∞∞∞5∞∞∞43∞∞33第五行第一行第二行第三行第四行将个元素填入各行即得邻接矩阵：（2分）A=(2)根据第一步所得矩阵A容易做出有向带权图G，如下：（2分）0123454654333(3)下图中粗线箭头所标识的4个活动组成G的关键路径（3分）0123454654333由上

4、图容易求得图的关键路径长度为：4+5+4+3=16。42．【答案解析】此题考察的知识点是基本算法的灵活运用。（1）算法的基本设计思想：（5分）1)       比较笨的方法：将两升序序列归并排序，然后求其中位数，时间复杂度是O(n)，空间复杂度O(n)。2)高效的方法：分别求两个升序序列A和B的中位数，设为a和b。如果a=b，则a或者b即为所求的中位数。原因：如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素；排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。如果

5、a≠b（假设a

6、1!=e1

7、

8、s2!=e2){mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(A[mid1]==B[mid2])returnA[mid1];if(A[mid1]

9、=0)//若元素个数为奇数个{e1=mid1;//舍弃A中间点以后部分且保留中间点s2=mid2;//舍弃B中间点以前部分且保留中间点}else//若元素个数为偶数个{e1=mid1+1；//舍弃A中间点以后部分且保留中间点s2=mid2；//舍弃B中间点以前部分且保留中间点}}}return（A[s1]