南郵數(shù)據(jù)結構B期末試卷

數(shù)*MB期末試卷班級學號得分一、解答題：（共82一、解答題：（共82分）1、下列程序段或函數(shù)的時間復雜度。（1）for（intk=0;k<m;k++）for（intj=0;j<n;j++）

a[k][j]=k*j;(10%)(2)intfac(unsignedintn){if(n==0||n==1)return1;elsereturnn*fac(n-1);}題號四五六分數(shù)((4)k=1;x=0;do{x++;k*=2;}while(k<n);(3)intPrime(intn){intk=2,x=(int)sqrt(n);while(k<=x){if(n%k==0)break;k++; }if(k>x)return1;elsereturn0;}2、有A、B、C、D四個元素依次入棧，即入棧序列唯一，問共能得到多少種出棧序列？能否得到以下四種出棧序列：ABCD、BDAC、CBDA、口84^對能得到的序列，請寫出Push、Pop序列；對不能得到的序列，請說明理由。（6%）

3、矩陣人日以行優(yōu)先方式從1000H處開始存放，元素類型未知，已知*[2][3]存放在1011H處，人[1][1]存放在1005H處，求元素人[2][0]的存放位置。（6%）4、根據(jù)下圖所示的樹回答問題：（共13%）（1）畫出該樹等效的二叉樹。（3%）BG等效的二叉樹BG等效的二叉樹（2）、寫出對該樹進行先序、后序遍歷的結點序列。（4%）（3）用帶右鏈的先序表示法來存儲此樹，填寫下表。（6%）下標0 1 2 3 4 5 6 7 8 9 10 11

siblingelementItag5、假設用于通訊的電文僅由{ABCDEFGH}8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。請畫出哈夫曼樹并在樹中標明編碼情況，給出這8個字母的哈夫曼編碼，最后求出WPL。（9%）6、對下圖，要求：（共13%）（1）畫出它的鄰接表。（3%）（2）寫出從頂點1到頂點8的四條路徑長度為3的簡單路徑。（2%）（3）分別寫出從頂點1出發(fā)根據(jù)（1）所示的鄰接表用深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖得到的頂點序列。（4%）（4）求出它的一棵最小代價生成樹（方法任選），其代價是多少？你所求出的最小代價生成樹是唯一的嗎？（4%）7、一項工程P由PI,P2,P3,P4,P5,P6六個子工程組成，這些工程之間有下列關系：P1>P2,P1>P3,P1>P4,P2>P3,P2>P5,P3>P6,P4>P6,P5>P6。其中符號“〉”表示先于關系,例如P1>P2表示只有在工程P1完成之后才能進行P2的工作。請：（7%）(1)畫出該工程的AOV網(wǎng)(2)給出工程P的其中四種可能的施工順序。8、按如下關鍵字序列(60,88,107,15,8,23,100)從空樹開始建立一棵AVL搜索樹，畫出建樹的步驟以及調整平衡的過程(6%)9、設散列表川[13],散列函數(shù)八66丫)=卜6丫%13。采用二次探查法解決沖突，試用關鍵字值序列：{56，78，14，27，41，70，51，66，24，50，36}建立散列表。(6%)0 10 1 2 3 4 5 6 7 8 9 10 11 12ht[i]10、元素序列：{55，71，12，98，4，70，51}，請寫出用冒泡排序法和2路合并排序法進行排序的各趟排序結果。(6%)冒泡排序法2路合并排序法 ：二、算法填空：(8%)以下算法實現(xiàn)二叉搜索樹的刪除，根據(jù)給定的關鍵字燈找到待刪除元素后將元素值通過參數(shù)6返回，若成功刪除則返回皿6；找不到待刪除元素則返回￡@屈.template<classE,classK> BSTree<E,K>::Delete(constK&k,E&e){BTNode<E>*p=root,*q=0;while(p&&p->element!=k){q=p;if(k<p->element)p=p->lchild;else ;}if(!p){cerr<<”Noelementwithkeyk\n”; ;}e=p->element;while(p->lchild&&p->rchild){BTNode<E>*s=p->rchild,*r=p;while(s->lchild){ ;s=s->lchild;} ;p=s;q=r;}BTNode<E>*c;if(p->lchild)c=p->lchild;else ;if( )root=c;elseif(p==q->lchild)q->lchild=c;elseq->rchild=c; ;returntrue;}三、算法設計(10%)編程實現(xiàn)將兩個按元素遞增排序的單向循環(huán)鏈表合并成一個單向循環(huán)鏈表，合并后元素仍遞增有序，注意：不允許再增加新的結點，相同元素只保留一份。該算法為SingleList類的成員函數(shù)乂6僧6,該函數(shù)的作用是將形參「代表的單向循環(huán)鏈表合并到當前單向循環(huán)鏈表中，合并后的結果存于當前單循環(huán)鏈表。template<classT>classSingleList;template<classT>classNode{private:

Tdata;Node<T>*link;friendclassSingleList<T>;};template<classT>classSingleList:publicLinearList<T>{public:voidMerge(constSingleList<T>&r);private:Node<T>*first;};例：合并前:this