二﹑綜合應(yīng)用題：41~47小題，共70分

　　1 設(shè)哈希函數(shù)H(k)=3 K mod 11，散列地址空間為0～10，對關(guān)鍵字序列(32,13,49,24,38,21,4,12)按下述兩種解決沖突的方法構(gòu)造哈希表(1)線性探測再散列(2)鏈地址法，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。(15分)

　　2 圖的D_搜索類似與BFS,不同之處在于使用棧代替BFS中的隊列 ,入出隊列的操作改為入出棧的操作，即當(dāng)一個頂點的所有鄰接點被搜索之后,下一個搜索出發(fā)點應(yīng)該是最近入棧(棧頂)的頂點。用鄰接表做存儲結(jié)構(gòu),寫一個D_搜索算法(10分)

　　3 求信息碼01101110的海明校驗碼，畫出能指出2位出錯和糾正一位出錯位的海明校驗邏輯。(15分)

　　4 什么叫頁式虛擬存儲器?什么叫頁表?說明工作原理。(6分)

　　5 有一個虛擬存儲系統(tǒng),分配給某個進程3頁內(nèi)存,開始時內(nèi)存為空,頁面訪問序列如下:6,5,4,3,2,1,5,4,3,6,5,4,3,2,1,6,5.

　　(1) (2分)采用先進先出頁面置換算法,缺頁次數(shù)為多少?

　　(2) (2分)采用最近最少使用頁面置換算法,缺頁次數(shù)為多少?

　　(3) (2分)采用最佳頁面置換算法,缺頁次數(shù)為多少?

　　6 什么是AND信號量?試?yán)�用AND信號量寫出生產(chǎn)者-消費者問題的解法。(9分)

　　7 在數(shù)據(jù)傳輸速率為50kb/s的衛(wèi)星信道上發(fā)送長度為1kb的幀。假設(shè)確認(rèn)總是由數(shù)據(jù)幀捎帶。幀頭很短，幀序號的長度為3比特。對于下列三種協(xié)議可以取得的最大利用率是多少?(假設(shè)衛(wèi)星信道端到端的單向傳播延遲時間為270ms)

　　(1) (3分)停止等待協(xié)議;

　　(2) (3分)后退N滑動窗口協(xié)議;

　　(3) (3分)選擇重發(fā)滑動窗口協(xié)議。