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

不那么

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

不那么

hao ding ding ding