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

華南理工大學2004年攻讀碩士學位研究生入學考試試卷 （試卷上做答無效，請在答題紙上做答，試后本卷必須與答題紙一同交回） 科目名稱：計算機專業(yè)綜合一(組成原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)) 適用專業(yè)：計算機系統(tǒng)結(jié)構(gòu)、計算機應用技術(shù)、軟件工程、計算機應用技術(shù) I. 計算機組成原理試題 （50分） 一．填空題（共10分） 1．計算機的工作過程主要是周而復始地　A　、　B　和　C　的過程。 2．在浮點運算中，當運算結(jié)果階碼大于所能表示的　A　時稱為溢出，若階碼用雙符號S0′S0的移碼表示，則當S0′S0 =　B　時為溢出。 3．雙端口存儲器和多模塊交叉存儲器屬于 A 存儲器結(jié)構(gòu)；前者采用 B 并行技術(shù)，后者采用 C 并行技術(shù)。 4．在微程序控制器中，一般采用較簡單的 A 、 B 二級時序體制。 5．CPU響應中斷時保護兩個關(guān)鍵的硬件狀態(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é)構(gòu)試題 （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é)構(gòu)（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. 在構(gòu)造哈希表方面，下面的說法_________是正確的。 A．鏈地址法在處理沖突時會產(chǎn)生聚集 B．線性探測再散列在處理沖突時會產(chǎn)生聚集 C．好的哈希函數(shù)可以完全避免沖突 D．在哈希表中進行查找是不需要關(guān)鍵字的比較的 6. 以下圖的敘述中，正確的是_______。 A．強連通有向圖的任何頂點到其它所有頂點都有弧 B．任意圖頂點的入度等于出度 C．有向完全圖一定是強連通有向圖 D. 有向圖的邊集的子集和頂點集的子集可構(gòu)成原有向圖的子圖 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é)構(gòu)，下列結(jié)論中不正確的是_____。 A． 相同的邏輯結(jié)構(gòu)，對應的存儲結(jié)構(gòu)也必相同 B． 數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作三個方面組成 C． 數(shù)據(jù)存儲結(jié)構(gòu)就是數(shù)據(jù)邏輯結(jié)構(gòu)的機內(nèi)的實現(xiàn) D． 對數(shù)據(jù)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān) 12. 對AOE網(wǎng)的關(guān)鍵路徑，下面的說法_______是正確的。 A．提高關(guān)鍵路徑上的一個關(guān)鍵活動的速度，必然使整個工程縮短工期 B．完成工程的最短時間是從始點到終點的最短路徑的長度 C．一個AOE網(wǎng)的關(guān)鍵路徑只有一條，但關(guān)鍵活動可有多個 D．任何一項活動持續(xù)時間的改變都可能會影響關(guān)鍵路徑的改變 二． 解答題（每題4分，共40分） 1. 設有關(guān)鍵字序列為：{ 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)先）生成樹是否唯一？與什么因素有關(guān)？什么情況下是唯一的？ 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é)構(gòu) 一． 選選擇題（每題只有一個答案正確，每題2分，共26分） 1. 以下圖的敘述中，正確的是_______。 A．圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點數(shù) B．假設有圖G=(V, {E}), 頂點集V’íV，E’ íE，則V’和{E’}構(gòu)成G的子圖 C．無向圖的連通分量指無向圖中的極大連通子圖 D. 圖的遍歷就是從圖中某一頂點出發(fā)訪遍圖中其余頂點 2. 下列判斷中，______是正確的。 A. 深度為k的二叉樹最多有2k-1個結(jié)點(k≥1)，最少有k個結(jié)點 B. 二叉樹中不存在度大于2的結(jié)點 C. 對二叉樹遍歷是指先序、中序或后序遍歷中的一種 D. 構(gòu)造線索二叉樹是為能方便找到每個結(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．用逐點插入法構(gòu)造二叉排序樹時，若先后插入的關(guān)鍵字有序，二叉排序樹的深度最大 D．在二叉排序樹中進行查找，關(guān)鍵字的比較次數(shù)不超過結(jié)點數(shù)的1/2 6. 在構(gòu)造哈希表方面，下面的說法_________是正確的。 A．再哈希法在處理沖突時不會產(chǎn)生聚集 B．哈希表的裝填因子越大說明空間利用率越好，因此應使裝填因子盡量大 C．哈希函數(shù)選的好可減少沖突現(xiàn)象 D．對任何具體關(guān)鍵字集都不可能找到不產(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個關(guān)鍵字，并且每個結(jié)點的關(guān)鍵字都達到最少狀態(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é)構(gòu)存儲 D. 結(jié)點按層序編號的二叉樹，第i個結(jié)點的左孩子（如果存在）的編號為2i 13. 給定一組關(guān)鍵字{4，26，46，12，9，33}，哈希函數(shù)為H(key)=key MOD 6，則用線性探測再散列方法來處理沖突，則構(gòu)造此哈希表共需要比較關(guān)鍵字____次。 A. 4 B. 5 C. 6 D. 7 二． 解答題（每題4分，共36分） 1. 線性表的雙向鏈表的存儲結(jié)構(gòu)為： 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)，回答：工程完成的最短時間是多少？寫出關(guān)鍵路徑（不需過程），是否有某些活動提高速度后能導致整個工程縮短工期？ 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é)構(gòu)時，主要應考慮哪些方面的內(nèi)容？ 三． 算法設計。做出簡要分析并寫函數(shù)。（共13分） 1. 以二叉鏈表作存儲結(jié)構(gòu)，試編寫非遞規(guī)的前序遍歷算法。(5分) 2. 無向圖用鄰接表存儲，寫出鄰接表定義，給出求圖中頂點Vi到 Vj的最短路徑的函數(shù)。（8分） 操作系統(tǒng) 一、名詞解釋：（18分） 1． 進程 2． Spooling技術(shù) 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)的權(quán)限是如何控制的（8分） 華南理工大學2007年計算機專業(yè)綜合431考研試卷 數(shù)據(jù)結(jié)構(gòu) 一、 選擇題（每小題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é)構(gòu)如圖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é)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ ）。 A、文件結(jié)構(gòu) B、樹結(jié)構(gòu) C、圖結(jié)構(gòu) D、廣義表 7． 在下列網(wǎng)中，（ ）是邊不帶權(quán)值的圖。 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é)構(gòu)變量q中，用C/C++編寫元素x入隊的算法。 5、 設有n個關(guān)鍵字，它們具有相同的哈希函數(shù)值。若采用線性探測法將它們存放到某個哈希表中，至少需要進行多少次探測？為什么？ 6、“有序鏈表”是指什么值有序？其有序性在存儲結(jié)構(gòu)上用什么方式表示？ 三、 算法設計（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分）