南郵數(shù)據(jù)結(jié)構(gòu)B期末試卷

數(shù)*MB期末試卷班級(jí)學(xué)號(hào)得分一、解答題：（共82一、解答題：（共82分）1、下列程序段或函數(shù)的時(shí)間復(fù)雜度。（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);}題號(hào)四五六分?jǐn)?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四個(gè)元素依次入棧，即入棧序列唯一，問(wèn)共能得到多少種出棧序列？能否得到以下四種出棧序列：ABCD、BDAC、CBDA、口84^對(duì)能得到的序列，請(qǐng)寫(xiě)出Push、Pop序列；對(duì)不能得到的序列，請(qǐng)說(shuō)明理由。（6%）

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

siblingelementItag5、假設(shè)用于通訊的電文僅由{ABCDEFGH}8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。請(qǐng)畫(huà)出哈夫曼樹(shù)并在樹(shù)中標(biāo)明編碼情況，給出這8個(gè)字母的哈夫曼編碼，最后求出WPL。（9%）6、對(duì)下圖，要求：（共13%）（1）畫(huà)出它的鄰接表。（3%）（2）寫(xiě)出從頂點(diǎn)1到頂點(diǎn)8的四條路徑長(zhǎng)度為3的簡(jiǎn)單路徑。（2%）（3）分別寫(xiě)出從頂點(diǎn)1出發(fā)根據(jù)（1）所示的鄰接表用深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖得到的頂點(diǎn)序列。（4%）（4）求出它的一棵最小代價(jià)生成樹(shù)（方法任選），其代價(jià)是多少？你所求出的最小代價(jià)生成樹(shù)是唯一的嗎？（4%）7、一項(xiàng)工程P由PI,P2,P3,P4,P5,P6六個(gè)子工程組成，這些工程之間有下列關(guān)系：P1>P2,P1>P3,P1>P4,P2>P3,P2>P5,P3>P6,P4>P6,P5>P6。其中符號(hào)“〉”表示先于關(guān)系,例如P1>P2表示只有在工程P1完成之后才能進(jìn)行P2的工作。請(qǐng)：（7%）(1)畫(huà)出該工程的AOV網(wǎng)(2)給出工程P的其中四種可能的施工順序。8、按如下關(guān)鍵字序列(60,88,107,15,8,23,100)從空樹(shù)開(kāi)始建立一棵AVL搜索樹(shù)，畫(huà)出建樹(shù)的步驟以及調(diào)整平衡的過(guò)程(6%)9、設(shè)散列表川[13],散列函數(shù)八66丫)=卜6丫%13。采用二次探查法解決沖突，試用關(guān)鍵字值序列：{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}，請(qǐng)寫(xiě)出用冒泡排序法和2路合并排序法進(jìn)行排序的各趟排序結(jié)果。(6%)冒泡排序法2路合并排序法 ：二、算法填空：(8%)以下算法實(shí)現(xiàn)二叉搜索樹(shù)的刪除，根據(jù)給定的關(guān)鍵字燈找到待刪除元素后將元素值通過(guò)參數(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;}三、算法設(shè)計(jì)(10%)編程實(shí)現(xiàn)將兩個(gè)按元素遞增排序的單向循環(huán)鏈表合并成一個(gè)單向循環(huán)鏈表，合并后元素仍遞增有序，注意：不允許再增加新的結(jié)點(diǎn)，相同元素只保留一份。該算法為SingleList類的成員函數(shù)乂6僧6,該函數(shù)的作用是將形參「代表的單向循環(huán)鏈表合并到當(dāng)前單向循環(huán)鏈表中，合并后的結(jié)果存于當(dāng)前單循環(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