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

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