1、哈爾濱工程大學計算機科學與技術學院 816計算機 專業基礎綜合（自命題數據結構，計算機組成原理）歷年考研真題匯編最新資料，WORM式，可編輯修改!目錄說明：2016年公布的專業目錄中，科目名稱改為“816計算機專業基礎綜合（自命題數據結構，計算機組成原理）”，本書收錄20012008年的真題，以供參考。2004 年哈爾濱工程大學計算機科學與技術學院 816數據結構考研真題2003年哈爾濱工程大學計算機科學與技術學院816數據結構考研真題哈爾濱工程大學2003年數據結構試題一、判斷題（每小題一分，共十分）1數據結構，數據元素，數據項在計算機中的映象（表示）分別稱為存儲 結構，結點，數據域。對2.

2、線性表的邏輯順序與存儲順序總是一致的。3.廣義表的表頭或是元素或是一個廣義表，而表尾總是一個廣義表。4.拓撲排序是一種內部排序的算法。5.字符串是一種特殊的線性表，其特殊性體現在數據元素是一個字符。6.若線索二叉樹有n個結點，則必有n+1條不空的指向樹中結點的線索。7.稀疏矩陣的壓縮存儲方法一般有三元組和十字鏈表兩種。8.在AOE網中，一定有不止一條關鍵路徑。9.二維數組是其數據元素為線性表的線性表。1.2.10.一個棧的輸入序列是12345,則輸出序列43512是可能的。、單項選擇（每小題 2分，共20分） 數據結構從邏輯上可以分成 線性和非線性 兩種結構。哈希（Hash）法查找的基本思想是

3、根據關鍵字值來決定記錄的存儲位3.4.5. 排序。6.利用棧求表達式（A-B） -C） -（D-（E-F）,操作數棧須有4項。 圖的廣度優先搜索算法類似于二叉樹的按層 遍歷操作。在所有排序方法中關鍵字比較次數與記錄初始排列次序有關的是插入二維數組A的行下標從1到8,列下標從1到10,若每個元素占3個單A 58的起始位置是 180abc+*d 元，則該數組按“以列序為主序”存放時，7. 表達式a*（b+c）-d的后綴表示（逆波蘭式）是8. 在一個具有n個結點的單鏈表中查找，查找成功時需要平均計較 結點。9. 設Q0n-1為循環隊列，front,rear分別為隊列的頭，尾,中的元素個數為 （rea

4、r-front+n） MOD n10 .在各種查找方法中，平均查找長度與結點個數無關的查找方法是 樹查找(n+1)/2則隊列二叉三、計算題（每小題 6分，共30分）Nm個度為1. 一顆樹有N1個度為1的結點，N2個度為2的結點m的結點，求：該樹中終端（葉）結點的個數NO2. 對長度為 12 的有序表進行折半查找，求查找成功與不成功時各平均比 較次數。3 .已知一顆3階的B樹中含有25個關鍵字，求該B樹的最小高度和最 大高度（不包含葉子層）4. 已知一棵平衡二叉樹的深度為 6，求樹中最少可能的結點數和最多可能 的結點數。5對n個結點的平衡二叉樹，請分別求出當二叉樹具有最小深度K和最大深度K時，第

5、K層上的結點數。請寫出其鏈式存儲結構。 設鏈表中有 其中指針 hp 和 tp 分別指向表頭 tag = 0 元素值 97，75，13，27，51，55，10）進行希爾 d1=5 ,d2=3 ,d3=1 ，則請寫出每趟的四、綜合題 （每小題 8分，共 40分）1. 廣義表 A= （a）,（b,（c,d,e）,（）, 兩類結點，表結點形式為 tag=1 hp tp ,和表尾，元素（原子）結點形式為2. 對關鍵字序列（ 49， 38， 65， 排序。若排序三趟，各趟的增量分別為 結果及元素移動次數。他們出現的頻率為（ 4,7,5,2,9,8 ）, 請畫3. 電文中使用字符 a,b,c,d,e,f,出

6、對應的編碼哈夫曼樹，并求出傳送電文的總長度。4. 已知一棵二叉樹的中序序列為DAJFBGICEHK后序序列為DAFBJCIKHEG, 請畫出該二叉樹，并使其成為先序線索樹。5. 對于加權圖124101516201310方法構造最小生成樹，并寫出選邊的次序。2小題各 13分， 3，4小題各 12分，共 50分） root ，結點形式為：5 用克魯斯卡爾 （Kruskal） 五、算法題 （ 1，1 設用二叉鏈表表示的二叉樹不空，其根指針為 lchild data rchild請寫出將二叉樹中所有結點的左，右子樹相互交換的非遞歸算法。2利用兩個棧S1和S2來模擬一個隊列。若不存在棧溢出問題，則請寫出

7、 用棧的操作來實現隊列的插入和刪除的算法。3設計一個算法，在長度為 n的（小頂）堆R1n中刪除一個元素Rs （SV二n）產生一個長度為 n 1的（小頂）堆，并將Rs存放于Rn中。4 假設循環單鏈表不空，且無表頭結點亦無表頭指針，指針 p 指向鏈表中 某結點。請設計一個算法，將 p 所指節點的前驅結點變為 p 所指結點的后繼結 點。答案：三、計算題（每小題6分，共30分）1.2.3.4.5.mn0=1 + 刀（i-1）* ni）i=2查找成功平均比較次數：37/12查找不成功平均比較次數：49/13最小高度：3 最大高度：4最少結點數：20最多結點數：63最小深度時：n+1-2 k勺最大深度時：

8、1四、綜合題（每小題8分，共40分）111A1. A1AA1A11A0d10 a 10c0b2第1趟也：131310第2趟第3趟2710135149275538381027494951513855556565659797763.767697電文總度:移動5次移動3次移動5次87014 .2002年哈爾濱工程大學計算機科學與技術學院816數據結構考研真題哈爾濱工程大學2002年數據結構試題1.2.3.4.一、填空題 （13分）數據結構從邏輯上分（線性）結構和（非線性）結構。若廣義表中的每個元素都是（原子），則廣義表變成為線性表。連通圖的極小連通子圖稱為改圖的（生成樹）。哈希（hash）法存儲的基

9、本思想是根據（關鍵字）來決定（存儲地址）。5. 迪杰斯特拉算法是按（路徑長度遞增）次序產生最短路徑。6兩個字符串相等的充要條件是：兩個串的（長度）相等，且（對應位置） 的字符相等。7. 哈夫曼樹是葉子節點（帶權路徑長度）最短的二叉樹。8. 稀疏矩陣一般的壓縮方法有兩種（三元組表）和（十字鏈表）。9. N個結點的線索樹有（n+1 ）根線索。二、選擇題 （12分）1 .一個棧的入棧序列是 a,b,c,d,e,則棧的不可能的輸入序列是 dceab2h-12 深度為h的4階B-樹（根在第一層，葉子在第 h層），葉子結點的數目 最少為的尾是 (b,(c,(d,e)3.廣義表（a,b,（c,（d,e）4

10、.具有5層結點的平衡二叉樹至少有 12個結點。5設二叉樹是由森林變換得來的，若森林中有n個非終端結點，則二叉樹中無右孩子的結點有吐1個。6. 下列不屬于內部排序的算法是BABCD）。歸并排序拓撲排序樹型排序折半插入排序三、回答問題（20分）1. 對n個結點的二叉樹進行中序遍歷，算法中所設的棧，棧中元素最少時 可能是多少個？最多時可能是多少個？答：2個 ，n+1個2. 對n個記錄進行簡單的插入排序，最少共需要比較多少次？最多共需要 比較多少次？答：最少n 1次 最多1 + 2 + 3+（ n 1）次3. 對13個有序記錄進行折半查找，查找成功和不成功的平均查找長度各 為多少？4 采用上三角壓縮存

11、儲10階對稱矩陣A,若以行序為主存儲，且起始地址 為d則A3, 8的存儲地址為多少？它與以列序為主序存儲時的哪一個元素的起 始位置一致？答：d + 24.A4,75.設循環隊列最大空間為 m（0,，m- 1）,頭，尾指針為front , rear。 加入判別隊列空的條件是（front +1） MODrmrear，那么判別隊列滿的條件是 什么？ front ， rear 的初值應是多少？答：front = rear 初值 front = 0. rear = 1四、應用題（ 25 分）1. 對一組記錄的關鍵字（ 49， 38， 66， 80， 75， 19， 22）進行快速排序， 請寫出各趟排序后

12、的狀態，并說明總共比較了多少次？2. 設哈希表的地址空間為 0-6，哈希函數 H（K）=K MOD 7。請對關鍵字序 列（32， 13， 49， 18， 22， 38， 21）按鏈地址法解決沖突的辦法構造哈希表。 并求出查找成功的平均查找長度。1）左子樹的先序序列與中序序列相同，右子樹的先序序列與中序序列2）左子樹的中序序列與后序序列相同，右子樹的先序序列與中序序列3. 已知二叉樹的左，右子樹各含 3 個結點。試分別構造滿足如下要求的二 叉樹：（ 相同。（ 相同。對關鍵字（ 67，49，80，14，22，31，95，38，43，56， 73）構造平衡4. 二叉樹。5. 請寫出表達式 a+b*（

13、c-d）-e/f 的二叉樹表示，并使其成為后序線索樹。五、算法題（ 30 分）1. 設計一算法，在單鏈表中刪除數據元素的值相同的多余結點。2設計一算法，在中序線索樹上求指針P所指結點的前驅結點。3. 將二叉樹的結點按層編號（從根還是往下，同層自左至右）。請設計一 算法，將該二叉樹的結點按編號從小到大順序輸出。設二叉樹用二叉鏈表表示。2001年哈爾濱工程大學計算機科學與技術學院816數據結構考研真題哈爾濱工程大學2001年數據結構試題一、填空（每空一分，共 14分）1. 數據元素是數據結構的基本單位,數據項是數據的不可分割的最小單位。2. 深度是k的完全二叉樹至少有2八（k 1）個結點，至多有2

14、*1個結點。3. 哈希表的查找效率主要取決于造表時選取的哈希函數和處理沖突的方 法。4 .對100個記錄進行折半查找，最多比較 7次，最少比較 1次。5. 有n個頂點的無向圖，最少有 0條邊，最多有n（n-1）/2條邊。7. 對于堆排序，常用的建堆算法是篩選法，堆的形狀是一棵完全二叉樹。二、判斷題（每小題1分，共5分）1 .線性表的鏈式存儲結構優于順序存儲結構。2. 鏈表的每個節點中都帢包含一個指針。如雙向鏈表3.棧4.5.棧和隊列都是順序存儲結構的線性結構。6. AOE網中，從源點到匯點的最長路徑上的活動叫做關鍵活動。有環的圖 不能進行拓撲排序若數的度為2時，則該樹為二叉樹。 若廣義表中的每

15、個元素都是原子，則廣義表為線性表。三、問答題（每小題4分，共16分）1. 一棵3階4層（根為第一層，葉子為第四層）的B樹，至少有多少個 關鍵字，至多有多少個關鍵字？答：7個 26 個2. 利用棧秋表達式（A-B） -C） -（D-（E-F） 的值，運算符棧和操作數棧 各必須具有多少項？答：5項 4 項3. 以行序為主序存儲10階對稱矩陣A，米用下三角的壓縮存儲方式，若起 始地址是d則A85的存儲地址是多少？答：32+ d4. 設哈希表中以存在無個記錄 （如圖一所示）。哈希函數為H（K）=K M0D1,用二次探測再散列處理沖突。請問關鍵字為94的記錄的存儲地址是多少？123456789010圖一

16、451639 6)276答：存儲地址是2四、綜合題（每小題5分，共35分）1. 給定一組權值9，6，14，17, 2，15，3，16，請構造哈夫曼樹，并計 算其帶權路徑長度。答：帶權路徑長度1862 .已知二叉樹的先序遍歷的結果為ABCDEFGHIJ中序遍歷的結果為CBEDAHGIJ,請畫出這顆二叉樹。3對圖二所示的無向圖，（1）請用鄰接表表示，且頂點鏈接按序號從小 到大鏈接。（2）請寫出從V0出發的深度優先遍歷和廣度優先遍歷的結果。圖二: 其中 lc 和 rc 分別為指向左子樹和右子樹根的指針域。試編寫一個 非遞歸算法，求二叉樹的結點總數及其深度。KLMN53, 13, 37, 88, 24

17、, 61構造一棵平衡二叉樹。 4的最遲發生時間5對關鍵字序列6已知一個0E網，如圖四所示，求其關鍵路徑，并給出時間 和事件 圖四：44 ,12,5最早發生時間?141269115O50 9186564,377.五,12, 26, 48, 44, 35創建初始堆。結點單鏈表的首結點。試設一算法，刪對序列50 , 77,（8分）設指針head指向除鏈表中值為X的結點，若X結點不存在，則輸出“不存在”信息。六（10分）已知一個有向圖的鄰接表，試編寫一個算法求每個結點的出度和入度。七（ 12分）已知一個二叉樹存儲于二叉鏈表中，其結點結構為data rcIc【計算機組成原理】2008 年哈爾濱工程大學計

18、算機科學與技術學院819計算機組成原理考研真題2005 年哈爾濱工程大學計算機科學與技術學院 819計算機組成原理考研真題哈爾濱工程大學研究生入學考試 2005 計算機組成原理真題一、判斷題（ 20 分） 1某浮點機用補碼、尾數用原碼表示，則判斷結果是否為規格化數的方法 是：數符與尾數小數點后第 1 位的數字相異即為規格化數。1，各數位1。2由真值求移碼的簡單方法可以歸納為：對于正數，符號位為 不變；對于負數，符號位為 0，各數位變反后，在末位加3常規內存是按地址訪問的隨機方式，所以不便于信息檢索 4由于單地址的運算類指令中只提供一個操作數地址，因此它不能用于雙 操作數的運算5雙端口存儲器之所

19、以能高速地進行讀寫，是因為采用了兩套相互獨立的 讀寫電路。6決定計算機計算精度的主要技術指標是計算機的字長。 7組成總線不僅要有傳輸信息的傳輸線， 還應有實現總線傳輸控制的器件， 即總線緩沖器和總線控制器。8I/O 設備是處于主機之外的輸入 /輸出設備， 所以應為外圍設備分配獨立 的設備碼而不能與主存單元統一進行編址。9中斷級別最高的中斷是不可屏蔽的中斷。 10一個指令周期由若干工作周期組成，每個工作周期又包含若干時鐘周 期，由此構成了常用的三級時序系統。二、單選題（ 20 分）1數位每左移 1 位相當于原數乘以 2，為防止左移操作造成溢出，補碼左 移的前提條件是：其原最高有效位（）。 為0

20、為1 與原符號位相同 與原符號 位相異 2下列存儲設備中，（）的存取數據速度最快。RAM 磁帶 光盤 硬盤3原碼不恢復余數定點小數除法，要求被除數絕對值小于除數絕對值，其 目的是（）。 商為規格化小數 商為正數 商不溢出 不必恢復余數 4利用分段直接編譯法對微指令進行編碼時，應將（）微命令歸為一組。 控制同一部件的 使用頻度相近的 相容的 互斥的 5. 某校驗碼碼長為n （有效信息位數+冗余位數），合法碼字數量為m種 則必有（）。mn mv n m2n mv 2n6. 條件轉移指令執行時，需對（）的內容進行測試。PC PSW IR SP7. 在定點數運算中產生溢出的原因是（）。 運算過程中最高

21、位產生了進 指令長度固定，指令 增加寄存器的數目，以盡 以及很有用但不復雜的指位或借位 運算的結果超出了機器的表示范圍 參加運算的操作數超出了機器的 表示范圍 寄存器的位數太少，不得不舍棄最低有效位 8下列描述中，不符合 RISC指令系統特點是（）。）。 提高微程序的執 縮短微指令的長度 增大控制存儲器的容量 種類少 尋址方式種類盡量減少，指令功能盡可能強 量減少訪存次數 選取使用頻率最高的一些簡單指令， 令9.下列不屬于微指令結構設計所追求的目標的是行速度 提高微程序設計的靈活性10中斷向量地址是（）。 中斷源服務程序入口地址 子程序入口地址 中 斷服務程序入口地址 中斷返回地址 對齊。階符

22、 1 位，階碼 6 位；數符 1 位，尾數 8 ，分辨率是 。三、填空題（ 20 分） 1在估算加法器運算時間（即加法器速度）時，各位全加器本身的求和延 遲并不是主要因素，關鍵在于 。2浮點加減法的對階規則是使3一個全補碼浮點數的格式為：位。則該浮點數所能表示數的范圍是4. 十進制數183.5的8421BCD碼是，相應的十六進制數是5自底向上生成的堆棧， 若棧頂單元是待存元素的空單元， 則壓入操作時， 首先 ；然后 。6. I/O 設備的編址可分為 和 兩種方式。7. 在計算機系統中，多個系統部件之間信息傳送的公共通路稱為。就其 所傳送的信息的性質而言，在公共通路上傳送的信息包括 、和 信息8

23、. DRAM勺刷新一般有、和三種方式，之所以刷新是因為。9. 直接存儲器存取（DMA方式是一種簡單中斷，而不是中斷。10. 多體交叉存儲技術中，每個存儲體均是編址的。四、簡答題（ 30 分）1 .馮諾依曼提出的計算機的概念和思想是什么2. 奇偶校驗碼的碼距為幾有無糾錯能力查錯率能否達到100%，為什么若偶 校驗位放在第一位，則 7位信息代碼 01 1 1 000的偶校驗碼是什么3. 計算機時序控制方式分為哪兩大類試比較它們的優缺點及應用場合。4. 中斷系統之所以要設定中斷優先級，主要是為了解決哪兩方面的問題5. 高速硬盤與主機之間的信息交換采用程序中斷控制方式有何不妥五、計算題（ 24 分）1

24、 .某計算機系統的內存儲器由 Cache和主存構成，Cache的存取周期為 45ns,主存的存取周期為200ns。已知在一段給定的時間內，CPU共訪問內存4500 次，而Cache的未命中率為10%問：（1）CPU訪問Cache和主存各多少次（2）CPU訪問內存的平均時間是多少（3）Cache主存系統的效率是多少2. 已知某計算機的指令字長為 16 位且按字節編址，其雙操作數指令的格 式如下：其中0P為操作碼，R為通用寄存器地址，試說明在下列各種情況下能訪問 的最大主存區域為多少字（ 1 ） D 為直接操作數；（2）D為直接主存地址；（3）D為間接地址（一次間址）；（4） D為變址的形式地址，

25、假定變址寄存器為R1 （字長為16位）。3. 已知：X 2-10X 0.0110, Y= 210X 0.1001 （除底 2 以外，其余均是二 進制表示）。設在浮點機中，階碼 4位（補碼表示，含 2位符號）；尾數 6位 （原碼表示，含2位符號）。試按照機器的浮點運算步驟，計算X/Y =六、分析題（ 18 分）1 .如圖（a）所示米用不歸零一1 （NRZD制寫入磁表面存儲器的一組信息 的電流變化情況，據此分析說明：2004 年哈爾濱工程大學計算機科學與技術學院 819計算機組成原理考研真題2003 年哈爾濱工程大學計算機科學與技術學院819計算機組成原理考研真題哈爾濱工程大學 2003 年計算機

26、組成原理試題 一、判斷題 （每小題 1分，共 10 分） 1在用分段直接編譯法為微指令編碼時，須將互斥微命令歸為一組，而將 相容命令歸為不同組。2345能力。6789器。定點機不支持浮點運算功能。 子程序技術可以有效降低程序所占資源開銷。 中斷向量地址指中斷服務程序的入口地址。N位二進制的全碼編碼系統（即 n個“0”至n個“ 1”）不具備自校驗負數的源碼，補碼，反碼互不相同。 補碼數所對應的真值范圍在數軸上完全對稱于零點。 中斷指令作為一種指令，可以用編制程序。 串行進位加法器實際上是一種并行加法1 0大型機不宜采用總線型系統結構。二、填空題（每空 1 分，共 20 分） 1采用隱式 I/O

27、指令系統，須使外圍設備的接口寄存器與主存單元 而采用專用 I/O 指令系統，則應使外圍設備的接口寄存器與主存單元 。2 .定點整數的字長n只要影響其指標；而定點小數的字長 n主要影響其指標。字段兩部分組成；而一條指3一般而言，一條指令由 字段和 _令則由字段和 字段兩部分組成。功能，而不具有4奇偶校驗校驗從功能上看，只具有一定的 功能。觸發器。5在原碼兩位乘的規則中，需要設置一個 6各種外圍設備均需通過 電路，才能掛接到系統總線上。7在一個三級存儲器中，如果訪問命中率足夠大，則存儲系統所表現出的 性能將接近于 的容量和 的速度。8在轉移型指令中，地址形成部件按指定尋址方式所形成的有效地址是 地

28、址，應將其傳送給 。9目的地址單元在執行指令過程中應承但 和雙重任務。1 0在時序控制方式中， 方式是時序關系比較簡單，而 方式的優點是時間利用安排上較為緊湊。三、單項選擇 （每小題 2 分 共 20 分） 1四位機器內的數值代碼，它所表示的十進制真值為（）（ 1） 9（ 2） -1 （ 3） -7 （ 4） 以上三者均有可能2. 常用的分組校驗（n, k）碼中，冗余位的位數為（）位 （1） n+k （2） n-k （3） n （4） k3. 間接尋址第一次訪問內存所得到的是操作數的有效地址，該地址經系統 總線的（ ）傳送到 CPU(1) 數據總線 (2) 地址總線 ( 3)控制總線 ( 4)

29、總線控制器4. 下列()是不合法的BCD碼( 1) 01111001 ( 2) 1101 0110 ( 3) 00000100 ( 4) 100001015. 動態存儲器DRAM的刷新原則是()(1)各DRAM芯片輪流刷新(2)各DRAM芯片同時刷新，片內逐位刷新(3)各DRAM芯片同時刷新，片內逐字刷(4)各DRAM芯片同時刷新，片內逐行刷新6. 在向上生成(地址碼減小方向)堆棧中，若約定為實頂棧(即堆棧指針 隨時指向實有數據的堆頂)，則正確的彈出數據操作為( )( 1) 先使( SP) +1, 再讀出數據 ( 2) 先讀出數據，再使( SP) 1 ( 3) 先使( SP) -1 再讀出數據( 4) 先讀出數據， 再使( SP) 17. ( )不是常用三級時序系統中的一級( 1)指令周期( 2)工作周期( 3)時鐘周期(4)定時脈沖8. ( )存儲結構對程序員是透明的( 1)通用寄存器 ( 2)主存 ( 3)控制寄存器( 4)堆棧9. 相對尋址方式中，指令所提供的相對地址實質上是一種()( 1)立即數(2)內存地址( 3)以本條指令在存中首地址為基準位置的偏移量( 4)以下指令在存中首地址為基準位置的偏移量10 .程序