搜索
学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第1页2007年同等学力人员申请硕士学位学科综合水平全国统一考试计算机科学与技术模拟试题及解析第一部分数学基础课程第二部分专业知识课程Ⅰ计算机系统结构Ⅱ计算机网络Ⅲ软件工程Ⅳ人工智能原理Ⅴ计算机图形学第一部分数学基础课程一、形式下列语句（共同社分）1.(1分)发光的不都是金子。答：设L（x）：x是发光的东西。G（x）：x是金子。形式化为：))()()((xGxLx¬∧∃2.(2分)对于每一个实数x，存在一个更大的实数y。答：设R（x）：x是实数。Q（x，y）：y大于x。故)))(),()(()()((yRyxQyxRx∧∃→∀二、填空题(共9分)1.（1分）在一个有n个元素的集合上，可以有（22n）种不同的二元关系。解析：因为在X中的任何二元关系都是X*X的子集，而X*X中共有NP2P个元素，共可组成22n个子集，因此可以有22n个关系。2．（2分）设A={1，2}则APAP中有（4）个函数，其中（2）个是满射。3.（2分）一人在距家以东9个街区，以北7个街区的地点工作。每天他都要步行16个街区去上班，那么他有（!7!9!16）中不同的路线。学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第2页解析：用e表示一个东向街区，用n表示一个北向街区。该人从家至工作地点所走的每一条路径都必须包括9个e和7个n即每一个路径都对应多重集{9*e，7*n}的一个全排列。所以总共有!7!9!16条路径。4.（2分）在（3x-2y）P18P的展开式中，PPxP5PyP13P的系数是（⎟⎟⎠⎞⎜⎜⎝⎛−518*2*3135）。解析：135135135518*2*3)2()3(518yxyx⎟⎟⎠⎞⎜⎜⎝⎛−=−⎟⎟⎠⎞⎜⎜⎝⎛，故系数为⎟⎟⎠⎞⎜⎜⎝⎛−518*2*31355.（2分）将8个人分成3组有（966）种分法。解析：共有SB2B（8，3）=966三、解答题（共11分）1、（3分）设)(QPQP∨¬=↓，试将QPQPP∨∧¬,,仅用连接词↓表示出来。解析：①PPP↓⇔¬②)()()(QPQPQPQP↓↓↓⇔↓¬⇔∨③)()(QQPPQPQP↓↓↓⇔¬↓¬⇔∧2、（8分）用红白和蓝色对1*n棋盘方格涂色。设Hn是没有两个涂成红社的方格相邻的着色方法数，求出Hn所满足的递推关系，然后找出Hn的公式。解析：若第一个格为红色，则第二格只能涂白或蓝，余下n-2个格涂色方法数为Hn-2.若第一格不涂红，则或涂白或涂蓝，余下n-1个格涂色方法数为Hn-1，又n=1时，H1=3.若定义H0=1.则有Hn=2Hn-2+2Hn-1H0=1，H1=3.解得Hn=nn)31(3223)31(3223−−+++四、证明题（共17分）1、（3分）R是集合A上的二元关系，证明RP2P也是A上的等价关系。解析：（1）自反性对任意的a∈A，由于R是自反的，故a,a∈R,因此a,a∈RP2P，RP2P也是自反的。（2）对称性对任意的a,b∈RP2P存在c∈A，满足a,c∈R且c,b∈R,由于R是对称的，故有c,a∈R且b,c∈R，因此b,a∈RP2P，RP2P是对称的。学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第3页（3）传递性对任意的a,b∈RP2Pb,c∈RP2P存在x,y∈A，满足a,x∈R且x,b∈R,b,y∈R且y,c∈R由于R是传递的，故有a,b∈R且b,c∈R，因此a,c∈RP2P，RP2P是传递的。综上所述RP2P是A上的等价关系2、（4分）G为有限Abel群，如果G除了两个平凡子群外不再含有其他正规子群，则称G为单群。证明：当且仅当G的阶为素数，G为单群。解析：先证必要性：即若G为单群，则G的阶为素数。设H为G的正规子群，有Lagrange定理有：|G|=|G：H|*|H|因为G为单群，它只有两个平凡子群，所以|H|要么为|G|要么为1，因此|G|为素数。再证充分性，即若G的阶为素数，则G为单群。因为|G|为素数，所以G的子群只有平凡子群，因此G为单群。3.（4分）设G1和G2是无向完全图Kn（n=4）的两个不同的子图，它们都是欧拉图，证明21GG⊕的每个连通分支都是欧拉图（其中⊕为两个图的环和运算）。解析：对于21GG⊕的每个结点v,因为G1和G2为欧拉图，所以G1中v的度数d1（v）为偶数，且G2中v的度数d2（v）也是偶数。设G1∩G2中，v的度数为x，因为21GG⊕=（G1∪G2）--(G1∩G2）所以在21GG⊕中，v的度数d（v）=d1（v）+d2（v）-2x，仍为偶数。所以21GG⊕的每个连通分支都是欧拉图。4.（6分）设G=（V,E）是无向连通图，G中至少有3个顶点，证明G中存在两个顶点，将它们删除后，图仍然是连通的。解析：设图G上的最长初级路径（顶点不重复）为P：v0v1…vp因为P为最长的初级路径所以与v0或vp关联的顶点都在路径P上，所以图G-{v0,vp}仍然是连通的。否则，假设G-{v0,vp}中存在两个u0和u1不连通。又因为图G是连通的，所以在G中存在u0和u1的间路径P‘。而在G-{v0,vp}中u0和u1不连通。唯一的原因就是路径P‘上包含结点v0或vp。又因为与v0或vp关联的顶点都在路径P：v0v1…vp上，所以删去v0vp以及它们关联的边，路径P上的结点还是连通的。所以在G-{v0,vp}中一定可以找到另一条路径是u0和u1连通。因此可得图G-{v0,vp}仍然是连通的。第二部分专业知识课程课程Ⅰ计算机系统结构一、填空题（每空1分，共5分）1.假设一个采用组相联地址映像的Cache存储器，区内分为n组，Cache容量共有m块，若n=（1）时，组相联映像就是直接映像；若n=（m）时组相联映像就是全相联映像。学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第4页2.假设在1000次访存中，第一级Cache失效40次，第二级Cache失效20次，那么，第一级Cache的失效率是（4%），第二级Cache的失效率是（50%）。整个Cache的失效率是（2%）。二．计算题（6分）设存储系统由二级Cache和主存组成，第一级Cache和第二级Cache的访问周期均为Tc，主存访问周期为Tm，若第一级Cache和第二级Cache的命中率分别是Hc1和Hc2.（1）求该存储系统的平均访问周期（2）该存储系统相对于直接对主存进行访存的加速比是多少？加速比的最大值是多少解析：（1）该存储系统的平均访问周期T=∑=31iHiTi=Hc1Tc+Hc2Tc+(1-Hc1-Hc2)Tm=(Hc1+Hc2)Tc+[1-(Hc1+Hc2)]Tm(2)该存储系统相对于直接对主存进行访存的加速比S=Tm/T=Hc2)]TmHc1(-[1Hc2)TcHc1(Tm+++=H)Tm-(1HTcTm+其中H=Hc1+Hc2，当H-1时，有最大加速比Smax=Tm/Tc三．设计题（9分）设某台计算机有9条指令，各指令的使用频率分别是I1：52%I2：14%I3：12%I4：7%I5：6%I6：5%I7：2%I8：1%I9：1%试分别用哈夫曼编码和2-4-6等长扩展编码为其操作码编码，并分别计算平均码长。综合题由哈夫曼算法生成的哈夫曼树如图所示：学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第5页由哈夫曼树生成的哈夫曼码和2-4-6扩展码如下表所示由表中哈夫曼码计算操作码平均码长为：∑==91iiiilpl=2.06位IiPi哈夫曼码2-4-6扩展码IiPi哈夫曼码2-4-6扩展码I10.52000I60.0511101110I20.14100014I70.0211110111100I30.1211010I80.01111110111101I40.0710101100I90.01111111111110I50.0610111101由表中2-4-6扩展码计算操作码平均码长：∑==91iiiilpl=2.52位四．综合题（10分）试确定在下列各种计算机系统中计算下述算术表达式所需要的时间：S=C[1]*D[1]+C[2]*D[2]+C[3]*D[3]+C[4]*D[4]I10.010.010.020.050.120.520.140.070.060.020.040.090.210.130.270.481111100110100000I9I8I7I6I3I1I2I4I51.00学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第6页(1)具有一个通用PE的SISD系统(2)具有一个加法器和一个乘法器组成的流水线SISD系统(3)具有4个PE的SIMD系统(4)具有4个PE的MIMD系统假设一次加法需要2个单位时间，一次乘法需要4个单位时间，取指令和存取数据所需要的存储器访问时间忽略不计。数据从一个PE传送到直接相连的PE的传输时间按需要1个单位时间，在SIMD系统中，4个PE连接成单向环，在MIMD系统中，4个PE之间全连接。解析：计算S需要做4次乘法和3次加法，设单位时间为t（1）在单一通用PE的SISD计算机上，计算S所需时间T1=4*4t+3*2t=22t（2）在乘加流水线的SISD计算机上，计算S的时空图如下图所示，4次乘法分别用1~4表示，3次加法额分别用5~7表示。由上图所示的时空图可得，计算S所需时间T2=10*2t=20t（3）在由4个PE组成单向环的SIMD计算机上，并行计算S的树形流程图如下图所示。同一层的结点只能执行同一种运算。首先4个PE同时完成所需的4次乘法；然后由PE2和PE4同时完成所需的2次加法；最后，由PE4完成最后一次加法得到S。箭头表示相连PE之间按单向环方向的数据传送。如下图所示的树形流程图可得计算S所需时间T3=4t+t+2t+2t+2t=11t11433224576加乘tPE4PE4PE2PE4PE3PE2PE1学苑中心培训系列教材内部资料，翻版必究智力服务于中国，提高企业与个人整体竞争力第7页（4）在由4个PE组成全连接的MIMD计算机上，虽然MIMD计算机上的各个PE可同时执行不同的运算。但是计算S时要求先完成4次乘法才能再做3次加法，因此，并行计算S的树形流程图也如上图所示。但是由于PE2也同PE4直接连接，所以一次数据传送也只需t，可得计算S所需时间T4=4t+t+2t+t+2t=10t课程Ⅱ计算机网络一、单项选择题（共10分，每题1分）1.一座大楼内的一个计算机网络系统，属于（B）A、PANB、LANC、MAND、WAN2.信道容量是带宽与信噪比的函数，以下哪一个术语用来描述这种关系？（UAU）A.Shannon定理B.带宽C.Nyquist准则D.傅里叶原理3.有一个令牌环子网和以太子网，通过路由器连接，令牌环子网速率为4Mbps，使用TCP/IP。从令牌环子网拷贝文件到以太子网用了2分钟，而反之则少于30秒，最可能的原因是（UCU）。A.TCP的窗口大小不一致B.令牌环比以太网慢C.令牌环网的数据包大于以太网D.二种子网的帧类型不匹配解释：以太网帧长的最大值是1518字节。令牌环网的最大帧长无限制，典型地，4500字节用于4Mbps的令牌环；18000字节用于16Mbps的令牌环。4.以下哪一个选项按顺序包括了OSI模型的各个层次(A)。A、物理层，数据链路层，网络层，运输层，会话层，表示层和应用层B、物理层，数据链路层，网络层，运输层，系统层，表示层和应用层C、物理层，数据链路层，网络层，转换层，会话后，表示层和应用层D、表示层，数据链路层，网络层，运输层，会话层，物理层和应