同等学力申硕全国统考计算机科学与技术真题与答案.docx

2008年同等学力申硕全国统考计算机科学与技术试卷计算机科学与技术试卷第一部分数学基础课程第二部分专业知识课程.计算机系统结构.计算机网络.软件工程.人工智能原理.计算机图形学考生须知1.本试卷满分为100分，包括数学基础课程和专业知识课程两部分。数学基础课程满分40分，每位考生必答；专业知识课程包括五门课程，每门课程满分30分，考生须从中任选2门作答，多选者只按前选课程计分。2.请考生务必将本人准考证号最后两位数字填写在本页右上角方框内。3.考生一律用蓝色或黑色墨水笔在答题纸指定位置上按规定要求作答，未做在指定位置上的答案一律无效。4.监考员收卷时，考生须配合监考员验收，并请监考员在准考证上签字（作为考生交卷的凭据）。否则，若发生答卷遗失，责任由考生自负。计算机科学与技术试卷第1页共10页第一部分数学基础课程（共40分）一、用逻辑符号形式化下列语句（本大题共2小题，每小题2分，共4分）1每个人的指纹都不相同。2自然数不是奇数就是偶数，且奇数不能被2整除。二、填空题（本大题共4小题，第1小题每空1分，第2、3、4小题每空2分，共10分）1设A、B均为有穷集合，A和B的基数分别是m和n（m0,n0）。（1）当m和n满足时，存在从A到B的双射函数。此时共可生成个不同的双射函数。（2）当m和n满足时，存在从A到B的单射函数。此时共可生成个不同的单射函数。2已知5位老师和3位学生围圆桌就座，如果要求学生两两不相邻，则有种就座方案。3整除2310的正奇数有个。4设图的顶点集合为VG，边集合为。则G的生成树有G1234(),vvvv=1223344113(),EGvvvvvvvvvv=棵。三、解答题（本大题共3小题，第1、2小题每题4分，第3小题8分，共16分）1设PQ=(PQ)，仅用联结词分别表示出P，PQ，PQ。2设T是一棵有13个顶点的树，称树中度为1的顶点为叶子。如果T的顶点的度只可能是1,2,5且T恰好有3个度为2的顶点，那么，T中有多少个叶子？3求1,4,5,8,9这五个数字组成的位数的个数，要求4,8出现的次数均为偶数，而1,5,9出现的次数不加限制。n四、证明题（本大题共2小题，第1小题4分，第2小题6分，共10分）1设R是非空集合A上的二元关系，R满足条件：（1）R是自反的；（2）若RR，则R；试证明R是A上的等价关系。2随意地把一个9棋盘的每个方格涂成红色或蓝色，求证：必有两行方格的涂色是一样的。3计算机科学与技术试卷第2页共10页第二部分专业知识课程计算机系统结构（共30分）一、填空题（本大题共2小题，每小题2分，共4分）1用下面三条指令可以完成向量表达式D=A(B+C)的运算。假设向量长度N5THENS3ELSES4;n=1;WHILEn5THENS6ELSES7;END.3给出CMM的5级模型，并以其中一个CMM等级为例，列出该等级包含的关键过程域。四、建模题（本大题共3小题，共8分）问题陈述：在一简化的某学校图书管理系统中，库房管理员职责：根据各系的要求负责购买图书，并为新书编制图书卡片（分类目录号、流水号、书名、作者、价格、购书日期），写入图书目录文件。图书管理员职责：根据借还书的要求负责借还图书处理：（1）当没有要借的图书时，向借阅人发无书通知；（2）当借阅人将图书丢失时，以图书丢失单的形式报告图书管理员，由图书管理员下罚款单给借阅人；同时图书管理员负责修改图书目录文件，并通知库房管理员。图书馆主任职责：每月末根据分类目录号查看某种图书库存量，当库存量低于库存下限时，通知库房管理员购书。1（3分）用结构化分析方法给出该系统的顶层DFD（系统环境图）；2（2分）给出顶层DFD的数据字典；3（3分）选择该图书管理系统中的一个交互，并用顺序图来描述。计算机科学与技术试卷第8页共10页人工智能原理（共30分）一、单项选择题（本大题共4小题，每小题2分，共8分）1使用神经网络来求得分类问题的解，实际常用的手法是通过（）来达到。A增减神经网络的层数B调整神经网络的连接权值C增减输入节点2本体（Ontology）是一种（）。A推理方法B产生式系统的另一种形式C概念和概念间关系的表示方法3从理论上讲没有当今计算机不能计算求解的问题（）。A是B不是C尚无定论4像Baidu（百度），Google（谷歌）这类知识问答系统，所使用的主要技术是（）。A自然语言的语义理解方法B知识推理方法C简单的模式匹配方法二、证明题（7分）试用线性归结法证明AAB12A3()()()(其中)()()()()1A,xCxDxyGxyEy=$()()()()()()()2A,xCxFxyGxyFy=$()()()()3AxDxFx=()()()()BxExFx=三、问答题（本大题共3小题，每小题5分，共15分）1近年来人工智能学科的研究热点，主要在哪几个方面？2说明Agent（智能体或主体）概念，以及多Agent系统的主要研究内容。3说明一种归结方法是完备的含义，并举出一种不完备的归结策略。计算机科学与技术试卷第9页共10页计算机图形学（共30分）一、判断题（本大题共5小题，每小题1分，共5分。如果正确，用“”表示，否则，用“”表示）1在图形系统中，图形处理运算的精度不取决于显示器的分辩率。（）2Bezier曲线形状取决于所选择的坐标系和特征折线集（多边形）顶点的相对位置。（）3B样条曲线具有几何不变性（形状和位置与坐标系的选择无关）。（）4定义了物体的边界也就唯一的定义了物体的几何形状边界，物体边界上的面可以是平面或任何形状曲面。（）5平行投影能真实地反映物体精确的尺寸和形状，视觉效果更有真实感。（）二、填空题（本大题共5小题，每小题2分，共10分）1使用二维图形变换矩阵=T12100100021将产生变换的结果是。2种子填充算法也是一种很常用的多边形区域填充算法，与边填充算法不同，其基本原理是。3Z-Buffer消隐算法是一种典型的消隐算法，其缺点是。4Phong模型是简单光反射模型，它模拟物体表面对光的反射作用，主要考虑的是物体表面对的反射作用。对物体间的光反射作用，只用一个做近似处理。5用于减少或消除“走样”的技术措施，就被称为“反走样”。除了提高分辨率之外，还有和两种常用的“反走样”方法。三、问答题（本大题共3小题，每小题5分，共15分）1在计算机图形学中，通常所谓“物体”的含义是什么？并写出其准确的定义。2已知三次B样条曲线上的五个形值点分别为Q0(30,0),Q1(24,24),Q2(0,18),Q3(-24,24),Q4(-30,0)控制顶点P0,P1,P2,P3,P4，该曲线起点Q0与P0重合，切于向量P0P1，终点Q4与P4重合,切于向量P3P4，求控制顶点P1,P2,P3。3为生成真实感图形，可采用一种HLS颜色模型，试分别说明H、L和S所代表的三个要素及其含义。计算机科学与技术试卷第10页共10页2008年同等学力人员申请硕士学位学科综合水平全国统一考试计算机科学与技术试卷答案及评分参考第一部分数学基础课程一、形式化下列语句（本大题共2小题，每小题2分，共4分）1解：设M(x)：x是人；N(x,y)：xy，即x与y是不同的人；E(x，y)：x与y的指纹相同。则原句可形式化为以下两种形式之一：（1）(x)(y)(M(x)M(y)N(x,y)E(x,y)（2）(x)(M(x)(y)(M(y)N(x,y)E(x,y)说明：如仅缺少N(x,y)的内容，则只给1分。2解：设P(x)：x是自然数，Q(x)：x是奇数，R(x)：x是偶数，D(x)：x能被2整除。原句可形式化为：(x)(P(x)(Q(x)R(x)(Q(x)D(x)说明：（1）如仅答对部分内容最多给1分。（2）全句必须写成一个式子，且中间用联结词联结，否则扣0.5分。二、填空题（本大题共4小题，第1小题每空1分，第2、3、4小题每空2分，共10分）1（1）m=nm!（2）mn!mmnnCmA=2或14404!54331648三、解答题（本大题共3小题，第1、2小题每题4分，第3小题8分，共16分）1解：（1）P(PP)PP-1分（2）PQ(PQ)(P)(Q)(PP)(QQ)（见下面说明）计算机科学与技术试卷答案第1页共14页（3）PQ(PQ)(PQ)(PQ)(PQ)（见下面说明）如（2）、（3）小题中仅做对一题则给2分，（2）和（3）小题都做对则给3分。2解设T中有x个叶子，则T中有13310xx-=-个度为5的顶点，由于树中的边数等于顶点个数减去1，即边数为12-2分由顶点度数之和等于边数的两倍得1235(10)21xx+-=2解得，故中有8个叶子。-2分8x=T3解设满足条件的位数的个数为，则序列对应的指数型母函数G(iia123,aaaL)x为24232G()=(1+)(1)2!4!2!3!xxxxxx+L3L-2分由于23e=12!3!xxxx+L故23e=12!3!xxxx-+-+L于是2411(2!4!2)xxxxee-+=+L-3分故231G()=()4xxxxeee-+=531(24)xxxeee+01(5231)4!nnnnxn=+-2分故=na1(5231)4nn+-1分四、证明题（本大题共2小题，第1小题4分，第2小题6分，共10分）1证明：由条件（1），R已满足自反性。需证明R满足对称性和传递性。1）对于任意的，R且由条件（1）RR-1分由条件（2）R-1分所以，R满足对称性。计算机科学与技术试卷答案第2页共14页2）对于任意的，RR由对称性RR-1分由条件（2）R-1分所以，R满足传递性。综合1），2）可得，R是A上的等价关系。2证明：用红、蓝两色去涂1棋盘，共有3328=种涂色方法。-2分设表示第种涂色方法.设是任一个已用红、蓝涂了色的棋盘，以表示的第k行的涂色方法。设(1,2,8)iai=L(1,2,9)bk=LiJ93kJ129,Bbbb=L并令|,(1,2,8)jBbbBbaj=j且与相同L。则。-2分8j=jBBB=1且UjB)B中9个元素放到这8个抽屉里，由鸽笼原理，必有正整数,使得|，即(1,2,8jBj=L(18)tt2tBtB中至少有两个元素不妨设为，这说明在涂色中，棋盘的第行和第行的涂色一样。-2分mbb和lJml计算机科学与技术试卷答案第3页共14页第二部分专业知识课程计算机系统结构试卷答案及评分参考一、填空题（本大题共2小题，每小题2分，共4分）13N+22；N+1623；9二、问答题（本大题共3小题，每小题2分，共6分）因为主存包含4096=212个块，Cache中包含64=26个块，每个块大小128=27个字，所以：1主存字地址为12+7=19位2Cache字地址为6+7=13位3区号为19-13=6位，组号为6-2=4位，块号为2位，块内地址为7位区号组号块号块内地址12627（注：只要得数正确就可以得分）三、设计题（本题共5小题，每小题2分，共10分）1禁止集合为2，3，5，初始冲突向量为（10110）2流水线调度的状态转移图如下：简单循环平均启动距离（1，6）3.5（4，6）5（4）4（6）63流水线的最小启动循环为（1，6）；最小平均启动距离为3.5计算机科学与技术试卷答案第4页共14页4流水线各功能段之间的连接图如下：输出输入S1S2S35插入非计算延迟后，流水线的最佳平均启动距离为3，所以，最大可能的吞吐率TP=1/(3*20)ns四、计算题（本大题共4小题，共10分）1指令n+1与n+2之间有关于寄存器R0的写读数据相关；-1分指令n+3与n+6之间有关于寄存器R2的写读数据相关；-1分指令n+4与n+5之间有关于寄存器R4的读写数据相关；-1分指令n+3与n+6之间有关于寄存器R2的写写数据相关。-1分2采用顺序发射顺序完成调度方法的流水线时空图：（1分）12345678910111213n+1IF1ID1LSWR1n+2IF2ID2ADDADDWR2n+3IF1ID1LSWR1n+4IF2ID2MULMULMULWR2n+5IF1ID1ANDWR1n+6IF2ID2ADDADDWR2执行这个程序共用130ns。-1分3采用顺序发射乱序完成调度方法的流水线时空图：（1分）123456789n+1IF1ID1LSWR1n+2IF2ID2ADDADDWR2n+3IF1ID1LSWR1n+4IF2ID2MULMULMULWR2计算机科学与技术试卷答案第5页共14页n+5IF1ID1ANDWR1n+6IF2ID2ADDADDWR2执行这个程序共用90ns-1分4采用顺序发射乱序完成调度方法的流水线时空图：（1分）1234567n+1IF1ID1LSWR1n+2IF2ID2ADDADDWR2n+3IF1ID1LSWR1n+4IF2ID2MULMULMULWR2n+5IF1ID1ANDWR1n+6IF2ID2ADDADDWR1执行这个程序共用70ns-1分IF：取指令ID：译码LS：LOAD访存WR：写结果ADD：加法MUL：乘法AND：与操作计算机科学与技术试卷答案第6页共14页计算机网络试卷答案及评分参考一、单项选择题（本大题共10小题，每小题1分，共10分）1C；2C；3D；4B；5C；6B；7B；8D；9B10A二、名词解释（本大题共2小题，每小题3分，共6分）1答：指具有单一管理权限（或独立行政单位管辖下）的网络和路由器（2分）；采用AS内部网关协议（域内路由选择协议）确定分组在AS内的路由（0.5分）；采用外部网关协议（域间路由选择协议）处理分组在AS之间的路由（0.5分）。2答：TCP进行拥塞控制的一种方法（1分）；使拥塞窗口在初始时大小为1（1个最大报文段长度），每收到一个ACK应答（对新报文段的确认），拥塞窗口增1，逐步增加拥塞窗口大小（2分）。三、问答和计算题（本大题共4小题，共14分）1答：以太网定义最短帧长为64字节（1分）。最短长度的限制与以太网MAC层的CSMA/CD协议有关（1分）。以太网在发送数据帧时能够检测到冲突并停止发送。如果帧长度过短，在检测到冲突之前帧已经发送完毕，则协议无法进行有效冲突检测（1分）。2答：TCP协议是面向连接的协议（1分）；可靠建立连接（也可答三次握手建立连接）和终止连接（1分）；采用滑动窗口协议进行流量控制和差错控制（1分）。3答：发送一帧所需时间t1=1KB*8/1.6Mbps=5ms（1分）RTT=45ms若使用滑动窗口协议，可连续发送帧数：145/5=10帧（1分），241023,因此，至少使用4位序号；（2分）4答：收到路由向量：A（0，3，12，16）B（15，0，4，6），C更新后的路由表（分别到A,B,C,D的路由向量）;(（7，A），（10，A），（0，），（20，B）)评分说明：每答对到一个节点的路由的时延值得0.5分，答对输出线路得0.5分；若答案为（7，10，0，20）得2分计算机科学与技术试卷答案第7页共14页软件工程试卷答案及评分参考一、单项选择题（本大题共5小题，每小题1分，共5分）1D；2B；3B；4A；5C二、判断题（本大题共5小题，每小题1分，共5分。如果正确，用“”表示，否则，用“”表示）12345三、简答题（本大题共3小题，每小题4分，共12分）1.答：耦合是对不同模块之间相互依赖程度的度量。（定义1分）一般地，模块耦合可分为：1）内容耦合：当一个模块直接修改或操作另一个模块的数据时，模块间的这种耦合称为内容耦合。2）公共耦合：当两个以上的模块共同引用一个全局数据项时，模块间的这种耦合称为公共耦合。3）控制耦合：一个模块在界面上传递一个信号控制另一个模块，接收信号的模块的动作根据信号值进行调整，模块间的这种耦合称为控制耦合。4）标记耦合：当两个模块至少有一个通过界面传递的公共参数时，模块间的这种耦合称为标记耦合。5）数据耦合：当模块间通过参数传递基本类型的数据时，模块间的这种耦合称为数据耦合。（给出任意3种模块耦合，得3分，其中每种耦合1分）2答：对应的N-S图如下所示：（2分）S2Ta5FS3S4n=1n5FS6S7S1计算机科学与技术试卷答案第8页共14页对应的PAD图如下所示：（2分）b5a5S1开始结束WHILEn=5S2S3S4S5S6n=1n=n+1S73答：CMM的5级模型如下所示：（2分）初始级(1)可重复级(2)已定义级(3)已管理级(4)持续优化级(5)例如：（1）可重复级的关键过程域包括：软件配置管理、软件质量保证、软件子合同管理、软件项目跟踪和监督、软件项目规划以及需求管理。（2）已定义级的关键过程域包括：组织过程焦点、组织过程定义、培训大纲、集成软件管理、软件产品工程、组间协调以及同行评审。（3）已管理级的关键过程域包括：定量过程管理和软件质量管理。（4）持续优化级的关键过程域包括：缺陷预防、技术变化管理和过程变化管理。（至少答出2个关键过程域，得2分）。计算机科学与技术试卷答案第9页共14页四、建模题（本大题共3小题，共8分）答：（1）系统的顶层DFD如下：（3分）图书管理系统顶层DFD时钟库房管理员图书管理员图书馆主任借阅人入库告单丢失报单购书通知时间月末库存量查看要求借还书的要求图书丢失单无书通知单罚款单购书通知2）数据字典：（2分）入库单分类目录号流水号书名作者价格购书日期借还书的要求借书信息|还书信息借书信息书名|作者借书日期还书信息书名还书日期借阅人图书证号无书通知单借阅人图书证号无书信息罚款单借阅人图书证号罚款金额查看要求分类目录号月末库存量分类目录号书名库存量购书通知分类目录号书名购买量购书”这一交互，给出其顺序图：（图书丢失单图书流水号丢失报告单书名分类目录号图书流水号（3）以下针对“图书图书馆主任根据3分）月末库存情况通知库房管理员计算机科学与技术试卷答案第10页共14页其中，对象“图书馆主任”是界面对象，它调用对象“图书库存信息文件”，根据图书的分类目录号统计图书月末库存情况，当图书的库存量低于下限时，对象“图书馆主任”向对象“库房管理员”发购书通知。注：该题的答案在形式上可能是多种多样的，但在回答时，主要注意三点：（1）顶层DFD是否符合系统环境图的构造特点；（2）数据字典的定义是否符合其书写原则；（3）所画的顺序图是否符合UML中顺序图的定义。图书月末库存情况(分类目录号，书名，库存量)统计图书月末库存情况(分类目录号)：图书馆主任：图书库存信息文件：库房管理员When库存量下限购书通知(分类目录号，书名，购买量)计算机科学与技术试卷答案第11页共14页人工智能原理试卷答案及评分参考一、单项选择题（每小题2分，共8分）1B；2C；3B；4C；二、证明题（7分）答：123AAAB的子句集为()()()(),CxDxGxfx()()()(),CxDxEfx()Ca，()Fa，()(),yFy(Ga，)()DxFx，()()ExFx（占3分）一种线性归结证明过程（可能有多种）：（占4分）三、问答题（每小题5分，共15分）答：1Agent理论与应用，数据挖掘，统计机器学习。（答出一个方面占2分，全答出占5分）2Agent是某个环境下的计算机系统，具有在该环境下自动行动来实现目标的能力（自主性）。还具有与其他Agent交互共同完成问题求解的能力（社会性）（占2分）。多Agent系统主要研究Agent和Agent群体的模型，以及多Agent合作求解的机理（占3分）。3一种归结方法是完备的，指的是如果定理成立，使用这种归结方法必会给出证明（占3分）。如单元归结策略就是不完备的（占2分）。计算机科学与技术试卷答案第12页共14页计算机图形学试卷答案及评分参考一、判断题（本大题共5小题，每小题1分，共5分。如果正确，用“”表示，否则，用“”表示）1.2.3.4.5.二、填空题（本大题共5小题，每小题2分，共10分）1沿X坐标轴方向缩小1/2倍，沿Y坐标轴方向移动1/2个绘图单位2假设在多边形区内部有一象素已知，由此出发找到区域内的所有图象3图象空间面需要有较多的存储空间，即还需要