華南理工考研計(jì)算機(jī)歷年真題.doc

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

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