13年研究生昆明理工计算机818考试题目和答案

第1页共6页昆明理工大学2013年硕士研究生招生入学考试试题(A卷)考试科目代码：817考试科目名称：计算机学科专业基础综合考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分：一、选择题:(25题，每题1分，共25分)1.在执行下面程序段时，语句S的执行次数是B。m=1;do{k=m;do{S;k++;}while(k=n)m++;}while(m=n)(A)n*(n+1)/2(B)n*(n-1)/2(C)n!(D)n*n2.下面程序段的时间复杂度是C。j=0;s=0;while(sn){j++;s=s+j;}(A)O（√n）(B)O（√2n）(C)O（n）(D)O（n2）3.下面算法的空间复杂度为A。floataver(floata[],intn){intj;for(j=n;j0;j--)printf(“%8.2f”,a[j]);}(A)O（1）(B)O（log2n）(C)O（n）(D)O（n2）4.向一个栈顶指针为HS的链栈中删除一个结点，用X保存其值，则执行D。(A)X=HS;HS=HS-next;(B)X=HS-data;(C)HS=HS-next;X=HS-data;(D)X=HS-data;HS=HS-next;5.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行C。(A)s-next=p-next;p-next=s;(B)p-next=s-next;s-next=p;(C)q-next=s;s-next=p;(D)p-next=s;s-next=q;6.在一个带空结头的链队列中，f和r分别为队首尾指针，则进行s结点的入队操作时执行B。(A)r-next=s;r=s;(B)r-next=s;s-next=r-next;(C)s-next=r-next;r=s;(D)s-next=r-next;r-next=s;第2页共6页7.假定一个带空结头链队的队首和队尾指针分别为f和r，则判断队空的条件是D。（A）f==r（B）f==NULL（C）r==NULL（D）f-next==NULL8.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为1个，那么度为0的结点数为C个。(A)4(B)5(C)6(D)79.二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为B个。(A)15(B)16(C)17(D)47根据二叉树的性质,有n0=n2+1,故n0=1610.一棵二叉树结点数为18个，则其最小高度为，其最大高度为B。(A)4,16(B)5,18(C)6,18(D)3,18[log2(18)]+1=511.在一个顺序存储的循环队列中，队首指向队首元素的A。(A)前一个位置(B)后一个位置(C)队首元素位置队头指针指向前一位置是为了方便插入新元素,队尾指针指向队尾元素是为了取出或删除队尾元素.12.在一棵高度为h的完全三叉树中，结点总数是B。(A)3h-1(B)（3h-1）/2(C)（3h-1）/3(D)3h13.在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数为B。(A)O(n)(B)O(log2n)(C)O(nlog2n)(D)O(n2)14.中缀表达式Ａ－(Ｂ＋Ｃ)*Ｄ／Ｅ的后缀形式是D。(A)ＡＢＣ＋－Ｄ*Ｅ/(B)ＡＢＣ＋Ｄ*－Ｅ/(C)ＡＢＣ＋Ｄ－*Ｅ／(D)ＡＢＣ＋Ｄ*Ｅ／－15.下列陈述中正确的是(D)A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分16.在一个无向图中，所有顶点的度数之和等于所有边数的C倍。(A)1/2(B)1(C)2(D)417.有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为和个表结点。(A)n,e(B)n,2e(C)(n-1),e(D)(n-1),2e表头向量大小,就是表头结点数组的大小,即顶点总数,对无向图邻接表的边结点个数是边数两倍18.在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；第3页共6页(A)出边，入边(B)入边，出边19.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(C)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构20.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为A)A.n-i+1B.n-iC.iD.i-121.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表22.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为()A.4B.5C.6D.723.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为()A.356B.358C.360D.362LOC(i,j,k)=LOC(0,0,0)+x*(i*N*H+j*H+k)已知数组A[M][N][H]，求A[i][j][k]的地址x=224.排序趟数与序列的原始状态有关的排序方法是()排序法。A.插入B．选择C.起泡D．快速25.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行()元素间的比较。A．4次B．5次C.7次D．10次创建规则是以第一个元素为根结点，比它小的放在它的左子树上，比它大的放在它的右子树上。依次比较50、43、20和35第4页共6页V1V2V3V4V5V6V7∞18∞∞234618∞5812∞∞∞5∞10∞∞∞∞810∞1520∞2312∞15∞25∞4∞∞2025∞76∞∞∞∞7∞V1V2V3V4V5V6V7二、综合应用题：1.完成如下问题:(3题，每题10分，共30分)1)已知一组权值W={6,8,2,4,9,15,19},请构造一棵哈夫曼树,并计算出其WPL值。2)一棵二叉树的先序序列和中序序列分别如下，试画出该二叉树。先序序列：ABCDEFGHIJ；中序序列：CBEDAGHFJI3)已知以下无向网络的邻接矩阵存储示意。写出从顶点V2出发的深度优先搜索序列;从顶点V5出发的广度优先搜索序列。2.要在编号为0—6这7个村庄之间架设通讯网，两个村庄之间架设线路所花代价用以下无向网所带权值表示。按要求完成下列问题：1)用图的什么原理求解架设通讯网的总费用最小问题；（6分）最小生成树2)用类算法语言及图示描述实现铺设总费用最小的方案的Kruskal算法（14分）（要求：图示要画出算法所涉及的存储结构及其初始化情况）第5页共6页计算机网络部分一、单项选择题（第1小题0.5，其它每小题2分，总分22.5分）1、按照网络覆盖范围可把计算机网络分类为（D）A.广播式网络、点对点式网络B.存储转发网络、电路交换网络B.公众网、专用网D.局域网、城域网和广域网2、在OSI参考模型中，数据链路层的协议数据单元是(D)。A.DataB.SegmentC.packetD.frame3、在全双工通讯的传输中，两个连接实体之间（A）。A.同时进行双向比特流的传输B.交替进行双向比特流的传输C.只能进行单向的传输D.以上答案都不正确4、将模拟信号转换为数字信号的过程叫做（C）。A.编码B.解码C.调制D.解调5、（C）协议可以防止以太网交换网络中因为环路而出现的广播风暴问题。A.ARPB.CSMA/CDC.STPD.HDLC6、常用的A类私有地址是（A）。A.10.10.0.0～10.255.255.255B.10.0.0.0～10.255.255.255C.10.168.0.0～10.168.255.255D.172.16.0.0～172.31.255.2557、下面（C）动态路由协议属于IGP协议，使用了链路状态算法。A.BGPB.RIPC.OSPFD.EGP8、（D）协议使用的是80端口，()协议使用的是21端口。A.HTTP,TELNETB.DNS,TFTPC.HTTP,DNSD.HTTP,FTP9、客户端软件与POP3服务器建立（A）连接来（）。A.TCP,接收邮件B.UDP,发送文件C.TCP,浏览网页D.UDP,发送文件10、下列关于IP的说法，正确的是(B)。A无连接的，可靠的B无连接的，不可靠的C面向连接的，可靠的D面向连接的，不可靠的11、(B)用作教育机构的顶级域名.A.comB.eduC.cnD.orgEin-addr.arpa12、如果有多个局域网需要互联起来，并希望将局域网的广播信息很好的隔离开，那么最基本的A.网桥B.路由器C.网关D.中继方法是用（B）二、综合应用题（总分52.5分）1、请给出计算机网络的定义并予以简要解释。（10分）（1）资源共享（2）数据传送（3）均衡负荷和分布式处理功能（4）数据信息的集中和综合处理2、请简要描述OSI环境中数据的传输过程。（10分）物理层,数据链路层,网络层,传输层,会话层,表示层,应用层.第6页共6页数据传输的基本过程本人没有图解,不过可以解释一下.数据在应用层,表示层和会话层时属于高层数据,到了传输层数据被封装上TCP头部,到物理层封装上一层IP包头,继续传输到数据链路层,数据被封装上一层LLC子层的头部和MAC子层的头部信息,然后通过物理层将数据通过电信线路传输出去,接受信息则与这个规则正好相反3、试分析TCP可靠性是如何实现的。（10分）首先，为了防止数据在传输的过程中被损坏，每个信息包都包含一个校验码，这个校验码头就是一个用来保证信息包在传输过程中没有被更改的代码，当信息到达目的地的时候，接收方会对比较验码和收到的信息中的数据，如果校验码不对，则被信息包将被省略。第二，为了防止信息包丢失，TCP会要求接收方每收到一个信息包都反馈一下，如果接收方没有提供反馈，发送方会自动重发一次，一直到接收方收到为止，或者它会判断网络链接断开了，就会在程序中返回一个错误的提示。第三，为了防止信息包重复或顺序错误，TCP每传送一个信息包都会传送一个序号，接收方会检查这个序号，确保收到该信息包，并把全部信息包按顺序重新合并，同时，如果接收方看到一个已接收了的序号，则这个信息包就会被丢弃。4、试对静态路由和动态路由进行比较，说明各自的原理、优缺点和适用场合。（10分）大型网络和小型网络5、将IP地址空间202.118.1.0/24划分为两个子网，分配给局域网1、局域网2，每个局域网分配的地址数不少于120个，请给出子网划分结果。说明理由或给出必要的计算过程。（12.5分）