2017年考研计算机统考408真题.docx

2017年考研计算机统考一、单项选择题

408真题

下列函数的时间复杂度是 1 。

intfunc(intn)

{inti=0;sum=0;

while(sumn)sum+=++i;returni;

}

O(logn)

B. O(n1/2 )

O(n)

O(nlogn)

下列关于栈的叙述中，错误的是 2 。

I.采用非递归方式重写递归程序时必须使用栈II.函数调用时，系统要用栈保存必要的信息III.只要确定了入栈的次序，即可确定出栈次序

IV.栈是一种受限的线性表，允许在其两端进行操作

仅I

仅I、II、III

仅I、III、IV

仅II、III、IV

适用于压缩存储稀疏矩阵的两种存储结构是 3 。

三元组表和十字链表

三元组表和邻接矩阵

十字链表和二叉链表

邻接矩阵和十字链表

要使一棵非空二叉树的先序序列与中序序列相同，

其所有非叶结点须满足的条件是

4 。

只有左子树

只有右子树

结点的度均为1

结点的度均为2

已知一棵二叉树的树形如下图所示，其后序序列为 e,a,c,b,d,g,f，树中与结点 a同层

的结点是 5 。

c

d

f

g

已知字 符 集{a,b,c,d,e,f,g,h} ， 若各 字符的 哈 夫曼 编 码依 次 是

0100,10,0000,0101,001,011,11,0001 ，则编码序列0100011001001011110101 的译码结

果是6。

acgabfh

adbagbb

afbeagd

afeefgd

已知无向图G含有16条边，其中度为4的顶点个数为 3，度为3的顶点个数为 4，其他顶点的度均小于 3。图G所含的顶点个数至少是 7 。

10

11

13

15

下列二叉树中，可能成为折半查找判定树（不含外部结点）的是 8。

A.

B.

C.

D.

下列应用中，适合使用 B+树的是 9 。

编译器中的词法分析

关系数据库系统中的索引

网络中的路由表快速查找

操作系统的磁盘空闲块管理

在内部排序中，若选择了归并排序而没有选择插入排序，则可能的理由是 10

。

仅II

仅III

仅I、II

仅I、III

下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效果会降低的是

11 。I.插入排序II.选择排序III.起泡排序IV.希尔排序V.堆排序

仅I、II

仅II、III

仅III、IV

仅IV、V

假定计算机

M1和M2 具有相同的指令集体系结构（

ISA），主频分别为 1.5GHz 和

1.2GHz。在M1和M2

上运行某基准程序

P，平均CPI分别为2和1，则程序P在

M1和M2 上运行时间的比值是12 。

A. 0.4

B. 0.625

C. 1.6

D. 2.5

某计算机主存按字节编址， 由4个64M*8 位的DRAM芯片采用交叉编址方式构成，

并与宽度为 32位的存储器总线相连，主存每次最多读写32 位数据。若 double型

变量x的主存地址为

804001AH，则读取x需要的存储周期是

13 。

1

2

3

4

某C语言程序段如下：

for(i=0;i=9;i++)

{ lemp=1;

for(j0;j=I;j++)temp*=a[j];sum+=temp;

}

下列关于数组a的访问局部性的描述中，正确的是

14 。

时间局部性和空间局部性皆有

无时间局部性，有空间局部性

有时间局部性，无空间局部性

时间局部性和空间局部性皆无

下列寻址方式中，最适合按下标顺序访问一维数组元素的是

15 。

相对寻址

寄存器寻址

直接寻址

变址寻址

某计算机按字节编址， 指令字长固定且只有两种指令格式， 其中三地址指令29条，二地址指令 107条，每个地址字段为 6位，则指令字长至少应该是 16 。

24位

26位

28位

32位

下列关于超标量流水线特性的叙述中，正确的是 16 。

仅II

仅I、III

仅II、III

I、II和III

下列关于主存储器（MM）和控制存储器（CS）的叙述中，错误的是

。

MM在CPU外，CS在CPU内

MM按地址访问，CS按内存访问

MM存储指令和数据，CS存储微指令

MM用RAM和ROM实现，CS用ROM实现

下列关于指令流水线数据通路的叙述中，错误的是

。

包含生成控制信号的控制部件

包含算法逻辑运算部件（ ALU）

包含通用寄存器组和取指部件

由组