2009计算机科学与技术

绝密★启用前 2009 年同等学力人员申请硕士学位 学科综合水平全国统一考试 计算机科学与技术试卷 第一部分 数学基础课程 第二部分 专业知识课程 Ⅰ.计算机系统结构 Ⅱ.计算机网络 Ⅲ.软件工程 Ⅳ.人工智能原理 Ⅴ.计算机图形学 考生须知 1. 本试卷满分为 100 分，包括数学基础课程和专业知识课程两部分。数学基础课程满分 40 分，每位考生必答；专业知识课程包括五门课程，每门课程满分 30 分，考生须从中任选 2 门作答，多选者只按前选课程计分。 2. 请考生务必将本人考号最后两位数字填写在本页右上角方框内。 3. 考生一律用蓝色或黑色墨水笔在答题纸指定位置上按规定要求作答，未做在指定位置上 的答案一律无效。 4. 监考员收卷时，考生须配合监考员验收，并请监考员在准考证上签字（作为考生交卷的 凭据）。否则，若发生答卷遗失，责任由考生自负。 计算机科学与技术试卷 第 1 页 共 10 页 第一部分 数学基础课程 （共 40 分） 一、用逻辑符号形式化下列语句（每小题 2 分，共 4 分） 1．并非一切事情都能由机器来完成。 2．存在一个唯一的偶素数。 二、填空题（前两小题每题 2 分，最后一小题 3 分，共 7 分） 1．5 位男生和 5 位女生排成男女相间的一列，有________种不同的排法。 2．具有 n ( 1 个顶点的连通图至少有________条边。 )n … 3．一个大正方形是由四个相同的小正方形构成，如图 1 所示，用黑白两种颜色对 4 个小正方 形着色，如果经过某种旋转，颜色能完全吻合的方案认为是相同的，则有________种不同 的方案。 2 1 3 4 图 1 三、解答题（前两小题每题 5 分，第 3 小题 7 分，第 4 小题 6 分，共 23 分） 1．求由 2 个 0、3 个 2 和 3 个 5 构成的八位数共有多少个。 2．设图 G 有 14 个顶点，27 条边，每个顶点的度只可能为 3、4 或 5，且 G 有 6 个度为 4 的顶 点，问 G 有多少个度为 3 的顶点？多少个度为 5 的顶点？ 3．有 200 本相同的，欲摆放在四个不同的书柜里，使得每个书柜摆放的书的数目只可能是 20、40、60、80、100 本，问有多少种摆放方法？ 4．设集合 A={a, b}，试回答下列问题： （1）写出A上所有的偏序关系。 （2）写出 A 上所有的函数，并指出哪些是双射函数。 四、证明题（共 6 分） 对任意集合 A、B，试证明 A B＝A A B。  计算机科学与技术试卷 第 2 页 共 10 页 第二部分 专业知识课程 Ⅰ．计算机系统结构 （共 30 分） 一、填空题（每空 2 分，共 10 分） 1．一台具有 5 级指令流水线的标量处理机，每级流水线均耗时 1 个时钟周期。现将此标量处 理机改为超流水线处理机，采用同样基准的指令流水线，不同的是每隔 1/4 个时钟周期发 射 1 条指令。若执行一个具有 20 条指令的代码序列，改进前后执行的加速比为________。 2．用 2-4 扩展编码法最多能设计出________条指令，其中操作码长度为 2 位的指令________ 条，操作码长度为 4 位的指令________条。 3．一个程序由 5 个虚页组成，在程序执行过程中依次访问的页地址流为 P4，P5，P3，P2， P5，P1，P3，P2，P3，P5，P1，P3。当采用 LFU 替换算法时，可能的最高页命中率是________。 二、计算题（每小题 5 分，共 10 分） 某传统 RISC 计算机（只有 Load／Store 指令可以访问存储器），其各类指令所占比例及对 应 CPI 数如下： 指令类型 指令所占比例 CPI 算逻指令 43％ 1 Load 指令 21％ 2 Store 指令 12％ 2 转移指令 24％ 2 1．求上述情况下的平均 CPI； 2．假设一个程序由 M 条指令组成。算逻运算中 25%的指令，其两个操作数中的一个来自寄 存器，另一个必须在算逻指令执行前用 Load 指令从存储器取到寄存器。若增加“寄存器 －存储器”类型算逻指令，其特点是一个操作数取自寄存器，另一个操作数取自存储器。 假设这种指令的 CPI 等于 2。同时，转移指令的 CPI 改为 3。求新指令系统的平均 CPI。 计算机科学与技术试卷 第 3 页 共 10 页 三、计算题（每小题 5 分，共 10 分） 试分别用下面两种计算机系统计算达式Ｓ=A0*B0+A1*B1+…+A31*B31。假设加法和乘 法分别需要 2 个和 4 个时间单位（从存储器取指令、取数据、译码的时间忽略不计），所有的 指令和数据已装入有关的 PE。试计算下列两种情况的最短计算时间： 1．一台 SISD 串行计算机； 2．一台有 8 个PE（PE0，PE1，…，PE7）的SIMD计算机。8 个PE用PM2I 网络连接，如图所示。每个PE用一个单位时间可以把数据直接送给 相邻PE。操作数Ai和Bi最初存放在PEi mod 8中，其中i=0，1，…，31。 每个PE可在不同时刻执行加法或乘法。 0 1 7 2 6 3 5 4 计算机科学与技术试卷 第 4 页 共 10 页 Ⅱ．计算机网络 （共 30 分） 一、单项选择题（每小题 1 分，共 10 分） 1．下列不属于．．．数据链路层的功能是（ ）。 A．使用滑动窗口进行流量控制 B．提供数据的透明传输机制 C．为应用进程之间提供端到端的可靠通信 D．将 IP 分组封装成帧 2．传统以太网发送的数据采用曼彻斯特（Manchester）编码，所占的频带宽度（ ）。 A．与原始基带信号相同 B．是原始基带信号的一半 C．是原始基带信号的两倍 D．是原始基带信号的四倍 3．生成树（spanning tree）算法的作用是（ ）。 A．发现网络中允许通过帧的最大长度 B．避免转发的帧在网络中死循环 C．减小重新传输帧时再次发生冲突的概率 D．逆向地址学习 4．下列关于虚拟局域网（VLAN）的描述，错误．．的是（ ）。 A．IEEE 802.1Q 协议定义了虚拟局域网的概念 B．虚拟局域网可以隔离广播风暴 C．虚拟局域网的帧格式与传统以太网的帧格式不同 D．虚拟局域网是由一些局域网段组成的、与物理位置相关的结点集合 5．主机 A 向主机 B 发送 IP 分组，途中经过了 4 个路由器，那么，在 IP 分组的发送过程中， 共使用了（ ）次 ARP 协议。 A．1 B．3 C．4 D．5 6．IP 地址 10.224.12.1 的子网掩码为 255.240.0.0，和该地址在同一子网中的地址是（ ）。 A．10.223.21.121 B．10.240.46.23 C．10.236.23.171 D．10.242.23.120 7．下面关于 OSPF 协议的描述，错误．．的是（ ）。 A．OSPF 协议直接用 IP 分组传送 OSPF 报文 B．OSPF 协议中，相邻路由器定期交换整个路由表信息 C．OSPF 协议中，所有路由器最终都能建立一个全网的拓扑结构图 D．OSPF 协议可以将一个自治系统划分成若干区域 计算机科学与技术试卷 第 5 页 共 10 页 8．TCP 协议是面向字节流的协议，其特点是（ ）。 A．接收方收到的数据块和发送方发出的数据块大小可能不相同 B．接收方的 TCP 每次向应用层交付一个完整的报文 C．TCP 协议知道所传输的数据块的含义 D．TCP 协议不要求主机维护复杂的状态表 9．在 TCP 协议的慢启动（Slow Start）中，若初始发送方设置拥塞窗口（cwnd）大小为 1，在 经过三个往返时延（也称为传输轮次）后，拥塞窗口变为（ ）。 A．3 B．4 C．6 D．8 10．下列关于客户／服务器方式的说法，错误．．的是（ ）。 A．客户端在通信时主动向服务器发起通信请求 B．服务器必须事先知道客户端的地址才能通信 C．客户端系统通常使用随机的传输层端口号 D．客户端和服务器之间的通信是双向的，都可以发送和接收数据 二、名词解释（每小题 3 分，共 6 分） 1．子网掩码 2．拥塞（congestion） 三、问答和计算题（本大题共 4 小题，共 14 分） 1．以太网适配器（网卡）工作在哪一层？实现该层的哪些功能? （3 分） 2．试说明如何在停止等待协议中提供可靠传输机制？（3 分） 3．假设一个通信网络，源端和目的端的平均距离为 150km，信号在传输介质中的传播速度为 2×108 m/s，当数据长度为 1500bit，数据传输速率为 1Gbps时，试问数据的传输时延和往返 传播时延分别是多少？（注：1G按 109计算）（4 分） 4．某个网络中使用 RIP 协议，路由器 B 和 C 相邻，路由器 B 的路由表如表 1 所示。表 2 为 路由器 C 广播的路由信息，试求路由器 B 更新后的路由表。（4 分） 表 1 路由器 B 的原路由表 目的网络 距离 下一跳路由器 N1 0 直接连接 N2 7 C N3 3 F 表 2 路由器 C 广播的路由信息 目的网络 距离 N1 4 N2 2 N3 3 N4 6 计算机科学与技术试卷 第 6 页 共 10 页 Ⅲ．软件工程 （共 30 分） 一、单项选择题（每小题 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．聚合 二、判断题（每小题 1 分，共 5 分。如果正确，用“√”表示，否则，用“×”表示） 1．软件的正确性是指软件产品能正常工作。（ ） 2．两个模块都使用同一张表，模块之间的这种耦合称为数据耦合。（ ） 3．演化模型与增量模型的主要区别是软件工程活动不同。（ ） 4．ISO9003 是一种用于“供方建立质量保证体系的”。（ ） 5．软件开发环境是一些软件工具的集合。（ ） 三、问答题（每小题 4 分，共 12 分） 1．给出模块内聚的定义，并举例说明 3 种模块内聚类型。 计算机科学与技术试卷 第 7 页 共 10 页 2．将下面的伪码转换成 N-S 图和 PAD 图。 begin 输入 10 个数给 x[0]到 x[9]； max=0; min=0; if x[0]>x[1] then { max=x[0]; min=x[1];} else{ max=x[1]; min=x[0];} i=2; while i<=9 begin if x[i]>max then max=x[i]; else if x[i], }； R2 = IA∪{}； R3= IA∪{< b, a>}； ……3分 A上的函数共有4个： f1 = {, }； f2 = {, }； f3 ={, }； f4 = {, } 其中f2、 f3是双射函数。 ……3分 四．证明题（共 6 分） 证明：先证A B = A AB   若A B = A，则：  x，x∈ A  x ∈ A B (A B = A)  x∈A∧ x∈B (集合交定义)  x ∈B (命题逻辑化简律) 从而有A B = A AB。 ……3分  再证 AB A B = A   利用反证法，假设AB，但A B≠A，则 （1）必存在元素 e，e∈A，但 e 不属于 A B。 即e∈A∧eB，而由AB知，e∈A必有e∈B， 则e∈A必有e∈A B，所以假设不成立。 或 （2）假设 A B，但 A B≠A，则存在元素 e∈A  B，但 e 不属于 A。 由e∈A B，则有e∈A∧e∈B，同样与假设矛盾。 ……3分  综合上述，有A B = A  AB 成立。 计算机科学与技术试题答案及评分参考 第 3 页 共 13 页 第二部分 专业知识课程 Ⅰ．计算机系统结构 一、填空题（每空 2 分，5 个空共 10 分） 1．2.46 2．7 3 4 3．7/12（计算成小数 0.58 也算对） 二、计算题（每小题 5 分，共 10 分） 1．CPI＝0.43×1＋0.21×2＋0.12×2+0.24×2=1.57 2．原算逻指令中的 25％变成了寄存器--存储器型指令，所以算逻指令（寄存器寄存器型） 少了(0.25×0.43)*M 条，Load 指令少了(0.25×0.43)*M 条，而(0.25×0.43)*M 条的新指令为 寄存器--存储器型指令。指令总数少了(0.25×43%)*M 条。设执行算逻指令（寄存器--寄存 器型）、Load 指令、算逻指令（寄存器存储器型）、Store 指令和转移指令的周期总数分 别为 C1，C2，C3，C4，C5，所以: C1=(0.43-(0.25×0.43))M×1=0.3225M C2=(0.21-(0.25×0.43))M×2=0.205M C3=(0.25×0.43)M×2=0.215M C4=0.12M×2=0.24M C5=0.24×3M=0.72M 新指令总数 N=（1-(0.25×0.43)）*M=0.8925M CPI新=（C1+C2+C3+C4+C5）/ N=1.7025M/0.8925M=1.908 三、计算题（每小题 5 分，共 10 分） 1．在 SISD 计算机中计算 S 需要串行计算 32 次乘法和 31 次加法。 共需要时间：T=4*32+2*31=190 时间单位 0 1 7 2 6 3 5 4 2．SIMD 计算机互连网络如下： 把向量中的 32 对元素平均地分配到 8 个处理其中，每个处理器 分配 4 对 共需要时间 T=4*4+3*2+1+2+1+2+1+2=31 单位时间 计算机科学与技术试题答案及评分参考 第 4 页 共 13 页 Ⅱ．计算机网络 一、单项选择题（每小题 1 分，共 10 分） 1．C 2．C 3．B 4．D 5．D 6．C 7．B 8．A 9．D 10．B 二、名词解释（每小题 3 分，共 6 分） 1．子网掩码是 IP 网络的重要属性，由 32 位的位模式组成（包括一串 1 和跟随的一串 0）；（1 分） 其中 1 对应 IP 地址中的网络号部分；0 对应 IP 地址中的主机号部分。（2 分） 2．一定时间内，对网络中某种资源的需求超出了该资源的可用部分，造成网络性能变坏；（2 分）整个网络的吞吐量随输入负载增加而下降。（1 分）。 三、问答和计算题（共 14 分） 1．数据链路层（答 介质访问控制层或 MAC 层也给分）（1 分） 数据帧处理、接收和发送；（1 分） 以太网协议：CSMA/CD （1 分） 2．发送一个分组后设置超时计时器，超时重传； （1 分） 对数据分组和确认分组进行编号；（1 分） 缓存已发送的分组副本。（1 分） 3．单向传播时延：（150×103）/（2×108）＝75×10-5 s = 0.75 ms （1 分） 往返传播时延 RTT = 1.5 ms （1 分） 分组的传输时延＝1500/109＝1.5×10-6 s = 1.5 μs 4．每空 0.5 分，共 4 分。 目的网络 距离 下一跳路由器 N1 0 直接连接 N2 3 C N3 3 F N4 7 C 计算机科学与技术试题答案及评分参考 第 5 页 共 13 页 Ⅲ．软件工程 一、单项选择题（每小题 1 分，共 5 分） 1．A 2．B 3．D 4．C 5．A 二、判断题（每小题 1 分，共 5 分。如果正确，用“√”表示，否则，用“×”表示） 1．× 2．× 3．× 4．× 5．√ 三、问答题（每小题 4 分，共 12 分） 1．模块内聚是模块内各处理成分之间的相互关联。作为模块化度量指标之一，它是指导人们 进行模块结构设计的重要概念。（1 分） 模块内聚可分为：（给出 3 种模块内聚类型，得 3 分，其中每种内聚 1 分） （1）偶然内聚：即一个模块内各成分之间毫无关系，则称为偶然内聚。 （2）逻辑内聚：即把几个逻辑上相关的功能放在一个模块中，则称为逻辑内聚。 （3）时间内聚：即如果一个模块完成的功能必须在同一时间内执行，则称为时间内聚。 （4）过程内聚：即如果一个模块内部的处理成分相关，且这些处理成分必须以特定的次序 执行，则称为过程内聚。 （5）通信内聚：即如果一个模块的所有成分都操作同一数据集或生成同一数据集，则称为 通信内聚。 （6）顺序内聚：即如果一个模块的各个处理成分和同一功能相关，且一个成分的输出作为 另一成分的输入，则称为顺序内聚。 （7）功能内聚：即模块的所有成分对于完成单一功能都是基本的，则称为功能内聚。 评分说明：定义 1 分，3 个模块内聚例子各 1 分。 2．对应的 N-S 图如下所示： 输入 10 个数给 x[0]到 x[9] max=0 min=0 T x[0]>x[1] F max=x[0]; max=x[1]; min=x[1] min=x[0] i=2 while i<=9 T x[i]>max F max=x[i] T x[i]x[1] min=x[0] x[i]>max max=x[i] x[i] s.r) {p 和 s 不相交;} else { p 和 s 交线为一圆： c= s.c-d*p.w; /*圆心*/ r=sqr (s.r2-d2); /*半径*/ w= p.w; /*所在平面的法向量*/ } } 评分说明：可用任何程序设计语言或伪语言，只要能完全正确表达该算法，就可得分，次要 语法错误应酌量扣 1-2 分。共 5 分。 TL2009050812计算机科学与技术 TL2009050812计算机科学与技术答案