南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)B數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)專(zhuān)業(yè)碩士歷年考研真題匯編

南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)B數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)專(zhuān)業(yè)碩士歷年考研真題匯編第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共75分)選擇題(每題2分，共20分)0A)L->ncx[->nex(=B)L>next==L存儲(chǔ)單元。6.將下圖所示的二叉樹(shù)按中序線索化后，結(jié)點(diǎn)E的左指針指向結(jié)點(diǎn)7.一棵完全二叉樹(shù)上有722個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)是8.對(duì)下圖所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)序列為。A)I,2,4,5,6,3,7,8B)1,2,4,3,5,6,7.8元素時(shí)，所需的比較次數(shù)為。A)4B)3C)2D)5108簡(jiǎn)單排序方法中，當(dāng)序列中的記錄已“基本有序”時(shí)，是最佳的排序A)起泡排序B)簡(jiǎn)單選釋排序C)快速排序D)直接插入排序二、填空題(每空1分；共5分) 三、簡(jiǎn)答題(共6題，共42分)插入和刪除操作，則該線性表宜采用何種存儲(chǔ)方式?(5分)該二叉樹(shù)共有多少個(gè)結(jié)點(diǎn)?(4分)5.根據(jù)下圖所示的AOE網(wǎng)，頂點(diǎn)Vi,Vz,V?,Vs(1)求出所有事件的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間。(4分)(2)求出所有活動(dòng)的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間。(4分)(3)列出所有關(guān)鍵活動(dòng)。(2分)(4)將本題的AOE網(wǎng)視為無(wú)向圖(即將圖中的有向邊看成無(wú)向邊),用克魯斯卡爾算法構(gòu)造一棵最小生成樹(shù)并畫(huà)出。(4分)狀態(tài)。(4分)四、算法設(shè)計(jì)題(共8分)第二部分操作系統(tǒng)(75分)一、單項(xiàng)選擇題(每題1分，共20分)柱面號(hào)為100,185,39,124,16,126,67,69。當(dāng)55柱面號(hào)操作完成后，若825計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)(B)第4頁(yè)共7頁(yè)12.設(shè)備的打開(kāi)、關(guān)閉、讀、寫(xiě)等操作是由A)用戶程序B)編譯程序C)設(shè)備分配程序D)設(shè)備驅(qū)動(dòng)程序13.能使作業(yè)平均周轉(zhuǎn)時(shí)間最小的作業(yè)調(diào)度算法是A)先來(lái)先服務(wù)算法B)計(jì)算時(shí)間最短的作業(yè)優(yōu)先算法C)優(yōu)先級(jí)調(diào)度算法D)均衡調(diào)度算法14.管理磁盤(pán)存儲(chǔ)空間的方法是A)索引表、位示圖、空閑塊表B)位示圖、空閑塊表、空閑塊鏈C)空閑塊表、空閑塊鏈、索引表D)空閑塊鏈、索引表、位示圖15.關(guān)于處理機(jī)調(diào)度，以下說(shuō)法錯(cuò)誤的是A)衡量調(diào)度策名的主要指標(biāo)有：周轉(zhuǎn)時(shí)間、吞吐率、響應(yīng)時(shí)間和設(shè)備利用率B)處理機(jī)調(diào)度可以分為4級(jí)：作業(yè)調(diào)度、交換調(diào)度、進(jìn)程調(diào)度和線程調(diào)度D)進(jìn)程調(diào)度的算法有：輪轉(zhuǎn)法、先來(lái)先服務(wù)法、優(yōu)先級(jí)法16,分段管理提供維的地址結(jié)構(gòu)。17.如果允許不同用戶的文件可以具有相同的文件名，通常采用來(lái)保A)重名翻譯機(jī)構(gòu)]B)建立索引表C)建立指針D)多級(jí)目錄結(jié)構(gòu)18.SPOOLing技術(shù)利用于則它的最大頁(yè)號(hào)和最大頁(yè)內(nèi)地址是A)256和65536B)255和65535C)256和65535D)255和6553620.實(shí)現(xiàn)“分配主存空間和重定位”"屬于操作系統(tǒng)中的A)處理器管理B)存儲(chǔ)管理C)文件管理D)設(shè)備管理I.創(chuàng)建線程比創(chuàng)建進(jìn)程開(kāi)銷(xiāo)小。2.FCB長(zhǎng)期存放于操作系統(tǒng)核心空間。3.同一程序可以由多個(gè)進(jìn)程運(yùn)行。4.緩沖技術(shù)因?yàn)樵黾恿藬?shù)據(jù)拷貝次數(shù)，所以不能改善I/O性能。5.磁盤(pán)驅(qū)動(dòng)程序磁盤(pán)請(qǐng)求生成后插入請(qǐng)求隊(duì)列時(shí)進(jìn)行為減少尋道時(shí)間的排隊(duì)優(yōu)6.磁盤(pán)中斷優(yōu)先級(jí)應(yīng)該比打印機(jī)中斷優(yōu)先級(jí)低。7.在處理系統(tǒng)調(diào)用請(qǐng)求時(shí)應(yīng)該屏蔽外部中斷。8.進(jìn)程申請(qǐng)資源時(shí)有可能進(jìn)入等待狀態(tài)。9.用戶級(jí)線程實(shí)現(xiàn)不能支持同一進(jìn)程的多線程在多處理機(jī)并行運(yùn)行。10.死鎖避免比死鎖檢測(cè)實(shí)用。三.填空題(每空1分，共10分)1,一個(gè)程序在一個(gè)數(shù)據(jù)集上的一次運(yùn)行稱(chēng)為一個(gè)。2.地址轉(zhuǎn)換是在作業(yè)執(zhí)行前集中完成，執(zhí)行中無(wú)需再進(jìn)行地址轉(zhuǎn)換的定位方式稱(chēng)為"3.設(shè)與某資源關(guān)聯(lián)的信號(hào)量初值為4,當(dāng)前值為-2。若M表示該資源的可用個(gè)數(shù)，第5頁(yè)共7頁(yè)8,分頁(yè)系統(tǒng)中，作業(yè)內(nèi)部碎片的平均大小為9-10,頁(yè)是信息的單位，進(jìn)行分頁(yè)是出于系統(tǒng)管理的需要；段是信息的 單位，分段是出于用戶的需要。四.填空題(1-4題每空1分，5題每空2分，共20分)1.假設(shè)一個(gè)磁盤(pán)組有100個(gè)柱面，編號(hào)為0—99,每個(gè)柱面有32個(gè)磁道，編號(hào)為0-31,每個(gè)盤(pán)面有16個(gè)扇區(qū)，編號(hào)為0-15?，F(xiàn)采用位示圖的方法管理磁盤(pán)3.假設(shè)某操作系統(tǒng)采用時(shí)間片輪轉(zhuǎn)調(diào)度策略，時(shí)間片大小為100ms,就緒進(jìn)程隊(duì)列的平均長(zhǎng)度為5,如果在系統(tǒng)中運(yùn)行一個(gè)需要在CPU上執(zhí)行.0.8s時(shí)間的問(wèn)的程面號(hào)順序?yàn)?9,18,44,18,67,75,如果使用SCAN算法，服務(wù)的順五.簡(jiǎn)答題(每題5分，共15分)2011年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院825計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)B[專(zhuān)業(yè)碩士]考研真題2011年碩士學(xué)位研究生入學(xué)考試試題科目代碼：825科目名稱(chēng)：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)(B)滿分：150分第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共75分)一、填空(每題2分，共20分)1.算法分析的目的是2.用鄰接表表示圖時(shí)，頂點(diǎn)數(shù)為n,邊數(shù)為e,在鄰接表上執(zhí)行圖的深度優(yōu)先遍歷操作時(shí)，時(shí)間復(fù)雜性。指向鏈表中任意結(jié)點(diǎn)。若在指針p所指結(jié)點(diǎn)之后插入結(jié)點(diǎn)s,則應(yīng)執(zhí)行的操作;若在指針p所指結(jié)點(diǎn)之前插入結(jié)點(diǎn)s,則應(yīng)執(zhí)行的操作5.設(shè)待排序的序列為{48,35,60,13,75,80,26,49}下面是排序過(guò)程：(4)這一趟排序的序列為(6)6.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)定義為T(mén)ypedefstructBiTreeNode*Lchild;*Rchild;//指針t是二叉樹(shù)的根指針elsereturnunknownLchildunknowtypedefstructLNode{二、簡(jiǎn)答題(共23分)3.(12分)對(duì)于下圖的AOE網(wǎng)(1)填寫(xiě)下面的2個(gè)表(各2分)事件最早發(fā)生時(shí)間最遲發(fā)生時(shí)間活動(dòng)最早發(fā)生時(shí)間最遲發(fā)生時(shí)問(wèn)(2)列出關(guān)鍵活動(dòng)(2分);(3)忽略圖中的權(quán)值，將圖看成AOE網(wǎng)，寫(xiě)出圖的3個(gè)拓?fù)湫蛄?3分):825共6頁(yè)第2頁(yè)4.(5分)簡(jiǎn)述分塊查找的數(shù)據(jù)組織方式及查找過(guò)程。三、(每題5分，共20分)設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,2.逐個(gè)輸入各個(gè)數(shù)據(jù)生成的3階B-樹(shù)，畫(huà)出過(guò)程；1.(4分)圖用鄰接表存儲(chǔ)，若已知頂點(diǎn)Yi和Vj.寫(xiě)出判斷Vi與Yj__intadjvex;//邊(弧)的另一頂點(diǎn)的在數(shù)組中的位置ArcNode*finrstarc://指向關(guān)聯(lián)該頂點(diǎn)的邊(弧)鏈表2.(8分)設(shè)有線性表L={al,a2,…,an),順序存儲(chǔ)，試寫(xiě)一個(gè)算法將該線性表typedefstruct{typedefstructLNode{第二部分操作系統(tǒng)(75分)、選擇題(每題1.5分，共30分)。A)就緒狀態(tài)B)阻塞狀態(tài)C)運(yùn)行狀態(tài)D)撤消狀態(tài)85共6頁(yè)第4頁(yè)A)重名翻譯機(jī)構(gòu)B)建立索引表C)建立指針D)多級(jí)目錄結(jié)構(gòu)A)分區(qū)式B)分頁(yè)式C)分段式D)段頁(yè)式A)地址動(dòng)態(tài)重定位B)時(shí)鐘管理C)進(jìn)程調(diào)度D)中斷系統(tǒng)A)磁盤(pán)B)磁帶C)打印機(jī)D)鍵盤(pán)、顯示終端二、填空題(每空1分，共5分)三、問(wèn)答題(共15分，每題1分)1、已知某分頁(yè)系統(tǒng)，主存容量為64K,頁(yè)面大小為1K,對(duì)一個(gè)4頁(yè)大的作業(yè)，其0、1、2、3頁(yè)分別被分配到主存的2、4、6、7塊中。則十進(jìn)制的邏輯地查找時(shí)間，實(shí)行電梯算法(初始由外向里移動(dòng))需要查找時(shí)間(假定磁指令。塊號(hào)頁(yè)號(hào)訪問(wèn)時(shí)間修改位01232103塊號(hào)頁(yè)號(hào)訪問(wèn)時(shí)間修改位012321030011001FIFO算法(8)塊將被換出，使用CLOCK算法(9)塊將被換出加載時(shí)間a)每個(gè)信號(hào)量的初值應(yīng)該是多少?b)填寫(xiě)下面的P、V操作讀者進(jìn)入閱覽室的動(dòng)作描述填寫(xiě)登記表；進(jìn)入閱覽室讀書(shū)；}四、簡(jiǎn)單題(25分，每題5分)2010年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院825計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)B[專(zhuān)業(yè)碩士]考研真題2010年碩士學(xué)位研究生入學(xué)考試試題第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(75分)一、選擇題(每題2分，共20分)1.算法的空間復(fù)雜度是指()。A)B)C)D)結(jié)點(diǎn)的()。7.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有()條邊。9.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表。二、填空題(每空1分，共10分)7.以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù)的帶權(quán)路9.一組記錄的排序值為{25,48,16,35,79,82,23,40,36,72},請(qǐng)給出三、簡(jiǎn)答題(共6題，共35分)1.(4分)簡(jiǎn)述二叉樹(shù)的定義。2.(5分)簡(jiǎn)述拓?fù)渑判虻母拍詈屯負(fù)渑判虻倪^(guò)程。3.(7分)一個(gè)二叉樹(shù)如下圖所示：4.(6分)已知無(wú)向圖G如下圖所示：(1)請(qǐng)畫(huà)出該無(wú)向圖G的鄰接矩陣表示。(3分)(2)請(qǐng)畫(huà)出該無(wú)向圖G的鄰接表表示。(3分)(3)列出所有關(guān)鍵活動(dòng)。(2分)6.(5分)設(shè)有一組關(guān)鍵字{6,01,36,14,29,20,84,27,68,11,10,70},四、算法設(shè)計(jì)題(共2題，共10分)編寫(xiě)在該單鏈表中刪除一個(gè)最小值結(jié)點(diǎn)的算法voidDelMinNode(LinkListtypedefstruct{基于上述類(lèi)型模塊，寫(xiě)出循環(huán)隊(duì)列出隊(duì)算法intDeQueue(SqQueue&Q,第二部分操作系統(tǒng)(75分)一、選擇題(每一選項(xiàng)1分，共15分)A)尺寸從小到大B)尺寸從大到小C)地址從小到大D)地址從大到小A)一個(gè)進(jìn)程多次申請(qǐng)，釋放該資源B)若干并A)主存與外設(shè)B)CPU與外設(shè)C)外設(shè)與外設(shè)D)CPU與輔存A)允許有兩個(gè)B)可以有多個(gè)C)最多有1個(gè)D)至少有1個(gè)量15、設(shè)有12個(gè)同類(lèi)資源可供四個(gè)進(jìn)程共享，目前剩余資源數(shù)為2?，F(xiàn)資源分配2332333進(jìn)程P46742341P.1P當(dāng)進(jìn)程P,P?,P,P,滿足的要求。二、填空題(本大題共10小空，每空1分，共10分)(1)采用先進(jìn)先出(FIFO)淘汰算法，缺頁(yè)次數(shù)是(3)(2)采用最進(jìn)最少使用(LRU)淘汰算法，缺頁(yè)次數(shù)是(4)(3)若用優(yōu)化(0PT)算法，則次數(shù)是(5)4、假定一磁盤(pán)有200個(gè)磁道，編號(hào)是0至199,在完成了磁道143處的請(qǐng)求后，當(dāng)用FCFS(先來(lái)先服務(wù)),最短尋道時(shí)間優(yōu)先(SSTF)和掃描(SCAN,按磁道號(hào)遞增移動(dòng))來(lái)按排磁頭移動(dòng)時(shí)，其移動(dòng)的總量分別是(6),三、概念填空，從供選擇的答案選出最確切的答案填入下面敘述中的內(nèi)(1*16分)1、A以操作系統(tǒng)為支