科學(xué)院大學(xué)吉林省培養(yǎng)單位計算機原理歷年考研真題匯編

單位計算機原理歷年考研真題匯編2013年中國科學(xué)院大學(xué)吉林省培養(yǎng)單位866計算機原理考研真題2013年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題1.本試卷滿分為150分，全部考試時間總計180分鐘。2.所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。一、單選題(每空3分，共45分)1.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除一個元素，則采用最節(jié)省運算時間的存儲方式是。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表2.鏈表不具有的特點是。A.插入、刪除操作不需要移動元素B.可隨機訪問任一元素C.不必事先估計存儲空間D.所需空間與線性表長度成正比3.設(shè)廣義表L=((a,b,c)),則L的長度和深度分別是。4.在樹的雙親表示法中，對樹按層次編號，用數(shù)組進行存儲，則下面說法不正確的是。A.兄結(jié)點的下標值小于弟結(jié)點的下標值B.所有結(jié)點的雙親可以找到C.任意結(jié)點的孩子信息可以找到D.下標值為i和i+1結(jié)點的關(guān)系是孩子和雙親5.對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進行的操作A.求一個頂點的鄰接點B.求一個頂點的度C.深度優(yōu)先遍歷D.廣度優(yōu)先遍歷6.含n個關(guān)鍵字的二叉排序樹的平均查找長度主要取決于。A.關(guān)鍵字的個數(shù)B.樹的形態(tài)C.關(guān)鍵字的取值范圍D.關(guān)鍵字的數(shù)據(jù)類型7.下列排序算法中，其時間復(fù)雜度和記錄的初始排列無關(guān)的A.折半插入排序B.堆排序C.快速排序D.冒泡排序A.存取獨立B.存儲程序C.流水處理D.并行處理10.某浮點數(shù)x按IEEE754標準表示其16進制存儲格式為(C1360000)?6,則其十進制數(shù)值為。A.相對尋址B.寄存器間接尋址C.變址尋址D.先相對后間接尋址12.一片容量為64k×8bit的SRAM存儲器芯片，地址范圍從0000H。13.CPU從主存中取出一條指令的時間為m,執(zhí)行這條指令的時間為n,CPU的指令周期是。A.mB.nC.mtnD.時鐘周期14.CPU從主存中讀取一條指令字的最短時間稱為。A.取址周期B.尋址周期C.指令周期D.機器周期15.在Cache和主存構(gòu)成的二級存儲體系中，Cache的存取時間是10ns,主存的存取時間為100ns,如果希望平均存取時間不超過主存存取時間的15%,則Cache的命中率至少為。二、簡答題(每小題5分，共35分)1.設(shè)有5個元素，其進棧次序為A、B、C、D、E,在各種可能的出棧序列中，第一個出棧元素是C且第二個出棧元素是D的出棧序列有哪幾2.數(shù)組A[-1..9,1.11]中，每個元素的長度為32位，從首地址S開始連續(xù)存放在主存儲器中，主存儲器字長為16位。求：1)存放該數(shù)組需要多少單元?2)存放該數(shù)組第4列所有元素至少需要多少單元?科目名稱：計算機原理3)數(shù)組按行存放時，元素A[7][4]的起始地址是多少?xBCxExGH,CxDAxGHF,xDBxxFEA,但有些字母已模糊不清了(用x表示),試畫出這顆二叉樹。最少可達n,最多可達2n-1。歸并過程中進行的元素比較次數(shù)分別達到最少和最多2)寫出一般情況下，使歸并所需進行的元素比較次數(shù)分別達到最少和最5.RISC指令系統(tǒng)的特點是什么?6.在一個分頁虛存系統(tǒng)中，用戶虛地址空間為32頁，頁長2KB,主存物理空間為16KB。已知某用戶程序有7頁長，虛頁0、1、2、3已經(jīng)分別被調(diào)入到主存7、4、5、1頁中，求虛地址(0ED7)?6和(2ED7)16對應(yīng)7.分別說出SRAM和DRAM的工作機理，比較它們的優(yōu)缺點。三、(20分)已知一顆樹采用下列結(jié)點結(jié)構(gòu)用孩子兄弟法表示：hd和hx的初值都為0。編寫算法，將每個結(jié)點的后代結(jié)點數(shù)存入hd域，將每個結(jié)點所有右邊的兄弟結(jié)點數(shù)存入hx域。四、(20分)已知無向圖G有n個頂點(用1,2,…n表示),采用鄰接表存儲方式，試編寫求圖G的連通分量的算法。要求輸出每一連通分量的頂點值。五、(15分)一臺字長16位的計算機，有16個寄存器，主存容量為8M,具有無操作數(shù)、單操作數(shù)、雙操作數(shù)三類指令，其中無操作數(shù)指令10個，單操作數(shù)指令20個，雙操作數(shù)指令8個，1.操作碼的位寬應(yīng)是多少?2.RS型雙操作數(shù)間接尋址所允許的最大尋址空間是多少?3.設(shè)計段尋址方式使段尋址可達整個主存空間?六、(15分)用若干個8x8RAM設(shè)計一個8位字長，容量32位的RAM,說明2012年中國科學(xué)院大學(xué)吉林省培養(yǎng)單位866計算機原理考研真題中國科學(xué)院研究生院2012年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題科目名稱：計算機原理1.本試卷滿分為150分，全部考試時間總計180分鐘。一、填空題(每空2分，共36分)位置固定在哪一位都可以，但是通常將數(shù)據(jù)表示成或05.規(guī)格化的浮點數(shù)是指,使用IEEE754表示0.15625時，編碼為,編碼為(41360000)16的浮點數(shù)其十進制數(shù)值為。6.若按層次順序給二叉樹各結(jié)點從0開始編號，則含n個結(jié)點的完全二叉7.后綴表達式32*4-563/*+的值為,表達式對應(yīng)的后綴表達式為。針域，其中個指針域存放了地址，而個指針域存放的是二、判斷下列說法的正誤，并糾正其中錯誤的說法(每小題3分，共18分)4.在一個包含n個元素的線性表中查找指定元素，采用折半查找比采用順5.線性表的邏輯順序和物理順序總是一致的。6.假設(shè)高度為H的二叉樹上只有度為0和度為2的結(jié)點，則該二叉樹結(jié)點數(shù)的最大值為2#'。三、簡答題(每小題5分，共30分)1.指令和數(shù)據(jù)都存放在內(nèi)存中，計算機如何區(qū)分它們是指令還是數(shù)據(jù)?2.假設(shè)由S、E、M三個域組成的一個32位二進制數(shù)所表示的非0規(guī)格化浮點數(shù)x,其真值表示為x=(-1)?×(1.M)×28-128,則它所表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負數(shù)、最小負數(shù)分別是多少?1XD程序計數(shù)器，請指出下表中的(1)~(6)分別為何種尋址方式。尋址方式1X有效地址E0000114.ASCⅡ碼是7位，如果設(shè)計主存單元字長為32位，指令字長為12位，是否合理?為什么?5.一個用高級語言編寫的程序在計算機上運行時所消耗的時間一般取決于哪些因素?什么是算法的時間復(fù)雜度?四、(15分)某機字長16位，使用4片74181組成ALU,設(shè)最低位序號標注為第0位。根據(jù)上述信息完成下列各題：1.(5分)寫出第5位的進位信息C?的邏輯表達式；2.(5分)估算產(chǎn)生C?所需的最長時間：3.(5分)估算最長求和時間。現(xiàn)在再用一種RAM芯片(8K×8)形成40K×16位的RAM區(qū)域，起始地1.(7分)畫出地址譯碼方案；2.(8分)畫出ROM與RAM同CPU的連接圖。六、(8分)試編寫算法，計算七、(16分)求證：若一棵二叉樹的先序序列是u,u?,…,u,,則其中序序列是八、(12分)設(shè)有向圖G采用鄰接表方式存儲，試設(shè)計一個算法，采用廣度優(yōu)科目名稱：計算機原理2007年中國科學(xué)院大學(xué)吉林省培養(yǎng)單位866計算機原理考研真題2007年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題1.本試卷滿分為150分，全部考試時間總計180分鐘。2.所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。數(shù)據(jù)結(jié)構(gòu)部分(共75分)一、選擇題(共20分，每題2分);AA444240B:科目名稱：計算機原理5、一棵滿3叉樹，按層次遍歷的方式存儲在一維數(shù)組A[1…N]中，A、2mB、m+1C、2m-1D不能唯一確定0-11-41-62-33-44-25-26二、簡答題(16分)(2)(4分)如果我們使用線性探測再Hash法為1000個元素設(shè)計Hash表，Hash函數(shù)的類型(3)(4分)下圖表示的是一個三階B-樹，請畫出在此樹中插入值47后的結(jié)果。第2頁第2頁共6頁(4)、(4分)假設(shè)科目名稱：計算機原理計算機組成原理部分(共75分)一、填空題：(共25分)(1)(4分)馮·羅依曼計算機由()、()、()和()組成。馮氏機比起之前的計算裝置最大的改進是()。早期的馮氏機以(心，現(xiàn)在的計算機是以()為中心，這種變化的主要原因是((分)在計算機中，浮點數(shù)不能夠精確表示，產(chǎn)生這種誤差的(浮點數(shù)IEEE754的編碼為((3)(7分)已知CPU第4頁第4頁共6頁假定一個應(yīng)用程序被分配給4個物理頁框，頁面訪問序列為1817827218()、主存地址格式為()主存地址48AB9H映射到Cache的()