一、選擇題：( 共70 題，每題1 分，滿分70 分。其中1-55 題為中文題，56-70 題為英文題)。 下列各題A)、B)、C)、D)四個選項中,只有一個是正確的,請將正確選項塗寫在答題卡相應位置上,答在試卷上不得分。
(1)若一個子程式起始地址為3K，呼叫指令CALL 的記憶體地址為K+1，則執行CALL 指令所要執行指令的地址為( )。
A) 3K
B) 3K+1
C) 3K-1
D) K+2
(2)若邏輯變數X=0,Y=1,則執行按位加XY 以後的值為( )。
A) 1
B) 0
C) 10
D) 2
(3)一般情況下，運算元左移3 位的結果是原運算元( )。
A) 整除8
B) 乘以8
C) 整除4
D) 乘以4
(4) 設用一維陣列A[1… n]來儲存一個棧， 令A[n] 為棧底，用整型變數T 指示當前棧頂位置，A[T]為棧頂元素。當從棧中彈出一個元素時，變數T 的變化為( )。
A) T:=T+1
B) T:=T-1
C) T 不變
D) T:=n
(5)在排序方法中，關鍵碼比較次數與記錄的初始排列無關的是( )。
A)Shell 排序
B)歸併排序
C) 直接插入排序
D)選擇排序
(6) 對一棵非空的二叉樹(設第0 層為根結點)，那麼其第i 層上至多有多少個結點( )。
A) i
B) 2i-1
C) 2i+1
D) 2i
(7)對下列四個序列用快速排序方法進行排序，以序列的第一個元素為劃分的基準。在第一趟劃分過程中，元素的移動次數最多的是哪一個序列?( )。
A) 70，75，68，23，10，16，90，82
B) 82，75，70，16，10，90，68，23
C) 70，75，82，90，23，16，10，68
D) 23，10，16，70，82，75，68，90
(8) 陣列Q[0，n-1]作為一個環形佇列，f 為當前隊頭元素的前一位置，r為隊尾元素的位置，假定佇列中元素的個數總小於n，佇列中元素的個數是什麼?( )。
A)r-f
B)n+f-r
C)n+r-f
D)(n+r-f)mod n
(9)A={x|x<100 且為質數}，在A 上定義*和·如下：x*y=max(x,y)， x·y=LCM(x,y)，x,y∈A， 這裡LCM(x, y)表示x 與y 的最小公 倍數，則下面命題正確的是：( )。
Ⅰ 構成代數系統;
Ⅱ 構成代數系統;
A)只有Ⅰ
B) 只有Ⅱ
C) Ⅰ和Ⅱ
D)沒有
(10)設V ′和E′分別為無向連通圖G 的點割集和邊割集，下面的說法中正確的是( )。
Ⅰ.G-E′的連通分支數p(G-E′)=2。
Ⅱ. G-V′的連通分支數p(G-V′)一定等於G-E′的連通分支數 p(G-E′)。
Ⅲ. G-V′的連通分支數p(G-V′)≥2。
A) Ⅰ和Ⅱ
B) Ⅰ和Ⅲ
C) Ⅱ
D)沒有
(11)設R，S 是集合A 上的二元關係，則下面命題是真命題的是( )。
A) 若R，S 是自反的，則R·S 是自反的
B) 若R，S 是反自反的，則R·S 是反自反的
C) 若R，S 是對稱的，則R·S 是對稱的
D) 若R，S 是傳遞的，則R·S 是傳遞的
(12)下面的謂詞公式是有效式的是( )。
Ⅰ(x)(y)p(x,y) (y)(x)p(x,y)
Ⅱ┐(x)(p(x)→(y)q(y))∧(y)q(y)
Ⅲ (x)(p(x)∨q(x))→((x)p(x)∨(y)q(y)
A)Ⅰ和Ⅱ
B)只有Ⅱ
C)只有Ⅲ
D)只有Ⅰ
(13)下面的符號集合中，是字首碼的是( )。其中B1={0,10,110,1111}、B2={1,01,001,000}、B3={1,11,101,001,0011}、B4={b,c,aa,ac,aba,abb,abc}
A) B1 和B2
B) B2 和B3
C) B1、B2和B4
D) B1、B2和B3
(14)下面命題的判斷正確的是( )。
Ⅰ 完全圖Kn(n≥1)都是哈密爾頓圖;
Ⅱ 完全二部圖Kn,m(n≥1,m≥1)都是尤拉圖;
Ⅲ 任何平面圖G 的對偶圖G*的對偶圖G**與G 同構。
A) 只有Ⅰ和Ⅱ為真
B) 只有Ⅲ為真
C) 只有Ⅱ為假
D)全為假
(15)已經獲得除( )以外的所有執行所需資源的程序處於就緒狀態。
A)儲存器 B)CPU C)外設 D)磁碟空間
(16) 在儲存分配的策略中，( ) 是程式設計師在程式設計時或者編譯程式對源程式編譯時直接指定儲存區。
A)直接分配 B)間接分配 C)靜態分配 D)動態分配
(17)作業系統的作用是( )。
A) 把源程式編譯為目標程式
B) 便於進行目標管理
C) 控制和管理系統資源的使用
D) 實現軟硬體的轉接
(18)程序排程的關鍵問題是選擇合理的( )和進行恰當的程式碼轉換。
A)時間片間隔 B)排程演算法 C)CPU 速度 D)記憶體空間
(19)( )儲存管理支援多道程式設計，演算法簡單，但儲存器碎片多。
A) 段式 B)頁式 C)段頁式 D)固定分割槽
(20)虛存技術是( )。
A)擴充記憶體物理空間的技術 B)擴充相對地址空間的技術
C)擴充外存空間的技術 D)擴充輸入/輸出快取區技術
(21)緩衝技術用於( )。
A)提高主機和裝置交換資訊的排程
B)提供主、輔存介面
C)提高裝置利用率
D)擴充相對地址空間
(22)通道是一種( )。
A)I/O 埠 B)資料通道 C)I/O 專用處理機 D)軟體工具
(23)在請求分頁儲存管理中，若採用FIFO 頁面淘汰演算法，則當分配的`頁面增加時，缺頁
中斷的次數( )。
A)減少 B)增加 C)無影響 D)可能增加也可能減少
(24)軟體的複審是保證軟體質量的必要手段，下述
Ⅰ.軟體的可追溯性
Ⅱ.軟體的可維護性
Ⅲ.方案的可選擇性
Ⅳ.介面的明確性
( )是軟體複審時所涉及的技術內容?
A) Ⅰ和Ⅱ B) Ⅰ、Ⅱ和Ⅲ C) Ⅱ和Ⅲ D) 都正確
(25)以下關於結構化程式的說法中，正確的是( )。
A)結構化程式由單入口，單出口和迴圈三種結構組成
B)結構化程式由順序、單入口和單出口三種結構組成
C)結構化程式由順序、迴圈和GOTO語句結構組成
D)結構化程式由順序、迴圈和分支三種結構組成
(26)原型化方法大致可分為三類，它們是拋棄式、演化式和( )。
A)遞增式 B)維護式
C)測試式 D)技術式
(27)不論採用何種技術方法開發軟體，都必須完成一系列性質各異的工作，下述工作：
Ⅰ.怎樣做
Ⅱ.修改
Ⅲ.做什麼
Ⅳ.實現和完善
( )是必須完成的工作。
A) Ⅰ和Ⅱ B) Ⅰ、Ⅲ和Ⅳ C) Ⅱ和Ⅲ D) 都正確
(28) 需求分析所要做的工作是深入描述軟體的功能和效能，確定軟體設計的限制和軟體同
其他系統元素的介面細節， 定義軟體的其他有效性需求。分析員通過需求分析，逐步
細化對軟體的需求，描述軟體要處理的()，並給軟體開發提供一種可轉化為資料設計，結構設計和過程設計的資料與功能表示。
A)過程 B)物件C)資料域 D)環境
(29)需求分析的目的是理清資料流或資料結構，匯出完全的、精製的( )。
A)系統流程圖 B)系統邏輯模型C)系統物理模型 D)資料流圖
(30)在下述( )測試中,測試程式的設計者必須接觸到源程式。
Ⅰ. 功能測試
Ⅱ. 結構測試
A) 均不須 B) 只有Ⅰ C) 只有Ⅱ D) Ⅰ和Ⅱ
