2017年考研计算机统考408真题一、单项选择题
1下列函数的时间复杂度是1。i
tfu
ci
t
i
ti0sum0whilesum
sumiretur
iAOlog
BO
12CO
DO
log
2下列关于栈的叙述中，错误的是2。I采用非递归方式重写递归程序时必须使用栈II函数调用时，系统要用栈保存必要的信息III只要确定了入栈的次序，即可确定出栈次序IV栈是一种受限的线性表，允许在其两端进行操作A仅IB仅I、II、IIIC仅I、III、IVD仅II、III、IV
3适用于压缩存储稀疏矩阵的两种存储结构是3。A三元组表和十字链表B三元组表和邻接矩阵C十字链表和二叉链表D邻接矩阵和十字链表
4要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是4。
A只有左子树B只有右子树C结点的度均为1D结点的度均为25已知一棵二叉树的树形如下图所示，其后序序列为eacbdgf，树中与结点a同层的结点是5。
AcBd
fCfDg6已知字符集abcdefgh，若各字符的哈夫曼编码依次是01001000000101001011110001，则编码序列0100011001001011110101的译码结果是6。AacgabfhBadbagbbCafbeagdDafeefgd7已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是7。A10B11C13D158下列二叉树中，可能成为折半查找判定树（不含外部结点）的是8。
A
B
C
D
f9下列应用中，适合使用B树的是9。
A编译器中的词法分析
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），主频分别为15GHz和
12GHz。在M1和M2上运行某基准程序P，平均CPI分别为2和1，则程序P在
M1和M2上运行时间的比值是12。
A04
B0625
C16
D25
13某计算机主存按字节编址，由4个64M8位的DRAM芯片采用交叉编址方式构成，
并与宽度为32位的存储器总线相连，主存每次最多读写32位数据。若double型
变量x的主存地址为804r