工大計算機(jī)2008年考研試題

1、哈爾濱工業(yè)大學(xué)二八年入學(xué)試題科目：計算機(jī)專業(yè)基礎(chǔ)科目代碼：【 424 】報考專業(yè)：計算機(jī)科學(xué)與技術(shù)是否允許使用計算器：【 否 】考生注意：務(wù)必寫在答題紙上，并標(biāo)明題號。答在試題上無效。答題.數(shù)據(jù)結(jié)構(gòu)（含高級語言）部分（75分）一、填空（每題2分共20分）1.已知一個線性表有n個元素，其中每個元素的數(shù)據(jù)占8個字節(jié)，假設(shè)一個指針的大小為個字節(jié)，如果采用有30個元素的數(shù)組4時，數(shù)組的效率比不2.給定14個字母假設(shè)它們的權(quán)值都相等采用huffman編碼，則每個字母的平均代碼長度是。按C語言的運算符優(yōu)先級，中綴表達(dá)式“A&B|!(EF)”的等價后綴形式為。 設(shè)按順時針方向移動的循環(huán)隊列QN的頭尾指針分別

2、為F、R，頭指針F總是指在隊列中的第一個元素的前一位置，尾指針R在最后一個元素的位置，則隊列中的元素個數(shù)為。3.4.5.從空二叉樹開始嚴(yán)格按照BST（二又查找樹）的算法，逐個關(guān)鍵字18，73，10，5. 68，99，27，41 , 32，25）構(gòu)造出一顆BST ，對該BST按照先根遍歷得到的序列為。6. 將兩個長度為m的有序序列歸井為一個有序序列，最少需要做次關(guān)鍵字比較，最多需要做次關(guān)鍵字比較。散列查找中，現(xiàn)象稱為設(shè)可用的內(nèi)存單元可處理4個，現(xiàn)象稱為。始?xì)w井段，對有12個在案的文件，產(chǎn)生的第一個初的歸井段長度為個。9. 在兩種求圖的最小生成樹的算法中，算法適合稀疏的圖的最小生成樹。10. 已知

3、一個序列為21，39，35，12，17，43，則利用堆排序方法建立的初始堆為：。二、判斷（每題1分共9分）1.2.3.4.倒排文件只能按關(guān)鍵字的順序。（ ）堆的表示可能是式的，也可以是順序的。（ ）在AOE網(wǎng)中，任何一個關(guān)鍵活動的延遲，都會使整個工程延遲。（ ）有環(huán)路的有向圖不能進(jìn)行拓?fù)渑判颉＃?）題號一二三四五六七總分分?jǐn)?shù)2091630153299105.6.7.8.9.對無向圖進(jìn)行一次深度優(yōu)先搜索可以到圖中的所有頂點。（ ）大根堆的最大元素應(yīng)該在堆頂，即根結(jié)點。（ ）歸并排序的平均時間復(fù)雜度為O（nn）,為O（n2）。（ ）?？偸窃跅５讋h除元素。（ ）分塊查找只適合靜態(tài)查找，不適合動態(tài)查找

4、。（ ）三、問答題（每題8分共16分）1. 許多文獻(xiàn)中認(rèn)為常用的排序算法是快速排序算法，而不是歸并排序，你是如何理解的？在包含n個關(guān)鍵字的線性表中進(jìn)行順序查找,若查找第i個關(guān)鍵字的概率為Pi且分布如下：2.P1=1/2, P2=1/4Pn-1=1/2(n-1), Pn=1/2n,；求：（1）查找成功的平均查找長度。（2）查找失敗的情況下的平均查找長度。四、算法設(shè)計題(每題15分共30分)1. 設(shè)二叉樹結(jié)點表示的數(shù)據(jù)元素類型為Elementtype,二叉樹用左右鏈表示。一棵二叉樹的最和最小枝長分別如下定義：最邊數(shù)。就是二叉樹的層數(shù)；最小枝長就是離根結(jié)點距離最近的葉結(jié)點到根路徑上的請設(shè)計一個算法，

5、同時求出一棵二叉樹的最大和最小枝長。2. 設(shè)計一找無環(huán)路有向圖第對頂點間“最長簡單路徑“（所謂最長簡單路徑是指該簡單路徑包含邊最多）的算法，即以一個無環(huán)路有向圖作為輸入，對于每個頂點如果它們之間存在簡單路徑，則輸出其中最長的，否則輸出為空。.計算機(jī)組成原理部分（共75分）五、填空題（每空1分共15分）1.2.總線控制主要解決問題。集中式仲裁有、三種。若數(shù)據(jù)在器中采用以低字節(jié)地址的存放方式，則十六進(jìn)制數(shù)12,34,56,78H按字節(jié)地址由小到大依次為。總線技術(shù)是指不同的信號（如地址信號和數(shù)據(jù)信號）共用一組物理線路，分時使用，此時需要配置相應(yīng)的電路。一個四級流水的處理器，共有關(guān)12條指令連續(xù)輸入此

6、流水線，則在12個時鐘周期結(jié)束時執(zhí)行完條指令。CPU在時刻采樣中斷請求信號（在開中斷情況下）。而在時刻采樣DMA的總路線請求信號。32位字長的浮點數(shù)，其中階碼8位（含1位階符），基值為2，尾數(shù)為24位（含1位數(shù)符）。當(dāng)機(jī)器數(shù)采用原碼表示，則其對應(yīng)的最小正數(shù)是，最小負(fù)數(shù)是；當(dāng)機(jī)器數(shù)采用補碼表示，尾數(shù)為規(guī)格化形式，則其對應(yīng)的最大正數(shù)是，最大負(fù)數(shù)是。（均用十進(jìn)制表示）定點原碼除法和定點補碼除法均可采用法，但補碼除法中參與運算。3.4.5.6.7.六、問答題(每題8分共32分)1.2.DMA（特點）,簡述采用DMA方式實現(xiàn)主機(jī)與I/O交換信息的數(shù)據(jù)傳遞過程。下圖為某SRAM的寫入時序圖，線為讀寫信號線

7、，線為片選信號線，要求寫入地址為2450H的單元中，圖中的錯誤，并把相應(yīng)的正確的時序圖畫出來。3.單重分組和雙重分組跳躍進(jìn)位鏈？一個按3、5、3、5分組的雙重分組跳躍進(jìn)位鏈（最低為第0位）。試問大組中產(chǎn)生的是哪幾位進(jìn)位？與按4444分組的雙重分組跳躍進(jìn)位鏈相比，試問產(chǎn)生全部進(jìn)位的時間是否一致？為什么？若某機(jī)采用微程序控制方式，微指令字長24位，共有微指令30個，一條微指令允許同時啟4.動4個微操作命令，可判定的外部條件共3個，畫出微指令格式，并為多少?控制器的容量七、設(shè)某計算機(jī)機(jī)器字長為16位，共有16個通用寄存器，4種尋址方式（尋址模式只需用一個字段表示），采用擴(kuò)展操作碼技術(shù)，指令字長可變，

8、主存容量為1M*16位，器按字編址。（1） 設(shè)計單字長寄存器-寄存器型指令格式，并這類指令最多允許幾條。（2） 在（1）的基礎(chǔ)上，擴(kuò)展成單操作數(shù)的指令，設(shè)計指令格式，并許幾條。這類指令最多允（3） 設(shè)計允許直接主存一單元的寄存器-器指令格式。（4） 若可指定任一通用寄存器作為變址寄存器，設(shè)計變址尋址的寄存器-器型指令格式。八、設(shè)CPU有18根地址線和16根數(shù)據(jù)線，并用IO/M作訪存控制信號，RD為讀命令，WR為寫命令，已知：（1）下列及各種電路（門電路自定）（2）地址空間分配為：032767 為系統(tǒng)程序區(qū)，32768-98303 為用戶程序區(qū)，最大 16K 地址空間為系統(tǒng)程序工作區(qū)；要求：（1）選用的器類型及數(shù)量；寫出每片畫出 CPU 與的二進(jìn)制地址范圍；器的連接圖。九、（1）多級時序系統(tǒng)？（2）假設(shè) CU 為組全邏輯控制，且采用控制和局部控制相結(jié)合的辦法，寫出完成乘法指令 MUL a 指令（a 為主