北航計(jì)算機(jī)專業(yè)基礎(chǔ)真題

不那么

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

不那么

hao ding ding ding