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