2016 年云南昆明理工大学计算机学科专业基础综合考研真
题 A 卷
数据结构部分
一、单项选择题(共 25 题,每题 1 分,共 25 分)
1. 对一个算法的评价,不包括如下( )方面的内容。
(A).健壮性和可读性
(B)并行性
(C)正确性
(D)时空复杂度
2.
对线性表,在下列哪种情况下应当采用链表表示?(
)
(A)经常需要随机地存取元素
(C)表中元素需要占据一片连续的存储空间
(B)经常需要进行插入和删除操作
(D)表中元素的个数不变
3. 下面程序段的时间复杂度是( )。
j=0;
(A)
while
s=0;
O(√n) (B) O(√2 n) (C) O(n) (D) O(n2)
s=s+j;
}
(snext=p->next->next
(B)
p=p->next
(C) p=p->next->next
(D)
next=p
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
9. 一个栈的入栈序列为 1 2 3,入栈时可以出栈,则下列序列中不可能是出栈序列的是
(
)
(A) 2 3 1
(C) 3 1 2
(B) 3 2 1
(D) 1 2 3
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 个元素的有序线性表。若采用顺序存储结构,则在等概率前提下,删除
其中的一个元素平均需要移动 个元素。
n/2
(n+1)/2
( A).
(B) .
(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) a
(C) a
b
b
x
x
y
-
- *
+;
(B) a
y *
+;
(D) a
b
b
x
x
-
y
+ y
*;
* -
+;
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
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 分)
②利用快速排序第一趟的变化序列; (10 分)
8
1
4
2
20
5
5
6
4
12
15
10
9
8
3
6
计算机网络部分
一、单项选择题(每空 1 分,总分 20 分)
1、Internet 中域名与 IP 地址之间的翻译是由__(1)__ 来完成的。
A. 域名服务器
C.FTP 服务器
B. 代理服务器
D.Web 服务器
2、浏览器与 WWW 服务器之间传输信息时使用的协议是___(2)___。
A.HTTP
D.SNMP
B.HTML
C.FTP
3、属于物理层的互连设备是_(3)_。
A 中继器
B 网桥
C.交换机
D.路由器
4、路由器是一种常用的网络互连设备,它工作在 OSI/RM 的(4) 上,在网络中它能够根
据网络通信的情况(5) ,并识别(6)·相互分离的网络经路由器互连后(7) 。
(4):A.物理层
(5):A.动态选择路由
(6):A.MAC 地址
B.数据链路层
B.控制数据流量 C.调节数据传输率 D.改变路由结构
C.网络层
D.传输层
B.网络地址
D.MAC 地址和网络地址的共同逻辑地址
C.MAC 地址和网络地址
(7):A.形成了一个更大的物理网络
C.形成了一个逻辑上单一的网络
B.仍然还是原来的网络
D.成为若干个互连的子网
5、ADSL 对应的中文术语是__(8)__。
A.分析数字系统层
C.非对称数字用户线
B.非对称数字线
D.异步数字系统层
6、以下网络设备中,工作于网络层的设备是__(9)__ 。
A.调制解调器 B. 以太网交换机 C. 集线器
D. 路由器
7、在 Windows 中,可以提供 WWW 服务的软件是__(10)__ 。
A. IIS
C. ISP
B. ISA
D. ASP
8、网络 122.21.136.0/22 中最多可用的主机地址是__(11)__ 。
A. 1024
D. 1000
9、通过__(12)__ 命令可以查看当前计算机的 TCP 连接状态。
A. route
C. netstat
C. 1022
B. 1023
B. ping
D. ipconfig
10、在下列网络服务中,__(13)__ 是远程登陆服务,默认端口号为__(14)__ 。
(13)A. WWW
(14)A.21
D. Telnet
D.80
C. BBS
C.25
B. FTP
B.23
11、在网络地址 178.15.0.0 中划分出 10 个大小相同的子网,每个子网最多有___(15)___
个可用的主机地址。
A.2046
D.4096
B.2048
C.4094
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
15、Internet 中用于文件传输的是_(19)_。
A.DHCP 服务器
B.DNS 服务器
C.FTP 服务器
D.SNMP 和 POP3
D.路由器
16、代理服务器可以提供_(20)_功能。
A.信息转发
二、综合应用题(总分 55 分)
B.路由选择
C.域名解析
D.帧封装
1、制作交叉双绞线(一端按 EIA/TIA 568A 线序,另一端按 EIA/TIA 568B 线序)时,其
中一端的线序如图(a)所示,另一端线序如图(b)所示,将图(b)中(1)~(8)处空缺的颜色名
称填写出来(每空 2.5 分,20 分)。
2、某公司内部有一个采用 TCP/IP 作为传输协议的 100Base-TX 局域网,包括 1 台服务器和
20 台客户机,通过一台 16 端口的交换机与一台 8 端口共享集线器级连,其网络结构如下图
所示。服务器上运行 DHCP 服务软件,客户机的 IP 地址由 DHCP 服务程序自动分配。(15
分)
[问题 1]
连接主机 A 与交换机的单根网线的最大长度为多少? (5 分)
[问题 2]
该局域网中的集线器每个端口平均享有的带宽是多少? (5 分)
[问题 3]}
为了控制局域网用户访问 Internet 时只能进行 WWW 浏览,网管应该在路由器上采取什
么措施? (5 分)
3、某一网络地址块 192.168.75.0 中有 5 台主机 A、B、C、D 和 E,它们的 IP 地址及子网掩
码如下表所示。(20 分)
主机 IP 地址及子网掩码表
主机
IP 地址
子网掩码
A
B
C
D
E
192.168.75.18
255.255.255.240
192.168.75.146
255.255.255.240
192.168.75.158
255.255.255.240
192.168.75.161
255.255.255.240
192.168.75.173
255.255.255.240
【问题 1】(10 分)
5 台主机 A、B、C、D、E 分属几个网段?哪些主机位于同一网段?
【问题 2】(5 分)
主机 D 的网络地址为多少?
【问题 3】(5 分)
若要加入第六台主机 F,使它能与主机 A 属于同一网段,其 IP 地址范围是多少?