2013中國科學(xué)院大學(xué)考研真題之計算機(jī)原理

1、科目名稱：計算機(jī)原理第1頁共4頁中國科學(xué)院中國科學(xué)院大學(xué)大學(xué)2013年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題年招收攻讀碩士學(xué)位研究生入學(xué)統(tǒng)一考試試題科目名稱：科目名稱：計算機(jī)原理計算機(jī)原理考生須知：考生須知：1本試卷滿分為150分，全部考試時間總計180分鐘。2所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。一、單選題（每空3分，共45分）1.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除一個元素，則采用最節(jié)省運

2、算時間的存儲方式是。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表2.鏈表不具有的特點是。A.插入、刪除操作不需要移動元素B.可隨機(jī)訪問任一元素C.不必事先估計存儲空間D.所需空間與線性表長度成正比3.設(shè)廣義表L=（（a，b，c）），則L的長度和深度分別是。A1和1B.1和3C.1和2D.2和34.在樹的雙親表示法中，對樹按層次編號，用數(shù)組進(jìn)行存儲，則下面說法不正確的是。A.兄結(jié)點的下標(biāo)值小于弟結(jié)點的下標(biāo)值B.

3、所有結(jié)點的雙親可以找到C.任意結(jié)點的孩子信息可以找到D.下標(biāo)值為i和i1結(jié)點的關(guān)系是孩子和雙親5.對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進(jìn)行的操作為。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ù)類型科目名稱：計算機(jī)原理第3頁共4頁3）數(shù)組按行存放時，元素A[7][4]的起始地址是多少？

4、4）數(shù)組按列存放時，A[4][7]的起始地址是多少？3.已知一顆二叉樹的先序遍歷序列、中序遍歷序列和后續(xù)遍歷序列分別為：xBCxExGH，CxDAxGHF，xDBxxFEA，但有些字母已模糊不清了（用x表示），試畫出這顆二叉樹。4.當(dāng)將兩個長度為n的有序表A=(a1a2…..an)與B=(b1b2….bn)，(ai≠bj1≤ij≤n)歸并為一個有序表C=(c1c2…c2n)時，所需進(jìn)行的元素比較次數(shù)最少可達(dá)n，最多可達(dá)2n1。1）假設(shè)有

5、序表C=(245679)，試舉出兩組A與B的例子，使它們在歸并過程中進(jìn)行的元素比較次數(shù)分別達(dá)到最少和最多；2）寫出一般情況下，使歸并所需進(jìn)行的元素比較次數(shù)分別達(dá)到最少和最多時，A與B中的元素應(yīng)滿足的條件。5.RISC指令系統(tǒng)的特點是什么？6.在一個分頁虛存系統(tǒng)中，用戶虛地址空間為32頁，頁長2KB，主存物理空間為16KB。已知某用戶程序有7頁長，虛頁0、1、2、3已經(jīng)分別被調(diào)入到主存7、4、5、1頁中，求虛地址(0ED7)16和(2ED

6、7)16對應(yīng)的物理地址。7.分別說出SRAM和DRAM的工作機(jī)理，比較它們的優(yōu)缺點。三、（20分）已知一顆樹采用下列結(jié)點結(jié)構(gòu)用孩子兄弟法表示：FirstChildhddataNextSiblinghx其中，data為數(shù)據(jù)域，F(xiàn)irstChild為左鏈域，NextSibling為右鏈域，hd域用于存放該結(jié)點的后代結(jié)點數(shù)，hx域用于存放該結(jié)點所有右邊的兄弟結(jié)點數(shù)。hd和hx的初值都為0。編寫算法，將每個結(jié)點的后代結(jié)點數(shù)存入hd域，將每個結(jié)點

7、所有右邊的兄弟結(jié)點數(shù)存入hx域。四、（20分）已知無向圖G有n個頂點(用12…n表示)，采用鄰接表存儲方式，試編寫求圖G的連通分量的算法。要求輸出每一連通分量的頂點值。五、（15分）一臺字長16位的計算機(jī)，有16個寄存器，主存容量為8M，具有無操作數(shù)、單操作數(shù)、雙操作數(shù)三類指令，其中無操作數(shù)指令10個，單操作數(shù)指令20個，雙操作數(shù)指令8個，1.操作碼的位寬應(yīng)是多少？2.RS型雙操作數(shù)間接尋址所允許的最大尋址空間是多少？3.設(shè)計段尋址方式