2019年全国硕士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题 （第1～ 40 小题，每小题 2分，共 80分。下列每题给出的四个选项中，
只有一个选项最符合试题要求）
1 ．设 n是描述问题规模的非负整数，下列程序段的时间复杂度是
。
x=0;
while (n>=(x+1)*(x+1))
x=x+1;
A ． O(log n) B． O(n 1/2
) C． O(n ) D． O(n 2
)
2 ．若将一棵树 T转化为对应的二叉树 BT，则下列对 BT的遍历中，其遍历序列与 T的后
I．若 v是 T
1的叶结点，则
T
1与
T
3可能不相同
II ．若 v不是 T
1的叶结点，则
T
1与
T
3一定不相同
III ．若 v不是 T
1的叶结点，则
T
1与
T
3一定相同
A ．仅 I B．仅 II C．仅 I、 II D．仅 I、 III
5 ．下图所示的 AOE网表示一项包含 8个活动的工程。活动 d的最早开始时间和最迟开始
时间分别是
。
A ． 3和 7 B． 12 和12 C． 12 和14 D． 15 和 15
6 ．用有向无环图描述表达式
( )(( ) / ) x y x y x ，需要的顶点个数至少是 。
A ． 5 B． 6 C． 8 D． 9
7 ．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是
。
I ．数据的规模 II．数据的存储方式 III．算法的稳定性 IV．数据的初始状态
A ．仅 III B．仅 I、 II
C ．仅 II、 III、 IV D． I、 II、 III、IV
根遍历序列相同的是 。
A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历
3 ．对 n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115个结点，则 n的值
是 。 A． 56 B． 57 C． 58 D． 60
4 ．在任意一棵非空平衡二叉树（ AVL树）T
1中，删除某结点
v之后形成平衡二叉树 T
2，
再将 v插入 T
2形成平衡二叉树
T
3。下列关于
T
1与
T
3的叙述中，正确的是 。
· ·
8
．
现有长度为 11且初始为空的散列表 HT，散列函数是 H(key) = key % 7 ，采用线性探查
（线性探测再散列）法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20依次插入HT后， HT
查找失败的平均查找长度是
。
A ． 4 B． 5.25 C． 6 D． 6.29
9 ．设主串 T = "abaabaabcabaabc" ，模式串S = "abaabc" ，采用KMP算法进行模式匹配，到
匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是
。
A ． 9 B． 10 C． 12 D． 15
10 ．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列
中，不 ．可能是快速排序第二趟结果的是
。
A ． 5, 2, 16, 12, 28, 60, 32, 72 B． 2, 16, 5, 28, 12, 60, 32, 72
C ． 2, 12, 16, 5, 28, 32, 72, 60 D． 5, 2, 12, 28, 16, 32, 72, 60
11 ．设外存上有 120个初始归并段，进行 12路归并时，为实现最佳归并，需要补充的虚段
个数是
。 D． 4
。
unsigned short usi = 65535;
short si = usi;
执行上述程序段后， si的值是
。
A ．- 1 B．- 32767 C．- 32768 D．- 65535
14 ．下列关于缺页处理的叙述中，错误的是
。
A ．缺页是在地址转换时 CPU检测到的一种异常
B ．缺页处理由操作系统提供的缺页处理程序来完成
C ．缺页处理程序根据页故障地址从外存读入所缺失的页
D ．缺页处理完成后回到发生缺页的指令的下一条指令执行
15 ．某计算机采用大端方式，按字节编址。某指令中操作数的机器数为 1234 FF00H，该操
作数采用基址寻址方式，形式地址（用补码表示）为 FF12H，基址寄存器的内容为 F000 0000H，
则该操作数的 LSB（最低有效字节）所在的地址是
。
A ． F000 FF12H B ．F000 FF15H C ．EFFF FF12H D ．EFFF FF15H
16 ．下列有关处理器时钟脉冲信号的叙述中，错误的是
。
A ．时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
B ．时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频
C ．时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定
D ．处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
17 ．某指令功能为 R[r2]←R[r1] + M[R[r0]] ，其两个源操作数分别采用寄存器、寄存器间接
寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是
。
I ．通用寄存器组（ GPRs） II．算术逻辑单元（ ALU）
A． 1 B． 2 C． 3
12 ．下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是
A ．程序的功能都通过中央处理器执行指令实现
B ．指令和数据都用二进制数表示，形式上无差别
C ．指令按地址访问，数据都在指令中直接给出
D ．程序执行前，指令和数据需预先存放在存储器中
13 ．考虑以下 C语言代码：
· ·
III ．存储器（ Memory） IV．指令译码器（ ID）
A ．仅 I、 II B．仅 I、 II、 III C ．仅II、 III、 IV D ．仅I、 III、IV
18 ．在采用“取指、译码/取数、执行、访存、写回” 5段流水线的处理器中，执行如下指
令序列，其中 s0、 s1、 s2、 s3 和 t2表示寄存器编号。
I1：add s2,s1,s0 //R[s2]
R[s1]+R[s0]
I2：load s3,0(t2) //R[s3]
M[R[t2]+0]
I3：add s2,s2,s3 //R[s2]
R[s2]+R[s3]
I4：store s2,0(t2) //M[R[t2]+0
2019年计算机408统考真题.pdf
