（A）O（√n）（B）O（√2n）（C）O（n）（D）O（n2）
4.从一个长度为n的顺序表中，如果删除第i个元素时，需要向前移动（）个元素。
（A）n-i（B）n-i+1（C）n-i-1（D）i
5.设单链表中指针p指向结点Ａ，若要删除Ａ之后的结点（结点若存在），则需修改指针的操作是（ ）。
（A）p->next=p->next->next（B）p=p->next
（C）p=p->next->next（D）next=p
q:
=p^.next;
p^.next:
=p^.next^.next;
dispose（q）;
6.若某线性表最常用的操作是读取任一指定序号的元素和在最后进行插入和删除运算，则采用（ ）存储方式最省时间。
（A）顺序表（B）双链表（C）带头结点的双循环链表（D）单循环链表
顺序表便于存取,如果要插入,删除则需要移动大量的数据,工作量大.而在末尾的插入删除既不需要了.链表方便与插入,删除存取的话需要遍历整个链表,工作量大.
7.用链接方式存储的队列，在进行插入运算时（）.
（A）仅修改头指针 （B）头、尾指针都要修改
（C）仅修改尾指针（D）头、尾指针可能都要修改
8.在顺序栈中，假定以高端地址作为栈底，以top作为栈顶，则当做出栈处理时，top的变化为（）。
（A）不变（B）top=0（C）top=top-1（D）top=top+1
昆明理工大学2016年硕士研究生招生入学考试试题
9.一个栈的入栈序列为123，入栈时可以出栈，则下列序列中不可能是出栈序列的是（）
（A）231（B）321
（C）312（D）123
10.输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。
若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列（）.。
输入受限的双端队列
（A）.2、8、1、4（B）.1、4、8、2（C）.4、2、1、8（D）.2、1、4、8
11.栈和队列的共同特点是（）。
（A）只允许在端点处插入和删除元素（B）都是先进后出
（C）都是先进先出（D）没有共同点
12.给定一个有n个元素的有序线性表。
若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动个元素。
（A）.（n+1）/2（B）.n/2（C）.（n-1）/2（D）.1
13.在具有n个单元的顺序存储的循环队列中，假定front、rear分别为队首和队尾指针，则判断队满的条件是（）.。
（A）（rear%n）==front（B）（（front+1%n）==rear
（C）（（rear-1）%n）==front（D）（（rear+1）%n）==front
14.一个中缀算术表达式a+（b-x）*y，则对应的后缀算术表达式为（）.。
（A）abxy-*+;（B）abx-+y*;
（C）abx-y*+;（D）abxy*-+;
15.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]（10）存放在什么位置？
（）.脚注（10）表示用10进制表示。
（A）688（B）678（C）692（D）696
计算公式A[i][j]：
A[0][0]+nj+i;
644+2*n+2=676；
n=15;A[3][3]=644+3*15+3=692；
16.树最适合用来表示（）。
（A）有序数据元素（B）无序数据元素
（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据
17.在有n个结点的二叉链表中，值非空的链域的个数为（）。
（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）n2
19.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
（A）n（B）n+1（C）n-1（D）n/2
20.任何一个无向连通图的最小生成树（）
（A）只有一棵（B）有一棵或多棵（C）一定有多棵（D）可能不存在。
21.在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有（）邻接点；在有向图的逆邻接表中，每个顶点的邻接表链接着该顶点的所有（）邻接点；
（A）出边，入边（B）入边，出边
22.在线性表的存储结构中，（）查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；（）查找和存取速度快，但插入、删除速度慢；（）查找、插入和删除速度快，但不能进行顺序存取；（）插入、删除和顺序存取速度快；但查找速度慢。
（A）散列表，顺序有序表，顺序表，链接表
（B）顺序表，顺序有序表，散列表，链接表
（C）链接表，顺序有序表，散列表，顺序表
（D）顺序有序表，顺序表，链接表，散列表
23.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是（）
（A）选择排序（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，2
25.在顺序存储的线性表A[30]上进行顺序查找的平均查找长度为（）。
（A）15（B）15.5（C）16（D）20
二、综合题：
（共3题，共50分）
1.在算法设计中，存储结构的设计与什么因素有关？
（10分）
数据的逻辑结构
2.
在几个居民点铺设煤气管道，每两个居民间的铺设费用是可以估算的（如右图所示）。
1）如果要求铺设的总费用最小，从图的理论上，这实际上是什么求解问题。
（8分）
最小生成树
2）请用Prim算法思想，从V1点开始，画出铺设方案选边的图示过程。
（12分）
3.一组待排序的记录为（46,79,56,38,40,84），写出从小到大：
①利用冒泡排序第一,二趟的变化序列;（10分）
46,56,38,40,79,84
46,38,40,56,79,84
②利用快速排序第一趟的变化序列;（10分）
40，38，46，56，79，84）
[],79,56,38,40,84
40,79,56,38,[],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
昆明理工大学2016年硕士研究生招生入学考试试题
计算机网络部分
一、单项选择题（每空1分，总分20分）
1、Internet中域名与IP地址之间的翻译是由__
（1）__来完成的。
A.域名服务器 B.代理服务器 C．FTP服务器 D．Web服务器
2、浏览器与WWW服务器之间传输信息时使用的协议是___
（2）___。
A．HTTP B．HTML C．FTP D．SNMP
3、属于物理层的互连设备是_（3）_。
A 中继器 B 网桥 C.交换机 D.路由器
4、路由器是一种常用的网络互连设备，它工作在OSI／RM的（4）上，在网络中它能够根据网络通信的情况（5），并识别（6）·相互分离的网络经路由器互连后（7）。
（4）：
A．物理层 B．数据链路层 C．网络层 D．传输层
（5）：
A．动态选择路由 B．控制数据流量C．调节数据传输率D．改变路由结构
（6）：
A．MAC地址 B．网络地址
C．MAC地址和网络地址D．MAC地址和网络地址的共同逻辑地址
（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.ASP
8、网络122.21.136.0/22中最多可用的主机地址是__（11）__。
A.1024 B.1023 C.1022 D.1000
昆明理工大学2016年硕士研究生招生入学考试试题
9、通过__（12）__命令可以查看当前计算机的TCP连接状态。
A.route B.ping C.netstat D.ipconfig
10、在下列网络服务中，__（13）__是远程登陆服务，默认端口号为__（14）__。
（13）A.WWW B.FTP C.BBS D.Telnet
（14）A．21 B．23 C．25 D．80
11、在网络地址178.15.0.0中划分出10个大小相同的子网，每个子网最多有___（15）___个可用的主机地址。
A．2046 B．2048 C．4094 D．4096
12、在浏览Web页面时，发现了自己需要经常使用的Web页面，此时最好的方法是___（16）___。
A．将该Web页面的地址加入到"收藏夹"
B．将该Web页面的地址加入到"地址簿"
C．将该Web页面的地址加入到"notepad"
D．将该Web页面的地址加入到"历史记录"
13、在Windows的网络属性配置中，“默认网关”应该设置为_（17）_的地址。
A．DNS服务器 B．Web服务器 C．路由器 D．交换机
14、电子邮件通常使用的协议有_（18）_。
A．SMTP和POP3 B．SMTP和RMON C．RMON和SNMP D．SNMP和POP3
15、Internet中用于文件传输的是_（19）_。
A．DHCP服务器 B．DNS服务器 C．FTP服务器 D．路由器
16、代理服务器可以提供_（20）_功能。
A．信息转发 B．路由选择 C．域名解析 D．帧封装
昆明理工大学2016年硕士研究生招生入学考试试题
二、综合应用题（总分55分）
1、制作交叉双绞线（一端按EIA/TIA568A线序，另一端按EIA/TIA568B线序）时，其中一端的线序如图（a）所示，另一端线序如图（b）所示，将图（b）中
（1）～（8）处空缺的颜色名称填写出来（每空2.5分，20分）。
2、某公司内部有一个采用TCP/IP作为传输协议的100Base-TX局域网，包括1台服务器和20台客户机，通过一台16端口的交换机与一台8端口共享集线器级连，其网络结构如下图所示。
服务器上运行DHCP服务软件，客户机的IP地址由DHCP服务程序自动分配。
（15分）
[问题1]
连接主机A与交换机的单根网线的最大长度为多少?
（5分）
100m
[问题2]
该局域网中的集线器每个端口平均享有的带宽是多少?
（5分）
以一个10M的HUB和一个10M的交换机为例,HUB的每个端口带宽（正在使用）之和等于10M.而交换机是每个端口都是10M
100/8兆带宽
[问题3]｝
为了控制局域网用户访问Internet时只能进行WWW浏览，网管应该在路由器上采取什么措施?
（5分）
策略设置，只让TCP80的端口进行传输
昆明理工大学2016年硕士研究生招生入学考试试题
3、某一网络地址块192.168.75.0中有5台主机A、B、C、D和E，它们的IP地址及子网掩码如下表所示。
（20分）
主机IP地址及子网掩码表
主机
IP地址
子网掩码
A
192.168.75.18
255.255.255.240
B
192.168.75.146
255.255.255.240
C
192.168.75.158
255.255.255.240
D
192.168.75.161
255.255.255.240
E
192.168.75.173
255.255.255.240
【问题1】（10分）
5台主机A、B、C、D、E分属几个网段？
哪些主机位于同一网段？
3个
【问题2】（5分）
主机D的网络地址为多少？
192.168.75.160/28
【问题3】（5分）
若要加入第六台主机F，使它能与主机A属于同一网段，其IP地址范围是多少？
192.168.75.17/28~192.168.72.30/28
升级会员 