一、選擇題:( 共70 題，每題1 分， 滿分70 分。其中1-55 題爲中文題，56-70 題爲英文題) 。下列各題A)、B)、C)、D)四個選項中,只有一個是正確的,請將正確選項塗寫在答題卡相應位置上,答在試卷上不得分。
(1) 二進制數1011010 的十進制值是( )。
A)90 B)88 C)86 D)92
(2) 一般情況下，操作數右移1 位的結果是原操作數( )。
A)整除2 B)乘以2 C)整除4 D)乘以4
(3) 在下列敘述中，選擇一條正確的( )。
A)Cache 的功能全由軟件實現
B)Cache 的作用是擴大存儲器容量
C)硬磁盤在柱面上有多少個磁道，就有多少個讀寫磁頭
D)在流水線計算機中，當執行條件轉移指令或中斷程序時，會影響流水線的效率
(4) 設有兩個散列函數H1(K)=K mod 13 和H2(K)=K mod 11+1 ，散列表爲T[0…12] ，用二次散列法解決衝突。函數H1 用來計算散列地址， 當發生衝突時，H2 作爲計算下一個探測地址的地址增量。假定某一時刻散列表的狀態爲： 0 1 2 3 4 5 6 7 8 9 10 11 12 80 55 34 下一個插入的關鍵碼爲42，其插入位置應是( )。
A)0 B)1 C) 3 D)4
(5)下面是一段Pascal 程序：
for h:=1 to n-1 do begin
x:=A[h+1];
k:=h;
while (k>=1) and (A[k]>x) do begin
A[k+1]:=A[k];
k:=k-1
end;
A[k+1]:=x
end;
假設在程序開始執行時， 數組A[1… n]是一組隨機整數。下列答案中，哪一個最好地描述了最差情況下的程序執行時間(運行時間階數)?( )。
A)O(n log2n) B) O(n) C) O(log2n) D)O(n2)
(6)某二叉樹的後序序列爲 B,D,C,A,F,G,E, 對稱序序列爲A,B,C,D,E, F,G,則該二叉樹的前序序列爲( )。
A) E,G,F,A,C,D,B B)E,A,C,B,D,G,F
C)E,A,G,C,F,B,D D)E,G,A,C,D,F,B
(7) 設待排序的記錄爲(20，16，13，14，19)，經過下列過程將這些記錄排序，
20 16 13 14 19
16 20 13 14 19
13 16 20 14 19
12
13
14 16 20 19
13
14 16 19 20
所用的排序方法是：( )。
A)直接插入排序 B) 堆排序 C) 希爾排序 D) 二路歸併排序
(8) 若一棵二叉樹中只有葉結點和左右子樹皆非空的結點，設葉結點的個數爲k，則左右子樹皆非空的結點個數是( )。
A) 2k B) k-1 C) 2k -1 D) 2k-1
(9)設無向樹T有7片樹葉，其餘頂點度數均爲3， 則T中3度頂點有( )個。
A) 3 B) 4 C) 5 D) 6
(10)設R，N 分別表示實數、整數和自然數集，下面定義函數f1，f2，f3.：
f1：R→R，f(x)=2x，
f2：N→N×N，f(n)=，
f3：N→N，f(x)=(x)mod3，x 除以3 的餘數，
則下面說法正確的是( )。
A) f1和f2是單射但不是滿射函數;
B) f1和f3都是滿射函數
C)f2是雙射函數
D)以上說法全都是錯誤的
(11)公式(┐xF(x)∨yG(y)∧(F(u)→zH(z))的前束範式爲( )。
A) xyz((┐F(x)∨G(y))∧(F(u)→H(z))
B)xyz((┐F(x)∨G(y))∧(F(u)→H(z))
C)xyz((┐F(x)∨G(y))∧(F(x)→H(z))
D)xyz((┐F(x)∨G(y))∧(F(y)→H(z))
(12)有向圖G 如下所示，G中長度爲4 的通路共有多少條(包括迴路)?( )。
V4V5V3
V1
V2
有向圖G
A) 6 B) 12 C) 24 D) 32
(13)下面命題爲真的是( )。
Ⅰ設A={A1，A2，…An}是集合A 的劃分，若Ai∩B≠(1≤i≤n),則{{A1∩B，A2∩B，…An∩B }}是集合A 的劃分。
Ⅱ對任意的非空集合A，P(A)-{}也可構成A 的一個劃分。
A)只有Ⅰ B) 只有Ⅱ C) 都爲真 D) 都不爲真
(14)下面的無向圖中，能一筆畫成的是( )。
a b c
13
A) 只有a B) b 和c C) 只有c D) 沒有
(15)文件系統的主要目的是( )。
A)實現按名存取
B)實現虛擬存儲器
C)提高外部設備的輸入輸出設備
D)用於存儲系統文檔
(16)按邏輯結構劃分，文件主要分爲( )。
A) 系統文件、用戶文件 B)臨時文件、永久文件
C)流式文件、記錄文件 D)索引文件、順序文件
(17) 文件系統採用二級目錄結構的目的是( )。
A)縮短訪問文件存儲器的時間
B)實現文件共享
C)節省主存空間
D)解決不同用戶之間的文件名的衝突問題
(18) 堆棧存儲器存取數據的方式是：( )。
A)先進先出 B)隨機存取 C)先進後出 D)不同前三種方式
(19)若將DOS 提示符改成“MS-DOS5<”， 並在提示符前面加上日期及時間， 則使用下面哪一
條命令?( )。
A)PROMPT MS-DOS5$D$T$G B)PROMPT $D$TMS-DOS5$G
C)PROMPT $T$DMS-DOS5$L D)PROMPT $D$TMS-DOS5$L
(20)一個進程被喚醒意味着( )。
A)該進程重新佔有了CPU B)它的優先權變爲最大
C)其PCB 移至就緒隊列隊首 D)進程變爲就緒狀態
(21)在請求頁式存儲管理中，當查找的頁不在( )時，產生缺頁中斷。
A)內存 B)外存
C)虛存 D)地址空間
(22)下面所述步驟中，( )不是創建進程所必需的步驟?
