2018 年全国硕士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中， 只有一个选项最符合试题要求。
1.若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F()依次执行下述各步操作：
（1）从 S1 中依次弹出两个操作数 a 和 b；
（2）从 S2 中弹出一个运算符 op；
（3）执行相应的运算 b op a；
（4）将运算结果压人 S1 中。
假定 S1 中的操作数依次是 5, 8, 3, 2（2 在栈顶），S2 中的运算符依次是*, - , +（+在栈顶）。调用 3 次 F()后，S1 栈顶保存的值是 。
A. -15 B. 15 C. -20 D. 20
2.现有队列 Q 与栈 S，初始时 Q 中的元素依次是 1, 2, 3, 4, 5, 6（1 在队头），S 为空。若仅允许下列 3 种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素， 则不能得到的输出序列是 。
A. 1, 2, 5, 6, 4, 3 B. 2, 3, 4, 5, 6, 1
C. 3, 4, 5, 6, 1, 2 D. 6, 5, 4, 3, 2, 1
3.设有一个 12×12 的对称矩阵 M，将其上三角部分的元素 mi, j（1≤i≤j≤12）按行优先存人 C
语言的一维数组 N 中，元素 m6, 6 在 N 中的下标是 。
A. 50 B. 51 C. 55 D. 66
4.设一棵非空完全二叉树 T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是 。
A. 2k-1 B. 2k C. k2 D. 2k-1
5.已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为 6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是 。
A. 00, 1011, 01, 1010, 11, 100 B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010 D. 0011, 10, 11, 0010, 01, 000
6.已知二叉排序树如下图所示，元素之间应满足的大小关系是 。
A. x1<x2<x5 B. x1<x4<x5 C. x3<x5<x4 D. x4<x3<x5
7.
下列选项中，不是如下有向图的拓扑序列的是 。 A. 1, 5, 2, 3, 6, 4 B. 5, 1, 2, 6, 3, 4
C. 5, 1, 2, 3, 6, 4 D. 5, 2, 1, 6, 3, 4
8.高度为 5 的 3 阶 B 树含有的关键字个数至少是 。
A. 15 B. 31 C. 62 D. 242
9.现有长度为 7、初始为空的散列表 HT，散列函数 H(k) = k % 7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插人到 HT 后，查找成功的平均查找长度是 。
A. 1.5 B. 1.6 C. 2 D. 3
10. 对初始数据序列（8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6）进行希尔排序。若第一趟排序结果为
（1,
3, 7, 5, 2, 6, 4, 9, 11, 10, 8），第二趟排序结果为（1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9），则两趟排序采用的增量（间隔）依次是 。
A. 3, 1 B. 3,2 C. 5,2 D. 5,3
11.在将数据序列（6, 1, 5, 9, 8, 4, 7)建成大根堆时，正确的序列变化过程是 。A. 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
B. 6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
C. 6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
D. 6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5 → 9,8,6,1,7,4,5
12.冯•诺依曼结构计算机中数据采用二进制编码表示，其主要原因是 。Ⅰ.二进制的运算规则简单
Ⅱ.制造两个稳态的物理器件较容易Ⅲ.便于用逻辑门电路实现算术运算
A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ C. 仅Ⅱ、Ⅲ D.Ⅰ、Ⅱ和Ⅲ
13.假定带符号整数采用补码表示，若 int 型变量x 和y 的机器数分别是FFFF FFDFH 和 0000 0041H，则 x、y 的值以及 x - y 的机器数分别是 。
A.x = -65, y = 41, x -y 的机器数溢出
B.x = -33, y = 65, x-y 的机器数为 FFFF FF9DH
C.x = -33, y = 65, x-y 的机器数为 FFFF FF9EH
D.x = -65, y = 41, x-y 的机器数为 FFFF FF96H
14.IEEE 754 单精度浮点格式表示的数中，最小的规格化正数是 。
A. 1.0×2 -126 B. 1.0×2 -127 C. 1.0×2 -128 D. 1.0×2 -149
15.某 32 位计算机按字节编址，采用小端(Little Endian)方式。若语令“int i = 0;”对应指令的
机器代码为“C7 45 FC 00 00 00 00”，则语句“int i = - 64;”对应指令的机器代码是 。
A. C7 45 FC C0 FF FF FF B. C7 45 FC 0C FF FF FF
C. C7 45 FC FF FF FF C0 D. C7 45 FC FF FF FF 0C
16.整数 x 的机器数为 1101 1000，分别对 x 进行逻辑右移 1 位和算术右移 1 位操作，得到的机器数各是 。
A. 1110 1100、1110 1100 B. 0110 1100、1110 1100
C. 1110 1100、0110 1100 D. 0110 1100 、 0110 1100
17.假定 DRAM 芯片中存储阵列的行数为 r、列数为 c，对于一个 2K×1 位的 DRAM 芯片， 为保证其地址引脚数最少，并尽量减少刷新开销，则 r、c 的取值分别是 。
A. 2048、1 B. 64、32 C. 32、64 D. 1、2048
18.按字节编址的计算机中，某 double 型数组 A 的首地址为 2000H，使用变址寻址和循环
结构访问数组 A，保存数组下标的变址寄存器初值为 0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是 。
A. 25 B. 32 C. 64 D. 100
19.减法指令“sub R1, R2, R3”的功能为“（R1）-（R2）→ R3”，该指令执行后将生成进位/借位标志 CF 和溢出标志 OF。若（R1）= FFFF FFFFH，（R2）= FFFF FFF0H，则该减法指令执行后，CF 与 OF 分别为 。
