资源描述
第 1 页 共 5 页昆明理工大学 2017 年硕士研究生招生入学考试试题(A 卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔） ，用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分1、填空题：（每空 1 分，共 20 分）3.用计算机处理问题的方法称为 。评价其优劣的的办法是在其 的前提下主要是考察其 和 复杂度。1.在 Data Set 中，数据元素分为 元素和 元素；元素间的关系是独立于计算机之外的称为 关系，分为 和 关系。实际?问题2.这里的数据关系称为 关系，有 、 、和 存储方法。用数据描述实际问题获得数据集Data Set计算机存储器数据存入计算机第 2 页 共 5 页昆明理工大学 2017 年硕士研究生招生入学考试试题4. 多维数组采用的存储结构是 ；广义表采用的存储结构是 。5. 哈希表的查找效率主要取决于所选择的 与 。6. 与后缀表达式 a b c - d * + ，等价的中缀表达式为 。7. 树转换成的二叉树，其根结点的 子树一定为空。二、单项选择题（每题 2 分，共 20 分）1.下面程序段的时间复杂度为（ ） 。for(i=0;inext=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. 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/2第 3 页 共 5 页9. n 个顶点的连通图至少有（ ）条边。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 的规则进行） 四、已知如下无向网络的邻接矩阵（其权值为整型数据） （共 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 种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ） 。A12kbps B.24 kbps C.48 kbps D.96 kbps 3.数据链路层采用了后退 N 帧（GBN）协议，发送方已经发送了编号为 07 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是（ ） 。A2 B.3 C.4 D.5 4. 在 OSI 参考模型中，数据链路层的数据服务单元是（ ） 。第 4 页 共 5 页A.帧 B.报文 C.分组 D.比特序列5.100BaseT 的传输介质是（ ） 。A3 类双绞线 B. 5 类双绞线 C.光纤 D.同轴电缆6. 在 TCP/IP 协议中，UDP 协议是一种（ ）协议。A.主机网络层 B.互联层 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 B.5 C.6 D.811. 在（ ）差错控制方式中，只会重新传输那些差错的数据帧。A.连续工作 B.停止等待 C. 选择重发 D. 拉回12.IP 地址块 202.120.80.128/26 包含了（ ）个主机地址。A. 15 B. 31 C. 62 D. 12713.以下关于 Ethernet 帧结构的描述中，错误的是（ ） 。A. Ethernet V2.0 规范和 IEEE802.3 标准中的 Ethernet 帧结构有差别。802.3 标准规定的“类型字段”对应 Ethernet V2.0 帧的“类型/长度字段 ” B.前导码与帧前定界符字段长度为 64 位 C.目的地址与源地址字段为全 1 表示广播地址，该帧将被所有的结点接收D. 数据字段的最小长度为 46B，最大长度为 1500B14.某网络的 IP 地址为 192.168.5.0/24 采用定长子网划分，子网掩码为 255.255.255.248，则该网络的最大子网个数为（ ） ，每个子网内的最大可分配地址个数为（ ） 。A.32，8 B.32，6 C.8，32 D.8，30第 5 页 共 5 页15.若路由器 R 因为拥塞丢弃 IP 分组，则此时 R 可以向发出该 IP 分组的源主机发送的 ICMP报文件类型是（ ） 。A.路由重定向 B.目的不可达 C.源抑制 D.超时16.给定一个用二进制数表示的 IP 地址为：11010111 00111100 00011111 11000000，那么如果用点分十进制表示应该是（ ） 。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.20 C.30 D.4020. 设计传输层的目的是弥补通信子网的服务的不足，提高传输服务的可靠性与保证（ ） 。A.安全性 B.进程通信 C.保密性 D.服务质量 QoS21.下列选项中，不属于网络体系结构中所描述的内容是（ ） 。A网络的层次 B.每一层使用的协议C协议的内部实现细节 D.每一层必须完成的功能22.采用 OSPF 协议配置路由协议时，主干区域为（ ） 。A.区域 0 B.区域 1 C.区域 10 D.区域 100二、综合应用题（总分 53 分）1.请给出计算机网络的定义并予以简要解释。 （10 分）2.ISO 在制定 OSI 参考模型时对层次划分的主要原则是什么？（10 分）3.广域网采用的数据交换技术主要有哪些类型？（10 分） 4.请简单说明四种虚拟局域网的组网方法。 （10 分）5将某 C 类网络 192.168.25.0 划分成 4 个子网，请计算出每个子网的有效的 IP 地址范围和对应的网络掩码（掩码用二进制表示） 。(13 分)
展开阅读全文