2017江蘇南京航空航天大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題

1、2017江蘇南京航空航天大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研真題數(shù)據(jù)結(jié)構(gòu)部分（75 分）1（5 分）已知帶權(quán)圖如下所示，用 Kruskal 算法產(chǎn)生最小生成樹，并說明算法思想。2（10 分）為一個(gè)家譜管理程序設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，以一個(gè)四代人，11 個(gè)家庭成員為例，（A 有 3 個(gè)孩子 A1、A2、A3；A1 有 2 個(gè)孩子 A11、A12；A2 無子，A3 有 3 個(gè)孩子 A31、A32、A33；A11 有 1 個(gè)孩子 A111；A32 有 1 個(gè)孩子 A321；其余尚無子），畫出家譜示意圖，給出所設(shè)計(jì)的存儲結(jié)構(gòu)示意圖，并給出在該存儲結(jié)構(gòu)上輸出第 k 代所有人員的算法思想。3. （10 分）設(shè)有 8 個(gè)字

2、符（a, b, c, d, e, f, g, h），其權(quán)值為（48,15,20,12,6,61,8,10），給出進(jìn)行 Huffman 編碼所用的數(shù)據(jù)結(jié)構(gòu)和求解過程數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的最后結(jié)果。4（10 分）已知輸入數(shù)據(jù)序列為 (58,68,42,10,88,32,70,52,55,46 )，給出建立 3 階 B樹示意圖，再給出刪除 55，70 后的 B-樹。5（10 分）試用 Dijkstra 算法，求下圖中從 V1 到其余各頂點(diǎn)的最短路徑，給出實(shí)現(xiàn)算法所用的數(shù)據(jù)結(jié)構(gòu)和求解過程中每一步的狀態(tài)。6（10 分）設(shè) A、B 為遞減有序（元素值為整型）的單鏈表，編寫函數(shù)，利用原結(jié)點(diǎn)將它們合并成一個(gè)遞增有序

3、的單鏈表，相同元素值只保留一個(gè)結(jié)點(diǎn)。先給出算法思想，再寫出相應(yīng)代碼。7.（10 分）設(shè)二叉樹 T，用二叉鏈表結(jié)構(gòu)存儲。編寫函數(shù)，對于每個(gè)元素值為 x 的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。要求先給出算法思想，再寫出相應(yīng)代碼。8.（10 分）設(shè)有 n 個(gè)學(xué)生成績（0-100 整數(shù)）的順序結(jié)構(gòu)線性表 L，編寫函數(shù)，將該線性表中調(diào)整為成績及格（大于等于 60）在不及格之前，要求 T(n)=O(n), S(n)=O(1)。先給出算法思想，再寫出相應(yīng)代碼。操作系統(tǒng)部分（75 分）1. 單選題（10 分，每題 1 分)（1）在下列系統(tǒng)中，( )是實(shí)時(shí)系統(tǒng)。A.計(jì)算機(jī)激光照排系統(tǒng) B.軍用反導(dǎo)彈系統(tǒng)

4、C.辦公自動(dòng)化系統(tǒng) D.計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)（2）. 引入多道程序的目的在于( )。A.充分利用 CPU，減少 CPU 等待時(shí)間 B提高實(shí)時(shí)響應(yīng)速度C.有利于代碼共享，減少主、輔存信息交換量 D解放 cpu 對外設(shè)的管理（3）已經(jīng)獲得除( )以外的所有運(yùn)行所需資源的進(jìn)程處于就緒狀態(tài)A.存儲器 B打印機(jī) CCPU D磁盤空間（4）采用時(shí)間片輪轉(zhuǎn)法調(diào)度是為了( )。A.多個(gè)終端都能得到系統(tǒng)的及時(shí)響應(yīng) B.先來先服務(wù)C.優(yōu)先級較高的進(jìn)程得到及時(shí)調(diào)度 D.需 CPU 最短的進(jìn)程先做（5）在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源，稱為( ) 。A.共享資源 B臨界區(qū) C臨界資源 D共享區(qū)（6）.并發(fā)性是指若干

5、事件在( )發(fā)生 。A同一時(shí)刻 B同一時(shí)間間隔內(nèi) C不同時(shí)刻 D不同時(shí)間間隔內(nèi)（7）管道通信是以( )進(jìn)行寫入和讀出。A消息為單位 B自然字符流 C文件 D報(bào)文（8）操作系統(tǒng)中有一組特殊的程序它們不能被系統(tǒng)中斷，在操作系統(tǒng)中稱為( )A.初始化程序 B原語 C子程序 D.控制模塊（9）. 在分段管理中( )。A以段為單位分配，每段是一個(gè)連續(xù)存儲區(qū) B段與段之間必定不連續(xù)C段與段之間必定連續(xù) D每段是等長的（10）.通道是一種( )。A.IO 端口 B數(shù)據(jù)通道 CIO 專用處理機(jī) D軟件工具2. 簡答題（20 分，每題 4 分）（1）. 系統(tǒng)型線程和用戶型線程有何區(qū)別？（2）. 多級反饋隊(duì)列調(diào)度

6、算法是如何工作的？（3）. 分段式系統(tǒng)和分頁式系統(tǒng)有何區(qū)別？（4）. 引入緩沖的目的是什么，有哪些常見的緩沖模式？（5）. SPOOLING 技術(shù)如何實(shí)現(xiàn)，在操作系統(tǒng)中起何作用？3. （9 分） 設(shè)有三道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間由下表給出:（1）周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間的區(qū)別是什么，為何引入帶權(quán)周轉(zhuǎn)時(shí)間？（2 分）（2）試計(jì)算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間 。（7 分）4. （9 分）某系統(tǒng)有 A、B、C、D 四類資源可供五個(gè)進(jìn)程 P1、P2、P3、P4、P5 共享。系統(tǒng)共有這四類資源為:A 類 3 個(gè)、B 類 14 個(gè)、C 類 12 個(gè)、D

7、 類 12 個(gè)。進(jìn)程對資源的需求和分配情況如下：（1）現(xiàn)在系統(tǒng)是否處于安全狀態(tài)？（4 分）（2）如果進(jìn)程 P2 提出需要 A 類資源 0 個(gè)、B 類資源 4 個(gè)、C 類資源 2 個(gè)和 D 類資源0 個(gè)，系統(tǒng)能否去滿足它的請求？（5 分）5. （9 分）某分頁系統(tǒng)，每個(gè)頁面長為 1KB，某時(shí)刻該用戶進(jìn)程的頁表如下：（1） 請寫出分頁系統(tǒng)的地址轉(zhuǎn)換過程（3 分）（2）計(jì)算兩個(gè)邏輯地址：0AC5H、1AC5H 對應(yīng)的物理地址（16 進(jìn)制表示）。（3 分）（3）已知主存的一次存取為 2us，對于快表的查詢時(shí)間可以忽略，則訪問上述兩個(gè)邏輯地址分別耗費(fèi)多少時(shí)間？（3 分）6. （9 分） 在某請求分頁管理系統(tǒng)中，作業(yè)執(zhí)行時(shí)一次訪問如下頁面：1，4，3，1，2，5，1，4，2，1，4，5，若分配給該作業(yè)的主存塊數(shù)為 3.（1）頁面置換算法在虛擬存儲管理中的重要性。（2 分）（2）FIFO, LRU 算法各適用于什么場合（3 分）（3）計(jì)算 FIFO，LRU，頁面置換算法，試求出缺頁中斷次數(shù)。（4 分）7. （9