2018 年全國碩士研究生入學統(tǒng)一考試
計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題
一、單項選擇題：第 1～40 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中， 只有一個選項最符合試題要求。
1.若棧 S1 中保存整數(shù)，棧 S2 中保存運算符，函數(shù) F()依次執(zhí)行下述各步操作：
（1）從 S1 中依次彈出兩個操作數(shù) a 和 b；
（2）從 S2 中彈出一個運算符 op；
（3）執(zhí)行相應的運算 b op a；
（4）將運算結(jié)果壓人 S1 中。
假定 S1 中的操作數(shù)依次是 5, 8, 3, 2（2 在棧頂），S2 中的運算符依次是*, - , +（+在棧頂）。調(diào)用 3 次 F()后，S1 棧頂保存的值是 。
A. -15 B. 15 C. -20 D. 20
2.現(xiàn)有隊列 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）按行優(yōu)先存人 C
語言的一維數(shù)組 N 中，元素 m6, 6 在 N 中的下標是 。
A. 50 B. 51 C. 55 D. 66
4.設一棵非空完全二叉樹 T 的所有葉結(jié)點均位于同一層，且每個非葉結(jié)點都有 2 個子結(jié)點。若 T 有 k 個葉結(jié)點，則 T 的結(jié)點總數(shù)是 。
A. 2k-1 B. 2k C. k2 D. 2k-1
5.已知字符集{a, b, c, d, e, f}，若各字符出現(xiàn)的次數(shù)分別為 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 樹含有的關鍵字個數(shù)至少是 。
A. 15 B. 31 C. 62 D. 242
9.現(xiàn)有長度為 7、初始為空的散列表 HT，散列函數(shù) H(k) = k % 7，用線性探測再散列法解決沖突。將關鍵字 22, 43, 15 依次插人到 HT 后，查找成功的平均查找長度是 。
A. 1.5 B. 1.6 C. 2 D. 3
10. 對初始數(shù)據(jù)序列（8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6）進行希爾排序。若第一趟排序結(jié)果為
（1,
3, 7, 5, 2, 6, 4, 9, 11, 10, 8），第二趟排序結(jié)果為（1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9），則兩趟排序采用的增量（間隔）依次是 。
A. 3, 1 B. 3,2 C. 5,2 D. 5,3
11.在將數(shù)據(jù)序列（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.馮?諾依曼結(jié)構(gòu)計算機中數(shù)據(jù)采用二進制編碼表示，其主要原因是 。Ⅰ.二進制的運算規(guī)則簡單
Ⅱ.制造兩個穩(wěn)態(tài)的物理器件較容易Ⅲ.便于用邏輯門電路實現(xiàn)算術運算
A. 僅Ⅰ、Ⅱ B. 僅Ⅰ、Ⅲ C. 僅Ⅱ、Ⅲ D.Ⅰ、Ⅱ和Ⅲ
13.假定帶符號整數(shù)采用補碼表示，若 int 型變量x 和y 的機器數(shù)分別是FFFF FFDFH 和 0000 0041H，則 x、y 的值以及 x - y 的機器數(shù)分別是 。
A.x = -65, y = 41, x -y 的機器數(shù)溢出
B.x = -33, y = 65, x-y 的機器數(shù)為 FFFF FF9DH
C.x = -33, y = 65, x-y 的機器數(shù)為 FFFF FF9EH
D.x = -65, y = 41, x-y 的機器數(shù)為 FFFF FF96H
14.IEEE 754 單精度浮點格式表示的數(shù)中，最小的規(guī)格化正數(shù)是 。
A. 1.0×2 -126 B. 1.0×2 -127 C. 1.0×2 -128 D. 1.0×2 -149
15.某 32 位計算機按字節(jié)編址，采用小端(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.整數(shù) x 的機器數(shù)為 1101 1000，分別對 x 進行邏輯右移 1 位和算術右移 1 位操作，得到的機器數(shù)各是 。
A. 1110 1100、1110 1100 B. 0110 1100、1110 1100
C. 1110 1100、0110 1100 D. 0110 1100 、 0110 1100
17.假定 DRAM 芯片中存儲陣列的行數(shù)為 r、列數(shù)為 c，對于一個 2K×1 位的 DRAM 芯片， 為保證其地址引腳數(shù)最少，并盡量減少刷新開銷，則 r、c 的取值分別是 。
A. 2048、1 B. 64、32 C. 32、64 D. 1、2048
18.按字節(jié)編址的計算機中，某 double 型數(shù)組 A 的首地址為 2000H，使用變址尋址和循環(huán)
結(jié)構(gòu)訪問數(shù)組 A，保存數(shù)組下標的變址寄存器初值為 0，每次循環(huán)取一個數(shù)組元素，其偏移地址為變址值乘以sizeof(double)，取完后變址寄存器內(nèi)容自動加1。若某次循環(huán)所取元素的地址為2100H，則進入該次循環(huán)時變址寄存器的內(nèi)容是 。
A. 25 B. 32 C. 64 D. 100
19.減法指令“sub R1, R2, R3”的功能為“（R1）-（R2）→ R3”，該指令執(zhí)行后將生成進位/借位標志 CF 和溢出標志 OF。若（R1）= FFFF FFFFH，（R2）= FFFF FFF0H，則該減法指令執(zhí)行后，CF 與 OF 分別為 。
