1、昆明理工大学2015年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、 单项选择题（共15题，每题2分，共30分）1、下面语句段执行的时间复杂度是（ ） for(i=1;i=n;i
2、+) for(j=i;jnext=p-next-next B） p=p-next C）p=p-next-next D） next=p4、线性表是（ ）。A）一个有限序列，可以为空 B）一个有限序列，不能为空C）一个无限序列，可以为空 D）一个无限序列，不能为空 5、在数组A810中，每一个数组元素占用4个字节，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的空间是( ）字节。A) 80 B) 100 C) 280 D) 320 6、假定一个顺序循环队列中空一个存储单元不用，其队首和队尾指针分别用front和rear表示,则判断队满的条件为（ ） A) front+1=rear
3、 B) rear+1=front C) front=0 D) front=rear7、一个栈的入栈序列是1,2,3,4,5,则该栈不可能的输出序列是（ ）A) 54321B) 43512 C) 45321D) 123458、栈操作的特点是( )。A) 先进后出 B) 先进先出 C)随机存取 D) 顺序存取昆明理工大学2015年硕士研究生招生入学考试试题9、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( )。A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续或不连续都可以10、树最适合用来表示（ ）。A）有序数据元素 B）元素之间具有分支层次关系的数据C）无序
4、数据元素 D）元素间无联系的数据11、深度为5的二叉树最多有（ ）个结点。A）10B）16 C）32 D）3112、在以下所示的有向图中，顶点D的入度和出度分别是（ ）A）1 2 B）2 1C）3 1 D）1 313、一个AOV网的拓扑序列（ ）A）一定是唯一的 B）不一定是唯一的 C）一定不是唯一的 D）以上说法都不正确14、对长度为18的顺序存储的有序表，采用二分查找，则查找第15个元素的比较次数为( )。A）3 B）4 C） 5 D）615、在下面的排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。A）选择排序B）冒泡排序 C）快速排序D）插入排序二、判断题（共10题，每题1
5、分，共10分）1、时间复杂度用来描述算法占用存储空间的多少【 】2、空串就是由空格组成的字符串。【 】3、在顺序表中进行插入和删除操作需要移动大量元素，时间效率较低。【 】4、二叉树中结点最大的度为2。【 】5、树中所有结点都有双亲结点。【 】6、一个有n个顶点连通图，其生成树有n-1条边。【 】7、有向图跟无向图的领接矩阵都是对称距阵。【 】昆明理工大学2015年硕士研究生招生入学考试试题8、二叉排序树的中序编历序列是按结点关键字递增排序的有序序列。【 】9、若待排序的记录数目较小，可采用直接插入排序或直接选择排序。【 】10、直接插入排序是不稳定的。【 】三、完成如下问题: （共3题，每题
6、6分，共18分）1. 已知一组权值W=6,8,2,4,9,15,19,请（按左小右大方式）构造一棵哈夫曼树,并计算出其WPL值。（6分）2. 一棵二叉树的后序序列和中序序列分别如下，试画出该二叉树。（6分） 中序序列：a + b * c d / e ； 后序序列: a b c * + d e / -V1V2V3V4V5V6V7 18 23 4 618 5 8 12 5 10 8 10 15 20 23 12 15 25 4 20 25 7 6 7 V1V2V3V4V5V6V73. 已知以下无向网络的邻接矩阵存储示意。写出从顶点V4出发的深度优先搜索序列; 从顶点V7出发的广度优先搜索序列（6分
7、）。四、算法设计：（17分）1. 已知DBF(int j)是连通图的遍历算法。非连通图的遍历算法如下，请在此基础上修改算法，使该算法具有求出非连通图中有多少连通分量的功能：TRAVER() int j;for ( j=0; jn; j+) visitedj=FALSE; for ( j=0; jn; j+) if ( ! visitedj) DBF( j ); printf( “comp end n”); 昆明理工大学2015年硕士研究生招生入学考试试题网路部分一、单项选择题（每小题1分，总分22分）1、按照网络覆盖范围可把计算机网络分类为（ ）。A.广播式网络、点对点式网络 B.存储转发网络
8、、电路交换网络C.公众网、专用网 D.局域网、城域网和广域网2、在OSI参考模型中，数据链路层的协议数据单元是（ ）。A.Data B.Segment C. packet D.frame3、将物理信道的总频带宽分割成若干个子信道，每个子信道传输一路信号，这就是（ ）。A.同步时分多路复用 B.空分多路复用 C.异步时分多路复用 D.频分多路复用4、在TCP/IP协议栈中，（ ）用来完成域名和IP地址之间的映射。ADNSB. ARPC. RARPD. ICMP5、网络中管理计算机通信的规则称为（ ）。A. 协议 B. 介质 C. 服务 D. 网络操作系统 6、（ ）这种数字数据编码方式属于自含时
9、钟编码。A.非归零制 B.脉冲编码C.曼彻斯特编码D.二进制编码7、 计算机自动拨号建立线路连接的过程属于OSI/RM的（ ）功能。A. 物理层 B. 数据链路层 C. 网络层 D. 传输层8. 双绞线由两个具有绝缘保护层的铜导线按一定密度互相绞在一起组成，这样可以（ ）。A. 降低成本 B. 降低信号干扰的程度C. 提高传输速度 D. 无任何作用9、 在OSI参考模型中，第N层和其上的第N+1层的关系是（ ）。A. 第N+1层将为从第N层接收的信息增加一个信头B. 第N层利用第N+1层的服务C. 第N层对第N+1层没有任何作用D. 第N层为第N+1层提供服务10、 UDP是TCP/IP协议簇
10、的（ ）协议。A. 应用层 B. 传输层 C. 网络层 D. 网络接口层11、 一座大楼内的一个计算机网络系统，属于（ ）。A. PAN B. LAN C. MAN D. WAN12、 制定FDDI标准的机构是（ ）。A. ISO B. IEEE802委员会 C. ANSI D. IT13、 通信系统必须具备的三个基本要素是（ ）.。A. 终端、电缆、计算机 B. 信号发生器、通信线路、信号接收设备C. 信源、信道、信宿 D. 终端、通信设施、接收设备昆明理工大学2015年硕士研究生招生入学考试试题14、 Internet上的3个传统的基本应用是（ ）。A. Telnet、FTP、Email
11、B. Telnet、FTP、WWW C. FTP、WWW、Email D. WWW、BBS、SNMP15、 OSI的网络管理标准框架的基本网络管理功能不包括（ ）A. 计费管理 B. 应用程序管理 C. 性能管理 D. 安全管理16、 IP地址190.100.80.99是（ ）地址。A. A类 B. B类 C. C类 D. D类17、 以下哪种总线不是网卡的总线类型（ ）。A. AGP B. ISA C. PCI D. EISA18、 IEEE802.5与以下哪个网络相关（ ）。A. Token Ring B. Ethernet C. Internet D. ATM19、当电子邮件程序向邮件服
12、务器发送邮件时，使用的是（ ）协议。A.PPP B.POP3C.SMTPD.UDP20、不同自治系统的路由器之间所使用的动态路由协议归类为（ ）。A.OSPF B.EGP C.IGP D.RIP21、 以下软件中（ ）不是浏览器。A. Outlook Express B. Netscape C. Firefox D. Internet Explorer22、 Intranet指（ ）。A. 万维网 B. 企业内部网 C. 环球互连网 D. 交换网二、综合应用题（总分53分）1、简述调制解调器的主要功能。（10分）2、网络互连的含义是什么？（10分）3、设某数据通信系统采用CRC校验，生成多项式G（X）=X4+X3+1。若目的节点接收到的二进制比特串是110111001，试问传输过程中是否出现了差错？为什么？（10分）4、电子邮件地址的格式是怎么样的？各部分的含义是什么？（10分）5、十进制IP地址为199.5.48.3请转换成二进制形式，并说明是哪一类IP地址，该类地址最大网络数和每个网络中最大主机数。（13分）第 6 页 共 6页
