北京大學(xué)2005年碩士研究生入學(xué)考試試題
考試科目：計(jì)算機(jī)軟件基礎(chǔ)                 考試時(shí)間：2005年1月23號(hào)下午
招生專業(yè)：計(jì)算機(jī)軟件與理論、計(jì)算機(jī)應(yīng)用  
研究方向：                                                            
 
 說(shuō)明：答案一律寫(xiě)在答題紙上（含填空題，選擇題等客觀題），寫(xiě)在此頁(yè)無(wú)效。
 
一、（35分） 基礎(chǔ)知識(shí)填空

1．   對(duì)于非空滿K叉樹(shù)，其分支結(jié)點(diǎn)數(shù)目為n，則其葉結(jié)點(diǎn)數(shù)目為_(kāi)_______________。

2．   高度為h的AVL樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是__________個(gè)，最多結(jié)點(diǎn)個(gè)數(shù)是_______。

3．   有n個(gè)頂點(diǎn)的有向連通圖最少有_________條邊。

4．   某二叉樹(shù)中序序列為A，B，C，D，E，F(xiàn)，G，后序序列為B，D，C，A，F(xiàn)，G，E，則前序序列是____________________________。

5．   關(guān)鍵碼序列（tang,deng ,an ,wan,shi,bai ,fang ,liu）按字典順序排序（”an”<”bai”,空格小于任何其它字符）。采用“右補(bǔ)空格”，使得這些關(guān)鍵碼都成為4位字符的等長(zhǎng)關(guān)鍵碼。按最低位優(yōu)先法進(jìn)行基數(shù)排序，進(jìn)行兩趟分配和收集后得到的序列為_(kāi)________________。

6．   將一個(gè)A[1…100,1…100]的三對(duì)角矩陣，按行優(yōu)先順序存儲(chǔ)在一維數(shù)組B[1…298]中，A中元素A[66][65]在B數(shù)組中的位置K為
注釋：三對(duì)角矩陣是對(duì)角線以及對(duì)角線的上下兩條與對(duì)角線斜率相同的緊鄰斜線上的元素不為零，而其它位置元素都是零的矩陣，它的特點(diǎn)是第一行和最后以行各有兩個(gè)非零元素，去他各行各有三個(gè)非零元素

二（30分） 辨析題

1.請(qǐng)?jiān)O(shè)計(jì)一種“自調(diào)整’數(shù)據(jù)結(jié)構(gòu)。假設(shè)檢索的關(guān)鍵碼是中文詞組。 要求：

（1）定義其ADT（說(shuō)明其邏輯結(jié)構(gòu)，以及主要的運(yùn)算）。

（2）簡(jiǎn)單的說(shuō)明它怎樣根據(jù)所檢索過(guò)的中文詞組的而進(jìn)行調(diào)整，使得最近出現(xiàn)的詞組能比較快速的被檢索到。

2．請(qǐng)判斷下述計(jì)算前綴表達(dá)式的算法是否正確。
（a）如果正確，請(qǐng)給出一個(gè)簡(jiǎn)單實(shí)例，演示算法運(yùn)行步驟；
(b)如果不正確，請(qǐng)指出錯(cuò)誤之處，并給出改正后的算法，如果只是局部修改，可以只具體給出所修改部分 ，其他未修改部分，用其原來(lái)的功能編號(hào)(1)(2)，a, b.1,b.2 指代。
[計(jì)算前綴表達(dá)式的算法]
// 利用一個(gè)棧，從左向右掃描，邊掃描邊求值。

（1）         從左向右掃描前綴表達(dá)式：
a : 當(dāng)遇到的是一個(gè)運(yùn)算符時(shí)，則操作數(shù)入棧，轉(zhuǎn)到1。
b．對(duì)于操作數(shù)，如果棧為空，則將該操作數(shù)返回，退出；如果棧不空：
  b.1：當(dāng)棧頂是一個(gè)操作符時(shí)，則將操作數(shù)壓入棧中，轉(zhuǎn)到1；
  b.2：當(dāng)棧頂也是一個(gè)操作數(shù)是，兩次取棧頂（第二次取得的應(yīng)為操作符），并按照運(yùn)算符對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算（其中從棧中取得的操作數(shù)為第一操作數(shù)），所的計(jì)算結(jié)果作為操作數(shù)，將新操作數(shù)入棧，轉(zhuǎn)到1。

（2）掃描結(jié)束，正確的情況，輸出結(jié)果應(yīng)該在b處返回，并退出；如果程序沒(méi)有在b處返回退出，而是進(jìn)行到此處，則表明出錯(cuò)，輸出錯(cuò)誤消息。
[計(jì)算前綴表達(dá)式的算法結(jié)束]
注釋：前綴表達(dá)式與后綴表達(dá)式一樣，不包含括號(hào)，運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的前面，如*+213。

3．請(qǐng)判斷下面快速模式匹配算法KMP_FindPat()是否正確。
（a） 如果正確，請(qǐng)給出一個(gè)簡(jiǎn)單實(shí)例，演示算法運(yùn)行步驟；
 （b）如果不正確，請(qǐng)指出錯(cuò)誤之處，并給出改正后的算法，如果只是局部修
改，只需要具體給出所修改的部分（例如，第x行-第y行代碼修改為………）。
int *Next(String P){
int m=P.strlen();     //m為模板P的長(zhǎng)度
assert( m>0);       // 若m=0,退出
int *N = new int[m];    //動(dòng)態(tài)存儲(chǔ)區(qū)開(kāi)辟整數(shù)數(shù)組
assert ( N !=0); //若開(kāi)辟存儲(chǔ)區(qū)域失敗，退出
N[0]=0;       //分析P的每個(gè)位置i
for (int i=1;i<m;i++){
 int k=N[i-1];  //第（i-1）位置的最長(zhǎng)前綴串長(zhǎng)度
//以下while 語(yǔ)句遞推決定合適的前綴位置k
while (k>0 &&p[i]!=p[k])
K=N[k-1];
//根據(jù)P[i]比較第k位置前綴字符，決定N[i]
If  (p[i]==p[k])
N[i]=k+1;
else N[i] = 0;
}
return N;
}
int KMP_FindPat(String S,String P, int *N,int startindex){    /* 第1行*/
//假定事先已經(jīng)計(jì)算出P的特征數(shù)組N，并作為輸入?yún)��?shù)  /* 第2行*/
int LastIndex=S.strlen()-P.strlen();                        /* 第3行*/
if ((LastrIndex-startindex)<0)                            /* 第4行*/
Return(-1);   // 匹配失敗                              /* 第5行*/
int i;// i是指向S 內(nèi)部字符的游標(biāo)                       /* 第6行*/
int j=0;   //  j是指向P內(nèi)部字符的游標(biāo)                  /* 第7行*/
for (i=startindex;i<LastIndex;i++){ //I 是S游標(biāo)              /* 第8行*/
//若當(dāng)前位置的字符不同，則用N循環(huán)求當(dāng)前的j           /* 第9行*/
while ( P[j]!=S[i])                                     /* 第10行*/
j=N[j-1];  //尋找j將p 的恰當(dāng)位置與S 的i位置對(duì)準(zhǔn)    /* 第11行*/
if (P[j]==S[i])   //P[j]==S[i]位相同時(shí)，則繼續(xù)下一步循環(huán) /* 第12行*/
j++;  /* 第13行*/  
//若當(dāng)前位置的字符不同，j將由下一步循環(huán)的N循環(huán)決定     /* 第14行*/
if (j==P.strlen())                                     /* 第15行*//
return(i-j);   //匹配成功，返回該S子串的開(kāi)始位置    /* 第16行*/
}                                            /* 第17行*/
return (-1);                                        /* 第18行*/
}                                                  /* 第19行*/

三（15分）算法填空
下面是一個(gè)拓?fù)渑判蛩惴�，�?duì)于帶回路的圖，該算法將調(diào)用 “此圖有環(huán)！”，并逐步退出到調(diào)用它的主調(diào)函數(shù)。請(qǐng)?zhí)畛渌惴ㄖ锌杖钡牟糠�，使其成為完整的算法�?br />//深度優(yōu)先搜索方式實(shí)現(xiàn)拓?fù)渑判?br />void Do_topsort_Circle(Graph & G,int V, int *result,int & tag)
{
if(G.Mark[v]==VISITED){
空缺1                         
}
G.Mark[v]=VISITED;
for (Edge  e=G.FirstEdge(v);G.IsEdge(e);e.=G.NextEdge(e)){
If (空缺2                               ）
Do_topsort_Circle(G,G.ToVertex(e),result,tag);
}
result[tag++]=V;
空缺3                
}

四（40分） 問(wèn)答題

1. 實(shí)現(xiàn)進(jìn)程通信的方式有幾種？請(qǐng)分別簡(jiǎn)要描述這些通信方式。

2. 在實(shí)現(xiàn)虛擬頁(yè)式存儲(chǔ)管理方案時(shí)，頁(yè)表表項(xiàng)是由什么決定的？通常頁(yè)表設(shè)置那些表項(xiàng)？每一表項(xiàng)的作用是什么？

3.  文件系統(tǒng)的性能對(duì)整體系統(tǒng)的性能影響很大，請(qǐng)說(shuō)明在實(shí)現(xiàn)文件系統(tǒng)時(shí)可以從哪些方面提高文件系統(tǒng)的性能，簡(jiǎn)要給出這些手段的具體解決思路。

五（20分）綜合應(yīng)用題

1. 系統(tǒng)中有5個(gè)進(jìn)程，每個(gè)進(jìn)程的運(yùn)行時(shí)間（單位：ms）、優(yōu)先級(jí)和到達(dá)時(shí)刻如下表所示
進(jìn)    程：  P1   P2    P3   P4   P5
運(yùn)行時(shí)間：  10    1     2    1    5
優(yōu) 先 級(jí)：   4    6     2    3    6
到達(dá)時(shí)刻：  0     1      2     3    4
請(qǐng)給出當(dāng)系統(tǒng)跟別采用時(shí)間片輪轉(zhuǎn)算法（時(shí)間片為1ms）、不可搶占優(yōu)先級(jí)調(diào)度算法和搶占式優(yōu)先級(jí)調(diào)度算法時(shí)，各進(jìn)程的執(zhí)行情況。

2.        假設(shè)有如下訪盤請(qǐng)求，請(qǐng)計(jì)算出對(duì)于這些請(qǐng)求的服務(wù)次序，使得平均訪問(wèn)時(shí)間最短。設(shè)當(dāng)前磁頭的位置是6號(hào)柱面。，
 請(qǐng)求順序           柱面號(hào)         磁頭號(hào)        扇區(qū)號(hào)
①               3               2             1
②               5               1             5
③               3               2             5
④               3               4             1
⑤               9               2             1
⑥               9               1             5
⑦               5               2             5
⑧               5               4              8

六（10分） P，V 操作題
某系統(tǒng)如此定義P，V操作：
P （S）：
  S=S-1 ；
若S<0,本進(jìn)程進(jìn)入S信號(hào)量等待隊(duì)列的末尾；否則，繼續(xù)執(zhí)行。
V（S）
S=S+1；
若S≤0，釋放等待隊(duì)列中末尾的進(jìn)程，否則繼續(xù)運(yùn)行。
現(xiàn)有四個(gè)進(jìn)程 ， ， ， 競(jìng)爭(zhēng)使用某一個(gè)互斥資源（每個(gè)進(jìn)程可能反復(fù)使用多次），試用上面定義的P，V操作正確解決 ， ， ， 對(duì)該互斥資源的使用問(wèn)題。