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

1、華南理工大學(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)S0S0的移碼表示，則當(dāng)S0S0 =B時(shí)為溢出。3雙端口存儲(chǔ)器和多模塊交叉存儲(chǔ)器屬于 A 存儲(chǔ)器結(jié)構(gòu)；前者采用 B 并行技術(shù)，后者采用 C 并行技術(shù)。4在微程序控制器中，一般采用

2、較簡單的 A 、 B 二級(jí)時(shí)序體制。5CPU響應(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取代PCC. 控制存儲(chǔ)器可以用ROM實(shí)現(xiàn)D. 指令周期也稱為CPU周期3下列說法正確的是（ ）。A. 程序中斷過程是由硬件

3、和中斷服務(wù)程序共同完成的B. 每條指令的執(zhí)行過程中，每個(gè)總線周期要檢查一次有無中斷請(qǐng)求C. 檢測有無DMA請(qǐng)求，一般安排在一條指令執(zhí)行過程的末尾D. 中斷服務(wù)程序的最后指令是無條件轉(zhuǎn)移指令三完成下列各題（共36分）1設(shè)A補(bǔ)an-1an-2a1 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

4、能否包含在一條微指令中？為什么？如要將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ì)稱矩

5、陣，現(xiàn)將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。矩陣元素Aij (i =j ) 在B中的下標(biāo)是_。6 用鄰接矩陣求最短路徑的Floyd算法的時(shí)間復(fù)雜性為_。7 若一個(gè)無向圖有n個(gè)頂點(diǎn)，e條邊(ne)，且是一個(gè)森林。則它有_棵樹。8對(duì)n個(gè)元素進(jìn)行歸并排序，需要的輔助空間為_。二 解答題（共14分）1 一棵樹的先序和后序序列分別如下，畫出該樹。（3分）先序序列：ABCDEFGHIJKLM后序序列：CDBEFGJKLMIHA2 對(duì)下面的遞歸算法，寫出調(diào)用f(4)的執(zhí)行結(jié)果。（3分）void f(int k) if( k0 ) printf(%d ,k);f(k-1);f(k-1);華南理工大學(xué)200

6、5年計(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. 63. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即_。A二維數(shù)組和三維數(shù)組 B三元組表和散列C三元組表和十字鏈表 D散列和十字鏈表4. 下列判斷中，_是正確的。A. 二叉樹就是度為2的樹 B. 二叉樹中不存

7、在度大于2的結(jié)點(diǎn)C. 二叉樹是有序樹 C. 二叉樹的每個(gè)結(jié)點(diǎn)的度都為25. 在構(gòu)造哈希表方面，下面的說法_是正確的。A鏈地址法在處理沖突時(shí)會(huì)產(chǎn)生聚集B線性探測再散列在處理沖突時(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ù)為_。An(k-1)/k Bn-k C(n+1)/k D(nk-n+1)

8、/k8. 具有n個(gè)頂點(diǎn)的無向圖至多有_條邊。An-1 Bn(n-1)/2 C. n(n+1)/2 D. n2/29. 深度為4 的101階B樹，最少有_個(gè)結(jié)點(diǎn)。A. 154 B. 105 C. 103 D. 15110. 利用逐點(diǎn)插入法建立序列(60，74，44，99，75，30，36，45，68，9)對(duì)應(yīng)的二叉排序樹以后，查找元素75要進(jìn)行_元素間的比較。A4次 B3次 C. 7次 D5次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í)

9、現(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 08 0 1 4

10、00 0 0 0 20 0 2 5 03. 畫出下圖的鄰接表，并用克魯斯卡爾算法求其最小生成樹。4. 有以下算法，分析其時(shí)間復(fù)雜度。i=1;while(i*i*inext-next的值是（ ）。A、15 B、32 C、78 D、全不是圖14 一個(gè)nn的對(duì)稱矩陣，如果以行或列為主序放入內(nèi)存，其容量為（ ）。A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/25 快速排序在（ ）情況下最不利于發(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、

11、圖結(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!=NULLB、p-ltag=0|p-rtag=0C、p-lchild!=NULL&p-rchild!=NULLD、p-ltag=1 & p-rtag=19給定整數(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表

12、示。試問：（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ù)值。若采用線性探測法將它們存放到某個(gè)哈希表中，至少需要進(jìn)行多少次探測？為什么？6、“有序鏈表”是指什么值有序？其有序性在存儲(chǔ)結(jié)構(gòu)上用什么方式表示？三、 算法設(shè)計(jì)（25分）1、 （6分）編寫一個(gè)函數(shù)，從元素類型為in

13、t的有序表A中刪除所有元素值在（x, y）之間（xy，不包括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:beg

14、inrepeatproduce 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 什么是搶占式調(diào)度，什么是非搶占式調(diào)度？（6分）4 試說明頁面替換算法中的clock算法的基本思想（10分）5 在一個(gè)請(qǐng)求分頁系統(tǒng)中，采用L

15、RU頁面置換算法時(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分）歡迎您的光臨，Word文檔下載后可