2019年山東大學計算機基礎綜合考研真題

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