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

PAGEPAGE4數(shù)據(jù)結(jié)構(gòu)B 期末試卷班級 學(xué)號 姓名 得分題號一二三題號一二三四五六分?jǐn)?shù)1、下列程序段或函數(shù)的時間復(fù)雜度。（10％）（1）for(intk=0；k<m；k++）（2）intfac(unsignedintn）for(intj=0；j〈n;j++)｛if（n==0||n==1）return1;a［k]［j］=k*j；elsereturnn＊fac(n-1）;}（3）intPrime（intn)（4）k=1; x=0;{intk=2，x=(int)sqrt(n）;do｛while(k<=x）｛if(n%k==0) break;x++；k*=2；}k++; }while(k〈n）；if（k〉x)returnelsereturn0｝2、有A、B、C、D四個元素依次入棧，即入棧序列唯一，問共能得到多少種出棧序列？能否得到以下四種出棧序列：ABCD、BDAC、CBDA、DBAC。對能得到的序列，請寫出Push、Pop序列；對不能得到的序列，請說明理由。（6％）3、矩陣Am*n以行優(yōu)先方式從1000H處開始存放，元素類型未知，已知：A[2］[3]存放在1011H處，A［1][1]存放在1005H處，求元素A［2］[0］的存放位置.(6%）4、根據(jù)下圖所示的樹回答問題：（共13%)（1)畫出該樹等效的二叉樹。（3％）ABABCDEFGHIJKL（2)、寫出對該樹進(jìn)行先序、后序遍歷的結(jié)點序列。（4%）(3）用帶右鏈的先序表示法來存儲此樹，填寫下表.(6％）下標(biāo) 0 1 2 3 4 5 6 7 8siblingelementltag

9 10 115、假設(shè)用于通訊的電文僅由{ABCDEFGH｝8個字母組成，字母在電文中出現(xiàn)的頻率分別為0。070。19,0。02，0.06,0.32,0.03,0.21,0。10編碼情況，給出這8個字母的哈夫曼編碼,最后求出WPL（9%）6、對下圖，要求：（共13%）1163374255883445756556（1)畫出它的鄰接表。（3%)（2)寫出從頂點1到頂點8的四條路徑長度為3的簡單路徑。（2%）(3）1出發(fā)根據(jù)（1）圖得到的頂點序列.（4%）（4）求出它的一棵最小代價生成樹(方法任選)，其代價是多少?你所求出的最小代價生成樹是唯一的嗎?（4%)7、一項工程P由P1，P2，P3，P4，P5，P6六個子工程組成，這些工程之間有下列關(guān)系：P1>P2，P1>P3, P1P4,P2P3,P2>P5，P3>P6,P4>P6，P5>P6。其中符號“〉”表先于關(guān)系，例如P1>P2表示只有在工程P1完成之后才能進(jìn)行P2的工作。請:（7%)AOV網(wǎng)P的其中四種可能的施工順序.8、按如下關(guān)鍵字序列（60，88，107，15，8,23,100）AVL搜索樹,出建樹的步驟以及調(diào)整平衡的過程（6%）9、設(shè)散列表ht[13]，散列函數(shù)h（key)=key％13值序列：{56，78,14，27，41，70，51,66,24，50,36｝建立散列表。（6%)i 0 1 2 3 4 5 6 7 8 9 10 11 12ht[i]10:｛55，71，12，98，4，70，51｝2進(jìn)行排序的各趟排序結(jié)果。（6%）冒泡排序法 2路合并排序法二、算法填空:(8%)以下算法實現(xiàn)二叉搜索樹的刪除,根據(jù)給定的關(guān)鍵字k,找到待刪除元素后將元素值通過參數(shù)e返回，若成功刪除則返回true；找不到待刪除元素則返回false。template 〈classE,classK〉BSTree〈E，K>：:Delete（const K&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è)計(10%)SingleListMerge,r表中,合并后的結(jié)果存于當(dāng)前單循環(huán)鏈表。template〈classTclassSingleList;template<class〉classNode｛private:Tdata;Node<T〉＊link；friendclassSingleList〈T〉;｝；template〈classT>classSingleList：publicLinearList〈T〉{public：voidMerge（const SingleList〈T〉＆r);…………。private：Node〈T〉＊first；……。｝;例：合并前：this—