第一部分 數(shù)據(jù)結(jié)構(gòu) （共 75分）
一、單項(xiàng)選擇題（每題 2分，共10分）
1．表頭表尾均為空表的廣義表是（ ）。
① （） ② （（）） ③ （（），（）） ④ （（（）））
2. 對(duì) 下列 4個(gè)序列,以第一個(gè)關(guān)鍵字為基礎(chǔ)進(jìn)行用快速排序算法進(jìn)行排序，在第一趟過(guò)程中移動(dòng)記錄次數(shù)最多的是 ( )
① 92，96，100，110，42，35，30，88
② 92，96，88，42，30，35，110，100
③ 100，96，92，35，30，110，88，42
④ 42，30，35，92，100，96，88，110
3． 實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法時(shí)，使用的數(shù)據(jù)結(jié)構(gòu)是 （ ）
① 棧
② 隊(duì)列
③ 十字鏈表
④ 三元組
4．在有向圖G的鄰接矩陣中，頂點(diǎn)Vi 的度是 （ ）。
① 鄰接矩陣中第 i行元素之和
② 鄰接矩陣中第 i列元素之和
③ 鄰接矩陣中第 i行和第i列元素之和
④ 鄰接矩陣中第 i行元素之和與第i列元素之和的值
5．能有效縮短關(guān)鍵路徑長(zhǎng)度的方法是（ ）
① 縮短任意一個(gè)活動(dòng)的持續(xù)時(shí)間
② 縮短關(guān)鍵路徑上任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
③ 縮短多條關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
④ 縮短所有關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
二、填空題（每空 2分，共 8 分）
1． 由一棵二叉樹的后序序列和 可確定這棵二叉樹。
2． 二叉樹結(jié)點(diǎn)數(shù) n與邊數(shù)e的關(guān)系為 。
3． 在各種查找算法中，平均查找長(zhǎng)度與關(guān)鍵字個(gè)數(shù) n無(wú)關(guān)的方法是 。
4． 若希望得到樹高較矮的生成樹，則采用圖的 遍歷算法。
三、判斷題（用√表示對(duì)，用×表示錯(cuò)。每題 2分，共 12 分）
1． 循環(huán)隊(duì)列中不存在隊(duì)列滿的問(wèn)題。（ ）
2． 將一個(gè)新結(jié)點(diǎn)插入到二叉排序樹中，該結(jié)點(diǎn)一定成為葉結(jié)點(diǎn)。（ ）
3． 用單鏈表示的有序表可以使用折半查找方法來(lái)提高查找速度。（ ）
4． 若有向圖中每個(gè)頂點(diǎn)的入度和出度均為 1，則該有向圖必有回路。（ ）
5． 已知二叉排序樹的先序序列，能確定該二叉排序樹。（ ）
6． 交換完全二叉樹所有結(jié)點(diǎn)的左右子樹，得到的二叉樹仍是完全二叉樹。（ ）
四、簡(jiǎn)答題（每題 6分，共 30 分）
1．若一個(gè)有向圖的鄰接矩陣中主對(duì)角線以下的元素均為0，則該圖一定不存在回路。該說(shuō)法是否正確？為什么？
2． 在完全二叉樹中，設(shè)結(jié)點(diǎn)數(shù)為 n，
（ 1）如何斷定該完全二叉樹中度為1的結(jié)點(diǎn)數(shù)n1?
（ 2）給定結(jié)點(diǎn)x的編號(hào)m，又如何根據(jù)該編號(hào)斷定x是否為葉結(jié)點(diǎn)？
3． 當(dāng)查找表有既能較快查找又能適應(yīng)動(dòng)態(tài)變化的需求時(shí)，選用什么查找方法最適合？并簡(jiǎn)述其理由。
4． 在某個(gè)通信系統(tǒng)中，報(bào)文的字符集為 a,b,c,d,e,f,g,h八種，其出現(xiàn)頻率分別為6，28,8,9,13,22,4和1,試為各字符設(shè)計(jì)二進(jìn)制編碼，使得報(bào)文編碼長(zhǎng)度最短。給出各字符的二進(jìn)制編碼和報(bào)文編碼長(zhǎng)度。
5． 設(shè) L是不帶頭結(jié)點(diǎn)單鏈表的頭指針，P是指向鏈表中某個(gè)結(jié)點(diǎn)的指針，該結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)，S是指向待插入新結(jié)點(diǎn)的指針，用下面 ① -- ⑦選項(xiàng)完成 A、B功能。
A. 在P所指結(jié)點(diǎn)前面插入 S所指結(jié)點(diǎn)的語(yǔ)句序列是（ ）；
B. 在第一個(gè)結(jié)點(diǎn)前面插入 S所指結(jié)點(diǎn)的語(yǔ)句序列是（ ）；
① P↑.next ：=S；
② Q:= P；
③ L:= S；
④ P:= L；
⑤ WHILE ( P↑.next <> Q ) DO P：= P↑.next；
⑥ S↑.next：= P↑.next；
⑦ S↑.next：= L↑.next；
五、算法題（共 15 分）
1． 設(shè)p,q分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中的某個(gè)結(jié)點(diǎn)，試編寫一個(gè)算法，用O(1)時(shí)間將這兩個(gè)單鏈表合并為一個(gè)，并令p指向p和q兩者data域值較小的結(jié)點(diǎn)。（5分）
PROC xyz( p, q )；
{ p,q分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中的某個(gè)結(jié)點(diǎn),結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data和指針域next}
ENDP；
2． 設(shè)二叉樹采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為 lchild、data和rchild，試編寫輸出二叉樹中從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑的算法。設(shè)二叉樹最長(zhǎng)路徑結(jié)點(diǎn)個(gè)數(shù)小于m，可以使用隊(duì)列S[1：m]，初始時(shí)S.rear=S.front=1。（10分）
PROC RootToLeaf(bt：bitreptr )；
{ bt為二叉樹根指針，S[1：m]為隊(duì)列, 初始時(shí)S.rear=S.front=1}
ENDP；{ RootToLeaf }
第二部分 操作系統(tǒng) （共 75分）
六、單項(xiàng)選擇題（在每小題 2分，共 20 分）
1． 在 UNIX中的索引結(jié)點(diǎn)可以看成：（ ）
① 文件目錄
② 文件相關(guān)信息說(shuō)明
③ 設(shè)備控制塊
④ 訪問(wèn)的主機(jī)對(duì)象
2．根據(jù)作業(yè)說(shuō)明書中的信息，對(duì)作業(yè)進(jìn)行控制, 稱此種作業(yè)為( )
①計(jì)算型作業(yè)
②終端型作業(yè)
③聯(lián)機(jī)作業(yè)
④脫機(jī)作業(yè)
3．不會(huì)產(chǎn)生內(nèi)部碎片的存儲(chǔ)管理（ ）。
① 分頁(yè)式存儲(chǔ)管理
② 分段式存儲(chǔ)管理
③ 固定分區(qū)式存儲(chǔ)管理
④ 段頁(yè)式存儲(chǔ)管理
4．空白表中，空白區(qū)按其長(zhǎng)度由小到大進(jìn)行查找的算法稱為（ ）算法。
① 適應(yīng)
② 最差適應(yīng)
③ 最先適應(yīng)
④ 先進(jìn)先出
5．為使虛存系統(tǒng)有效地發(fā)揮其預(yù)期的作用，所運(yùn)行的程序應(yīng)具有的特性是（ ）。
① 該程序不應(yīng)含有過(guò)多的I/O操作
② 該程序的大小不應(yīng)超過(guò)實(shí)際的內(nèi)存容量
③ 該程序應(yīng)具有較好的局部性(Locality)
④ 該程序的指令相關(guān)不應(yīng)過(guò)多。
6．快表在計(jì)算機(jī)系統(tǒng)中是用于（ ）的。
① 存儲(chǔ)文件信息
② 與主存交換信息
③ 地址變換
④ 存儲(chǔ)通道程序
7．在下列文件中，不便于文件增、刪操作的是（ ）。
① 索引文件
② 連續(xù)文件
③ Hash文件
④ 串聯(lián)文件
8．在采用SPOOLing技術(shù)的系統(tǒng)中，用戶的打印數(shù)據(jù)首先被送到（ ）。
① 磁盤固定區(qū)域
② 內(nèi)存固定區(qū)域
③ 終端
④ 打印機(jī)
9．如果I/O設(shè)備與存儲(chǔ)設(shè)備間的數(shù)據(jù)交換不經(jīng)過(guò)CPU來(lái)完成，則這種數(shù)據(jù)交換方式是（ ）
① 程序查詢方式
② 中斷方式
③ DMA方式
④ 無(wú)條件存取方式
10．在可變式分區(qū)存儲(chǔ)管理中的拼接技術(shù)可以（ ）。
① 縮短訪問(wèn)周期
② 增加主存容量
③ 加速地址變換
④ 使空閑區(qū)集中
七、多項(xiàng)選擇題（在每小題的五個(gè)備選答案中，選出二個(gè)至五個(gè)正確的答案 ,并將其號(hào)碼分別填在題干的括號(hào)內(nèi)，多選，少選、錯(cuò)選，均無(wú)分。每小題2分，共10分）
1． 采用按序分配資源策略的目的是（ ）
① 預(yù)防死鎖的方法
② 占有且等待資源
③ 非搶奪資源
④ 破壞循環(huán)等待資源
⑤ 互斥使用資源
2．如果系統(tǒng)中有N個(gè)進(jìn)程，則在等待隊(duì)列中的進(jìn)程個(gè)數(shù)可能為（ ）。
① 1
② N
③ N-1
④ N-2
⑤ N+1
3．一個(gè)進(jìn)程被喚醒意味著（ ）。
① 該進(jìn)程重新占有了CPU
② 它的優(yōu)先權(quán)變?yōu)?BR> ③ 其PCB移到等待隊(duì)列隊(duì)首
④ 進(jìn)程變?yōu)榫途w狀態(tài)
⑤ 進(jìn)程獲得了資源，具備了運(yùn)行條件
4．當(dāng)用戶程序執(zhí)行訪管指令時(shí)，中斷裝置將使中央處理器（ ）
① 維持在目態(tài)
② 從目態(tài)轉(zhuǎn)換到管態(tài)
③ 從管態(tài)轉(zhuǎn)換到目態(tài)
④ 維持在管態(tài)
⑤ 從管態(tài)轉(zhuǎn)換到目態(tài)執(zhí)行系統(tǒng)調(diào)用
5．采用動(dòng)態(tài)重定位方式裝入的作業(yè)，在執(zhí)行中允許（ ）。
① 用戶有條件地移動(dòng)
② 地址變換
③ 操作系統(tǒng)有條件地移動(dòng)
④ 操作系統(tǒng)無(wú)條件地移動(dòng)
⑤ 用戶無(wú)條件地移動(dòng)
八、判斷并改錯(cuò)題（正確的劃上 “√”,錯(cuò)誤的劃上“╳”,每小題2分,共20分）
1．（ ）在串信通信中引入緩沖區(qū)，假設(shè)增加一位緩沖區(qū)則可以放寬1個(gè)單位的中斷響應(yīng)時(shí)間，給定8位緩沖則放寬8個(gè)單位的中斷響應(yīng)時(shí)間。
2．（ ）分頁(yè)存儲(chǔ)管理采用重定位技術(shù)實(shí)現(xiàn)頁(yè)式地址變換的。
3．（ ）在頁(yè)式管理中采用可變分配局部置換能使系統(tǒng)中的物理塊得到充分利用，但有可能影響其他進(jìn)程的運(yùn)行。
4．（ ）索引順序文件是按記錄鍵排序的。
5．（ ）設(shè)備控制器是CPU與I/O設(shè)備之間的接口，它接收從CPU發(fā)來(lái)的命令，并控制I/O設(shè)備工作。
6．（ ）程序鏈接是討論程序怎樣裝入內(nèi)存的方法。
7．（ ）銀行家的算法中的安全檢查就是檢查系統(tǒng)是否存在安全序列。
8．（ ）在有線程和進(jìn)程的系統(tǒng)中，CPU的占用是由線程調(diào)度和進(jìn)程調(diào)度協(xié)調(diào)進(jìn)行的，才能保證CPU的正常執(zhí)行。
9．（ ）對(duì)換空間管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度。
10．（ ）多級(jí)反饋隊(duì)列靜態(tài)調(diào)度算法，能較好地滿足各種類型用戶的需求。
九、簡(jiǎn)答題 （共 25分）
1．（9分）某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略擁有邏輯空間32頁(yè)，每頁(yè)2K，擁有物理空間1M。寫出頁(yè)的邏輯地址格式。若不考慮訪問(wèn)權(quán)限等，進(jìn)程的頁(yè)表有多少項(xiàng)？每項(xiàng)至少有多少位？如果物理空間減少一半，頁(yè)表相應(yīng)作怎樣的改變？
2．（8分）一個(gè)多道程序系統(tǒng),用戶空間為100K,有四臺(tái)打印機(jī);采用在主存的作業(yè)不能移動(dòng)的動(dòng)態(tài)分區(qū)方式管理主存。主存空間采用首次適應(yīng)算法，靜態(tài)分配打印機(jī)，對(duì)作業(yè)采用計(jì)算時(shí)間短的作業(yè)優(yōu)先調(diào)度算法管理。今有如下所示的作業(yè)序列，請(qǐng)分別列出各個(gè)作業(yè)的開(kāi)始執(zhí)行時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間（按十進(jìn)制計(jì)算）。注意：忽略系統(tǒng)開(kāi)銷。
作業(yè)名 進(jìn)入輸入井的時(shí)間 需計(jì)算時(shí)間 需打印機(jī)臺(tái)數(shù) 主存需求量
JOB1 8.0時(shí) 1小時(shí) 2臺(tái) 20K
JOB2 8.2時(shí) 0.6小時(shí) 1臺(tái) 60K
JOB3 8.4時(shí) 0.5小時(shí) 1臺(tái) 25K
JOB4 8.6時(shí) 1小時(shí) 3臺(tái) 20K
JOB5 9.0時(shí) 0.5小時(shí) 2臺(tái) 20K
3．（8分）假設(shè)一個(gè)文件系統(tǒng)基于索引分配策略來(lái)管理塊，假設(shè)每個(gè)文件有一個(gè)目錄項(xiàng)，該目錄項(xiàng)可給出文件名字、第一個(gè)索引塊以及文件的長(zhǎng)度。第一個(gè)索引塊最多依次指向249個(gè)文件數(shù)據(jù)塊并且指向下一個(gè)索引塊。如果文件的當(dāng)前位置在邏輯塊1992處，并且下一個(gè)操作將訪問(wèn)邏輯塊308，那么必須從磁盤中讀取多少個(gè)物理塊？解釋一下您的答案。
一、單項(xiàng)選擇題（每題 2分，共10分）
1．表頭表尾均為空表的廣義表是（ ）。
① （） ② （（）） ③ （（），（）） ④ （（（）））
2. 對(duì) 下列 4個(gè)序列,以第一個(gè)關(guān)鍵字為基礎(chǔ)進(jìn)行用快速排序算法進(jìn)行排序，在第一趟過(guò)程中移動(dòng)記錄次數(shù)最多的是 ( )
① 92，96，100，110，42，35，30，88
② 92，96，88，42，30，35，110，100
③ 100，96，92，35，30，110，88，42
④ 42，30，35，92，100，96，88，110
3． 實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法時(shí)，使用的數(shù)據(jù)結(jié)構(gòu)是 （ ）
① 棧
② 隊(duì)列
③ 十字鏈表
④ 三元組
4．在有向圖G的鄰接矩陣中，頂點(diǎn)Vi 的度是 （ ）。
① 鄰接矩陣中第 i行元素之和
② 鄰接矩陣中第 i列元素之和
③ 鄰接矩陣中第 i行和第i列元素之和
④ 鄰接矩陣中第 i行元素之和與第i列元素之和的值
5．能有效縮短關(guān)鍵路徑長(zhǎng)度的方法是（ ）
① 縮短任意一個(gè)活動(dòng)的持續(xù)時(shí)間
② 縮短關(guān)鍵路徑上任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
③ 縮短多條關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
④ 縮短所有關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間
二、填空題（每空 2分，共 8 分）
1． 由一棵二叉樹的后序序列和 可確定這棵二叉樹。
2． 二叉樹結(jié)點(diǎn)數(shù) n與邊數(shù)e的關(guān)系為 。
3． 在各種查找算法中，平均查找長(zhǎng)度與關(guān)鍵字個(gè)數(shù) n無(wú)關(guān)的方法是 。
4． 若希望得到樹高較矮的生成樹，則采用圖的 遍歷算法。
三、判斷題（用√表示對(duì)，用×表示錯(cuò)。每題 2分，共 12 分）
1． 循環(huán)隊(duì)列中不存在隊(duì)列滿的問(wèn)題。（ ）
2． 將一個(gè)新結(jié)點(diǎn)插入到二叉排序樹中，該結(jié)點(diǎn)一定成為葉結(jié)點(diǎn)。（ ）
3． 用單鏈表示的有序表可以使用折半查找方法來(lái)提高查找速度。（ ）
4． 若有向圖中每個(gè)頂點(diǎn)的入度和出度均為 1，則該有向圖必有回路。（ ）
5． 已知二叉排序樹的先序序列，能確定該二叉排序樹。（ ）
6． 交換完全二叉樹所有結(jié)點(diǎn)的左右子樹，得到的二叉樹仍是完全二叉樹。（ ）
四、簡(jiǎn)答題（每題 6分，共 30 分）
1．若一個(gè)有向圖的鄰接矩陣中主對(duì)角線以下的元素均為0，則該圖一定不存在回路。該說(shuō)法是否正確？為什么？
2． 在完全二叉樹中，設(shè)結(jié)點(diǎn)數(shù)為 n，
（ 1）如何斷定該完全二叉樹中度為1的結(jié)點(diǎn)數(shù)n1?
（ 2）給定結(jié)點(diǎn)x的編號(hào)m，又如何根據(jù)該編號(hào)斷定x是否為葉結(jié)點(diǎn)？
3． 當(dāng)查找表有既能較快查找又能適應(yīng)動(dòng)態(tài)變化的需求時(shí)，選用什么查找方法最適合？并簡(jiǎn)述其理由。
4． 在某個(gè)通信系統(tǒng)中，報(bào)文的字符集為 a,b,c,d,e,f,g,h八種，其出現(xiàn)頻率分別為6，28,8,9,13,22,4和1,試為各字符設(shè)計(jì)二進(jìn)制編碼，使得報(bào)文編碼長(zhǎng)度最短。給出各字符的二進(jìn)制編碼和報(bào)文編碼長(zhǎng)度。
5． 設(shè) L是不帶頭結(jié)點(diǎn)單鏈表的頭指針，P是指向鏈表中某個(gè)結(jié)點(diǎn)的指針，該結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)，S是指向待插入新結(jié)點(diǎn)的指針，用下面 ① -- ⑦選項(xiàng)完成 A、B功能。
A. 在P所指結(jié)點(diǎn)前面插入 S所指結(jié)點(diǎn)的語(yǔ)句序列是（ ）；
B. 在第一個(gè)結(jié)點(diǎn)前面插入 S所指結(jié)點(diǎn)的語(yǔ)句序列是（ ）；
① P↑.next ：=S；
② Q:= P；
③ L:= S；
④ P:= L；
⑤ WHILE ( P↑.next <> Q ) DO P：= P↑.next；
⑥ S↑.next：= P↑.next；
⑦ S↑.next：= L↑.next；
五、算法題（共 15 分）
1． 設(shè)p,q分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中的某個(gè)結(jié)點(diǎn)，試編寫一個(gè)算法，用O(1)時(shí)間將這兩個(gè)單鏈表合并為一個(gè)，并令p指向p和q兩者data域值較小的結(jié)點(diǎn)。（5分）
PROC xyz( p, q )；
{ p,q分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中的某個(gè)結(jié)點(diǎn),結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data和指針域next}
ENDP；
2． 設(shè)二叉樹采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為 lchild、data和rchild，試編寫輸出二叉樹中從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑的算法。設(shè)二叉樹最長(zhǎng)路徑結(jié)點(diǎn)個(gè)數(shù)小于m，可以使用隊(duì)列S[1：m]，初始時(shí)S.rear=S.front=1。（10分）
PROC RootToLeaf(bt：bitreptr )；
{ bt為二叉樹根指針，S[1：m]為隊(duì)列, 初始時(shí)S.rear=S.front=1}
ENDP；{ RootToLeaf }
第二部分 操作系統(tǒng) （共 75分）
六、單項(xiàng)選擇題（在每小題 2分，共 20 分）
1． 在 UNIX中的索引結(jié)點(diǎn)可以看成：（ ）
① 文件目錄
② 文件相關(guān)信息說(shuō)明
③ 設(shè)備控制塊
④ 訪問(wèn)的主機(jī)對(duì)象
2．根據(jù)作業(yè)說(shuō)明書中的信息，對(duì)作業(yè)進(jìn)行控制, 稱此種作業(yè)為( )
①計(jì)算型作業(yè)
②終端型作業(yè)
③聯(lián)機(jī)作業(yè)
④脫機(jī)作業(yè)
3．不會(huì)產(chǎn)生內(nèi)部碎片的存儲(chǔ)管理（ ）。
① 分頁(yè)式存儲(chǔ)管理
② 分段式存儲(chǔ)管理
③ 固定分區(qū)式存儲(chǔ)管理
④ 段頁(yè)式存儲(chǔ)管理
4．空白表中，空白區(qū)按其長(zhǎng)度由小到大進(jìn)行查找的算法稱為（ ）算法。
① 適應(yīng)
② 最差適應(yīng)
③ 最先適應(yīng)
④ 先進(jìn)先出
5．為使虛存系統(tǒng)有效地發(fā)揮其預(yù)期的作用，所運(yùn)行的程序應(yīng)具有的特性是（ ）。
① 該程序不應(yīng)含有過(guò)多的I/O操作
② 該程序的大小不應(yīng)超過(guò)實(shí)際的內(nèi)存容量
③ 該程序應(yīng)具有較好的局部性(Locality)
④ 該程序的指令相關(guān)不應(yīng)過(guò)多。
6．快表在計(jì)算機(jī)系統(tǒng)中是用于（ ）的。
① 存儲(chǔ)文件信息
② 與主存交換信息
③ 地址變換
④ 存儲(chǔ)通道程序
7．在下列文件中，不便于文件增、刪操作的是（ ）。
① 索引文件
② 連續(xù)文件
③ Hash文件
④ 串聯(lián)文件
8．在采用SPOOLing技術(shù)的系統(tǒng)中，用戶的打印數(shù)據(jù)首先被送到（ ）。
① 磁盤固定區(qū)域
② 內(nèi)存固定區(qū)域
③ 終端
④ 打印機(jī)
9．如果I/O設(shè)備與存儲(chǔ)設(shè)備間的數(shù)據(jù)交換不經(jīng)過(guò)CPU來(lái)完成，則這種數(shù)據(jù)交換方式是（ ）
① 程序查詢方式
② 中斷方式
③ DMA方式
④ 無(wú)條件存取方式
10．在可變式分區(qū)存儲(chǔ)管理中的拼接技術(shù)可以（ ）。
① 縮短訪問(wèn)周期
② 增加主存容量
③ 加速地址變換
④ 使空閑區(qū)集中
七、多項(xiàng)選擇題（在每小題的五個(gè)備選答案中，選出二個(gè)至五個(gè)正確的答案 ,并將其號(hào)碼分別填在題干的括號(hào)內(nèi)，多選，少選、錯(cuò)選，均無(wú)分。每小題2分，共10分）
1． 采用按序分配資源策略的目的是（ ）
① 預(yù)防死鎖的方法
② 占有且等待資源
③ 非搶奪資源
④ 破壞循環(huán)等待資源
⑤ 互斥使用資源
2．如果系統(tǒng)中有N個(gè)進(jìn)程，則在等待隊(duì)列中的進(jìn)程個(gè)數(shù)可能為（ ）。
① 1
② N
③ N-1
④ N-2
⑤ N+1
3．一個(gè)進(jìn)程被喚醒意味著（ ）。
① 該進(jìn)程重新占有了CPU
② 它的優(yōu)先權(quán)變?yōu)?BR> ③ 其PCB移到等待隊(duì)列隊(duì)首
④ 進(jìn)程變?yōu)榫途w狀態(tài)
⑤ 進(jìn)程獲得了資源，具備了運(yùn)行條件
4．當(dāng)用戶程序執(zhí)行訪管指令時(shí)，中斷裝置將使中央處理器（ ）
① 維持在目態(tài)
② 從目態(tài)轉(zhuǎn)換到管態(tài)
③ 從管態(tài)轉(zhuǎn)換到目態(tài)
④ 維持在管態(tài)
⑤ 從管態(tài)轉(zhuǎn)換到目態(tài)執(zhí)行系統(tǒng)調(diào)用
5．采用動(dòng)態(tài)重定位方式裝入的作業(yè)，在執(zhí)行中允許（ ）。
① 用戶有條件地移動(dòng)
② 地址變換
③ 操作系統(tǒng)有條件地移動(dòng)
④ 操作系統(tǒng)無(wú)條件地移動(dòng)
⑤ 用戶無(wú)條件地移動(dòng)
八、判斷并改錯(cuò)題（正確的劃上 “√”,錯(cuò)誤的劃上“╳”,每小題2分,共20分）
1．（ ）在串信通信中引入緩沖區(qū)，假設(shè)增加一位緩沖區(qū)則可以放寬1個(gè)單位的中斷響應(yīng)時(shí)間，給定8位緩沖則放寬8個(gè)單位的中斷響應(yīng)時(shí)間。
2．（ ）分頁(yè)存儲(chǔ)管理采用重定位技術(shù)實(shí)現(xiàn)頁(yè)式地址變換的。
3．（ ）在頁(yè)式管理中采用可變分配局部置換能使系統(tǒng)中的物理塊得到充分利用，但有可能影響其他進(jìn)程的運(yùn)行。
4．（ ）索引順序文件是按記錄鍵排序的。
5．（ ）設(shè)備控制器是CPU與I/O設(shè)備之間的接口，它接收從CPU發(fā)來(lái)的命令，并控制I/O設(shè)備工作。
6．（ ）程序鏈接是討論程序怎樣裝入內(nèi)存的方法。
7．（ ）銀行家的算法中的安全檢查就是檢查系統(tǒng)是否存在安全序列。
8．（ ）在有線程和進(jìn)程的系統(tǒng)中，CPU的占用是由線程調(diào)度和進(jìn)程調(diào)度協(xié)調(diào)進(jìn)行的，才能保證CPU的正常執(zhí)行。
9．（ ）對(duì)換空間管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度。
10．（ ）多級(jí)反饋隊(duì)列靜態(tài)調(diào)度算法，能較好地滿足各種類型用戶的需求。
九、簡(jiǎn)答題 （共 25分）
1．（9分）某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略擁有邏輯空間32頁(yè)，每頁(yè)2K，擁有物理空間1M。寫出頁(yè)的邏輯地址格式。若不考慮訪問(wèn)權(quán)限等，進(jìn)程的頁(yè)表有多少項(xiàng)？每項(xiàng)至少有多少位？如果物理空間減少一半，頁(yè)表相應(yīng)作怎樣的改變？
2．（8分）一個(gè)多道程序系統(tǒng),用戶空間為100K,有四臺(tái)打印機(jī);采用在主存的作業(yè)不能移動(dòng)的動(dòng)態(tài)分區(qū)方式管理主存。主存空間采用首次適應(yīng)算法，靜態(tài)分配打印機(jī)，對(duì)作業(yè)采用計(jì)算時(shí)間短的作業(yè)優(yōu)先調(diào)度算法管理。今有如下所示的作業(yè)序列，請(qǐng)分別列出各個(gè)作業(yè)的開(kāi)始執(zhí)行時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間（按十進(jìn)制計(jì)算）。注意：忽略系統(tǒng)開(kāi)銷。
作業(yè)名 進(jìn)入輸入井的時(shí)間 需計(jì)算時(shí)間 需打印機(jī)臺(tái)數(shù) 主存需求量
JOB1 8.0時(shí) 1小時(shí) 2臺(tái) 20K
JOB2 8.2時(shí) 0.6小時(shí) 1臺(tái) 60K
JOB3 8.4時(shí) 0.5小時(shí) 1臺(tái) 25K
JOB4 8.6時(shí) 1小時(shí) 3臺(tái) 20K
JOB5 9.0時(shí) 0.5小時(shí) 2臺(tái) 20K
3．（8分）假設(shè)一個(gè)文件系統(tǒng)基于索引分配策略來(lái)管理塊，假設(shè)每個(gè)文件有一個(gè)目錄項(xiàng)，該目錄項(xiàng)可給出文件名字、第一個(gè)索引塊以及文件的長(zhǎng)度。第一個(gè)索引塊最多依次指向249個(gè)文件數(shù)據(jù)塊并且指向下一個(gè)索引塊。如果文件的當(dāng)前位置在邏輯塊1992處，并且下一個(gè)操作將訪問(wèn)邏輯塊308，那么必須從磁盤中讀取多少個(gè)物理塊？解釋一下您的答案。