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

1．   對于非空滿K叉樹，其分支結(jié)點數(shù)目為n，則其葉結(jié)點數(shù)目為________________。

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

3．   有n個頂點的有向連通圖最少有_________條邊。

4．   某二叉樹中序序列為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”,空格小于任何其它字符）。采用“右補空格”，使得這些關(guān)鍵碼都成為4位字符的等長關(guān)鍵碼。按最低位優(yōu)先法進行基數(shù)排序，進行兩趟分配和收集后得到的序列為_________________。

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

二（30分） 辨析題

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

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

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

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

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

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

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

三（15分）算法填空
下面是一個拓撲排序算法，對于帶回路的圖，該算法將調(diào)用 “此圖有環(huán)！”，并逐步退出到調(diào)用它的主調(diào)函數(shù)。請?zhí)畛渌惴ㄖ锌杖钡牟糠�，使其成為完整的算法�?br />//深度優(yōu)先搜索方式實現(xiàn)拓撲排序
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分） 問答題

1. 實現(xiàn)進程通信的方式有幾種？請分別簡要描述這些通信方式。

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

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

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

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

2.        假設(shè)有如下訪盤請求，請計算出對于這些請求的服務(wù)次序，使得平均訪問時間最短。設(shè)當前磁頭的位置是6號柱面。，
 請求順序           柱面號         磁頭號        扇區(qū)號
①               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,本進程進入S信號量等待隊列的末尾；否則，繼續(xù)執(zhí)行。
V（S）
S=S+1；
若S≤0，釋放等待隊列中末尾的進程，否則繼續(xù)運行。
現(xiàn)有四個進程 ， ， ， 競爭使用某一個互斥資源（每個進程可能反復(fù)使用多次），試用上面定義的P，V操作正確解決 ， ， ， 對該互斥資源的使用問題。