【正文】 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14E 0 0 5 6 6 12 12 12 19 19 16 20 23 25L 4 0 9 6 16 12 19 16 19 19 23 20 23 25LE 4 0 4 0 10 0 7 4 0 0 7 0 0 0事件最早最遲開(kāi)始時(shí)間 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10VE 0 5 6 12 19 16 20 23 25 27VL 0 9 6 12 19 23 20 23 25 27 畫(huà)出進(jìn)行分塊查找的數(shù)據(jù)組織形式。解:設(shè)將數(shù)據(jù)分成4塊，每塊中記錄個(gè)數(shù)5， 先查找索引值97451 97517 97528 97543第1塊 2 3 497321,97421,97451,97241,9711897250,97407,97239,97227,9751797438,97102,9752897136,0733897543,97309 畫(huà)一棵對(duì)20個(gè)記錄進(jìn)行對(duì)分查找的判定樹(shù),并求等概率情況下的平均查找長(zhǎng)度。ASL=(1+2*2+3*4+4*8+5*5)/20= 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：向量和鏈表。本質(zhì)區(qū)別：向量是連續(xù)存放的，其存儲(chǔ)空間是靜態(tài)分配的，以存放順序來(lái)表達(dá)元素的前后件的關(guān)系。 鏈?zhǔn)酱鎯?chǔ)結(jié)果不需要一組連續(xù)的存儲(chǔ)單元，其數(shù)據(jù)元素可以分散存放在存儲(chǔ)空間中，其元素關(guān)系由指針來(lái)指向。 試比較順序表和鏈表的優(yōu)缺點(diǎn)。1. 線(xiàn)性表的長(zhǎng)度是否固定方面：由于向量的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，因此若表長(zhǎng)不固定時(shí)采用線(xiàn)性鏈表較好。2. 線(xiàn)性表的主要操作是什么：由于向量是連續(xù)存放的，所以適用于查找操作，不適用插入、刪除操作。由于線(xiàn)性鏈表只能順序存取，所以適用于插入、刪除操作，不適用于查找操作。3. 采用的算法語(yǔ)言：線(xiàn)性鏈表要求所使用的語(yǔ)言工具提供指針類(lèi)型變量。 試比較單向鏈表與雙向鏈表的優(yōu)缺點(diǎn)。1. 單向鏈表只能單方向地尋找表中的結(jié)點(diǎn)，雙向鏈表具有對(duì)稱(chēng)性，從表中某一給定的結(jié)點(diǎn)可隨意向前或向后查找。2. 在作插入、刪除運(yùn)算時(shí)，雙向鏈表需同時(shí)修改兩個(gè)方向上的指針，單向鏈表則簡(jiǎn)便些。 試說(shuō)明樹(shù)與二叉樹(shù)有何不同？為何要將一般樹(shù)轉(zhuǎn)換為二叉樹(shù)？樹(shù)與二叉樹(shù)區(qū)別：樹(shù)是由n個(gè)（n=0）結(jié)點(diǎn)組成的有限集合T，其中有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，在此類(lèi)元素結(jié)點(diǎn)之間存在明顯的分支和層次關(guān)系。二叉樹(shù)是一種特殊的樹(shù)結(jié)構(gòu)，每一個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子，即最多只有兩個(gè)分支。為何要轉(zhuǎn)換：一般樹(shù)，樹(shù)中結(jié)點(diǎn)次序沒(méi)有要求，分支龐雜。而二叉樹(shù)，元素之間存在嚴(yán)謹(jǐn)?shù)那昂蟠P(guān)系，在對(duì)數(shù)據(jù)元素進(jìn)行刪除、查找、插入等運(yùn)算時(shí)更加有效率。 若一棵排序二叉樹(shù)的關(guān)鍵字輸入序列為{80，6，10，7，8，25，100，90}，請(qǐng)畫(huà)出該二叉樹(shù)。解：二叉排序樹(shù)為： 80610090107258 對(duì)于關(guān)鍵字序列{49，38，65，97，76，13}，回答下述問(wèn)題。（共12分）（1）寫(xiě)出一趟冒泡排序的結(jié)果。（6分）（2）寫(xiě)出一趟快速排序的結(jié)果。參考答案如下：（1）寫(xiě)出一趟冒泡排序的結(jié)果。（6分）{38,49,65,76,13,97}（2）寫(xiě)出一趟快速排序的結(jié)果。（6分）{13,38,49,97,76,65} 請(qǐng)給出圖1的所有最小生成樹(shù)。（10分）aebdfc1238665圖1 答：共有兩顆： aebdfc12365aebdfc123665 。（16）圖2abdfgceh答案如下：僅有兩個(gè)第一個(gè)：abcdefgh 第二個(gè)：abcdegfh ：A B C D E F G和中序遍歷序列為：C B E D A F G。請(qǐng)畫(huà)出該二叉樹(shù)。答案如下：。aefgdbhc21111222243 圖的最小生成樹(shù)如下aefgdbhc2111122 第三章 操作系統(tǒng)的基本功能是什么？它包括哪些部分？ 基本功能： 操作系統(tǒng)應(yīng)該具有處理器管理，存儲(chǔ)管理，設(shè)備管理和文件管理功能，同時(shí)，為了使用戶(hù)能方便地使用機(jī)器，操作系統(tǒng)還應(yīng)提供用戶(hù)接口功能。 構(gòu)成部分： （1）. 對(duì)CPU的使用進(jìn)行管理的進(jìn)程調(diào)度程序 。 （2）. 對(duì)內(nèi)存分配進(jìn)行管理的內(nèi)存管理程序。 （3）. 對(duì)輸入輸出設(shè)備進(jìn)行管理的設(shè)備驅(qū)動(dòng)程序。（4） . 對(duì)外存中信息進(jìn)行管理的文件系統(tǒng)。 試說(shuō)明虛擬機(jī)的概念以及實(shí)現(xiàn)的方法。在裸機(jī)外面每增加一個(gè)軟件層后就會(huì)變成一臺(tái)功能更強(qiáng)的機(jī)器，我們通常把這種計(jì)算機(jī)系統(tǒng)稱(chēng)為虛擬機(jī)。 虛擬機(jī)的實(shí)現(xiàn)方法：在裸機(jī)上裝上操作系統(tǒng)對(duì)機(jī)器進(jìn)行首次擴(kuò)展，再在操作系統(tǒng)的基礎(chǔ)上增加其他軟件，這樣就可以實(shí)現(xiàn)“虛擬機(jī)”。？各有什么特點(diǎn)及適用于何種場(chǎng)合？三大類(lèi)：（1）多道批處理系統(tǒng)：計(jì)算機(jī)內(nèi)存中同時(shí)可以存放多道作業(yè)，用戶(hù)與作業(yè)之間沒(méi)有交互作用，用戶(hù)不能直接控制作業(yè)的運(yùn)行。此類(lèi)系統(tǒng)一般用于計(jì)算中心等較大型的計(jì)算機(jī)系統(tǒng)中。（2）分時(shí)系統(tǒng)：多個(gè)用戶(hù)通過(guò)終端分享同一臺(tái)計(jì)算機(jī)，并通過(guò)終端直接控制程序運(yùn)行，進(jìn)行人與機(jī)器之間的交互。此類(lèi)系統(tǒng)適用于程序的開(kāi)發(fā)。（3）實(shí)時(shí)系統(tǒng)：對(duì)外部發(fā)生的隨機(jī)事件作出及時(shí)的響應(yīng)，并對(duì)它進(jìn)行處理。此類(lèi)系統(tǒng)一般用于工業(yè)控制系統(tǒng)或事物處理系統(tǒng)。Windows系統(tǒng)：多用戶(hù)多任務(wù)操作系統(tǒng)。特點(diǎn)：全新的、友善的用戶(hù)界面。 提供了功能強(qiáng)大的應(yīng)用程序。 具有多任務(wù)并行處理能力，各種應(yīng)用程序之間可以方便地進(jìn)行切換和交換信息。 具有強(qiáng)大的內(nèi)存管理能力，支持?jǐn)U展內(nèi)存功能，提高系統(tǒng)運(yùn)行效率。 解釋名空間、作業(yè)地址空間和存儲(chǔ)空間的關(guān)系以及邏輯地址和物理地址的區(qū)別。存放源程序的空間稱(chēng)為名空間。當(dāng)匯編或編譯程序?qū)⒃闯绦蜣D(zhuǎn)換成目標(biāo)程序后，一個(gè)目標(biāo)程序所占有的地址范圍稱(chēng)為地址空間，這些地址的編號(hào)是相對(duì)于起始地址而定的，一般定起始位零，稱(chēng)為邏輯地址或相對(duì)地址。存儲(chǔ)空間是指當(dāng)目標(biāo)程序裝入主存后占用的一系列物理單元的集合，這些單元編號(hào)稱(chēng)為物理地址或絕對(duì)地址。 什么是重定位？靜態(tài)重定位和動(dòng)態(tài)重定位的區(qū)別是什么？各舉一例說(shuō)明。當(dāng)用戶(hù)程序要調(diào)入內(nèi)存時(shí)，必須把相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，同時(shí)要包括對(duì)程序中與地址有關(guān)的指令進(jìn)行修改，這一過(guò)程稱(chēng)為重定位。靜態(tài)重定位是在程序裝入時(shí)進(jìn)行，一般通過(guò)處理機(jī)中一對(duì)界地址寄存器來(lái)實(shí)現(xiàn)。動(dòng)態(tài)重定位是在程序執(zhí)行過(guò)程中進(jìn)行的，當(dāng)處理器訪(fǎng)問(wèn)主存指令時(shí)由動(dòng)態(tài)變換機(jī)構(gòu)自動(dòng)進(jìn)行地址轉(zhuǎn)換。 存儲(chǔ)管理器的功能是什么？為什么要引入虛擬存儲(chǔ)器的概念？虛存的容量由什么決定？存儲(chǔ)管理的功能主要分為：內(nèi)存分配、地址轉(zhuǎn)換、存儲(chǔ)保護(hù)和內(nèi)存擴(kuò)充。虛擬存儲(chǔ)器能提供給用戶(hù)一個(gè)比實(shí)際內(nèi)存大得多的存儲(chǔ)空間，使用戶(hù)在編制程序時(shí)可以不必考慮存儲(chǔ)空間的限制。虛存的容量受兩個(gè)條件約束：指令中地址場(chǎng)長(zhǎng)度的限制、外存儲(chǔ)器容量的限制。 什么是作業(yè)、作業(yè)步和進(jìn)程？作業(yè)是用戶(hù)在一次算題過(guò)程中或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做的集合。一個(gè)作業(yè)是由一系列有序的作業(yè)步所組成。一個(gè)作業(yè)步運(yùn)行的結(jié)果產(chǎn)生下一個(gè)作業(yè)步所需的文件。進(jìn)程可以看成是程序的一次執(zhí)行，即是在指定內(nèi)存區(qū)域的一組指令序列的執(zhí)行過(guò)程。 處理器管理主要解決什么問(wèn)題？在大型通用系統(tǒng)中，可能數(shù)百個(gè)批處理作業(yè)存放在磁盤(pán)中，又有數(shù)百個(gè)終端用戶(hù)與主機(jī)聯(lián)接，如何從這些作業(yè)中挑選一些作業(yè)進(jìn)入主存運(yùn)行，又如何在主存各進(jìn)程間分配處理器，是操作系統(tǒng)資源管理的一個(gè)重要問(wèn)題，處理器管理就是用來(lái)解決此問(wèn)題的。 什么是進(jìn)程的同步和互斥？什么是臨界區(qū)？ “同步”是指兩個(gè)事件的發(fā)生存在某種時(shí)序上的關(guān)系，如果系統(tǒng)中有若干個(gè)進(jìn)程要共同完成某一任務(wù)，那么它們相互之間必須協(xié)調(diào)配合?！盎コ狻笔侵府?dāng)多個(gè)進(jìn)程要求共享系統(tǒng)中某些硬件或軟件資源，而這些資源卻又要求排它性使用時(shí)，這樣往往引起由于多個(gè)進(jìn)程競(jìng)爭(zhēng)同一資源使運(yùn)行結(jié)果出現(xiàn)問(wèn)題。如果在兩個(gè)進(jìn)程PP2中加入P、V操作后，可以實(shí)現(xiàn)對(duì)公用變量count的互斥使用。其中P（s）、V（s）之間的程序段稱(chēng)為臨界區(qū)。 進(jìn)程間的通信可以由哪些方式進(jìn)行？低級(jí)通信方式：PV操作。高級(jí)通信方式：直接通信