2004年哈工大計算機科學(xué)與技術(shù)專業(yè)854考研真題

1、2004年哈工大計算機科學(xué)與技術(shù)專業(yè)854考研真題I. 數(shù)據(jù)結(jié)構(gòu)一、填空題1. 用下標從o開始的n個元素的數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下列變量m加1后，m仍在數(shù)組有效下標范圍內(nèi)，則m二(1)。2. 若二元樹的一個葉結(jié)點是某子樹的中根遍歷序列中的第一個結(jié)點，則它必然是該子樹的后根遍歷序列中的個結(jié)點。3. 對具有17個元素有序表A117作折半查找，在查找其元素值等于A8的元素時，被比較的兀素下標依次(3)。4快速分類的最大和最小遞歸深度分別和(5)。5. 外部分類過程主要分為兩個階段：階段和(7)階段。6. 已知下面這些字母在某字典中A出現(xiàn)的概率為0.08B出現(xiàn)的概率為0.04I出現(xiàn)的概率為0.15

2、C出現(xiàn)的概率是0.20E出現(xiàn)的概率是0.12F出現(xiàn)的概率是0.16R出現(xiàn)的概率是0.15K出現(xiàn)的概率是0.1Q若采用霍夫曼(Huffman)編碼，貝UE的編碼是3(要求概率小的作為左分支)。7. 索引文件在存儲器上分兩個區(qū)，分別為(9)和(10)_。二、選擇題1. 已知一算術(shù)表達式的中綴形式為a-(b+c/d)*e其后綴形式為(1)。A. -+b*c/dB. -+b*cd/eC. -+*bac/deD. Abcd/+e*-2. 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印機緩沖區(qū)，主機將數(shù)據(jù)依次寫入緩沖區(qū)，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)是一個(2)結(jié)構(gòu)。A. 棧B.

3、 隊列C. 線性表D. 以上都不是3. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧，一個元素出棧后即進入隊列Q,若6個元素出隊的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是(3)。A. 6B. 4C. 3D. 24. 在下列敘述中，不正確的是(4)。A. 關(guān)鍵活動不按期完成就會影響整個工程的完成時間B. 任何一個關(guān)鍵活動提前完成，將使整個工程提前完成C. 某些關(guān)鍵活動若提前完成，則整個工程提前完成D. 所有關(guān)鍵活動都提前完成，則整個工作將提前完成5. 若需在0(nlogn；時間內(nèi)完成對數(shù)組的分類，且要求分類是穩(wěn)定的，則可選擇的分類方法是：

4、(5)。A. 快速分類B. 堆分類C. 歸并分類D. 插入分類6. 就分類算法所用的輔助空間而言，堆分類，快速分類和歸并分類的關(guān)系是（6）。A. 堆分類快速分類歸并分類B. 堆分類歸并分類快速分類C. 堆分類歸并分類快速分類D. 堆分類快速分類歸并分類7將兩個具有n個整數(shù)的有序表歸并成一個有序表，其最少的比較次數(shù)是（7）。A. nB. 2n-1C. 2nD. n-18. 快速分類在（8）的情況下不利于發(fā)揮其長處。A. 待分類的數(shù)據(jù)量太大B. 待分類的數(shù)據(jù)相同值過多C. 待分類的數(shù)據(jù)已基本有序D. 待分類的數(shù)據(jù)值差過大9. 倒排文件的主要優(yōu)點為（9）。A. 便于進行文件的插入和刪除操作B. 便于

5、節(jié)省空間C. 便于進行文件合并操作D. 能大大提高基于非關(guān)鍵字的檢索速度三、判斷題1. 就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。（）2. 外部分類的K路平衡歸并，采用選擇樹法時，歸并效果與K有關(guān)。（）3. 對于n個記錄的集合進行歸并分類，最壞情況下時間復(fù)雜性為0（n2）。（）4. 倒排文件與多重表文件的次關(guān)鍵字索引結(jié)構(gòu)不同。（）5. 樹的父鏈表示法其實就是用數(shù)組表示樹的存儲結(jié)構(gòu)。（）6. 在n個結(jié)點的無向圖中，若邊數(shù)n-1，則該圖必是連通圖。（）7. 若一個有向圖的鄰接矩陣中對角線以下元素均為0，則該圖的拓撲有序序列一定存在。（）四、簡答題1. 已知散列函數(shù)hash（k）

6、=k%ll，把一個整數(shù)值轉(zhuǎn)換成散列值的下標，使用線性探測再散列法與鏈地址法構(gòu)造散列表。分別畫出所構(gòu)造的兩種散列表并把數(shù)據(jù)1，13，12，34，38，33，27，22依次插入到散列表中。2. 簡述堆的定義及堆分類算法的思想。3. 已知某數(shù)列輸入順序為10，5，7，14，3，1，18，12，15，16，按輸入順序畫出其二元查找樹并畫出刪除結(jié)點14后的二元查找樹。五、算法設(shè)計題1. 試寫一個算法建立有向圖的鄰接表，并保存每個結(jié)點的入度和出度。2. 試寫琴算法，在中根線索二元樹中求任意結(jié)點P的中根順序的前導(dǎo)結(jié)點SP。3. 設(shè)有一個雙向鏈表，每個結(jié)點中除有prior（指向其前導(dǎo)結(jié)點）、data（數(shù)據(jù)域）

7、和next（指向其后繼結(jié)點）三個域外，還有一個訪問頻度域freq在鏈表被起用之前，其值均初始化為零。每當在鏈表進行一次LocaeNode(L,X)運算時，令元素值為x的結(jié)點中freq域的值加1，并調(diào)整表中結(jié)點的次序，使其安訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。II計算機組成原理部分六、填空1. Cache的命中率是指，命中率與有關(guān)。2. 為了協(xié)調(diào)CPU和DMA訪問主存的沖突，DMA與主存交換數(shù)據(jù)時可采用三種方法，分另H是、和(2-3)。3. 某計算機采用微程序控制，微指令字中操作控制字段共12位，若采用直接控制，則此時一條微

8、指令最多可同時啟動個微操作。若采用字段直接編碼控制，并要求條微指令需同時啟動3個微操作，則微指令字中的操作控制字段應(yīng)段。若每個字段的微命令數(shù)相同，這樣的微指令格式最多可包含(3-3、個微操作命令。4. 利用訪存指令與設(shè)備交換信息，這在1/o編址方式中稱為_g。5. 每個總線部件一般都配有電路，以避免總線訪問沖突，當某個部件不占用總線時，由該電路禁止向總線輸出信息。6. I/O與主機交換信息的控制方式中，方式CPU和設(shè)備是串行工作的，而(6-2、和方式CPU和設(shè)備是并行工作的，前者傳送和主程序是并行進行的，后者傳送和主程序是串行進行的。7. 如果CPU處于開中斷狀態(tài)，一旦接受了中斷請求，CPU就

9、會自動，防止兩次接受中斷。同時為了返回程序斷點，CPU必須將(7-2、內(nèi)容存至(7-3、中。為了在中斷結(jié)點后返回主程序，并且允許接受新的中斷，必纟和(7-5、。&依次從控制器、運算器、存儲器和I/O系統(tǒng)四個方面，可采用、(8-3、和措施來提高計算機的整機速度。9. 32位字長的浮點數(shù)，其中階碼8位(含1位階符)，數(shù)符1位，尾數(shù)23位，其對應(yīng)的最大負數(shù)為，最小的絕對值為(9-2)，若機器數(shù)采用補碼規(guī)格化表示，則對應(yīng)的最大負數(shù)為。(均用于十進制表示)。10. 設(shè)指令字長等于存儲字長，均為16位，若指令系統(tǒng)共有120種操作，操作碼位數(shù)固定，且具有直接、間接、變址、基址、相對、立即等尋址方式，

10、則直接尋址的最大范圍直(10-1、，一次間址的范圍是(10-2、，立即數(shù)(補碼、的范圍是(10-3、。七、選擇題1. 采用DMA方式傳送數(shù)據(jù)時，每傳送一個數(shù)據(jù)要占用(1、的時間。A. 一個存取周期B. 一個指令周期C. 一個機器周期D. 一個中斷周期2. 在程序的執(zhí)行過程中，Cache與主存的地址映射是由(2)。A. 操作系統(tǒng)來管理的B. 程序員調(diào)度的C. 由操作系統(tǒng)和程序員共同協(xié)調(diào)完成的D. 由硬件自動完成的3. 存取周期是指(3、。A. 存儲器的寫入時間和讀出時間的最小值B. 存儲器進行連續(xù)寫操作允許的最短間隔時間C. 存儲器進行連續(xù)讀或?qū)懙牟僮魉试S的最短間隔時間D. 以上說法都不對4.

11、 下列敘述中（4）是正確的。A. 程序中斷方式和DMA方式中實現(xiàn)數(shù)據(jù)傳送都需中斷請求B. 程序中斷方式中有中斷請求，DMA方式中沒有中斷請求C. 程度中斷方式和DMA方式中都有中斷請求，但目的不同D. DMA要等指令周期結(jié)束時才可進行周期竊取5. 下列敘述中（5）是正確的。A. 虛擬存儲器實際上就是輔存B. 一條指令中可以包含多個操作碼C. I/O接是負責主存與外設(shè)交換信息的部件D. 由于定點乘法運算時不會出現(xiàn)溢出，所以浮點乘法運算時也不會出現(xiàn)溢出6. 某機指令系統(tǒng)共有101種操作，采用微程序控制方式時，控制儲存器中相應(yīng)有（6）個程序。A. 101B. 102C. 103D. 1047. 采用

12、變址尋址可擴大尋址范圍，且（7）。A. 變址寄存順由用戶確定，且在程度執(zhí)行過程中不可變B. 變址寄存器內(nèi)容由操作系統(tǒng)確定，且在程序執(zhí)行過程中不可變C. 變址寄存器內(nèi)容由用戶確定，且在程序執(zhí)行過程中可變D. 變址寄存器內(nèi)容由操作系統(tǒng)確定，且在程序執(zhí)行過程中可變八、簡答與計算1. 總線管理包括哪些內(nèi)容？簡要說明各種管理措施。2. 設(shè)機器字長為8位（含1位符號位）。設(shè)A=-ll/32,B=95/128,列出豎式計算A-B補九、綜合題1. 假設(shè)X,Y,Z寄存器均為16位（最高位為第0位），在乘法指令開始前，被乘數(shù)已存在于X中，并用X/Z存放乘積。要求：（1）畫出實現(xiàn)補碼Booth算法的運算器框圖。（2）假設(shè)CU為組合邏輯控制，且采用中央控制和局部控制相結(jié)合的辦法，寫出完成MULa指令（a為主存地址）的全部微操作及節(jié)拍安排，哪些節(jié)拍屬于局部控制節(jié)拍，局部控制最多需幾拍？2. 設(shè)CPU共有20根地址線,8根數(shù)據(jù)線，并用作訪存控制信號（低電平訪存），用作讀寫控制信號（高電平為讀，低電平為寫），存儲器按奇偶分體，按字節(jié)方式訪問?，F(xiàn)有下列芯片：(1)74138(2)門電路自定(3)ROM芯片1)64K*8位；2)32K*8位；3)32K*16位。(4)RAM