點選檢視試題答案及解析
一、選擇題：( 共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) 控制和管理系統資源的使用
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)沒有2
(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)擴充輸入/輸出快取區技術
