2017年考研计算机统考408真题
一、单项选择题
1下列函数的时间复杂度就是1。
i
tfu
ci
t

i
ti0sum0
whilesum
sumi
retur
i

AOlog

BO
12
CO

DO
log

2下列关于栈的叙述中错误的就是2。
I、采用非递归方式重写递归程序时必须使用栈
II、函数调用时系统要用栈保存必要的信息
III、只要确定了入栈的次序即可确定出栈次序
IV、栈就是一种受限的线性表允许在其两端进行操作
A仅I
B仅I、II、III
C仅I、III、IV
D仅II、III、IV
3适用于压缩存储稀疏矩阵的两种存储结构就是3。
A三元组表与十字链表
B三元组表与邻接矩阵
C十字链表与二叉链表
D邻接矩阵与十字链表
4要使一棵非空二叉树的先序序列与中序序列相同其所有非叶结点须满足的条件就
是
4。
A只有左子树
B只有右子树
C结点的度均为1
D结点的度均为2
5已知一棵二叉树的树形如下图所示其后序序列为eacbdgf树中与结点a同层的
结点就是5。
AcBd
fCf
Dg
6已知字符集abcdefgh若各字符的哈夫曼编码依次就是
01001000000101001011110001则编码序列的译码结果就是6。
Aacgabfh
Badbagbb
Cafbeagd
Dafeefgd
7已知无向图G含有16条边其中度为4的顶点个数为3度为3的顶点个数为4其她
顶点的度均小于3。图G所含的顶点个数至少就是7。
A10
B11
C13
D15
8下列二叉树中可能成为折半查找判定树不含外部结点的就是
8。
A
B
C
D9下列应用中适合使用B树的就是
9。
fA编译器中的词法分析
B关系数据库系统中的索引
C网络中的路由表快速查找
D操作系统的磁盘空闲块管理
10在内部排序中若选择了归并排序而没有选择插入排序则可能的理由就是
10
。
I、归并排序的程序代码更短
II、归并排序的占用空间更少
III、归并排序的运行效率更高
A仅II
B仅III
C仅I、II
D仅I、III
11下列排序方法中若将顺序存储更换为链式存储则算法的时间效果会降低的就是
11。
I、插入排序
II、选择排序
III、起泡排序
IV、希尔排序
V、堆排序
A仅I、II
B仅II、III
C仅III、IV
D仅IV、V
12假定计算机M1与M2具有相同的指令集体系结构ISA主频分别为1、5GHz与1、
2GHz。在M1与M2上运行某基准程序P平均CPI分别为2与1则程序P在M1与
M2上运行时间的比值就是12。
A0、4
B0、625
C1、6
D2、5
13某计算机主存按字节编址由4个64M8位的DRAM芯片采用交叉编址方式构成
并与宽度为32位的存储器总线相连主存每次最多读写32位数r