2001年數據結構與程序設計

2001年數據結構與程序設計
試題內容:
一、試給出下列有關并查集(mfsets)的操作序列的運算結果：
union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。（union是合并運算，在以前的書中命名為merge）
要求
(1) 對于union(i,j)，以i作為j的雙親； （5分）
(2) 按i和j為根的樹的高度實現union(i,j)，高度大者為高度小者的雙親； （5分）
(3) 按i和j為根的樹的結點個數實現union(i,j)，結點個數大者為結點個數小者的雙親； （5分）
二、設在4地（A,B,C,D）之間架設有6座橋,如圖所示:

要求從某一地出發,經過每座橋恰巧一次,比較后仍回到原地
(1) 試就以上圖形說明:此問題有解的條件是什么? (5分)
(2) 設圖中的頂點數為n,試用C或Pascal描述與求解此問題有關的數據結構并編寫一個算法,找出滿足要求的一條回路. (10分)
三、針對以下情況確定非遞歸的歸并排序的運行時間(數據比較次數與移動次數):
(1) 輸入的n個數據全部有序; (5分)
(2) 輸入的n個數據全部逆向有序; (5分)
(3) 隨機地輸入n個數據. (5分)
四、簡單回答有關AVL樹的問題.
(1) 在有N個結點的AVL樹中,為結點增加一個存放結點高度的數據成員,那么每一個結點需要增加多少個字位(bit)? (5分)
(2) 若每一個結點中的高度計數器有8bit,那么這樣的AVL樹可以有多少層?比較少有多少個關鍵碼? (5分)
五、設一個散列表包含hashSize=13個表項,.其下標從0到12,采用線性探查法解決沖突. 請按以下要求,將下列關鍵碼散列到表中.
10 100 32 45 58 126 3 29 200 400 0
(1) 散列函數采用除留余數法,用%hashSize(取余運算)將各關鍵碼映像到表中. 請指出每一個產生沖突的關鍵碼可能產生多少次沖突. (7分)
(2) 散列函數采用先將關鍵碼各位數字折疊相加, 再用%hashSize將相加的結果映像到表中的辦法. 請指出每一個產生沖突的關鍵碼可能產生多少次沖突. (8分)
六、設一棵二叉樹的結點定義為
struct BinTreeNode{
ElemType data;
BinTreeNode *leftChild, *rightChild;
}
現采用輸入廣義表表示建立二叉樹. 具體規定如下:
(1) 樹的根結點作為由子樹構成的表的表名放在表的比較前面;
(2) 每個結點的左子樹和右子樹用逗號隔開. 若僅有右子樹沒有左子樹, 逗號不能省略.
(3) 在整個廣義表表示輸入的結尾加上一個特殊的符號(例如”#”)表示輸入結果.
例如,對于如右圖所示的二叉樹, 其廣義表表示為A(B(D,E(G,)),C(,F))
A
/
B C
/
D E F
/
G
此算法的基本思路是:依次從保存廣義表的字符串ls中輸入每個字符. 若遇到的是字母(假定以字母作為結點的值), 則表示是結點的值, 應為它建立一個新的結點, 并把該結點作為左子女(當k=1)或有子女(當k=2)鏈接到其雙親結點上. 若遇到的是左括號”(“, 則表明子表的開始,將k置為1;若遇到的是右括號”)”, 則表明子表結果. 若遇到的是逗號”,”, 則表示以左子女為根的子樹處理完畢,應接著處理以右子女為根的子樹, 將k置為2.
在算法中使用了一個棧s, 在進入子表之前,將根結點指針進棧, 以便括號內的子女鏈接之用. 在子表處理結束時退棧. 相關的棧操作如下:
MakeEmpty(s) 置空棧
Push(s,p) 元素p進棧
Pop(s) 進棧
Top(s) 存取棧頂元素的函數
下面給出了建立二叉樹的算法, 其中有5個語句缺失. 請閱讀此算法并把缺失的語句補上. (每空3分)
Void CreateBinTree(BinTreeNode *&BT, char ls){
Stacks; MakeEmpty(s);
BT=NULL; //置二叉樹
BinTreeNode *p;
int k;
istream ins(ls); //把串ls定義為輸入字符串流對象ins
Char ch;
ins>>ch; //從ins順序讀入一個字符
While(ch!=”#”){ //逐個字符處理,直到遇到'#'為止
Switch(ch){
case’(‘: _______(1)_______
k=1;
break;
case’)’: pop(s);
break;
case’,‘: _______(2)_______
break;
default: p=new BinTreeNode;
_______(3)_______
p->leftChild=NULL;
p->rightChild=NULL;
if(BT==NULL)
_______(4)_______
else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
}
_______(5)_______
}
}

七、下面是一個用C編寫的快速排序算法. 為了避免比較壞情況,取基準記錄pivot采用從left,right和mid=[(left+right)/2>中取中間值, 并交換到right位置的辦法. 數組a存放待排序的一組記錄, 數據類型為Type, left和right是呆排序子區間的比較左端點和比較右端點.
Void quicksort(Type a&#;,int left,int right){
Type temp;
If(leftType pivot=median3(a,left,right);
Int I=left, j=right-1;
For( ; ; ){
While(iWhile(i) j--;
if(itemp=a; a[j>=a; a=temp;
I++; j--;
}
else break;
}
if(a>pivot)
{temp=a: a=a[right>; a[right>=temp;}
quicksort(a,left,i-1); //遞歸排序左子區間
quicksort(a,i+1,right); //遞歸排序右子區間
}
}
(1) 用C或Pascal實現三者取中子程序 median3(a,left,right); (5分)
(2) 改寫 quicksort 算法, 不用棧消去第二個遞歸調用 quicksort(a,i+1,right); (5分)
(3) 繼續改寫 quicksort 算法, 用棧消去剩下的遞歸調用. (5分)



編譯原理及操作系統

試題內容:

編譯原理部分
1.(5%) 給出下述NFA M的五元組表示, 并將其確定化









2 (5%) 構造一個不具有ε-轉移的NFA M’ , 使得L(M’)=L(M)








3 (10%) 證明文法G[A>是LR(1)文法.
G[A>: A->BA|ε
B->aB|b
4 (5%) 證明合并不存在沖突(移進/歸約、歸約/歸約)的LR(1)項目集的同心集不會產生新的移進/歸約沖突.


5.(5%) 對目標代碼運行時的存儲空間采用基于過程活動記錄的棧式分配方案, 舉例說明象PASCAL這樣的語言如何實現對非局部變量的訪問.


6(15%) 文法G[R>: R->R+R | R·R | R*| (R) | a | b | ε
(1) 證明文法 G[R> 生成字母表 Σ={a, b} 上的所有正規表達式(用+代替”|”, 連接符·沒有省略)
(2) 證明此文法是二義的
(3) 根據正規式的三個運算符(+,·, *) (或, 連接, 閉包) 的優先性和結合性約定重新構造一個等價的LL(1) 文法


7(5%) 找出下列流圖中的回邊和回邊組成的循環.編譯中利用流圖完成什么工作?

























操作系統部分

一、 名次解釋（10分）
多道程序、多重處理、進程、線程、虛存
二、 畫出NT操作系統的線程狀態轉移圖（10分）
三、 UNIX系統與Linux系統等中都提供pipe文件功能，簡述pipe() 的工作原理。（10分）
四、 設周期性任務P1，P2，P3的周期T1，T2，T3分別為100，150，350；執行時間分別為20，40，100。試計算后回答是否可以用頻率單調調度算法進行調度？（10分）
五、 I/O控制可用那幾種方式實現？各有何優缺點？（10分）