1、昆明理工大学2018年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、单项选择题（每题1分，共20分）1.下面程序的时间复杂为（ ）for（i=1，s=0； i=n； i+） t=
2、1；for(j=1；jnext=p; q-next=s; B. p-next=s-next; s-next=p; C. q-next=s-next; s-next=p; D. p-next=s; s-next=q;昆明理工大学2018年硕士研究生招生入学考试试题7.栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点8.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 2 3 4 1 5 6 D. 3 4 6 5 2 19.设C语
3、言数组Datam+1作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为 （ ）A. front=front+1 B. front=（front+1）% mC. rear=(rear+1)%(m+1) D. front=(front+1)%(m+1)10.一棵二叉树上有50个度为2的结点，其中叶子结点的个数是（ ）A 100 B 51 C25 D以上答案都不对 11.二叉树的第I层上最多含有结点数为（ ）A 2I B 2I-1-1 C 2I-1 D2I -112. 一棵有n个结点的完全二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，
4、则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）AA2i(2i=n) BA2i+1(2i+1=n) B Ai-2 D条件不充分，无法确定13. n个结点的线索二叉树上含有的线索数为（ ）A 2n Bnl Cnl Dn14.以下说法错误的是 ( )A哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。B若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。C已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵二叉树，因为不知道二叉树的根结点是哪一个。C 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是
5、直接跟在该结点的之后。15.任何一个带权的无向连通图的最小生成树（ ）A 只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在16.设无向图的顶点个数为n，则该图最多有（ ）条边。A- n-1 Bn(n-1)/2 C n(n+1)/2 D0 v En217.要连通具有n个顶点的有向图，至少需要（ ）条边。A- n-l Bn +1 Cn D2n18.当采用分块查找时，数据的组织方式为 ( ) A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 以上
6、都不是昆明理工大学2018年硕士研究生招生入学考试试题19.下图所示的4棵二叉树,( )是平衡二叉树。 A B C D20.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆 二、简答题（共55分）1.将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）（10分）NPGHJMOLIKEDFBAC12654320101166181014592.已知一个无向图如下图所示，要求用Prim算法生成最小生成树（假设以为起点，试画出构造过程）。（15分） 3.对于给定的一组关键字值：83，40，63， 84，35，96，57，39，7
7、9 。请画出应用直接插入排序对上述序列进行排序中各趟的结果。（15分）4. 已知一个带头结点的单链表L中的节点是按整数值递增排序的，写一个算法将值为x的结点插入表L中，使L仍然有序。（15分）计算机网络部分一、单项选择题（每题1分，共20分）1.所有互联网标准都以（ ）的形式在互联网上发表。A.MD5B.DESC. RFCD.Diffie-Hellman2.当前在局域网中最常见的有线传输介质是（ ）A非屏蔽双绞线 B屏蔽双绞线 C粗同轴电缆 D细同轴电缆3.基带信号往往包含有较多的低频成分，而许多信道并不能传输这种低频分量或直流分量。因此必须对基带信号进行调制 (modulation)。最基本
8、的二元制调制方法有以下几种：（ ）A.加法调制B减法调制 C.乘法调制 D调幅(AM)、调频(FM)和调相(PM)4.具有自同步功能的编码方式是（ ）A不归零制 B归零制 C.曼彻斯特编码 DASCII编码昆明理工大学2018年硕士研究生招生入学考试试题5.源IP地址和目的IP地址、源端口号和目的端口号及（ ）的组合称为套接字，用于标识客户端请求的服务器和服务。A运输层协议B.IP协议 C.ICMP D.邮件传输协议6.路由协议可分为两类：在一个自治系统AS（Autonomous System，）内的路由协议称为（ ），AS之间的路由协议称为（ ）。A.RIP 、OSPF B内部网关协议、 外
9、部网关协议C.802.3、802.3 D. CSMA/CD 、CSMA/CA 7.TCP中采用滑动窗口来进行传输控制，当发送窗口和接收窗口的大小固定为1时，滑动窗口协议退化为（ ）。ARIP路由协议 B.CSMA/CD协议 C. 停等协议（stop-and-wait） D.PPP协议8.现在最流行的局域网的网络拓扑是（ ）A总线拓扑B.环形拓扑C.星形和扩展星形拓扑 D.层状拓扑9.下面（ ）属于C类地址，而且同时属于私有地址（专有地址，private address）A. 10.0.0.1B. 172.31.0.1C. 192.168.1.1 D. 224.0.0.210.由于IPv4最大的
10、问题在于网络地址资源有限，严重制约了互联网的应用和发展。IPv6能解决网络地址资源数量的问题，IPv6的地址长度是（ ）位。A.16B.48C.64D.128 11.IP首部格式中，（ ）字段每经过一个路由器其值会减1，当值为0时，则路由器会丢弃该数据包。A. 校验和B.标识C.TTLD.片偏移12.一个子网网段地址为10.32.0.0 掩码为 255.224.0.0 的网络，它允许的最大主机地址是（ ） A. 10.32.254.254 B. 10.32.255.254 C. 10.63.255.254 D. 10.63.255.255 13.IPv4地址斜线记法192.168.1.0/30
11、对应的网络地址的掩码应该是（ ）A. 255.255.255.0 B 255.255.255.128 C. 255.255.255.248D. 255.255.255.25214. （ ）属于内部网关协议，使用链路状态算法。A. RIPB. OSPFC. BGPD.IGP昆明理工大学2018年硕士研究生招生入学考试试题15.一般情况下，浏览器使用（ ）协议访问WEB服务器TCP的（ ）端口，读取网页发布的命令是（ ）。A.HTTP，53，READ B.WEB，80，GET C.WEB，80，READD.HTTP，80，GET16.Windows系统中（ ）命令的功能是显示网络连接、路由表和网络
12、接口信息，可以让用户得知有哪些网络连接正在运行。A.netstatB.pingC.ipconfigD.tracert17. 应用层的许多协议都是基于客户服务器方式。客户(client)和服务器(server)都是指通信中所涉及的两个应用进程。客户服务器方式所描述的是进程之间服务和被服务的关系。客户是（ ），服务器是（ ）。 A.在PC机中运行、在服务器中运行B.手机中运行、大型机中运行C.服务请求方、 服务提供方D.运行QQ、运行Web服务18. 名字到 IP 地址的解析是由若干个（ ）程序完成的。AWeb服务器 B.微信 C路由D域名服务器19. （ ）是由一串用点分隔的名字组成的Internet上某一台计算机或计算机组的名称，用于在数据传输时标识计算机的电子方位。A网名B域名（Domain Name） C自制系统编号D.邮件地址20. 计算机网络上的通信面临以下两大类威胁：（ ）。A熊猫烧香和震网 B.恶意代码和病毒 C. 被动攻击和主动攻击D.木马和蠕虫二、简答题（共55分）1.什么是互联网？（10分）2.简述互联网带来的负面影响。（10分）3.简述路由器的作用。（10分）4.简述以太网适配器即以太网卡的作用。（10分）5.简述网络软件Wireshark主要功能。（15分）第 6 页 共 6页
