1、昆明理工大学2017年硕士研究生招生入学考试试题(A卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分3. 用计算机处理问题的方法称为 。评价其优劣的的办法是在其 的前提下主要是考察其 和 复杂度。1.在Data S
2、et中，数据元素分为 元素和 元素；元素间的关系是独立于计算机之外的称为 关系，分为 和 关系。实际?问题2. 这里的数据关系称为 关系，有 、 、 和 存储方法。用数据描述实际问题获得数据集Data Set计算机存储器数据存入计算机1、 填空题：（每空1分，共20分）昆明理工大学2017年硕士研究生招生入学考试试题 4. 多维数组采用的存储结构是；广义表采用的存储结构是。 5. 哈希表的查找效率主要取决于所选择的 与 。 6. 与后缀表达式a b c - d * + ，等价的中缀表达式为 。 7. 树转换成的二叉树，其根结点的 子树一定为空。二、单项选择题（每题2分，共20分）1.下面程序段
3、的时间复杂度为（ ）。 for(i=0;in+1;i+) for(j=0;jnext=p-next; p-next=q; B. p-next=q-next; q=p; C. q-next=p; p-next=q-next; D.p-next=q-next; q-next=p;4. 若入栈序列为A、B、C、D、E,入栈过程中可以出栈，则不可以是出栈序列（ ）。 A. ABCDE B. BCDEA C. EABCD D. EDCBA5. 一链队列中，假设f和r分别为队首指针和队尾指针，则出队列时，下列（ ）语句是必要的。 A. r=f-next B. r=r-next C. f=f-next D.
4、 f=r-next6. 假定一个顺序循环队列的队首队尾指针分别用front和rear表示，则判断队空的条件是（ ）。 A. front=rear B. rear+1=front C. front=0 D. front+1=rear7. 以下叙述中，正确的是（ ）。 A. 线性表的顺序存储结构优于链式存储结构 B. 网络的最小生成树是唯一的 C. 二维数组是它的数据元素为线性表的线性表 D. 数据的逻辑结构与存储结构都是依赖于计算机的8. 在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（ ）。 A. 2j B. 2j+1 C. 2j-1 D. j/29. n个顶点的连通图至少有（ ）条
5、边。 A. n-1 B. n-2 C. n D. n+110. 一有序表(6,9,11,12,14,17,21,33,37)，当二分查找值为11的结点时，（ ）次比较后查找成功。 A. 2 B. 3 C. 4 D. 5三、完成如下问题（每题5，共,10分）1.已知二叉树的中序遍历序列为CDBAEGF,后序遍历序列为DCBGFEA,请画出该二叉树。2. 若一篇文档有以下字符：A、B、C、D、E、F，各字符在文档中出现的概率依次为4,5,6,7,10,12。请构建以各字符为叶子结点的Huffman树，并写出各字符的Huffman编码。（构建时按左小右大、左0右1的规则进行） 四、已知如下无向网络的
6、邻接矩阵（其权值为整型数据）（共25）1. 用C语言描述网络的邻接矩阵的存储结构。（10分）2. 写出从顶点4出发的深度优先搜索序列、从顶点1出发的广度优先搜索序列。（6分）3. 用prim算法思想求最小生成树，要求画出生成过程。（9分） 1 2 3 4 5 61 3 1 2 3 2 4 3 1 2 2 4 4 2 3 45 3 16 4 1 网络部分：一、单项选择题（每小题1分，总分22分）1.在OSI参考模型中，自下而上第一个提供端到端服务的层次是（ ）。A数据链路层 B.传输层 C.会话层 D.应用层2.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的Q
7、AM调制技术，则该通信链路的最大数据传输速率是（ ）。 A12kbps B.24 kbps C.48 kbps D.96 kbps 3.数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为07的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。 A2B.3C.4D.5 4. 在OSI参考模型中，数据链路层的数据服务单元是（ ）。 A.帧 B.报文 C.分组 D.比特序列5.100BaseT的传输介质是（ ）。 A3类双绞线 B. 5类双绞线 C.光纤 D.同轴电缆6. 在TCP/IP协议中，UDP协议是一种（ ）协议。 A.主机网络层 B.互联层
8、 C.传输层 D.应用层7.下面关于VLAN的描述中，正确的是（ ）。 A.一个VLAN是一个广播域B.一个VLAN是一个冲突域 C.一个VLAN必须连接同一个交换机 D.不同VLAN之间不能通信 8.设立数据链路层的主要目的是将一条原始的、有差错的物理线路变为对网络层无差错的（ ）。 A.物理链路 B.数据链路 C.传输介质 D.端到端连接9. 世界上第一个计算机网络是在（ ）年诞生。 A.1946 B.1969 C.1977 D.1973 10. 按0比特插入/删除方法规定，在两个标志字段F之间的比特序列中，如果检查出连续的 （ ）个1，不管后面的比特位是0或1，都需要增加一个0。 A.4
9、 B.5 C.6 D.811. 在（ ）差错控制方式中，只会重新传输那些差错的数据帧。 A.连续工作 B.停止等待 C. 选择重发 D. 拉回12.IP地址块202.120.80.128/26包含了（ ）个主机地址。 A.15B.31 C.62D.12713.以下关于Ethernet帧结构的描述中，错误的是（ ）。 A. Ethernet V2.0规范和IEEE802.3标准中的Ethernet帧结构有差别。802.3标准规定的“类型字段”对应Ethernet V2.0帧的“类型/长度字段” B.前导码与帧前定界符字段长度为64位 C.目的地址与源地址字段为全1表示广播地址，该帧将被所有的结点
10、接收 D. 数据字段的最小长度为46B，最大长度为1500B14.某网络的IP地址为192.168.5.0/24采用定长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数为（ ），每个子网内的最大可分配地址个数为（ ）。 A.32，8B.32，6 C.8，32 D.8，3015.若路由器R因为拥塞丢弃IP分组，则此时R可以向发出该IP分组的源主机发送的ICMP报文件类型是（ ）。 A.路由重定向 B.目的不可达 C.源抑制 D.超时16.给定一个用二进制数表示的IP地址为：11010111 00111100 00011111 11000000，那么如果用点分十进制表示应
11、该是（ ）。 A.211.60.31.120 B.215.64.31.120 C.215.60.31.192 D.211.64.31.19217.SMTP协议的默认端口为 （ ），其作用是（ ）。 A.21，发送邮件 B.23，接受邮件 C.25，浏览网页D.80， QQ聊天18. 在Internet中，用于文件传输的协议是（ ）。 A.HTML B.SMTP C.FTP D.POP19.IPv4数据包首部的最小长度为（ ）字节。 A.10 B.20C.30D.4020. 设计传输层的目的是弥补通信子网的服务的不足，提高传输服务的可靠性与保证（ ）。 A.安全性 B.进程通信 C.保密性 D.
12、服务质量QoS21.下列选项中，不属于网络体系结构中所描述的内容是（ ）。 A网络的层次B.每一层使用的协议 C协议的内部实现细节D.每一层必须完成的功能22.采用OSPF协议配置路由协议时，主干区域为（ ）。 A.区域0 B.区域1C.区域10D.区域100二、综合应用题（总分53分） 1.请给出计算机网络的定义并予以简要解释。（10分） 2.ISO在制定OSI参考模型时对层次划分的主要原则是什么？（10分） 3.广域网采用的数据交换技术主要有哪些类型？（10分） 4.请简单说明四种虚拟局域网的组网方法。（10分） 5将某C类网络192.168.25.0划分成4个子网，请计算出每个子网的有效的IP地址范围和对应的网络掩码（掩码用二进制表示）。(13分)第 5 页 共 5页
