|
 減小字體 增大字體
一、簡(jiǎn)答題(4’×5)
1、寫(xiě)出影響算法執(zhí)行的時(shí)間效率的主要因素，并指出哪些因素與算法的時(shí)間效率直接相關(guān)。
2、已知元素的入棧順序?yàn)锳,B,C,D,E，在所有可能的出棧順序中，寫(xiě)出第一個(gè)出棧的元素為C且第二個(gè)出棧的元素為D的所有組合。
3、根據(jù)單詞(Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr)的第一個(gè)字母在字母表中的順序建立二叉排序樹(shù)，當(dāng)每個(gè)元素的查找概率相等時(shí)，求查找成功時(shí)的平均查找長(zhǎng)度ASL。
4、證明：具有n個(gè)頂點(diǎn)的無(wú)向圖最多有 條邊。
5、有人說(shuō)，折半查找的時(shí)間效率一定比順序查找的時(shí)間效率高，你怎么看待這種說(shuō)法?為什么?
二、算法設(shè)計(jì)題(10’)
已知一非空完全二叉樹(shù)存放于數(shù)組 中，請(qǐng)寫(xiě)出中序遍歷該二叉樹(shù)的非遞歸算法。
三、算法設(shè)計(jì)題(10’)
寫(xiě)出不帶頭結(jié)點(diǎn)的雙向鏈表的插入排序算法。
四、簡(jiǎn)答題(4’×5)
1、數(shù)據(jù)傳輸控制方式有哪些?
2、引入線程的目的是什么?
3、P, V操作是如何實(shí)現(xiàn)互斥的的?
4、什么是死鎖?產(chǎn)生死鎖的原因是什么?
5、什么是文件系統(tǒng)?
五、判斷題(1’×10)
略。(基本上來(lái)自于歷年真題)
六、解答題(10’)
某機(jī)器字長(zhǎng)為16位，采用段頁(yè)式存儲(chǔ)管理算法，頁(yè)內(nèi)偏移為12位，段表和頁(yè)表內(nèi)容如下，給出4個(gè)虛擬地址(二進(jìn)制形式)，問(wèn)哪個(gè)地址產(chǎn)生缺段中斷，哪個(gè)地址產(chǎn)生缺頁(yè)中斷，哪些地址可以轉(zhuǎn)換為物理地址，并求轉(zhuǎn)換后的物理地址。(地址格式中段號(hào)占1位，段內(nèi)頁(yè)號(hào)占3位，頁(yè)內(nèi)偏移為12位，另外，在給出的頁(yè)表中，物理塊號(hào)占6位，最后又問(wèn)該機(jī)器的最大物理內(nèi)存是多少(答案：256 KB)。)
七、簡(jiǎn)答題(4’×4)
1、利用等值演算的方法，寫(xiě)出求命題邏輯公式的主范式的方法。
2、謂詞邏輯中的永假式、可滿(mǎn)足式、重言式、永真式之間的關(guān)系是什么?
3、 之間的真值關(guān)系是什么?
4、如何判斷公式中某個(gè)變?cè)羌s束變?cè)�是自由變?cè)?舉例說(shuō)明一個(gè)變?cè)梢约仁羌s束的又是自由的。
八、判斷下列結(jié)論是否成立，并至少用兩種方法證明你的判斷(6’ + 8’)
1、
2、
九、填空題(1’×8)
1、馮•諾依曼計(jì)算機(jī)體系包括存儲(chǔ)器、運(yùn)算器、控制器和輸入輸出設(shè)備。
2、在總線同步控制方式種，哪一種速度最快，哪一種對(duì)電路故障最敏感?
3、在程序查詢(xún)方式、程序中斷方式和DMA方式中，哪一種方式主存與設(shè)備間有數(shù)據(jù)通路，哪一種方式使CPU與外設(shè)串行化?
4、指令中的操作數(shù)分別為立即尋址和寄存器直接尋址時(shí)CPU訪問(wèn)主存的次數(shù)分別為多少次?
5、存儲(chǔ)器分層體系是根據(jù)程序訪問(wèn)的局部性原理提出的。
十、存儲(chǔ)器擴(kuò)展的題(6’)
某機(jī)器字長(zhǎng)為16位，最大物理內(nèi)存為64 KB，最低地址的8 KB存放BIOS程序，其他空間存放用戶(hù)程序，現(xiàn)有4K×4的ROM和4K×4的SRAM，問(wèn)各需要多少片?
十一、Cache題(8’)
主存大小為2 MB，Cache大小為8 KB，采用2路組相聯(lián)方式，每個(gè)Cache塊大小為128字節(jié)。
(1)求主存地址格式及各字段的位數(shù)和含義
(2)Cache的格式
(3)Cache的Tag需多少位?
十二、指令系統(tǒng)的設(shè)計(jì)(8’)
某機(jī)器字長(zhǎng)為16位，有8個(gè)16位的通用寄存器，請(qǐng)?jiān)O(shè)計(jì)一指令系統(tǒng)，要求：
(1)共有128條雙操作數(shù)指令，且必有一操作數(shù)為寄存器直接尋址，另一個(gè)操作數(shù)有4種尋址方式，可以是立即尋址、寄存器直接尋址、寄存器間接尋址或變址尋址，其中立即尋址和變址尋址的偏移量均為16位;
(2)指令所占的位數(shù)必須是16的倍數(shù)且要盡可能地短。
要求：
(1)寫(xiě)出影響指令系統(tǒng)設(shè)計(jì)的因素;
(2)設(shè)計(jì)該機(jī)器的指令系統(tǒng)，寫(xiě)出各字段的位數(shù)和含義。
十三、微程序設(shè)計(jì)題(10’)
指令為SUB R0, (R1)，其中R0為目的操作數(shù)，采用寄存器直接尋址，R1為源操作數(shù)，尋址方式為寄存器間接尋址，每個(gè)機(jī)器周期包含4個(gè)節(jié)拍周期，寫(xiě)出該指令執(zhí)行的詳細(xì)微操作流程和對(duì)應(yīng)處于有效狀態(tài)的控制信號(hào)。
| |
你的位置：
中國(guó)研究生信息網(wǎng)-復(fù)習(xí)指導(dǎo)_歷年試題