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

昆明理工大学2014年硕士研究生招生入学考试试题(A卷)考试科目代码：818考试科目名称：计算机学科专业基础综合考生答题须知.所有题目(包括填空、选择、图表等类型题目)答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。.评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。.答题时一律使用蓝、黑色墨水笔或圆珠笔作答(画图可用铅笔)，用其它笔答题不给分。.答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、选择题：(25题，每题1分，共25分).从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较结点数是。(A)n(B)n/2(C)(n-1)/2(D)(n+1)/22.下面算法的空间复杂度为。floataver(floata[n]){intj;for(j=n;j<0;j--)printf("%8.2f"，明]);(A)O(1)(B)O(log2n)(C)O(n)(D)O(n).在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为。(A)O(1)(B)O(n)(C)O(n2)(D)O(log2n).在一个单链表中，若要删除*p结点的后继结点，则执行。p->next=p->next->next;p->next=p->next->next;free(p->next);p->next=p->next->next;q=p->next;free(q);q=p->next;p->next=p->next->next;free(q);.在一个链队列中，f和r分别为队首尾指针，则进行插入s结点的操作时执行—。(A)f->next=s;f=s;(B)r->next=s;r=s;(C)s->next=r;r=s;D)s->next=f;f=s;做了一个入队操作，新节点当做尾结点.从顺序存储的循环队列中删除一个元素时，是。(A)先移动队首指针，后取出元素(B)先取出元素，后移动队首指针.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为1个，那么度为0的结点数为个。TOC\o"1-5"\h\z(A)4(B)5(C)6(D)7树中结点数等于所有2点度数的和加1.在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为个。(A)15(B)16(C)17(D)4715+1.一棵二叉树结点数为18个，则其最小高度为—，其最大高度为一。(A)4,16(B)5,18(C)6,18(D)3,1810g2(18)+1.一棵三叉树结点数为50个，则其最小高度为。(A)3(B)4(C)5(D)6

昆明理工大学2014年硕士研究生招生入学考试试题.由分别带权为9,2,5,7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度(A)23(B)37(C)44(D)46.已知10个数据元素(54,28,16,34,73,62,95,60,26,43),按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是3;在查找成功的情况下，查找每个元素的平均比较次数(又称平均查找长度，即查找每个元素时平均比较的结点数)为。(A)2.5(B)3.2(C)2.6(D)2.9.在一个无向图中，所有顶点的度数之和等于所有边数的倍。(A)1/2(B)1(C)2(D)4.有n个顶点的无向图中，要连通全部顶点至少需要条边。(A)n(B)(n+1)(C)(n-1)(D)n/2.有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为条边。(A)n(B)(n+1)(C)(n-1)(D)n/2.在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有邻接点；(A)出边，入边(B)入边，出边.对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少为(A)n(B)n+e(C)e(D)2e.如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得到的一种顶点序列是。V1,V2,V5,V3,V6,V7,V4V1,V5,V2,V4,V3,V7,V6图1V1,V2,V5,V4,V3,V7,V6V1,V5,V2,V3,V7,V6,V4.如图2所示，在该图的最小生成树中，各边上权值之和是在该图的最小生成树中，从点V1到点V6的路径是31,(V1,V3,V4,V6)36,(V1,V3,V4,V6)38,(V1,V4,V6)图243,(V1,V4,V3,V6)已选定点里离目标定点最近的.如图3所示，该图得到的一种拓扑序列为。(V1,V4,V6,V2,V5,V3)(V1,V2,V3,V4,V5,V6)(V1,V4,V2,V3,V6,V5)图3(V1,V2,V4,V6,V3,V5)(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。昆明理工大学2014年硕士研究生招生入学考试试题.在对长度为n的顺序存储的有序表进行二分查找时，对应的二分查找判定树的高度为。(A)n(B)_log2n_|(C)_log2(n+1)J(D)10g2(n+1).顺序查找一个具有n个元素的线性表，其时间复杂度为,二分查找为一个具有n个元素的线性表，其时间复杂度为。(A)O(n),O(1og2n)(B)O(log2n),O(1og2n)(C)O(n2),O(n)(D)O(n1og2n),O(1og2n)二分查找好比二叉树里树的层数.已知一个有序表为(12,18,24,35,47,50,62,83,90,115,134),当二分查找值为90的元素时，次比较后查找成功；当二分查找值为47的元素时，次比较后查找成功。(A)1,4(B)2,4(C)3,2(D)4,2根据二分法查找的查找过程，首先将90与表中中间的元素50进行比较，由于90大于50,所以在线性表的后半部分查找。第二次与比较的元素是后半部分的中间元素，即90,这时两者相等，即查找成功。.在顺序存储的线性表A[30]上进行顺序查找的平均查找长度为。(A)15(B)15.5(C)16(D)20(n+1)/2.已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=Kmod7计算散列地址进行散列存储时，若利用线性探测的开放定地址法处理冲突，则在该散列表上进行查找的平均查找长度为;若利用链接法处理冲突，则在该散列表上进行查找的平均查找长度为。(A)1.5,1(B)1.7,3/2(C)2,4/3(D)2.3,7/6、综合应用题：(2题，每题25分，共50分).中缀表达式中，如果不规定运算符的优先级又不加括号，则运算结果不唯一；后缀表达式中，不规定运算符的优先级又不需括号，就能得到唯一的运算结果。现以中缀表达式：(8+3*6)/(2+3*5-4)为例，回答如下问题：TOC\o"1-5"\h\z1)利用什么原理实现中缀表达式转换成后缀表达式？(5分)栈的数据结构2)写出中缀表达式转换成后缀表达式的算|法思想。(10分)3)用上中缀表达式为例，图示表现出其转换成后缀表达式的过程及结果。(10分)转换方法，对公式字符串进行逐位判断。遇到公式中的变量直接输出，运行符入栈。入栈时，比较栈顶运算符与入栈运算符的高低，再行出栈和入栈。中缀表达式转后缀表达式遵循以下原则：.遇到操作数，直接输出；.栈为空时，遇到运算符，入栈；.遇到左括号，将其入栈；.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；.遇到其他运算符‘+“-“*"时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；.最终将栈中的元素依次出栈2.在宾馆管理中，要求每间客房的出租率均等，以保证维持每间客房硬件设施的一个平均磨损率。回答如下问题：1）利用《数据结构》中什么原理处理这一问题？（5分）2）请简述并画出示意描述图。（20分）•用数据结构中的队列，把所有空房排成一个队。每次接待客人入住，从队头分配住房：客人结账退房，退掉的房间排入队尾。4-4023018137产空空―计算机网络部分一、单项选择题（每小题2分，总分22分）1、按照0比特插入/删除方法规定，在两个标志字段为F的比特序列中，如果检查出连续的（）1,不管后面的比特位是0或1,都需要增加一个0。A.4B.5C.6D.82、在（）差错控制方式中，只会重新传输那些出错的数据帧。A.连续工作B.停止等待C.选择重发D.后退N帧3、PPP协议可按功能划分为两层，其中负责建立、配置不同的网络层协议的是（）协议。A.PPTPB.HDLCC.LCPD.NCP昆明理工大学2014年硕士研究生招生入学考试试题4、常用的A类私有地址是（）。A.〜55B.〜55C.〜55D.〜555、下面（）动态路由协议属于IGP协议，使用了链路状态算法。A.BGPB.RIPC.OSPFD.EGP6、在TCP/IP协议中，UDPB议是一种（）协议。A.主机-网络层B.互联网络层C.传输层D.应用层7、如果有多个局域网需要互联起来，并希望将局域网的广播信息很好的隔离开，那么最基本的方法是用（）A.网桥B.路由器C.网关D.中继8、香农定理从定量的角度描述了带宽”与速率”的关系。在香农定理的公式中与信道的最大传输TOC\o"1-5"\h\z速率相关的参数主要有信道宽度与（）A.频率特性B.信噪比C.相位特性D.噪声功率9、（）用作商业机构的顶级域名.A.comB.eduC.cnD.orgE10、将模拟信号转换为数字数据的过程叫做（）。A.编码B.解码C.调制D.解调11、（）协议使用的是80端口，（）协议使用的是21端口。A.HTTP,TELNETB.DNS,TFTPC.HTTP,DNSD.HTTP,FTP二、综合应用题（总分53分）1、简述计算机网络的主要功能。（10分）数据通信，资源共享，分布处理，集中管理，均衡负荷2、计算机网络拓扑结构有哪几种？（10分）总线型拓扑、星型拓扑、环型拓扑、树型拓扑和混合型拓扑3、试分析TCP可靠性是如何实现的。（10分）首先，为了防止数据在传输的过程中被损坏，每个信息包都包含一个校验码，这个校验码头就是一个用来保证信息包在传输过程中没有被更改的代码，当信息到达目的地的时候，接收方会对比较验码和收到的信息中的数据，如果校验码不对，则被信息包将被省略。第二，为了防止信息包丢失，TCP会要求接收方每收到一个信息包都反馈一下，如果接收方没有提供反馈，发送方会自动重发一次，一直到接收方收到为止，或者它会判断网络链接断开了，就会在程序中返回一个错误的提示。第三，为了防止信息包重复或顺序错误，TCP每传送一个信息包都会传送一个序号，接收方会检查这个序号，确保收到该信息包，并把全部信息包按顺序重新合并，同时，如果接收方看到一个已接收了的序号，则这个信息包就会被丢弃。4、试解释TCP的三次握手过程。（10分）第一次握手：建立连接时，客户端发送syn包（syn=j）到服务器，并进入SYN_SEND状态