1、你考研的超級(jí)班讓考研更輕松！科學(xué)院研究生院學(xué)位研究生入學(xué)統(tǒng)一考試試題2012 年招收攻讀科目名稱：計(jì)算機(jī)原理考生須知：1本試卷滿分為 150 分，全部考試時(shí)間總計(jì) 180 分鐘。2所有必須寫在答題紙上，寫在試題紙上或草稿紙上一律無(wú)效。一、填空題（每空 2 分，共 36 分）1.2.3.計(jì)算是一個(gè)由和組成的復(fù)雜的自動(dòng)化。按總線的邏輯結(jié)構(gòu)來(lái)說，總線可分為和。所謂定點(diǎn)格式，即。原理上講，小數(shù)點(diǎn)位置固定在哪一位都可以， 但是通常將數(shù)據(jù)表示成或 。4. 系統(tǒng)不僅是硬件設(shè)計(jì)的依據(jù)，而且是量計(jì)算機(jī)性能的一個(gè)重要因素。設(shè)計(jì)的基礎(chǔ)，是衡5.規(guī)格化的浮點(diǎn)數(shù)是指，使用 IEEE754 表示0.15625 時(shí)，編碼為

2、，編碼為 (41360000)16 的浮點(diǎn)數(shù)其十進(jìn)制數(shù)值為。6.若按層次順序給二叉樹各結(jié)點(diǎn)從 0 開始編號(hào)，則含 n 個(gè)結(jié)點(diǎn)的完全二叉樹中葉結(jié)點(diǎn)的最小編號(hào)是。7.后綴表3 2 * 4 5 6 3 / * + 的值為，表c*(b+2)+(2-a)/3對(duì)應(yīng)的后綴表為。n 個(gè)頂點(diǎn)的連通圖至少有條邊。8.9.用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)二叉樹，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外還包含指向結(jié)點(diǎn)的鏈接指針，在這種結(jié)構(gòu)下，n 個(gè)結(jié)點(diǎn)的二叉樹共有個(gè)指針域，其中個(gè)指針域存放了地址，而個(gè)指針域存放的是空指針。二、下列說法的正誤，并糾正其中錯(cuò)誤的說法（每小題 3 分，共 18 分）在有向圖中，所有結(jié)點(diǎn)的出度之和等于入度之和。1.2.從一個(gè)小根堆

3、中查找具有給定鍵值的元素，在最壞情況下需要 lgn 次比較操作?？颇棵Q：計(jì)算機(jī)原理第 1 頁(yè) 共 3 頁(yè)掃描二維碼關(guān)研班QQ 公眾號(hào)：kaoyan33，獲取最新考研咨訊，獲取資料你考研的超級(jí)班讓考研更輕松！3.4.Huffman 樹的結(jié)點(diǎn)個(gè)數(shù)一定是偶數(shù)。在一個(gè)包含 n 個(gè)元素的線性表中查找指定元素，采用折半查找比采用順序查找所需時(shí)間少。5.6.線性表的邏輯順序和物理順序總是一致的。假設(shè)高度為 H 的二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)，則該二叉樹結(jié)點(diǎn)數(shù)的最大值為 2H-1。三、簡(jiǎn)答題（每小題 5 分，共 30 分）1.2.指令和數(shù)據(jù)都存放在內(nèi)存中，計(jì)算機(jī)如何區(qū)分它們是指令還是數(shù)據(jù)？假設(shè)由

4、 S、E、M 三個(gè)域組成的一個(gè) 32 位二進(jìn)制數(shù)所表示的非 0 規(guī)格化浮點(diǎn)數(shù) x，其真值表示為 x = (-1)S(1.M)2E-128 ，則它所表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負(fù)數(shù)、最小負(fù)數(shù)分別是多少？3.一種單地址指令格式如下所示：其中 I 為間接特征，X 為尋址模式，D 為形式地址。I、X、D 組成該指令的操作數(shù)有效地址 E。設(shè) R 為變址寄存器，R1 為基址寄存器，PC 為程序計(jì)數(shù)器，請(qǐng)指出下表中的 (1)(6) 分別為何種尋址方式。4.ASCII 碼是 7 位，如果設(shè)計(jì)主存單元字長(zhǎng)為 32 位，指令字長(zhǎng)為 12 位， 是否合理？為什么？5.一個(gè)用高級(jí)語(yǔ)言編寫的程序在計(jì)算機(jī)上運(yùn)行

5、時(shí)所消耗的時(shí)間哪些因素？什么是算法的時(shí)間復(fù)雜度？取決于6.畫出和下列已知森林的先序次序森林的中序次序序列對(duì)應(yīng)的森林：序列為：NHMCLIBKDFJEAG； 序列為：MCHLNBIFDJAGEK。四、（15 分）某機(jī)字長(zhǎng) 16 位，使用 4 片 74181 組成 ALU，設(shè)最低位序號(hào)標(biāo)注為第 0 位。根據(jù)上述完成下列各題：1.2.3.（5 分）寫出第 5 位的進(jìn)位C6 的邏輯表；（5 分）估算產(chǎn)生 C6 所需的最長(zhǎng)時(shí)間；（5 分）估算最長(zhǎng)求和時(shí)間。科目名稱：計(jì)算機(jī)原理第 2 頁(yè) 共 3 頁(yè)掃描二維碼關(guān)研班QQ 公眾號(hào)：kaoyan33，獲取最新考研咨訊，獲取資料尋址方式IX有效地址 E(1)(2

6、)(3)(4)(5)(6)000011000110110011E=D E=(PC)+D E=(R)+D E=(R1)+D E=(D)E=(R1)+D), D=0OPIXD你考研的超級(jí)班讓考研更輕松！五、（15 分）某機(jī)器中，已知配有一個(gè)地址空間為 0000H3FFFH 的 ROM 區(qū)域，現(xiàn)在再用一種 RAM址為 6000H。假設(shè) RAM（8K8）形成 40K16 位的 RAM 區(qū)域，起始地有CS 和WE 信號(hào)端，CPU 的地址總線為A15A0，數(shù)據(jù)總線為 D15D0，信號(hào)為 R/W（讀/寫）、MREQ （訪存）?；谏鲜?，請(qǐng)完成下列各題：1. （7 分）畫出地址譯碼方案；2. （8 分）畫出 ROM 與 RAM 同 CPU 的連接圖。六、（8 分）試編寫算法，計(jì)算 i!2i (i=0,1,n-1) 的值并依次存入整數(shù)數(shù)組aMAXSIZE中。假設(shè)計(jì)算機(jī)中的最大整數(shù)為 MAXINT。七、（16 分）求證：若一棵二叉樹的先序序列是u1, u2 ,L, un ，則其中序序列是up , up ,L, up 當(dāng)且僅當(dāng)序列1,2,L, n 可通過一個(gè)棧得到序列 p1, p2 ,L, pn 。12n八、（12 分）設(shè)有向圖 G 采用鄰接表方式，試設(shè)