華南理工考研計算機歷年真題.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條邊(ne)，且是一個森林。則它有_棵樹。8對n個元素進行歸并排序，需要的輔助空間為_。二 解答題（共14分）1 一棵樹的先序和后序序列分別如下，畫出該樹。（3分）先序序列：ABCDEFGHIJKLM后序序列：CDBEFGJKLMIHA2 對下面的遞歸算法，寫出調用f(4)的執(zhí)行結果。（3分）void f(int k) if( k0 ) 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*inext-next的值是（ ）。A、15 B、32 C、78 D、全不是圖14 一個nn的對稱矩陣，如果以行或列為主序放入內存，其容量為（ ）。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 試說明S