计算机学科专业基础综合.doc

昆明理工大学2014年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合 考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、选择题: (25题，每题1分，共25分)1. 从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较 结点数是 。(A) n (B) n/2 (C) (n-1)/2 (D) (n+1)/22. 下面算法的空间复杂度为 。float aver(float an) int j; for (j=n;jnext=p-next-next; (B) p-next=p-next-next; free(p-next);(C) p-next=p-next-next; q=p-next; free(q);(D) q=p-next; p-next=p-next-next; free(q);5. 在一个链队列中，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;6. 从顺序存储的循环队列中删除一个元素时，是 。(A) 先移动队首指针，后取出元素 (B) 先取出元素，后移动队首指针7. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为1个，那么度为0的结点数为 个。(A) 4 (B) 5 (C) 6 (D) 78. 在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为 个。(A) 15 (B) 16 (C) 17 (D) 479. 一棵二叉树结点数为18个，则其最小高度为 ，其最大高度为 。(A) 4,16 (B)5,18 (C) 6,18 (D) 3,1810. 一棵三叉树结点数为50个，则其最小高度为 。 (A) 3 (B) 4 (C) 5 (D) 6昆明理工大学2014年硕士研究生招生入学考试试题11. 由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是 。 (A) 23 (B)37 (C) 44 (D) 4612. 已知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 13. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。(A) 1/2 (B) 1 (C) 2 (D) 414. 有n个顶点的无向图中，要连通全部顶点至少需要 条边。 (A) n (B) (n+1) (C) (n-1) (D) n/215. 有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为 条边。(A) n (B) (n+1) (C) (n-1) (D) n/216. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；(A) 出边，入边 (B) 入边，出边17. 对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少为 个。1235467(A) n (B) n+e (C) e (D) 2e18. 如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得到的一种顶点序列是 。(A)V1,V2,V5,V3,V6,V7,V4 (B) V1,V5,V2,V4,V3,V7,V6 图1(C) V1,V2,V5,V4,V3,V7,V6 (D) V1, V5,V2,V3,V7,V6,V43124561281554201089619. 如图2所示，在该图的最小生成树中，各边上权值之和是 ；在该图的最小生成树中，从点V1到点V6的路径是 。 (A) 31 , (V1,V3,V4,V6) (B) 36 , (V1,V3,V4,V6) (C) 38 , (V1,V4,V6) 图2(D) 43 , (V1,V4,V3,V6)20. 如图3所示，该图得到的一种拓扑序列为 。 (A) (V1,V4,V6,V2,V5,V3) 123456(B) (V1,V2,V3,V4,V5,V6) （C) (V1,V4,V2,V3,V6,V5) 图3(D) (V1,V2,V4,V6,V3,V5)昆明理工大学2014年硕士研究生招生入学考试试题21. 在对长度为n的顺序存储的有序表进行二分查找时，对应的二分查找判定树的高度为 。 (A) n (B) log2n (C) log2(n+1) (D) log2(n+1) 22. 顺序查找一个具有n个元素的线性表，其时间复杂度为 ，二分查找为一个具有n个元素的线性表，其时间复杂度为 。(A) O(n),O(log2n) (B)O(log2n),O(log2n) (C) O(n2),O(n) (D) O(nlog2n),O(log2n) 23. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，224. 在顺序存储的线性表A30上进行顺序查找的平均查找长度为 。 (A) 15 (B) 15.5 (C) 16 (D) 2025. 已知一个线性表为（38，25，74，63，52，48），假定采用H（K）=K mod 7计算散列地址进行散列存储时，若利用线性探测的开放定地址法处理冲突，则在该散列表上进行查找的平均查找长度为 ；若利用链接法处理冲突，则在该散列表上进行查找的平均查找长度为 。 (A) 1.5,1 (B) 1.7,3/2 (C) 2,4/3 (D) 2.3,7/6二、综合应用题：(2题，每题25分，共50分)1. 中缀表达式中，如果不规定运算符的优先级又不加括号，则运算结果不唯一；后缀表达式中，不规定运算符的优先级又不需括号，就能得到唯一的运算结果。现以中缀表达式：（8+3*6）/（2+3*5-4）为例，回答如下问题：1) 利用什么原理实现中缀表达式转换成后缀表达式？（5分）2) 写出中缀表达式转换成后缀表达式的算法思想。（10分）3) 用上中缀表达式为例，图示表现出其转换成后缀表达式的过程及结果。（10分）2. 在宾馆管理中，要求每间客房的出租率均等，以保证维持每间客房硬件设施的一个平均磨损率。回答如下问题：1）利用数据结构中什么原理处理这一问题？（5分）2）请简述并画出示意描述图。（20分）计算机网络部分一、单项选择题（每小题2分，总分22分）1、按照0比特插入/删除方法规定，在两个标志字段为F的比特序列中，如果检查出连续的（）1，不管后面的比特位是0或1，都需要增加一个0。A4 B. 5 C. 6 D. 82、在（）差错控制方式中，只会重新传输那些出错的数据帧。A.连续工作B.停止等待 C.选择重发D.后退N帧3、PPP协议可按功能划分为两层，其中负责建立、配置不同的网络层协议的是（）协议。A.PPTPB.HDLCC.LCPD.NCP昆明理工大学2014年硕士研究生招生入学考试试题4、常用的A 类私有地址是 （）。A. 10.10.0.010.255.255.255 B. 10.0.0.010.255.255.255C. 10.168.0.010.168.255.255 D. 172.16.0.0172.31.255.2555、下面（）动态路由协议属于IGP协议，使用了链路状态算法。A.BGP B.RIP C.OSPF D.EGP6、在TCP/IP协议中，UDP协议是一种( )协议。A.主机-网络层B.互联网络层C.传输层D.应用层7、如果有多个局域网需要互联起来，并希望将局域网的广播信息很好的隔离开，那么最基本的方法是用（）A.网桥 B.路由器C.网关D.中继8、香农定理从定量的角度描述了“带宽”与“速率”的关系。在香农定理的公式中与信道的最大传输速率相关的参数主要有信道宽度与( )A.频率特性B.信噪比 C.相位特性D.噪声功率9、( )用作商业机构的顶级域名.A .com B .edu C .cn D .org E in-addr.arpa10、将模拟信号转换为数字数据的过程叫做（）。A.编码B.解码C.调制D.解调11、（）协议使用的是80端口，( )协议使用的是21端口。A.HTTP,TELNET B.DNS,TFTPC.HTTP,DNSD.HTTP,FTP二、综合应用题（总分53分）1、简述计算机网络的主要功能。（10分）2、计算机网络拓扑结构有哪几种？（10分）3、试分析TCP可靠性是如何实现的。（10分）4、试解释TCP的三次握手过程。（10分）5、已知某计算机所使用的IP地址是：195.169.20.25,子网掩码是：255.255.255.240，请计算出该计算机的网络号、子网号、主机号。（13分）