搜索
2010年同等学力申硕全国统考计算机科学与技术试卷作者：佚名来源：本站原创日期：2011-3-189:37:44计算机科学与技术试卷第一部分数学基础课程第二部分专业知识课程Ⅰ.计算机系统结构Ⅱ.计算机网络Ⅲ.软件工程Ⅳ.人工智能原理Ⅴ.计算机图形学考生须知1.本试卷满分为100分，包括数学基础课程和专业知识课程两部分。数学基础课程满分40分，每位考生必答；专业知识课程包括五门课程，每门课程满分30分，考生须从中任选2门作答，多选者只按前选课程计分。2.请考生务必将本人考号最后两位数字填写在本页右上角方框内。3.考生一律用蓝色或黑色墨水笔在答题纸指定位置上按规定要求作答，未做在指定位置上的答案一律无效。4.监考员收卷时，考生须配合监考员验收，并请监考员在准考证上签字（作为考生交卷的凭据）。否则，若发生答卷遗失，责任由考生自负。计算机科学与技术试卷第1页共10页第一部分数学基础课程（共40分）一、用逻辑符号表达下列语句（每小题2分，共4分）1．猫必捕鼠。2．任意两个不同的实数之间必存在另一个实数。二、填空题（每小题2分，共6分）1．设是个顶点（n为正整数）的完全图，对的每条边进行红、蓝两种颜色任意着色，都至少存在一个红色边三角形或蓝色边三角形，则最小的是nknnkn。2．+++(1)0123nnnnnnnæöæöæöæöæö---ç÷ç÷ç÷ç÷ç÷èøèøèøèøèøL=。其中表示从个不同元素中取个的组合数。nkæöç÷èønk3．设是有n个顶点的简单图，除其中一个顶点外，其余顶点的度（次）均为奇数。在的补图中有GG个度为奇数的顶点。三、计算题（共16分）1．（3分）计算xP(x)®$yP(y)的否定式。否定式中仅可使用{Ø,∨,∧}中的联结词，且否定词“Ø”不能出现在量词的前面。2．（5分）求方程123410xxxx+++=正整数解的个数。3．（8分）设个人的包事先存放在会议寄存处，且寄存处只存有这个包。会后，这个人随机进入这间黑暗的寄存处，每人随意取回一个包。试问所有人都拿错包的概率是多少？nnn四、证明题（共14分）1．（5分）证明自然数集N上的整除关系R是N上的偏序关系。2．（4分）设f：A®B，g：B®C，其中，对于任意的b∈B，g(b)={x|x∈A∧f(x)=b}，证明：当f为满射时，g为单射。3．（5分）设是一个顶点个数为（）、边数为的连通平面图，如果的最小圈的长度为5，证明：Gn5n³mG5(2)3mn£-。计算机科学与技术试卷第2页共10页第二部分专业知识课程Ⅰ．计算机系统结构（共30分）一、填空题（每小题2分，共10分）1．某模型机的Cache由64个存储块构成，每个存储块大小为128个字节。采用组相连映射方式，每组包含4个存储块。该机的主存大小为512K字节，访存地址单位为字节。则该主存地址需要用位表示，Cache地址需要用位表示。2．一个k段流水线，各段的执行时间分别为Δt1，Δt2，…，Δtk，在该流水线上完成n个连续任务时的加速比S=。3．一个非线性流水线处理机，通过插入非计算延迟的方法可以按最小启动循环（1,1,4）进行任务调度而不发生冲突，则该循环的周期P=，此时修改后的预约表所对应的禁止集F（modP）=。（F（modP）表示集合F中的每个元素模P后形成的有限集合）4．有4个中断源D1、D2、D3和D4，它们的中断优先级从高到低分别是1级、2级、3级和4级。这些中断源的中断屏蔽码如图1所示。每个中断源1位，共4位屏蔽码（1表示该中断源被屏蔽，0表示该中断源开放）。则处理机响应各中断源中断服务请求的顺序是，实际中断处理顺序是。中断屏蔽码中断源中断优先级D1D2D3D4D1D2D3D412341111011100110001图15．一台单处理机可以用标量方式运行，也可以用向量方式运行。在向量方式情况下，其计算速度是标量方式的9倍。设某基准程序P在此处理机上运行的时间为T。其中，25%T用于向量方式，其余的时间则以标量方式运行。则程序P向量化代码所占的比例为。计算机科学与技术试卷第3页共10页二、判断题（每小题1分，共10分）在系列机中发展一种新型号机器，为保证软件兼容性，你认为下列哪些设想是可行的，哪些是不可行的？（如果可行，用“Y”表示，否则用“N”表示）1．增加“字符”数据类型和“字符”处理指令；（）2．为增强中断处理功能，将中断由原来的4级增加到5级；（）3．在CPU和主存之间增设Cache存储器，以提高存储器平均访问速度；（）4．为减小计算误差，将机器中浮点数的下溢处理方法由原来的恒置“1”法，改为用只读存储器存放下溢处理结果的查表舍入法；（）5．为增加寻址灵活性和减少平均指令字长，将原来全部采用等长操作码的指令改成有3类不同码长的扩展操作码，并将源操作数寻址方式由原来的操作码指明改成增加一个寻址方式位字段来指明；（）6．将CPU与主存之间的数据通路宽度由16位扩到32位；（）7．为了减少使用公用总线的冲突，将单总线改为双总线；（）8．将原来的0号通用寄存器改为专用的堆栈指示器；（）9．将3级流水线改成5级流水线，以提高主频速度；（）10．将单核处理器改成同构双核处理器。（）三、计算题（10分）在一台每个时钟周期发射两条指令的超标量处理机上运行程序P。所有指令都要经过“取指令（IF）”、“译码（ID）”、“执行”和“写结果（WB）”4个阶段，其中，“取指令”、“译码”和“写结果”三个阶段各为一个流水段，其延迟时间都为10ns。在“执行”阶段，LOAD和AND操作延迟都为10ns，ADD操作延迟20ns，MUL操作延迟30ns，这四种操作部件各设置一个。ADD部件和MUL部件都采用流水线结构，每一级流水线的延迟时间都为10ns。其中，程序P：n1：LOADR0,A；R0←主存（A）单元n2：ADDR1,R0；R1←（R1）＋（R0）n3：LOADR2,B；R2←主存(B)单元n4：MULR3,R4；R3←（R3）×（R4）n5：ANDR4,R5；R4←（R4）∧（R5）n6：ADDR2,R5；R2←（R2）＋（R5）1．（4分）列出程序P中所有的数据相关，包括写读数据相关、读写数据相关和写写数据相关；2．（6分）如果所有运算型指令都在“译码（ID）”流水段读寄存器，在“写结果（WB）”流水段写寄存器，采用“顺序发射、乱序完成”调度方法，画出流水线的时空图，并计算执行这个程序所用的时间。计算机科学与技术试卷第4页共10页Ⅱ．计算机网络（共30分）一、填空题（每空1分，共5分）1．在OSI参考模型中，上层使用下层所提供的服务必须与下层交换命令，这些命令称为；相邻层之间的接口称为；对等层之间传送的数据单位称为。2．以太网交换机从某一个端口接收到正确的数据帧后，在转发表中查找该帧要到达的目的站点，若查不到，则交换机；若该帧的目的站点在同一端口，则交换机。二、单项选择题（每小题1分，共5分）1．一个12端口交换机的冲突域和广播域的个数分别是（）。A．12，12B．12，1C．1，12D．1，12．下面关于PPP协议的说法，错误．．的是（）。A．可以支持不同的网络层协议B．既支持异步链路，也支持同步链路C．在建立LCP链路后，进行身份鉴别D．使用帧序号来保证可靠传输3．下列不属于．．．传输层的功能是（）。A．使用滑动窗口协议进行流量控制B．提供数据的透明传输机制C．为应用进程之间提供端到端的可靠通信D．向高层协议提供用户数据报服务4．一台主机的IP地址为152.68.70.3，子网掩码为255.255.224.0，下列选项中必须经过路由器才能与该主机进行通信的是（）。A．152.68.67.15B．152.68.85.220C．152.68.62.23D．152.68.90.305．下列协议中，客户端和服务器之间采用无连接的传输层协议进行通信的是（）。A．DNSB．SMTPC．FTPD．HTTP计算机科学与技术试卷第5页共10页三、名词解释（每小题2.5分，共5分）1．网络地址转换（NAT）2．ARP协议四、问答和计算题（共15分）说明：计算中使用1G≈109；1M≈106；1K≈103。1．（4分）一个局域网采用CSMA/CD协议，网段长度为2km，数据传输速率为1Gbps，电磁信号的传播速率为200m/μs，问能够支持此协议的最短帧长应为多少字节？2．（5分）网络时延带宽积可以由带宽和往返时延相乘得到。考虑两个网络：一个是无线网络，带宽为54Mbps，RTT为0.33μs；另一个是远距离的光纤网络，带宽为10Gbps，RTT为40ms。①分别计算两个网络的时延带宽积；②说明该乘积值对于分析网络性能的意义；③若传输一个1MB的文件，试比较两个网络的有效利用率。3．（6分）如图1所示的网络中，每条链路边上的数字表示链路的开销。若采用距离向量算法进行路由选择，第一次交换距离向量时，每个节点仅将初始的路由表告知其邻居节点，试写出：①节点C的初始路由表；②第一次相邻节点之间交换距离向量后，节点C的路由表。（提示：路由表的基本信息包括目的节点，链路开销和下一跳节点）图1计算机科学与技术试卷第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．统一软件开发过程RUP是一种以体系结构为中心、迭代、增量式开发。（）5．ISO9000系列标准的主导思想是产品质量形成于产品生产的全过程。（）三、问答题（每小题4分，共12分）1．给出数据流图的定义，并举例说明数据流图的四个基本构成成份。2．给出软件测试中语句覆盖的定义，并举例说明。3．给出对象的聚合关系的定义，并举例说明松散聚合和紧密聚合。计算机科学与技术试卷第7页共10页四、建模题（共8分）问题陈述：在某超级市场销售管理系统中，供货员负责：（1）录入、删除、修改入/出库商品信息（商品编号，商品名称，生产厂家，数量，单价，入/出库日期）；（2）统计商品库存信息（商品编号，商品名称，库存量）。前台销售员负责：（1）录入顾客选购的商品信息（商品编号，商品名称，销售量，单价）；（2）打印顾客选购的商品清单（商品编号，商品名称，销售量，销售金额）；（3）计算每次顾客购买商品的总价并收费；（4）当商品销售量大于某一限额时，给供货员发供货通知（商品编号，商品名称，进货数量）。值班经理负责：（1）统计当日商品销售信息（商品编号，商品名称，销售量，销售金额）；（2）统计当日商品库存信息（商品编号，商品名称，库存量）。1．（3分）用结构化分析方法给出该系统的顶层DFD；2．（2分）给出顶层DFD的数据字典；3．（3分）选择该超级市场销售管理系统中的一个交互，并用顺序图来描述。计算机科学与技术试卷第8页共10页Ⅳ．人工智能原理（共30分）一、单项选择题（每小题2分，共8分）1．用神经网络求解问题过程中，（）陷入局部极值点。A．不可能B．可能C．必然2．提出非单调推理是由于（）。A．处理逻辑矛盾B．知识不完全C．知识表示方法3．建造专家系统的主要花费在于（）。A．建立推理机制B．收集知识建知识库C．程序设计4．采用单元归结策略的归结方法是（）。A．不完备的B．完备的C．不一定二、证明题（每小题5分，共10分）1．使用线性归结和支持集策略的归结法证明A1A2A3B儋其中