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

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