2019年山東大學(xué)計(jì)算機(jī)基礎(chǔ)綜合考研真題

2019年山東大學(xué)計(jì)算機(jī)基礎(chǔ)綜合考研真題數(shù)據(jù)結(jié)構(gòu)一、簡答題（共3題，共26分）1.（8分）散列表長度為13，散列函數(shù)為Hash（k）=k%13。請分別寫出序列（12，8，16，27，21，17，3，28，47）的線性開型尋址散列存儲結(jié)構(gòu)和鏈表散列結(jié)構(gòu)。2.（10分）假設(shè)用于通信的電文由字符集{a，b，c，d，e，f，g中的字母構(gòu)成，它們在電文中出現(xiàn)的頻率分別為{31，16，10，8，11，20，4）。（1）畫出霍夫曼樹（霍夫曼樹構(gòu)造中，左子樹權(quán)值小于等于右子樹），并求WPL;（2）為這7個(gè)字母設(shè)計(jì)霍夫曼編碼（分支編碼左0右1）;（3）對這7個(gè)字母進(jìn)行等長編碼，至少需要幾位二進(jìn)制數(shù)?霍夫曼編碼比等長編碼使電文總長壓縮多少?3.（8分）如何判別以鄰接表方式存儲的無向圖中是否存在由頂點(diǎn)u到頂點(diǎn)v的路徑（u≠v），請描述出實(shí)現(xiàn)思路。二、算法題（共2題，每小題12分，共24分）1.（12分）在包含n個(gè)元素的單向鏈表中，找到鏈表中倒數(shù)第k個(gè)元素，k<n。要求時(shí)間復(fù)雜性為0（n）。（1）描述算法的設(shè)計(jì)思想（（2）根據(jù)設(shè)計(jì)思想，給出算法實(shí)現(xiàn)，關(guān)鍵之處請給出注釋.2.（12分）設(shè)二叉樹采用鏈表描述，t為指向根節(jié)點(diǎn)的指針，節(jié)點(diǎn)結(jié)構(gòu)為（leftchild，data，rightchild，其中data為元素的值，，leftchild和rightchild分別表示指向左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)的指針。設(shè)計(jì)算法，判斷二叉樹是否為最小堆。（1）描述算法的設(shè)計(jì)思想（2）根據(jù)設(shè)計(jì)思想，給出算法實(shí)現(xiàn)，關(guān)鍵之處請給出注釋.（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。操作系統(tǒng)一、概念解釋（每小題4分，共20分）1.對等模式（PeertoPeer）2.應(yīng)用程序（ApplicationProgram）3.操作系統(tǒng)的分層設(shè)計(jì)方法4.虛擬機(jī)5.上下文切換二、簡答題（每題10分，共30分）1.有一個(gè)停車場，有兩個(gè)入口，三個(gè)出口。車輛進(jìn)入時(shí)需要登記，出來時(shí)要繳費(fèi)。每個(gè)入口或出口同時(shí)只能為一輛車服務(wù)。車庫內(nèi)的停車位有52個(gè)。請用信號量機(jī)制描述每輛車進(jìn)出停車場時(shí)，車輛之間的同步行為。2.什么是線程池（ThreadPool）?在服務(wù)器中采用線程池有什么好處?3.在調(diào)頁式虛擬內(nèi)存管理中，假設(shè)當(dāng)前進(jìn)程可分配頁面數(shù)為3，以下是頁面訪問的次序∶0,1,2,1,3,4,1,3,0,3,2請分別計(jì)算采用FIFO和LRU方法需要置換頁的次數(shù)。計(jì)算機(jī)組成一、簡答題（第1、3小題各5分，第2小題7分，第4小題8分，共25分）1.以全相聯(lián)映射技術(shù)為例，說明在帶有Cache的存儲系統(tǒng)中，"讀"操作是怎樣完成的。2.設(shè)用原碼一位乘法計(jì)算x·y，（寫出計(jì)算步驟）。3.設(shè)指令字長為16位，采用擴(kuò)展操作碼技術(shù)，每個(gè)操作數(shù)的地址為6位。如果定義了13條二地址指令，試問還可安排多少條一地址指令?4.在程序查詢方式的輸入輸出系統(tǒng)中，假設(shè)不考慮處理時(shí)間，每一個(gè)查詢操作需要100個(gè)時(shí)鐘周期，CPU的時(shí)鐘頻率為40MHz。現(xiàn)有鼠標(biāo)和硬盤兩個(gè)設(shè)備，而且CPU必須每秒對鼠標(biāo)進(jìn)行30次查詢，硬盤以32位字長為單位傳輸數(shù)據(jù)，即每32位被CPU查詢一次，傳輸率為2.5MBps。求CPU對這兩個(gè)設(shè)備查詢所花費(fèi)的時(shí)間比率，由此可得出什么結(jié)論?二、分析設(shè)計(jì)題（第1小題12分，第2小題13分，共25分）1.設(shè)某微型計(jì)算機(jī)的尋址范圍為64K，接有8片8K的存儲芯片，存儲芯片的片選信號為CS，要求∶（1）畫出選片譯碼邏輯電路（可選用74138譯碼器）（2）寫出每片RAM的地址范圍（3）如果運(yùn)行時(shí)發(fā)現(xiàn)只有以0000H為起始地址的一片存儲芯片不能讀寫，分析故障原因，如何解決?2.某主機(jī)數(shù)據(jù)通路如下圖所示。指令格式為∶ADD@B;其中，B是通用寄存器，@為間接尋址符號，指令含義為∶（AC）加（（B））—>AC;即將B的內(nèi)容