2008年同等学力人员申请硕士学位计算机科学与技术学科综合水平全国统一考试

考生须知
1.本试卷满分为100分，包括数学基础课程和专业知识课程两部分。数学基础课程满分40分，每位考生必答；专业知识课程包括五门课程，每门课程满分30分，考生须从中任选2门作答，多选者只按前选课程计分。
2.请考生务必将本人准考证号最后两位数字填写在本页右上角方框内。
3.考生一律用蓝色或黑色墨水笔在答题纸指定位置上按规定要求作答，未做在指定位置上的答案一律无效。
4.监考员收卷时，考生须配合监考员验收，并请监考员在准考证上签字（作为考生交卷的凭据）。否则，若发生答卷遗失，责任由考生自负。同等学力在职研究生报名 https://www.eduei.com/zzyjs/

第一部分 数学基础课程
（共40分）
一、用逻辑符号形式化下列语句（本大题共2小题，每小题2分，共4分）
1．每个人的指纹都不相同。
2．自然数不是奇数就是偶数，且奇数不能被2整除。
二、填空题（本大题共4小题，第1小题每空1分，第2、3、4小题每空2分，共10分）
1．设A、B均为有穷集合，A和B的基数分别是m和n（m >0, n >0）。
（1）当m和n满足 时，存在从A到B的双射函数。
此时共可生成 个不同的双射函数。
（2）当m和n满足 时，存在从A到B的单射函数。
此时共可生成 个不同的单射函数。
2．已知5位老师和3位学生围圆桌就座，如果要求学生两两不相邻，则有 种就座方案。
3．整除2310的正奇数有 个。 4．设图的顶点集合为VG，边集合为。则G 的生成树有 G 1223344113(){,,,,EGvvvvvvvvvv?棵。
三、解答题（本大题共3小题，第1、2小题每题4分，第3小题8分，共16分）
1．设P↓Q = ?(P∨Q)，仅用联结词↓分别表示出?P，P∧Q，P∨Q。
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）若<a，b>∈R ∧<a，c>∈R，则<b，c>∈R；
试证明R是A上的等价关系。
2．随意地把一个9棋盘的每个方格涂成红色或蓝色，求证：必有两行方格的涂色是一样的。
第二部分 专业知识课程
Ⅰ．计算机系统结构
（共30分）
一、填空题（本大题共2小题，每小题2分，共4分）
1．用下面三条指令可以完成向量表达式D=A×(B+C)的运算。假设向量长度N<64位，且向量B和C已经存于V0和V1，读写操作各需要时间1拍。
V3←A (6拍)
V2←V0+V1 (6拍)
V4←V2×V3 (7拍)
若这三条指令串行执行则需要的时间为 拍，当采用链接技术后所需时间为 拍。
2．有编号为0,1,2,…,31共32个处理机（结点），采用移数函数构成互连网，则网络直径为 ，结点度为 。
二、问答题（本大题共3小题，每小题2分，共6分）
一台计算机以字为单位访问存储器。其主存共包含4096个存储块，每个存储块大小为128个字。采用组相联映像方式的Cache由64个存储块构成，每组包含4个存储块。
1．问主存地址需要用多少位表示？
2．问Cache地址需要用多少位表示？
3．计算主存地址格式中，区号、组号、块号和块内地址字段的位数。
三、设计题（本大题共5小题，每小题2分，共10分）
一条具有3个功能段非线性流水线的预约表如下所示。
1．写出对应的禁止集合和初始冲突向量；
2．画出流水线调度的状态转移图；
3．求最小启动循环和最小平均启动距离；
4．画出流水线各功能段之间的连接图；
5．通过插入非计算延迟单元（预留算法），
四、计算题（本大题共4小题，共10分）
在一台每个时钟周期发射两条指令的超标量处理机上运行下面一段程序。所有指令都要经过“取指令”、“译码”、“执行”和“写结果”4个阶段，其中，“取指令”、“译码”和“写结果”三个阶段各为一个流水段，其延迟时间都为10ns。在“执行”阶段，LOAD操作和AND操作各需要延迟10ns，ADD操作需要延迟20ns，MUL操作需要延迟30ns，四种操作部件各设置一个。ADD部件和MUL部件都采用流水线结构，每一级流水线的延迟时间都为10ns。
程序：
n+1 ：LOAD R0, A ；R0←主存(A)单元
n+2 ：ADD R1, R0 ；R1←（R1）＋（R0）
n+3 ：LOAD R2, B ；R2←主存(B)单元
n+4 ：MUL R3, R4 ；R3←（R3）×（R4）
n+5 ：AND R4, R5 ；R4←（R4）∧（R5）
n+6 ：ADD R2, R5 ；R2←（R2）＋（R5）
1．（4分）列出这个程序中所有的数据相关，包括先写后读数据相关（RAW）、先读后写数据相关（WAR）和先写后写数据相关（WAW）；
2．（2分）如果所有运算型指令都在“译码”流水段读寄存器，在“写结果”流水段写寄存器，采用顺序发射顺序完成调度方法。画出流水线的时空图，并计算执行这段程序所用的时间；
3．（2分）如果所有运算型指令都在“译码”流水段读寄存器，在“写结果”流水段写寄存器，采用顺序发射乱序完成调度方法。画出流水线的时空图，并计算执行这段程序所用的时间；
4．（2分）如果每个操作部件的输出端都有直接数据通路与输入端相连，采用顺序发射乱序完成调度方法。画出流水线的时空图，并计算执行这段程序所用的时间。
Ⅱ．计算机网络
（共30分）
一、单项选择题（本大题共10小题，每小题1分，共10分）
1．下面对计算机网络体系结构中协议所做的描述，（ ）是错误．．的。
A．网络协议的三要素是语法、语义和同步
B．协议是控制两个对等层实体之间通信的规则的集合
C．在OSI参考模型中，要实现第N层的协议，需要使用N＋1层提供的服务
D．协议规定了对等层实体之间所交换的信息的格式和含义
2．若数据链路层采用回退N（go-back-N）滑动窗口协议，发送帧的序号用7bit表示，发送窗口的最大值为（ ）。
A．7 B．64
C．127 D．128
3．以太网中采用二进制指数后退算法处理发送冲突问题，下列数据帧中重传时再次发生冲突概率最低的是（ ）。
A．首次重传的帧 B．发生两次冲突的帧
C．发生三次冲突的帧 D．发生四次冲突的帧
4．采用二层以太网交换机扩展局域网，（ ）是错误．．的。
A．二层以太网交换机的各个端口可以支持不同的速率
B．二层以太网交换机可以隔离广播帧
C．二层以太网交换机需要对收到的数据帧进行处理，增加了传输时延
D．二层以太网交换机在转发帧时不改变帧的源地址
5．在采用（ ）的传输方式下，由网络负责差错控制和流量控制，分组按顺序被交付。
A．电路交换 B．报文交换
C．虚电路分组交换 D．数据报分组交换
6．对于IP分组的分段和重组，（ ）是正确的。
A．IP分组可以被源主机分段，并在中间路由器进行重组
B．IP分组可以被路径中的路由器分段，并在目的主机进行重组
C．IP分组可以被路径中的路由器分段，并在中间路由器上进行重组
D．IP分组可以被路径中的路由器分段，并在最后一跳的路由器进行重组
7．假定一台主机的IP地址是180.120.74.56，子网掩码为255.255.240.0，则该子网地址为（ ）。
A．180.120.0.0 B．180.120.64.0
C．180.120.72.0 D．180.120.74.0
计算机科学与技术试卷 第 5 页 共 10 页
8．在Internet上，主机采用（ ）标识，运行在主机上的应用程序用（ ）标识。
A．端口号 主机地址 B．主机地址 IP地址
C．IP地址 主机地址 D．IP地址 端口号
9．当客户端请求域名解析时，如果本地DNS服务器不能完成解析，就把请求发送给其他服务器，依次进行查询，直到把域名解析结果返回给请求的客户端。这种方式称为（ ）。
A．迭代解析 B．递归解析
C．迭代与递归相结合的解析 D．高速缓存解析
10．在信息安全领域，使用（ ）方法可以使通信的接收方验证收到报文是否受到篡改和伪造。
A．数字签名 B．数据加密
C．防火墙 D．身份认证
二、名词解释（本大题共2小题，每小题3分，共6分）
1．自治系统AS（autonomous system）
2．慢启动（slow start）
三、问答和计算题（本大题共4小题，共14分）
1．（3分）试说明以太网规定的最短帧长是多少？为什么要限制最短帧长？
2．（3分）试说明TCP协议是如何提供端到端可靠的传输服务的？
3．（4分）考虑一条带宽为1.6Mbps的链路，往返传播时延为45ms，假设数据帧的大小为1KB。若采用滑动窗口协议来保证链路的利用率，允许发送方在收到应答之前尽量连续发送多帧。那么，至少需要多少位作为序号？（忽略确认帧大小和接收处理开销）
4．（4分）如下图所示的网络中，采用距离向量路由算法进行路由选择。假设路由器C在启动时，测得与相邻路由器A、B的时延分别为7，14。此后，路由器C分别收到来自相邻路由器发出的路由向量：B（15，0，4，6），A（0，3，12，16）。上述向量表示发送该向量的路由器分别与网络中路由器A、B、C、D之间的时延。计算路由器C在收到相邻路由器发出的向量后，更新的路由表是什么？
Ⅲ．软件工程
（共30分）
一、单项选择题（本大题共5小题，每小题1分，共5分）
1．软件开发的需求活动，其主要任务是（ ）。
A．给出软件解决方案 B．给出系统模块结构
C．定义模块算法 D．定义需求并建立系统模型
2．软件总体设计结束后得到（ ）。
A．初始化的软件结构图B．优化的软件结构图
C．模块的算法D．程序编码
3．面向对象分析方法与结构化分析方法的区别之一是（ ）。
A．一个使用了“抽象”，而另一个没有使用“抽象”
B．一个以问题域的成分为基点来构造一个模块，而另一个不是
C．一个目标明确，而另一个目标不明确
D．一个需要考虑数据结构，而另一个不需要考虑数据结构
4．确定测试的计划是在（ ）阶段制定的。
A．需求分析 B．详细设计
C．编码 D．测试
5．按不同人员的工作内容来分类软件过程，基本过程包括（ ）。
A．维护过程和改进过程等 B．开发过程和改进过程等
C．获取过程和供应过程等 D．改进过程和裁减过程等
二、判断题（本大题共5小题，每小题1分，共5分。如果正确，用“√”表示，否则，用“×”表示）
1．在软件开发方法中，结构化方法总的指导原则是自顶向下、逐步求精。（ ）
2．当一个模块直接修改另一个模块的数据时，模块间的这种耦合称为数据耦合。（ ）
3．测试用例只需选用合理的输入数据。（ ）
4．边界值分析法是一种白盒测试法。（ ）
5．关联是建立类之间关系的一种手段。（ ）
三、简答题（本大题共3小题，每小题4分，共12分）
1．给出模块耦合的定义，并举例说明3种模块耦合。
2．将下面的伪码转换成N-S图和PAD图。
BEGIN
S1;
S2;
IF a>5 THEN S3 ELSE S4;
n=1;
WHILE n<=5 DO
{ S5;
n=n+1; }
IF b>5 THEN S6 ELSE S7;
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．简单的模式匹配方法
三、问答题（本大题共3小题，每小题5分，共15分）
1．近年来人工智能学科的研究热点，主要在哪几个方面？
2．说明Agent（智能体或主体）概念，以及多Agent系统的主要研究内容。
3．说明一种归结方法是完备的含义，并举出一种不完备的归结策略。
Ⅴ．计算机图形学
（共30分）
一、判断题（本大题共5小题，每小题1分，共5分。如果正确，用“√”表示，否则，用“×”表示）
1．在图形系统中，图形处理运算的精度不取决于显示器的分辩率。（ ）
2．Bezier曲线形状取决于所选择的坐标系和特征折线集（多边形）顶点的相对位置。（ ）
3．B样条曲线具有几何不变性（形状和位置与坐标系的选择无关）。（ ）
4．定义了物体的边界也就唯一的定义了物体的几何形状边界，物体边界上的面可以是平面或任何形状曲面。（ ）
5．平行投影能真实地反映物体精确的尺寸和形状，视觉效果更有真实感。（ ）
二、填空题（本大题共5小题，每小题2分，共10分）
2．种子填充算法也是一种很常用的多边形区域填充算法，与边填充算法不同，其基本原理是 。
3．Z-Buffer消隐算法是一种典型的 消隐算法，其缺点是 。
4．Phong模型是简单光反射模型，它模拟物体表面对光的反射作用，主要考虑的是物体表面对 的反射作用。对物体间的光反射作用，只用一个 做近似处理。
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，求控制顶点
3．为生成真实感图形，可采用一种HLS颜色模型，试分别说明H、L和S所代表的三个要素及其含义。