2011-2014年同等学力计算机综合真题答案解析(7)

2.已知北京市地图以及地图中任意两点A和B的最短路径算法，试给出一种计算A和B最短路径的启发式算法。

3.给出分类问题的描述，进而说明用于分类的有监督机器学习方法与无监督机器学习方法。

1

绝密★启用前

2013年同等学力人员申请硕士学位 学科综合水平全国统一考试 计算机科学与技术试卷 第一部分数学基础课程 第二部分专业知识课程 Ⅰ．计算机系统结构 Ⅱ．计算机网络 Ⅲ．软件工程 Ⅳ．人工智能原理 Ⅴ．计算机图形学 考生须知

1. 本试卷满分为100分，包括数学基础课程和专业知识课程两部分。数学基础课程满分为40分，每位考生必答；专业知识课程包括五门课程，每门课程满分为30分，考生须从中任选2门作答，多选者只按前选课程计分。

2. 考生务必将本人考号最后两位数字填写在本页右上角方框内。

3. 考生一律用蓝色或黑色墨水笔在答题纸指定位置上按规定要求作答，未做在指定位置上的答案一律无效。

4. 监考员收卷时，考生须配合监考员验收，并请监考员在准考证上签字（作为考生交卷的凭据），否则，若发生答卷遗失，责任由考生自负。 2

第一部分数学基础课程 （共40 分）

一、用逻辑符号表达下列语句（每小题2 分，共4 分） 1．发光的不都是金子。（注：给出两种表达，一种用存在量词，另一种用全称量词） 2．有些大学生不尊敬老人。

二、填空题（第1 小题2 分，第2 到第6 小题每空2 分，共16 分）

1．设集合A 有100 个元素，则A 有个子集。其中有个子集其元素个数为奇数。 2．任意一个图中度数是奇数的顶点个数一定是。

3．如果四对夫妻围圆桌就座，没有任何限制条件，共有种不同的座法；如果这四 对夫妻中的四个男士和四个女士排成一排，要求男女交替，则有种不同的排法; 如果这四对夫妻围圆桌就座, 要求夫妻相邻的座法有种。 4．设G ? (V,E)是顶点集为V、边集为E的图。令 1 ( ) ( ) | |v V D G d v

V ?

? ?，则用 D(G)和|V |把| E |

表示出来的表达式是。这里d(v)是顶点v 的度数（或次数），|V |和| E |分别是 V 和E 中所含元素的个数。

5．设 Q是一个有理数集。对任意的a,b?Q，定义二元运算a?b ? (a?b) / 2，则 Q关于运算 ? 的单位元是，其中“? ”是有理数中通常的乘法运算。

6．把6 个相同的球分到3 个同学手里，允许有的同学未分配到球的情况出现，则有种 不同的分法。

三、计算题（第1 小题3 分，第2 小题4 分，第3 小题6 分，共13 分） 1．定义P↑Q = ?(P∧Q)，试仅用与非联结词↑分别表示出 （1）?P （2）P∧Q （3）P?Q

均要求结果简洁。

2．设a、b、c、d 这四个元素的全排列中不允许出现ac 和bd 的排列数。 3．用红、黄、蓝色对1? n的棋盘方格涂色，设涂红色方格的个数是偶数且至少有一个方格

涂黄色的涂色方法数为n h （n 是正整数）。 （1）试确定n h 的指数型生成函数； （2）求n h 。 3

四、证明题（第1 小题4 分，第2 小题3 分，共7 分） 1．给出命题：“对于集合A 上的任意关系R，如果R 是对称的和传递的，则R 一定是自反 的。”若命题正确，则给出完整证明；若命题错误，则指出错误所在，并在集合{1, 2, 3} 上构造一个关系R1（反例）使得R1 是对称的和传递的，但不是自反的。

2．设A 为包含n 个元素的有限集，R 是A 上的关系，则必存在s 和t，使得s t R ? R ，且 2

0 2n ≤s ? t≤。 4

第二部分专业知识课程 Ⅰ．计算机系统结构 （共30分）

一、选择题（每小题1分，共5分） 某大型计算机有如下三种通道工作方式： A．字节多路通道 B．数组多路通道 C．选择通道

对于下面5种情况，选择对应的A或B或C填入括号中。 1．低速外部设备通常采用（）方式 2．使用硬件元件最少的是（）方式 3．使用硬件元件最多的是（）方式

4．通常只有一个磁盘工作，采用（）方式

5．经常需要多个磁盘同时工作，采用（）方式 二、填空题（每空1分，共10分）

1．采用2-4扩展编码法设计指令操作码，最多能设计出（）条指令，其中操作码长度为2位的指令（）条，操作码长度为4位的指令（）条。

2．用1M × 8b（二进制位）的静态存储芯片构成一个4M × 32b的存储器，需要存储器芯片（）片，各存储芯片的地址有（）位，该静态存储器的地址共有（）位。

3．在一个存储系统中，主存储器的访问周期、存储容量和单位容量价格分别为30ns、2GB和0.1元/MB；而Cache的访问周期、存储容量和单位容量价格分别为5ns、16MB和1元/MB，Cache的命中率为0.98。则这个存储系统的访问周期是（），存储容量是（），单位容量的价格是（），这个存储系统的访问效率是（）。 5

三、计算题（共15分） 1．（每小题2分，共8分）一个由20000条指令组成的程序，在一台工作主频为2GHz，采用5段流水线的双发射处理机上执行，忽略由于转移指令和乱序执行等造成的损失。 试计算：

（1）相对于同样工作主频的非流水线单发射处理机的加速比。 （2）指令流水线在执行这个程序时的效率。 （3）指令流水线在执行这个程序时的吞吐率。 （4）该处理机的峰值速度。 2．（共7分）在一台单流水线多操作部件处理机上执行下面的程序P。取指令和指令译码各需要一个时钟周期，执行MOVE、ADD和MUL操作分别需要2个、3个和4个时钟周期。每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。 程序P：

k ：MOVE R1, R0 ；R1←（R0）

k+1：MUL R0, R2, R1 ；R0←（R2）×（R1） k+2：ADD R0, R2, R3 ；R0←（R2）＋（R3）

（1）写出指令之间的所有数据相关（包括写读相关、读写相关和写写相关）。

（2）在程序实际执行过程中，有哪几种数据相关会引起流水线停顿？分别停顿了几个时钟周期？

（3）计算执行完这3条指令共用了多少个时钟周期。 6

Ⅱ．计算机网络 （共30分）

一、填空题（每空1分，共6分）

1．在网络协议的三要素中，表示事件实现顺序的详细说明；说明需要发出何种控制信息及如何响应。

2．一个路由器的路由表有如下表项： 目的网络地址 子网掩码 下一跳

172.80.120.0 255.255.252.0 接口0

172.80.124.0 255.255.252.0 接口1

130.42.35.0 255.255.240.0 路由器A Default Default

路由器B

若该路由收到一个分组，其目的地址为172.80.128.4，路由器转发的下一跳为。

3．考虑在主机A和主机B之间建立一个TCP连接，若主机A向主机B连续发送两个TCP报文段，第一个报文段的序号为200，第二个报文段的序号是1100，则第一个报文段中的数据为字节。若第一个报文段丢失，第二个报文段到达主机B，那么主机B发送的报文中确认号为。

4．在解析域名时，客户端向本地域名服务器发出查询请求，如果服务器不能回答该请求，就向其他域名服务器发出查询请求，直到最终将查询结果返回给客户端。这种方式可称之为查询。

二、单项选择题（每小题1分，共5分） 1．以太网的争用期是指（）。

A．信号从线路一端传输到另一端的时间 B．从数据发送完毕到收到应答的时间 C．相邻两个站之间的传播时延

D．总线两端的两个站之间的往返传播时延

2．在部署分层OSPF协议时，如果一个路由器同时连接两个不同区域，其中一个是主干区域，则该路由器（）。 A．是内部路由器

B．需要为每个区域单独运行最短路径算法 C．需要为每个区域单独运行距离向量算法 D．需要维护一个统一的链路状态数据库

3．某单位要新建一个可以连接16台主机的网络，并将其连入已有的内部网中。如果该网络采用划分子网的方法，则子网掩码为（）。 A．255.255.255.252 B．255.255.255.248 C．255.255.255.240 D．255.255.255.224 7

4．IP分组在转发过程中可能需要经过多个网络和路由器。在整个传输过程中，下列说法正确的是（）。

A．源MAC地址和目的MAC地址都可能发生变化。 B．源IP地址和源MAC地址都不会发生变化。 C．源IP地址和目的IP地址都可能发生变化。

D．源IP地址不会发生变化，目的IP地址可能发生变化。

5．一个公司的办事处和部门分散在多个城市中，希望能够利用Internet进行通信，同时保证安全性，数据流量不会泄漏到公司各工作场所以外。为满足该需求可以采用（）技术。 A．PGP B．NAT C．VPN D．Proxy

三、名词解释（每小题2分，共4分） 1．VLAN 2．CIDR

四、问答和计算题（共15分）

说明：计算中使用以下简化数值：1G≈109；1M≈106；1K≈103 1．（5分）两台主机之间通过长距离网络通信，彼此之间通过一条传输速率为1Gbps的信道相连。线路的单向传播时延为10ms。分组（包括头部和数据字段）长度为1500字节。如果ACK分组很小，接收方收到一个分组后立即发送ACK，试计算： （1）（2分）如果采用停等协议，信道的利用率是多少？ （2）（3分）若使信道的利用率达到80%，窗口长度应设为多少？最少需要多少位表示序号？ 2．（3分）设计一个传输层的协议，其序号为4位，最大报文段长度为512字节，段的最大生存期为60秒。试问每个连接的最大数据率是多少？ 3．（共7分）图1给出了TCP的拥塞控制过程。横坐标为时间轴，纵坐标为发送方的拥塞窗口大小。 （1）（2分）假设最大段长MSS为1000字节。如图1所示，当拥塞窗口大小达到A点时发送方共向网络中传输了15000字节。试计算A点对应的拥塞窗口大小（假设发送方在t=0时刻建立TCP连接，数据的发送时延可以忽略不计）。 （2）（3分）根据TCP的拥塞控制机制说明图1中A、B和E点拥塞窗口变化的原因。 （3）（2分）图1中C、D处分别是由于什么原因导致拥塞窗口减小的？ 8

拥塞窗口 t A B C D 0 E 图1 9

Ⅲ．软件工程 （共30分）

一、单项选择题（每小题1分，共5分）

1．一个重要的软件生存周期模型是增量模型。以下各选项中，不属于该模型开发活动的是（）。

A．增量分析 B．增量设计 C．增量实现 D．增量发布

2．在使用结构化分析方法时，首先需要定义系统的边界。通常用于表达系统边界的是（）。 A．数据存储 B．外部实体 C．数据接口 D．运行环境

3．内聚是模块内部各个成分之间相互关联的紧密程度的度量。如果一个模块内部各个处理必须按特定的次序执行，那么这种内聚类型是（）。 A．逻辑内聚 B．通信内聚 C．过程内聚 D．功能内聚 4．对于下图所示的程序流程图，为达到100%的语句覆盖率，至少需要的测试用例数为（）。 A．5 B．6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2011-2014年同等学力计算机综合真题答案解析(7)在线全文阅读。