華南理工考研計算機歷年真題.doc

《華南理工考研計算機歷年真題.doc》由會員分享，可在線閱讀，更多相關《華南理工考研計算機歷年真題.doc（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

華南理工大學2004年攻讀碩士學位研究生入學考試試卷 （試卷上做答無效，請在答題紙上做答，試后本卷必須與答題紙一同交回） 科目名稱：計算機專業(yè)綜合一(組成原理、數(shù)據(jù)結(jié)構、操作系統(tǒng)) 適用專業(yè)：計算機系統(tǒng)結(jié)構、計算機應用技術、軟件工程、計算機應用技術 I. 計算機組成原理試題 （50分） 一．填空題（共10分） 1．計算機的工作過程主要是周而復始地　A　、　B　和　C　的過程。 2．在浮點運算中，當運算結(jié)果階碼大于所能表示的　A　時稱為溢出，若階碼用雙符號S0′S0的移碼表示，則當S0′S0 =　B　時為溢出。 3．雙端口存儲器和多模塊交叉存儲器屬于 A 存儲器結(jié)構；前者采用 B 并行技術，后者采用 C 并行技術。 4．在微程序控制器中，一般采用較簡單的 A 、 B 二級時序體制。 5．CPU響應中斷時保護兩個關鍵的硬件狀態(tài)是 A 和 B 。 2． 選擇題（共6分） 1．設浮點數(shù)的階為8位（其中1位階符），用移碼表示，尾數(shù)為24位（其中1位數(shù)符），用原碼表示。則它所能表示的最大規(guī)格化正數(shù)是（　　）。 　　 A．(27-1)×(1-2-23 )　　　　　　 　　 B． ×(1-2-23 ) 　　 C． ×(1-2-23 ) 　 D． ×(1-2-22 ) 2．下列說法正確的是（　?。? A. 微程序控制方式和硬布線方式相比較，前者可以使指令的執(zhí)行速度更快 B. 若采用微程序控制方式，則可用μPC取代PC C. 控制存儲器可以用ROM實現(xiàn) D. 指令周期也稱為CPU周期 3．下列說法正確的是（ ）。 A. 程序中斷過程是由硬件和中斷服務程序共同完成的 B. 每條指令的執(zhí)行過程中，每個總線周期要檢查一次有無中斷請求 C. 檢測有無DMA請求，一般安排在一條指令執(zhí)行過程的末尾 D. 中斷服務程序的最后指令是無條件轉(zhuǎn)移指令 三．完成下列各題（共36分） 1．設[A]補＝an-1an-2…a1 a0，式中an-1為補碼符號位，求證真值： （8分） 2．假設主存只有a，b，c三個頁框，組成a進c出的FIFO隊列進程，訪問頁面的序列是0，1，3，4，3，2，0，2，1，3，2號。若采用：①FIFO算法；②FIFO+LRU算法。用列表法求以上兩種策略的命中率。 （12分） 3．某CPU的部分數(shù)據(jù)通路如圖1所示。WA和WB是分別寫入寄存器A和B的控制信號。WA和WB能否包含在一條微指令中？為什么？如要將WA和WB包含在一條微指令中，要采取什么措施？（10分） 4．在圖2中，當CPU對設備B的中斷請求進行服務時，設備A能否提出中斷請求？為什么？如果設備B一提出中斷請求總能立即得到服務，問怎樣調(diào)整才能滿足此要求？ （10分） II 數(shù)據(jù)結(jié)構試題 （50分） · 填空題?（每小題2分，共16分） 1． 若用兩個堆棧實現(xiàn)隊列操作，在隊中插入或刪除一個元素的時間復雜性是__________。 2． 在向量存儲的二叉樹中，根結(jié)點編號為1，則編號為i和j的兩個結(jié)點處在同一層的條件是 _____________。 3． n個頂點的無向圖G每個頂點的度最大可能是__________。 4． 高度為5的3階B樹至少有__________結(jié)點。 5． 已知A為n階（n>=1）的對稱矩陣，現(xiàn)將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。矩陣元素Aij (i >=j ) 在B中的下標是__________。 6． 用鄰接矩陣求最短路徑的Floyd算法的時間復雜性為__________。 7． 若一個無向圖有n個頂點，e條邊(n>e)，且是一個森林。則它有__________棵樹。 8．對n個元素進行歸并排序，需要的輔助空間為__________。 二． 解答題（共14分） 1． 一棵樹的先序和后序序列分別如下，畫出該樹。（3分） 先序序列：ABCDEFGHIJKLM 后序序列：CDBEFGJKLMIHA 2． 對下面的遞歸算法，寫出調(diào)用f(4)的執(zhí)行結(jié)果。（3分） void f(int k) { if( k>0 ) { printf("%d ",k); f(k-1); f(k-1); } 華南理工大學2005年計算機綜合431考研試卷 數(shù)據(jù)結(jié)構（75分） 一． 選擇題（每題只有一個答案正確，每題2分，共24分） 1. 廣義表A=（a,b,c,(d, (e,f))），則下面式子的值為 ；(Head與Tail分別是取表頭和表尾的函數(shù)) Head(Tail(Tail(Tail(A)))) A．(d,(e,f)) B. d C.f D.(e,f) 2. 一棵深度為4的完全二叉樹，最少有________個結(jié)點。 A. 4 B. 8 C. 15 D. 6 3. 稀疏矩陣一般的壓縮存儲方法有兩種，即_______。 A．二維數(shù)組和三維數(shù)組 B．三元組表和散列 C．三元組表和十字鏈表 D．散列和十字鏈表 4. 下列判斷中，______是正確的。 A. 二叉樹就是度為2的樹 B. 二叉樹中不存在度大于2的結(jié)點 C. 二叉樹是有序樹 C. 二叉樹的每個結(jié)點的度都為2 5. 在構造哈希表方面，下面的說法_________是正確的。 A．鏈地址法在處理沖突時會產(chǎn)生聚集 B．線性探測再散列在處理沖突時會產(chǎn)生聚集 C．好的哈希函數(shù)可以完全避免沖突 D．在哈希表中進行查找是不需要關鍵字的比較的 6. 以下圖的敘述中，正確的是_______。 A．強連通有向圖的任何頂點到其它所有頂點都有弧 B．任意圖頂點的入度等于出度 C．有向完全圖一定是強連通有向圖 D. 有向圖的邊集的子集和頂點集的子集可構成原有向圖的子圖 7. 一棵共有n個結(jié)點的樹，其中所有分枝結(jié)點的度均為k，則該樹中葉子結(jié)點的個數(shù)為________。 A．n(k-1)/k B．n-k C．(n+1)/k D．(nk-n+1)/k 8. 具有n個頂點的無向圖至多有_____條邊。 A．n-1 B．n(n-1)/2 C. n(n+1)/2 D. n2/2 9. 深度為4 的101階B樹，最少有______個結(jié)點。 A. 154 B. 105 C. 103 D. 151 10. 利用逐點插入法建立序列(60，74，44，99，75，30，36，45，68，9)對應的二叉排序樹以后，查找元素75要進行______元素間的比較。 A．4次 B．3次 C. 7次 D．5次 11. 對數(shù)據(jù)結(jié)構，下列結(jié)論中不正確的是_____。 A． 相同的邏輯結(jié)構，對應的存儲結(jié)構也必相同 B． 數(shù)據(jù)結(jié)構由邏輯結(jié)構、存儲結(jié)構和基本操作三個方面組成 C． 數(shù)據(jù)存儲結(jié)構就是數(shù)據(jù)邏輯結(jié)構的機內(nèi)的實現(xiàn) D． 對數(shù)據(jù)基本操作的實現(xiàn)與存儲結(jié)構有關 12. 對AOE網(wǎng)的關鍵路徑，下面的說法_______是正確的。 A．提高關鍵路徑上的一個關鍵活動的速度，必然使整個工程縮短工期 B．完成工程的最短時間是從始點到終點的最短路徑的長度 C．一個AOE網(wǎng)的關鍵路徑只有一條，但關鍵活動可有多個 D．任何一項活動持續(xù)時間的改變都可能會影響關鍵路徑的改變 二． 解答題（每題4分，共40分） 1. 設有關鍵字序列為：{ 50，71，80，60，55，40，25，99 }，用數(shù)組存儲。請以堆排序方式把數(shù)據(jù)排列成遞增序列。給出建堆和每趟堆調(diào)整后的數(shù)據(jù)序列。 解：建堆后的數(shù)據(jù)序列 每趟堆調(diào)整后的數(shù)據(jù)序列 2. 畫出下列矩陣的三元組表示法和十字鏈表表示法。 0 0 0 0 0 8 0 1 4 0 0 0 0 0 2 0 0 2 5 0 3. 畫出下圖的鄰接表，并用克魯斯卡爾算法求其最小生成樹。 4. 有以下算法，分析其時間復雜度。 i=1; while(i*i*i<=n) i++; 5． 循環(huán)隊列A[m]中，已知頭指針rear、尾指針front與元素個數(shù)len中的任意兩個，如何求另一個？ 6． 某完全二叉樹有360個結(jié)點，則葉子數(shù)有多少？度1結(jié)點有多少？ 7． 哪些排序思想或方法在排序過程中產(chǎn)生連續(xù)增長的有序子序列？ 8． 圖的遍歷（廣度優(yōu)先或深度優(yōu)先）生成樹是否唯一？與什么因素有關？什么情況下是唯一的？ 9． 求在8個結(jié)點的有序表中進行二分查找，等概率下查找成功和不成功時的平均查找長度 10．外部排序的時間由什么因素決定？為了減少外部排序時間，有什么方法？ 三．算法設計。做出簡要分析并寫函數(shù)。（共11分） 1． 設一個由字母組成的字符串，編寫算法對它們的字母順序進行調(diào)整，使輸出時所有大寫字母都在小寫字母之前，并且同類字母之間的相對位置不變。（5分） 例如，原有字符串為：AbcDEfghiJKlmn 輸出序列為： ADEJKbcfghilmn 2． 編寫算法，由無向圖的鄰接表生成鄰接矩陣。（6分） 操作系統(tǒng)（75分） 一、名詞解釋(15分) 1．臨界區(qū) 2．用戶級線程 3．并行交叉存取 二、一個線程是否可被時鐘中斷搶占？如果是，請說明在什么情況下可被搶占，否則請解釋為什么。（5分） 三、UNIX中對信號的處理有哪幾種方式？（6分） 四、在非搶占式調(diào)度方式中，什么情況下正在運行的進程會放棄CPU？（6分） 五、試說明中斷處理的主要過程。（6分） 六、試解釋成組鏈接法是如何管理文件系統(tǒng)中的空閑塊的？（10分） 七、在數(shù)據(jù)傳輸過程中為什么要進行數(shù)字簽名？試介紹簡單數(shù)字簽名的過程。簡單數(shù)字簽名能否達到保密的目的？為什么？（12分） 八、設有一進程共有5頁（0-4），其中程序占3頁（0-2），常數(shù)占1頁（3），工作單元占1頁（4），它們依次存放在外存的第45、46、98、99和100塊?，F(xiàn)在程序段已分配在內(nèi)存的第7、10、19頁，而常數(shù)區(qū)和工作區(qū)尚未獲得內(nèi)存，請回答下述問題： 1） 頁表應包括那些項目？填寫此頁表。若工作區(qū)分配到內(nèi)存的第9頁，則頁表應如何變化 2） 在運行中因需要使用常數(shù)而發(fā)生中斷，假定此時內(nèi)存無空閑頁面，需要把第9頁淘汰，操作系統(tǒng)應如何處理？頁表又發(fā)生什么變化？（15分） 華南理工大學2006年計算機專業(yè)綜合(431)考研試卷 數(shù)據(jù)結(jié)構 一． 選選擇題（每題只有一個答案正確，每題2分，共26分） 1. 以下圖的敘述中，正確的是_______。 A．圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點數(shù) B．假設有圖G=(V, {E}), 頂點集V’íV，E’ íE，則V’和{E’}構成G的子圖 C．無向圖的連通分量指無向圖中的極大連通子圖 D. 圖的遍歷就是從圖中某一頂點出發(fā)訪遍圖中其余頂點 2. 下列判斷中，______是正確的。 A. 深度為k的二叉樹最多有2k-1個結(jié)點(k≥1)，最少有k個結(jié)點 B. 二叉樹中不存在度大于2的結(jié)點 C. 對二叉樹遍歷是指先序、中序或后序遍歷中的一種 D. 構造線索二叉樹是為能方便找到每個結(jié)點的雙親 3. 對各種內(nèi)部排序方法來說，__________。 A. 快速排序時間性能最佳 B. 基數(shù)排序和歸并排序是穩(wěn)定的排序方法 C. 快速排序是一種選擇排序 D. 堆排序所用的輔助空間比較大 4. 稀疏矩陣的三元組存儲方法_______。 A．實現(xiàn)轉(zhuǎn)置運算很簡單，只需將每個三元組中的行標和列標交換 B．是一種鏈式存儲方法 C．矩陣的非零元個數(shù)和位置在操作過程中變化不大時較有效 D．比十字鏈表法更高效 5. 對于二叉排序樹，下面的說法_______是正確的。 A．二叉排序樹是動態(tài)樹表，查找不成功時插入新結(jié)點時，會引起樹的重新分裂和組合 B．對二叉排序樹進行層序遍歷可得到有序序列 C．用逐點插入法構造二叉排序樹時，若先后插入的關鍵字有序，二叉排序樹的深度最大 D．在二叉排序樹中進行查找，關鍵字的比較次數(shù)不超過結(jié)點數(shù)的1/2 6. 在構造哈希表方面，下面的說法_________是正確的。 A．再哈希法在處理沖突時不會產(chǎn)生聚集 B．哈希表的裝填因子越大說明空間利用率越好，因此應使裝填因子盡量大 C．哈希函數(shù)選的好可減少沖突現(xiàn)象 D．對任何具體關鍵字集都不可能找到不產(chǎn)生沖突的哈希函數(shù) 7. 已知廣義表(( ),(a), (b, c, (d), ((d, f))))，則以下說法正確的是__________。 A．表長為3，表頭為空表，表尾為((a), (b, c, (d), ((d, f)))) B．表長為3，表頭為空表，表尾為(b, c, (d), ((d, f))) C．表長為4，表頭為空表，表尾為((d, f)) D．表長為3，表頭為(())，表尾為((a), (b, c, (d), ((d, f)))) 8. 已知一棵5階B樹有53個關鍵字，并且每個結(jié)點的關鍵字都達到最少狀態(tài)，則它的深度是________。 A. 3 B. 4 C. 5 D. 6 9. 一個有向圖，共有n條弧，則所有頂點的度的總和為_______。 A．2n B. n C. n-1 D. n/2 10. 對鄰接表的敘述中，_____是正確的。 A．無向圖的鄰接表中，第i個頂點的度為第i個鏈表中結(jié)點數(shù)的二倍 B．鄰接表比鄰接矩陣的操作更簡便 C．鄰接矩陣比鄰接表的操作更簡便 D．求有向圖結(jié)點的度，必須遍歷整個鄰接表 11. 一棵二叉樹中序序列為FEABDC，后序序列為FBADCE，則層序序列為_____。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 12. 以下說法中，________是正確的。 A. 完全二叉樹中，葉結(jié)點的雙親的左兄弟（如果存在）一定不是葉結(jié)點 B. 任何一棵二叉樹，終端結(jié)點數(shù)為度為2的結(jié)點數(shù)減1 C. 二叉樹不適合用順序結(jié)構存儲 D. 結(jié)點按層序編號的二叉樹，第i個結(jié)點的左孩子（如果存在）的編號為2i 13. 給定一組關鍵字{4，26，46，12，9，33}，哈希函數(shù)為H(key)=key MOD 6，則用線性探測再散列方法來處理沖突，則構造此哈希表共需要比較關鍵字____次。 A. 4 B. 5 C. 6 D. 7 二． 解答題（每題4分，共36分） 1. 線性表的雙向鏈表的存儲結(jié)構為： typedef struct DNode { TElem info; struct DNode *left; struct DNode *right; }; 并假設已建立頭指針為head的雙向鏈表，p指向其中某個結(jié)點，寫一個程序段，從該循環(huán)鏈表中刪除p所指向結(jié)點的前一個結(jié)點(假設該結(jié)點存在)。 2. 簡述在AOV網(wǎng)中求拓撲排序的過程，并寫出下面AOV網(wǎng)中的兩個拓撲有序序列 3. 給出下面有向圖的鄰接矩陣、鄰接表及逆鄰接表。 4. 假定字符集{a, b, c, d, e, f}中的字符在通信網(wǎng)絡中出現(xiàn)的頻率見下表，請設計赫夫曼編碼。 字符 a b c d e f 頻率 0.10 0.23 0.36 0.11 0.15 0.05 5．對n個頂點的無向圖G，采用鄰接矩陣表示，如何判別下列問題； (1)圖中有多少條邊？ (2)任意兩個結(jié)點i和j是否有邊相連？ (3)任意一個頂點的度是多少？ 6．對下圖所示的AOE網(wǎng)，回答：工程完成的最短時間是多少？寫出關鍵路徑（不需過程），是否有某些活動提高速度后能導致整個工程縮短工期？ 7. 已知Q是一個非空隊列 ，S是一個空棧。僅用隊列和棧的ADT函數(shù)，用C語言偽碼編寫一個算法，將隊列Q中的所有元素逆置。 棧的ADT函數(shù)有： makeEmpty(stack s); 置空棧 push(stack s，datatype value); 新元素value進棧 datatype pop(stack s) 出棧，返回棧頂值 boolean isEmpty(stack s) 判?？辗? 隊列的ADT函數(shù)有 enQueue(queue q, datatype value) 元素value進隊 datatype deQueue(queue q) 出隊列，返回隊頭值 boolean isEmpty(queue q) 判隊列空否 8．你所知道的排序方法有幾類？簡述各類方法的原理。 9．在為一個實際應用設計數(shù)據(jù)結(jié)構時，主要應考慮哪些方面的內(nèi)容？ 三． 算法設計。做出簡要分析并寫函數(shù)。（共13分） 1. 以二叉鏈表作存儲結(jié)構，試編寫非遞規(guī)的前序遍歷算法。(5分) 2. 無向圖用鄰接表存儲，寫出鄰接表定義，給出求圖中頂點Vi到 Vj的最短路徑的函數(shù)。（8分） 操作系統(tǒng) 一、名詞解釋：（18分） 1． 進程 2． Spooling技術 3． 系統(tǒng)調(diào)用 4． 死鎖 5． 并發(fā) 6． 缺頁中斷 二、有3個并發(fā)進程R、M、P，它們共享同一個緩沖區(qū)，假定緩沖區(qū)只能存放一條記錄。進程R負責從輸入設備讀信息，每讀入一個記錄后，就把它放進緩沖區(qū)；進程M在緩沖區(qū)中加工讀入的記錄；進程P把加工后的記錄打印輸出。讀入的記錄經(jīng)加工輸出后，緩沖區(qū)又可以存放下一個記錄。試寫出他們能夠正確執(zhí)行的并發(fā)程序。（10分） 三、在某頁式管理系統(tǒng)中，假定主存為64K,分成16塊，塊號為0，1，2，…，15。設某進程有４頁，其頁號為0，1，2，3，被分別裝入主存的第9、0、1、14塊。試問：（10分） １） 該進程的總長度是多大？ ２） 寫出該進程每一頁在主存中的起始地址。 ３）若給出邏輯地址［0，0］、［1，72］、［2，1023］、［3，99］，請計算出相應的內(nèi)存地址。（方括號內(nèi)的第一個數(shù)為頁號，第二個數(shù)為頁內(nèi)地址，題目中的數(shù)字均為10進制）。 四、I/O控制可用哪幾種方式，各有什么優(yōu)缺點？（8分） 五、某軟盤有40個磁道，磁頭從一個磁道移到另一個磁道需要6ms。文件在磁盤上非連續(xù)存放，邏輯上相鄰的數(shù)據(jù)塊的平均距離為13個磁道，每塊的旋轉(zhuǎn)延遲時間及傳輸時間分別為100ms和25ms。問：（8分） 1） 讀取一個100塊的文件需要多少時間？ 2） 如果對磁盤進行整理使得同一文件的磁盤塊盡可能靠攏，從而使邏輯上相鄰的數(shù)據(jù)塊的平均距離降為2個磁道，這時讀取100塊的文件有需要多少時間？ 六、兩個進程A和B，每一個進程都需要讀取數(shù)據(jù)庫中的記錄1、2、3假如這兩個進程都以1、2、3的次序請求讀取記錄，系統(tǒng)將不會發(fā)生死鎖。但如果A以3、2、1的次序讀取記錄，B以1、2、3的次序讀取記錄，則死鎖可能會發(fā)生。試計算兩個進程讀取記錄的次序如果不確定，那么系統(tǒng)保證不發(fā)生死鎖的概率是多少？（6分） 七、為什么需要一個打開文件的系統(tǒng)調(diào)用？一般來講打開文件的系統(tǒng)調(diào)用主要做了些什么？（7分） 八、試說明UNIX操作系統(tǒng)中文件系統(tǒng)的權限是如何控制的（8分） 華南理工大學2007年計算機專業(yè)綜合431考研試卷 數(shù)據(jù)結(jié)構 一、 選擇題（每小題2分，共20分） 1． 折半查找法的時間復雜度是（ ）。 A、 O(n2) B、O(n) C、O(nlog2n) D、O(log2n) 2． 若一個棧的輸入序列是1，2，...，n，輸出的第一個元素是n，則第i個輸出的元素是（ ）。 A、n-i B、i C、n-i+1 D、n-i-1 3． 如果環(huán)形鏈表結(jié)構如圖1所示，則表達式p->next->next的值是（ ）。 A、15 B、32 C、78 D、全不是 圖1 4． 一個n×n的對稱矩陣，如果以行或列為主序放入內(nèi)存，其容量為（ ）。 A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2 5． 快速排序在（ ）情況下最不利于發(fā)揮其長處。 A、被排序的數(shù)據(jù)量太大 B、被排序的數(shù)據(jù)中有大量相同 C、被排序的數(shù)據(jù)基本有序 D、被排序的數(shù)據(jù)太分散 6． 具有線性結(jié)構的數(shù)據(jù)結(jié)構是（ ）。 A、文件結(jié)構 B、樹結(jié)構 C、圖結(jié)構 D、廣義表 7． 在下列網(wǎng)中，（ ）是邊不帶權值的圖。 A、郵電網(wǎng) B、AOV網(wǎng) C、公路網(wǎng) D、AOE網(wǎng) 8． 線索二叉樹中某結(jié)點為葉子的條件是（ ）。 A、p->lchild!=NULL||p->rchild!=NULL B、p->ltag==0||p->rtag==0 C、p->lchild!=NULL&&p->rchild!=NULL D、p->ltag==1 && p->rtag==1 9．給定整數(shù)集合{3,5,6,9,12}，與之對應的哈夫曼（Huffman）樹是（ ）。 10．圖2是一棵( )。 A、4階B-樹 B、4階B+樹 C、3階B-樹 D、3階B+樹 二、 簡答題（每小題5分，共30分） 1、 對n個頂點的無向圖G，采用鄰接矩陣A表示。試問： （1） 圖G有多少條邊？ （2） 如何判斷頂點i、j之間是否有邊相連？ （3） 如何計算一個頂點的度？ 2、 如果一棵二叉樹n個頂點，用遞歸算法執(zhí)行中序遍歷。最壞情況時處理遞歸的棧至少要多少個單元？為什么？ 3、 設n0為哈夫曼樹的葉子結(jié)點數(shù)目，簡要推導該樹的結(jié)點總數(shù)。 4、 設有循環(huán)隊列存儲在結(jié)構變量q中，用C/C++編寫元素x入隊的算法。 5、 設有n個關鍵字，它們具有相同的哈希函數(shù)值。若采用線性探測法將它們存放到某個哈希表中，至少需要進行多少次探測？為什么？ 6、“有序鏈表”是指什么值有序？其有序性在存儲結(jié)構上用什么方式表示？ 三、 算法設計（25分） 1、 （6分）編寫一個函數(shù)，從元素類型為int的有序表A中刪除所有元素值在（x, y）之間（x≤y，不包括x，y）所有元素。并分析你的算法效率。 2、 （12分）設計算法，將一棵以二叉鏈表形式存儲的二叉樹按順序方式存儲到數(shù)組A中。算法由以下幾個函數(shù)組成： 函數(shù)count根據(jù)樹的形態(tài)，返回要求順序存儲的數(shù)組長度 函數(shù)setAry建立指定長度n的動態(tài)數(shù)組 函數(shù)create把二叉樹存放到數(shù)組中。其中調(diào)用count和setAry函數(shù)。 3、 （7分）編寫算法，求有向圖G中距離頂點v的最短路徑長度為len的所有頂點。 操作系統(tǒng)部分 1． 試說明進程在三個基本狀態(tài)之間轉(zhuǎn)換的典型原因（8分） 2． 試修改下面消費者生產(chǎn)者問題解法中的錯誤（12分） Producer: begin repeat … produce an item in nextp; wait(mutex); wait(empty); buffer(in):=nextp; signal(mutex); until false; end Consumer: begin repeat wait(mutex); wait(full); nextc:=buffer(out); out:=out+1; signal(mutex); consume item in nextc; until false; end; 3． 什么是搶占式調(diào)度，什么是非搶占式調(diào)度？（6分） 4． 試說明頁面替換算法中的clock算法的基本思想（10分） 5． 在一個請求分頁系統(tǒng)中，采用LRU頁面置換算法時，假如一個作業(yè)的頁面走向為：1，3，2，1，1，3，5，1，3，2，1，5，當分配給該作業(yè)的物理塊數(shù)分別為3和4時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率。（8分） 6． 試說明SPOOLing系統(tǒng)的原理。（8分） 7． 某文件系統(tǒng)采用多級索引的方式組織文件的數(shù)據(jù)存放，假定在文件的i_node中設有13個地址項，其中直接索引10項，一次間接索引項1項，二次間接索引項1項，三次間接索引項1項。數(shù)據(jù)塊的大小為4k，磁盤地址用4個字節(jié)表示，問：（15分） 1） 這個文件系統(tǒng)允許的最大文件長度是多少？ 2） 一個2G大小的文件，在這個文件系統(tǒng)中實際占用多少空間？（不包括i_node占用的空間） 8． 什么是對稱加密算法和非對稱加密算法？（8分）