1、第 1 页 共 11 页昆明理工大学 2016 年硕士研究生招生入学考试试题(A 卷)考试科目代码：818 考试科目名称 ：计算机学科专业基础综合考生答题须知1 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔） ，用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。数据结构部分一、 单项选择题（共 25 题，每题 1 分，共 25 分）1. 对一个算法的评价
2、，不包括如下（ ）方面的内容。(A)健壮性和可读性 （ B）并行性 （C）正确性 （D）时空复杂度2. 对线性表，在下列哪种情况下应当采用链表表示？( )（A）经常需要随机地存取元素 （B）经常需要进行插入和删除操作（C）表中元素需要占据一片连续的存储空间 （D）表中元素的个数不变当数据在存储单元不连续时，采用链表比较好，连续时线性好3. 下面程序段的时间复杂度是（ ） 。j=0; s=0; while (snext=p-next-next (B) p=p-next(C) p=p-next-next (D) next=pq:=p.next;p.next:=p.next.next;dispose
3、(q);6. 若某线性表最常用的操作是读取任一指定序号的元素和在最后进行插入和删除运算，则采用 （ ）存储方式最省时间。(A) 顺序表 (B) 双链表 (C )带头结点的双循环链表 (D) 单循环链表顺序表便于存取,如果要插入,删除则需要移动大量的数据,工作量大.而在末尾的插入删除既不需要了.链表方便与插入,删除 存取的话需要遍历整个链表,工作量大.第 2 页 共 11 页7. 用链接方式存储的队列，在进行插入运算时( ).(A) 仅修改头指针 (B) 头、尾指针都要修改(C ) 仅修改尾指针 (D) 头、尾指针可能都要修改8. 在顺序栈中，假定以高端地址作为栈底，以 top 作为栈顶，则当做
4、出栈处理时，top 的变化为( )。(A) 不变 (B) top=0 (C ) top=top -1 (D) top=top+1昆明理工大学 2016 年硕士研究生招生入学考试试题第 3 页 共 11 页9. 一个栈的入栈序列为 1 2 3，入栈时可以出栈，则下列序列中不可能是出栈序列的是 ( )(A) 2 3 1 (B) 3 2 1(C) 3 1 2 (D) 1 2 310. 输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。若有 8、1 、4、2 依次进入输入受限的双端队列，则得不到输出序列( ).。输入受限的双端队列 (A). 2、 8、1 、4 (B).
5、 1、4、8 、2 ( C) . 4、2、1、8 (D). 2、1、4、811. 栈和队列的共同特点是( )。(A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出 (D)没有共同点 12. 给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 个元素。( A). (n+1)/2 (B) . n/2 (C) . (n-1)/2 (D). 113. 在具有 n 个单元的顺序存储的循环队列中，假定 front、rear 分别为队首和队尾指针，则判断队满的条件是( ).。（A）(rear%n)= front （B）(front+
6、1%n)=rear（C）(rear-1) %n)= front （D）(rear+1)%n)=front14. 一个中缀算术表达式 a+（b-x）*y，则对应的后缀算术表达式为 ( ).。(A) a b x y - * +; (B) a b x - + y *;(C) a b x - y * +; (D) a b x y * - +;15. 设有一个二维数组 Amn，假设 A00存放位置在 644(10)，A22存放位置在676(10)，每个元素占一个空间，问 A33(10)存放在什么位置？( ).脚注( 10)表示用 10 进制表示。(A)688 (B)678 (C) 692 （D）696计
7、算公式 Aij：A00+nj+i;644+2*n+2=676；n=15; A33=644+3*15+3=692；16. 树最适合用来表示( )。(A)有序数据元素 (B)无序数据元素(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据17. 在有n个结点的二叉链表中，值非空的链域的个数为( )。第 4 页 共 11 页 31 24 56128 15542010896(A) n-1 (B) 2n-1 (C) n+1 (D) 2n+1 18. 在一个具有 n 个顶点的无向图中，最多包含有( )边。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n219
8、. 在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要( )条边。(A) n (B) n+1 (C) n-1 (D) n/220. 任何一个无向连通图的最小生成树( )(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D)可能不存在。21. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有( )邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有( )邻接点；(A) 出边，入边 (B) 入边，出边22. 在线性表的存储结构中，( )查找（按关键字查找） 、插入、删除速度慢，但顺序存取和随机存取第 i 个元素速度快；( )查找和存取速度快，但插入、删除速度慢； (
9、)查找、插入和删除速度快，但不能进行顺序存取；( )插入、删除和顺序存取速度快；但查找速度慢。(A)散列表，顺序有序表，顺序表，链接表(B)顺序表，顺序有序表，散列表，链接表 (C)链接表，顺序有序表，散列表，顺序表 (D)顺序有序表，顺序表，链接表，散列表23. 用某种排序方法对关键字序列（25，84，21，47，15，27 ，68，35 ，20）进行排序时，序列的变化情况如下：20，15，21 ，25，47 ， 27，68，35，8415，20，21 ，25，35 ， 27，47，68，8415，20，21 ，25，27 ， 35，47，68，84则所采用的排序方法是（ ）(A)选择排序
10、（B ）希尔排序 （C）归并排序 （D）快速排序24. 已知一个有序表为（12，18，24，35，47，50 ，62，83 ，90，115，134） ，当二分查找值为 90 的元素时，( )次比较后查找成功；当二分查找值为 47 的元素时，( )次比较后查找成功。(A) 1，4 (B) 2，4 (C) 3，2 (D) 4，225. 在顺序存储的线性表 A30上进行顺序查找的平均查找长度为( )。(A) 15 (B) 15.5 (C) 16 (D) 20二、综合题：（共 3 题，共 50 分）1. 在算法设计中，存储结构的设计与什么因素有关？（10 分）数据的逻辑结构2. 在几个居民点铺设煤气管
11、道，每两个居民间的铺设费用是可以估算的（如右图所示） 。1) 如果要求铺设的总费用最小，从图的理论上，这实际上是第 5 页 共 11 页什么求解问题。 （8 分）最小生成树2) 请用 Prim 算法思想，从 V1 点开始，画出铺设方案选边的图示过程。 （12 分）3. 一组待排序的记录为（46,79,56,38,40,84） ，写出从小到大：利用冒泡排序第一, 二趟的变化序列; （10 分）46,56,38,40,79,8446,38,40,56,79,84利用快速排序第一趟的变化序列; （10 分）40，38，46 ，56，79 ，84),79,56,38,40,8440,79,56,38,
12、84 /从后往前扫找到 40 比 46 小，交换40,56,38,79,84 /从前往后扫找到 79 比 46 大，交换40,38,56,79,84 /从后往前扫找到 38 比 46 小，交换40,38,56,79,84 /从前往后扫找到 56 比 46 大，交换40,38,46,56,79,84 /最后插入基准 46第 6 页 共 11 页第 7 页 共 11 页昆明理工大学 2016 年硕士研究生招生入学考试试题计算机网络部分一、单项选择题（每空 1 分，总分 20 分）1、Internet 中域名与 IP 地址之间的翻译是由_(1)_ 来完成的。A. 域名服务器 B. 代理服务器 CFT
13、P 服务器 DWeb 服务器2、浏览器与 WWW 服务器之间传输信息时使用的协议是_(2)_。 AHTTP BHTML CFTP DSNMP 3、属于物理层的互连设备是_(3)_。A 中继器 B 网桥 C.交换机 D.路由器4、路由器是一种常用的网络互连设备，它工作在 OSIRM 的（4） 上，在网络中它能够根据网络通信的情况（5） ，并识别（6）相互分离的网络经路由器互连后（7） 。(4)：A物理层 B数据链路层 C网络层 D传输层(5)：A动态选择路由 B控制数据流量 C调节数据传输率 D改变路由结构 (6)：AMAC 地址 B网络地址 CMAC 地址和网络地址 DMAC 地址和网络地址的
14、共同逻辑地址 (7)：A形成了一个更大的物理网络 B仍然还是原来的网络C形成了一个逻辑上单一的网络 D成为若干个互连的子网 5、ADSL 对应的中文术语是_(8)_。A分析数字系统层 B非对称数字线C非对称数字用户线 D异步数字系统层HDSL 对称 6、以下网络设备中，工作于网络层的设备是_(9)_ 。A调制解调器 B. 以太网交换机 C. 集线器 D. 路由器7、在 Windows 中，可以提供 WWW 服务的软件是_(10)_ 。A. IIS B. ISA C. ISP D. ASP8、网络 122.21.136.0/22 中最多可用的主机地址是_(11)_ 。A. 1024 B. 102
15、3 C. 1022 D. 1000第 8 页 共 11 页昆明理工大学 2016 年硕士研究生招生入学考试试题9、通过_(12)_ 命令可以查看当前计算机的 TCP 连接状态。A. route B. ping C. netstat D. ipconfig10、在下列网络服务中，_(13)_ 是远程登陆服务，默认端口号为_(14)_ 。（13）A. WWW B. FTP C. BBS D. Telnet（14）A21 B23 C25 D8011、在网络地址 178.15.0.0 中划分出 10 个大小相同的子网，每个子网最多有_(15)_个可用的主机地址。 A2046 B2048 C4094 D
16、4096 12、在浏览 Web 页面时，发现了自己需要经常使用的 Web 页面，此时最好的方法是_(16)_。 A将该 Web 页面的地址加入到“收藏夹“ B将该 Web 页面的地址加入到“地址簿“ C将该 Web 页面的地址加入到“notepad“ D将该 Web 页面的地址加入到“历史记录“13、在 Windows 的网络属性配置中， “默认网关”应该设置为_(17)_的地址。ADNS 服务器 BWeb 服务器 C路由器 D交换机14、电子邮件通常使用的协议有_(18)_。ASMTP 和 POP3 BSMTP 和 RMON CRMON 和 SNMP DSNMP 和 POP315、Inter
17、net 中用于文件传输的是_(19)_。ADHCP 服务器 BDNS 服务器 CFTP 服务器 D路由器16、代理服务器可以提供_(20)_功能。A信息转发 B路由选择 C域名解析 D帧封装 第 9 页 共 11 页昆明理工大学 2016 年硕士研究生招生入学考试试题二、综合应用题（总分 55 分）1、制作交叉双绞线(一端按 EIA/TIA 568A 线序，另一端按 EIA/TIA 568B 线序)时，其中一端的线序如图(a)所示，另一端线序如图(b)所示，将图(b)中(1)(8)处空缺的颜色名称填写出来（每空 2.5 分，20 分）。2、某公司内部有一个采用 TCP/IP 作为传输协议的 1
18、00Base-TX 局域网，包括 1 台服务器和 20台客户机，通过一台 16 端口的交换机与一台 8 端口共享集线器级连，其网络结构如下图所示。服务器上运行 DHCP 服务软件，客户机的 IP 地址由 DHCP 服务程序自动分配。（15 分）问题 1连接主机 A 与交换机的单根网线的最大长度为多少? (5 分)100m问题 2该局域网中的集线器每个端口平均享有的带宽是多少? (5 分)以一个 10M 的 HUB 和一个 10M 的交换机为例,HUB 的每个端口带宽(正在使用)之和等于 10M.而交换机是每个端口都是 10M100/8 兆带宽问题 3为了控制局域网用户访问 Internet 时只能进行 WWW 浏览，网管应该在路由器上采取什么措第 10 页 共 11 页施? (5 分)策略设置，只让 TCP80 的端口进行传输昆明理工大学 2016 年硕士研究生招生入学考试试题
