數(shù)據(jù)結(jié)構(gòu)(c語言)課后習(xí)題參考資料_第1頁
數(shù)據(jù)結(jié)構(gòu)(c語言)課后習(xí)題參考資料_第2頁
數(shù)據(jù)結(jié)構(gòu)(c語言)課后習(xí)題參考資料_第3頁
數(shù)據(jù)結(jié)構(gòu)(c語言)課后習(xí)題參考資料_第4頁
數(shù)據(jù)結(jié)構(gòu)(c語言)課后習(xí)題參考資料_第5頁
已閱讀5頁,還剩5頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

數(shù)據(jù)構(gòu)造(c語言版)課后習(xí)題參照完滿版資料數(shù)據(jù)構(gòu)造(c語言版)課后習(xí)題參照完滿版資料10/10數(shù)據(jù)構(gòu)造(c語言版)課后習(xí)題參照完滿版資料第1章緒論5.:CCBDCA6.解析下面各程序段的復(fù)度。1)O(1)2)O(m*n)3)O(n2)4)O(log3n)(5)因x++共行了n-1+n-2+??+1=n(n-1)/2,所以行O(n2)(6)O(n)第2章線性表1.babadbcabdcddac2.算法6)一個算法,通一趟遍在表中確定最大的點。ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;

法(2)回文是指正反均相同的字符序列,如“abba”和“

abdba”均是回文,但“

good”不是回文。寫一個算法判判定的字符向量可否回文。(提示:將一半字符入

)?依照提示,算法可設(shè)計為:(1)已知模式串

適用t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符的模式串t的next和nextval以下:

next

nextval

函數(shù)。j

12

34

56

789

101112t串

ab

c

aab

b

ab

cabnext[j]

01

11

22

31

234

5nextval[j]

01

10

21

30

110

5(3)數(shù)A中,每個元素A[i,j]的度均32個二位,行下從-1到9,列下從1到開始存放主存器中,主存器字16位。求:①存放數(shù)所需多少元?②存放數(shù)第4列所有元素最少需多少元?③數(shù)按行存放,元素A[7,4]的初步地址是多少?④數(shù)按列存放,元素A[4,7]的初步地址是多少?每個元素32個二制位,主存字16位,故每個元素占2個字,行下可平移至(1)242(2)22(3)s+182(4)s+142(4)將香蕉banana用工具H( )—Head( ),T( )—Tail( )從L中取出。

11,從首地址1到11。

SL=(apple,(orange,(strawberry,(banana)),peach),pear)H(H(T(H(T(H(T(L)))))))(5)寫一個算法在入字符串中各個不相同字符出的度并將果存入文件(字符串中的合法字符A-Z26個字母和0-910個數(shù)字)。voidCount()入字符串中數(shù)字字符和字母字符的個數(shù)。{inti,num[36];charch;for(i=0;i<36;i++)num[i]=0;//初始化while((ch=getchar())!=‘#’)//‘#’表示入字符串束。if(‘0’<=ch<=‘9’){i=ch-48;num[i]++;}//數(shù)字字符elseif(‘A’<=ch<=‘Z’){i=ch-65+10;num[i]++;}//字母字符for(i=0;i<10;i++)//出數(shù)字字符的個數(shù)printf(“數(shù)字%d的個數(shù)=%d\n”,i,num[i]);for(i=10;i<36;i++)//求出字母字符的個數(shù)printf(“字母字符%c的個數(shù)=%d\n”,i+55,num[i]);}//算法束。第5章樹和二叉樹1.ADDCACCBDCCCACC2.用(2)一棵二叉的先序序列:ABDFCEGH,中序序列:BFDAGEHC①畫出棵二叉。②畫出棵二叉的后序索。③將棵二叉成的(或森林)。(1)(2)AC(3)假用于通信的文由8個字母成,字母在文中出的率分,,,,,,,。BMDEMH①8個字母赫夫曼。②另一種由二制表示的等方案。③于上述例,比兩種方案的缺點。FG解:方案1;哈夫曼先將概率放大100倍,以方便構(gòu)造哈夫曼。w={7,19,2,6,32,3,21,10},按哈夫曼:【[(2,3),6],(7,10)】,??19,21,32(100)(3)(40)(60)01192132(28)0101(17)19(11)32217106011201073方案比:1061023字母出字母出號率方案1的WPL=2+++4+++5+=++=率號11100方案2的WPL=3+++++++=31000200:哈夫曼于等二制20013.算法3111103010以二叉表作二叉的存構(gòu),寫以下算法:411104011(1)二叉的葉點個數(shù)。5105100intLeafNodeCount(BiTreeT)6{101if(T==NULL)return0;

//

若是是空樹,則葉子結(jié)點個數(shù)為

0elseif(T->lchild==NULL&&T->rchild==NULL)return1;

//

判斷該結(jié)點是否是葉子結(jié)點(左孩子右孩子都為空)

,若是則返回

1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);}(3)交換二叉樹每個結(jié)點的左孩子和右孩子。voidChangeLR(BiTree&T){BiTreetemp;if(T->lchild==NULL&&T->rchild==NULL)return;else{temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}ChangeLR(T->lchild);ChangeLR(T->rchild);}第6章圖1.選擇題CBBBCBABAADCCDDB2.應(yīng)用題1)已知以下列圖的有向圖,請給出:每個極點的入度和出度;毗鄰矩陣;毗鄰表;逆毗鄰表。2)已知以下列圖的無向網(wǎng),請給出:①毗鄰矩陣;②毗鄰表;③最小生成樹a→b4→c3圖無向網(wǎng)b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^(3)已知圖的毗鄰矩陣如所示。試分別畫出自極點樹。

1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成(4)有向網(wǎng)以下列圖,試用迪杰

斯特拉算法求出從頂點a到其他各極點間的最短路徑,完成表。D終i=1i=2i=3i=4i=5i=6點b151515151515(a,b)(a,b)(a,b)(a,b)(a,b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)e∞1010(a,c,e)(a,c,e)f∞6(a,c,f)g∞∞161614(a,c,f,g)(a,c,f,g)(a,c,f,d,g)S終{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}點集第7章查找1.選擇題CDCABCCCDCBCADA2.應(yīng)用題1)假定對有序表:(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找,試回答以下問題:畫出描述折半查找過程的判斷樹;若查找元素54,需依次與哪些元素比較?③若查找元素90,需依次與哪些元素比較?④假定每個元素的查找概率相等,求查找成功時的平均查找長度。①先畫出判斷樹以下(注:mid=(1+12)/2=6):30563374287424547295②查找元素54,需依次與30,63,42,54元素比較;③查找元素90,需依次與30,63,87,95元素比較;④求ASL從前,需要統(tǒng)計每個元素的查找次數(shù)。判斷樹的前3層共查找1+2×2+4×3=17次;但最后一層未滿,不能夠用8×4,只能用5×4=20次,所以ASL=1/12(17+20)=37/12≈(2)在一棵空的二叉排序樹中依次插入要點字序列為12,7,17,11,16,2,13,9,21,4,請畫出所獲取的二叉排序樹。1271721116214913驗算方法:用中序遍歷應(yīng)獲取排序結(jié)果:2,4,7,9,11,12,13,16,17,215)設(shè)哈希表的地址范圍為0~17,哈希函數(shù)為:H(key)=key%16。用線性探測法辦理矛盾,輸入要點字序列:(10,24,32,17,31,30,46,47,40,63,49),構(gòu)造哈希表,試回答以下問題:畫出哈希表的表示圖;若查找要點字63,需要依次與哪些要點字進(jìn)行比較?若查找要點字60,需要依次與哪些要點字比較?假定每個要點字的查找概率相等,求查找成功時的平均查找長度。①畫表以下:0

1

2

3

4

5

6

7

8

9

101112

1314

1516173217

6349

2440

10

30314647②查找

63,第一要與

H(63)=63%16=15號單元內(nèi)容比較,即

63vs31,no;爾后順移,與

46,47,32,17,63

對照,一共比較了

6次?、鄄檎?0,第一要與H(60)=60%16=12號單元內(nèi)容比較,但因為12號單元為空(應(yīng)當(dāng)有空標(biāo)記),所以應(yīng)當(dāng)只比較這一次即可。④對于黑色數(shù)據(jù)元素,各比較1次;共6次;對紅色元素則各不相同,要統(tǒng)計移位的位數(shù)?!?3”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次,所以ASL=1/11(6+2+3×3+6)=23/116)設(shè)有一組要點字(9,01,23,14,55,20,84,27),采用哈希函數(shù):H(key)=key%7,表長為10,用開放地址法的二次探測法辦理矛盾。要求:對該要點字序列構(gòu)造哈希表,并計算查找成功的平均查找長度。散列地址0123456789要點字140192384275520比較次數(shù)11123412平均查找長度:ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8以要點字27為例:H(27)=27%7=6(矛盾)H1=(6+1)%10=7(矛盾)22334次。H=(6+2)%10=0(矛盾)H=(6+3)%10=5所以比較了第8章排序1.選擇題CDBDCBCDBCBCCCA2.應(yīng)用題(1)設(shè)待排序的要點字序列為{12,2,16,30,28,10,16*,20,6,18},試分別寫出使用以下排序方法,每趟排序結(jié)束后要點字序列的狀態(tài)。①直接插入排序②折半插入排序③希爾排序(增量采用5,3,1)④冒泡排序⑤快速排序⑥簡單項選擇擇排序⑦堆排序⑧二路歸并排序①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序過程同①③希爾排序(增量采用5,3,1)102166181216*203028(增量采用5)621210181616*203028(增量采用3)2610121616*18202830(增量采用1)④冒泡排序21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]21012616[16*18202830]210612[1616*18202830]2610[121616*18202830]2610121616*18202830]⑤快速排序12[6210]12[283016*201618]6[2]6[10]12[283016*201618]28261012[181616*20]28[30]18261012[16*16]18[20]283016*26101216*[16]18202830左子序列遞歸深度為1,右子序列遞歸深度為3⑥簡單項選擇擇排序2[121630281016*20618]26[1630281016*201218]2610[30281616*201218]261012[281616*203018]26101216[2816*203018]2610121616*[28203018]2610121616*18[203028]2610121616*1820[2830]2610121616*182028[30]⑧二路歸并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830⑦堆排序第一步,形成初始大根堆(詳細(xì)過程略),第二步做堆排序。1230216281630281016*20181016*206182612初始排序不是大根堆形成初始大根堆12282816201620181016*12181016*26302630交換1與10對象從1到9重新形成堆6202016181612181016*1261016*2283022830交換1與9對象從1到8重新形成堆218181612161261016*2121016*202830202830交換1與8對象從1到7重新形成堆16*16*12161216261018261018202830202830交換1與7對象從1到6重新形成堆1016121612102616*182616*18202830202830交換1與6對象從1到5重新形成堆612121061021616*1821616*18202830202830交換1與5對象從1到4重新形成堆121061062121616*18121616*18202830202830交換1與4對象從1到3重新形成堆26610210121616*18121616*18202830202830交換1與3對象從1到2重新形成堆22610610121616*18121616*1820283020

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論