2019 年云南昆明理工大学计算机学科基础综合考研真题 A
卷
数据结构 部分:
一、 选择题:(40分,每题2分)
1.已知10个数据元素(54,28,16,34,73,62,95,60,26,43),按照依次插入结点
的方法生成一棵二叉排序树后,则查找值为62的结点所需比较的次数是[
]。
A. 2
B. 3
C. 4
D. 5
2.在一棵完全二叉树中,若编号为 j 的结点有右孩子,则该结点的编号为[
] 。
A. 2*j-1
B. 2*j
C. 2*j+1
D. j/2
3.在线性表的存储结构中,[
]查找(按关键字查找)、插入、删除速度慢,但顺序存
取和随机存取第i个元素速度快;[
]查找和存取速度快,但插入、删除速度慢;[
]
查找、插入和删除速度快,但不能进行顺序存取;[
]插入、删除和顺序存取速度快;但
查找速度慢。
A. 顺序有序表,散列表,顺序表,链接表 B. 顺序有序表,链接表,散列表,顺
序表
列表
C. 顺序表,顺序有序表,散列表,链接表 D. 顺序表,顺序有序表,链接表,散
4.由分别带权为9,2,5,7的四个叶结点构造一棵哈夫曼树,则该树的带权路径长度是
[
]。
A. 23
B.37
C. 44
D. 46
5.如果已知一个栈的入栈序列是:1,2,3,...,n,其出栈序列是:p1,p2,p3,...,
pn,若p1=n,则pi为 [
]
A.i
B.n+i
C.n-i
D.n-i+1
6.已知8个数据元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成
一棵二叉排序树,则最后两层上的结点总数是[
]。
A. 1
B. 2
C. 3
D. 4
7.对线性表进行二分查找时,要求线性表必须是[
]。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储,且数据元素有序 D.以链接方式存储,且数据元素有序
8.一个中缀算术表达式a+(b-x)*y,则对应的后缀算术表达式为[
]。
A. a
C. a
b
b
x
x
y
-
- *
y *
+;
+;
B. a
D. a
b
b
x
x
-
y
+ y
* -
*;
+;
9.已知一个有序表为(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
10.以下的叙述中,正确的是 : [
]
A.线性表的顺序存储结构优于链式存储结构。
B.栈的操作方式是先进先出。
C.二维数组是它的数据元素为线性表的线性表。 D.队列的操作方式是先进后出。
11.线性表是( )。
A.一个有限序列,可以为空
B.一个有限序列,不能为空
C.一个无限序列,可以为空
D.一个无限序列,不能为空
12.在无权图G的邻接矩阵A中,如果(vi,vj) 属于图G的边集合(其中vi,vj表示图的顶点),
则对应的元素A[i][j] 的值应该是 [
]
A.0
B.1
C.2
D.3
13.由分别带权为9,2,5,7的四个叶结点构造一棵哈夫曼树,则该树的带权路径长度是
[
]。
A. 23
B.37
C. 44
D. 46
14.已知一个图的邻接矩阵表示,计算第i个结点的入度的方法是 [
]
A.求矩阵第i行非零元素之和
B.求矩阵第i列非零元素之和
C.求矩阵第i行第i列元素之值 D.求矩阵非零元素第i行之和与第i列之和的差的
绝对值
15.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂度
[
]
A. O(1)
B. O(n)
C. O(n)/2
D. O(p*n)
16.栈结构一般采用的两种存储结构是:
[
]
A.线性存储结构和非线性存储结构
B.顺序存储结构和链表存储结构
C.散列方式和索引方式
D.链表存储结构和树形存储结构
17.在一个无向图中,所有顶点的度数之和等于所有边数的[
]倍。
A. 1/2
B. 1
C. 2
D. 4
18.在一个具有n个顶点的无向图中,要连通全部顶点至少需要[
]条边。
A. n
B. n+1
C. n-1
D. n/2
19.链式存储结构与顺序存储结构相比,下列哪一条是链式存储结构的缺点 [
]
A. 可实现动态分配 B.不需要一组地址连续的存储单元
C. 插入、删除时不用移动大量元素 D.不是可随机存取的结构
20.从未排序序列中依次取出元素与已排序序列中的元素作比较,将其放入已排序序列中的
正确位置上,此方法称为[
];从未排序序列中挑选元素,并将其放入已排序序列的另
一端,此方法称为[
];依次将每两个相邻的有序表合并成一个有序表的排序方法叫做
[
];当两个元素比较出现反序(即逆序)时就相互交换位置的排序方法叫做 [
]。
A. 归并排序,交换排序,选择排序,插入排序
B. 选择排序,插入排序,归并排序,交换排序
C. 交换排序,选择排序,插入排序,归并排序
D. 插入排序, 选择排序,归并排序,交换排序
二、判断题:(10 分,每题 1 分)
1.满二叉树也是完全二叉树。( )
2.二分查找要求所有记录按关键字排序。( )
3.直接插入排序是不稳定的。( )
4.线性表中所有结点的类型必须相同。( )
5.用树的前序遍历和中序遍历可以导出树的后序遍历;(
)
6.中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 ( )
7.若待排序的记录数目较小,可采用直接插入排序或直接选择排序。( )
8.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所
得的输出序列也一定相同; ( )
9.稀疏矩阵中值为0的元素分布有规律,因此可以采用三元组方法进行压缩存储。( )
10.树中所有结点都有双亲结点。( )
三、简答题(共 25 分)
1.已知用于通讯的电文由 7 个字母组成,其字母的出现的频度权值 W={6,8,2,4,9,15,19},
请构造出这组权值的哈夫曼树,并为这 7 个字母设计哈夫曼编码。(8 分)
2. 在顺序存储的线性表 A[30]上进行二分查找的平均查找长度是多少(要求计算过程)?
(7 分)
3.在运用计算机解决实际问题时,合理的存储结构设计应考虑哪些方面的因素?举例说明
为什么?(10 分)
网络 部分:
一、单项选择题(每小题 2 分,共 30 分)
1. 以下属于物理层的设备是( )。
A. 中继器 B. 以太网交换机 C. 桥 D. 网关
2.下面哪种 LAN 是应用 CSMA/CD 协议的 ( )。
A.令牌环
B.
FDDI
C.
ETHERNET D.
NOVELL
3.应用程序 PING 发出的是( )报文。
A.TCP 请求报文
B.TCP 应答报文 C.ICMP 请求报文 D.ICMP 应答报文
4. ARP 协议的作用是 ( )。
A.将端口号映射到 IP 地址 B.连接 IP 层和 TCP 层
C.广播 IP 地址
D.将 IP 地址映射到 MAC 地址
5. 路由选择协议位于( .)。
A. 物理层
B. 数据链路层
C. 网络层
D. 应用层
6. 255.255.255.224 可能代表的是( )。
A. 一个 B 类网络号 B. 一个 C 类网络中的广播
C. 一个具有子网的网络掩码 D. 以上都不是
7. IP 地址为 140.111.0.0 的 B 类网络,若要切割为 9 个子网,而且都要连上 Internet,
请问子网掩码设为( )。
A.255.0.0.0
B. 255.255.0.0
C. 255.255.128.0
D. 255.255.240.0
8. 相邻层间交换的数据单元称之为服务数据单元,其英文缩写为( )。
A. SDU
B.IDU
C. PDU
D . ICI
9. 在 IP 地址方案中,159.226.181.1 是一个( )。
A. A 类地址 B. B 类地址
C. C 类地址
D. D 类地址
10. 以下属于广域网技术的是( )。
A. 以太网 B. 令牌环网 C. 帧中继 D. FDDI
11. TCP 的协议数据单元被称为( )。
A. 比特
B. 帧
C. 分段
D. 字符
12. 世界上第一个计算机网络是 ( )。
A. ARPANET
B. ChinaNet
C.Internet
D.CERNET
13. 一般来说,用户上网要通过因特网服务提供商,其英文缩写为(
)。
A.IDC
B.ICP
C.ASP
D.ISP
14. PPP 协议是哪一层的协议(
)。
A.物理层 B.数据链路层 C.网络层 D.高层
15. TCP/IP 协议规定为( )。
A、 4 层
B、 5 层 C、 6 层
D、7 层
二、综合题(每小题 9 分,共 45 分)
1.简述 CSMA/CD 的工作原理。
2.简述 VPN 的工作原理。
3.简述路由器分组转发的过程。
4.简述 IP 地址与 MAC 地址的联系与区别。
5. 某公司使用 192.168.25.0 一个标准 C 类网络。请使用子网划分技术划分成 6 个子网,
给出子网划分方案,并给出每个子网的 IP 地址范围和子网掩码。