數(shù)據(jù)結(jié)構(gòu)作業(yè)題

1、第一章1、設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。 (1) i=1; k=0; while(i<n) k=k+10*i;i+;  (2) i=0; k=0; dok=k+10*i; i+; while(i<n);  (3) i=1; j=0; while(i+j<=n) if (i>j) j+;else i+;(4)x=n; / n>1 while (x>=(y+1)*(y+1) y+;(5) x=91; y=100;  

2、;   while(y>0) if(x>100) x=x-10;y-;else x+;2、按增長率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 第二章2-7 針對帶表頭結(jié)點(diǎn)的單鏈表，試編寫下列函數(shù)。(1) 定位函數(shù)Locate：在單鏈表中尋找第i個結(jié)點(diǎn)。若找到，則函數(shù)返回第i個結(jié)點(diǎn)的地址；若找不到，則函數(shù)返回NULL。(2) 求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。第三章 3-1.將編號為0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組

3、的兩端。當(dāng)?shù)?號棧的棧頂指針top0等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長。當(dāng)向第0號棧插入一個新元素時，使top0增1得到新的棧頂位置，當(dāng)向第1號棧插入一個新元素時，使top1減1得到新的棧頂位置。當(dāng)top0+1 = top1時或top0 = top1-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類型定義，并實(shí)現(xiàn)初始化、判?？铡⑴袟M、插入、刪除算法。-1 top0 top1 m0 m-1【提示】類型定義：#define m 100；Typedef int dsType；/雙棧的元素類型T

4、ypedef structint top2; /雙棧的棧頂指針和棧底指針dsType Vm;/棧數(shù)組 DoubleStack；初始化空雙棧算法：InitdStack(DoubleStack &ds ) /初始化空雙棧dsds.top0=-1;ds.top1=m;判棧空算法：int DStackEmpty(DoubleStack ds , int i) /判斷雙棧ds的第i（0或1）個棧是否為空，空則返回1，否則返回0if (i=0 && ds.top0=-1) return 1;if (i=1 && ds.top1=m) return 1;return

5、0;3-2. 試?yán)盟惴麅?yōu)先法，畫出對如下中綴算術(shù)表達(dá)式求值時運(yùn)算符棧和操作數(shù)棧的變化。a + b * (c - d) e# （#表示結(jié)束符）步序掃描項(xiàng)項(xiàng)類型 動作OPND棧變化OPTR棧變化0F OPTR棧與OPND棧初始化, # 進(jìn)OPTR棧, 取第一個符號#1a操作數(shù)F a 進(jìn)OPND棧, 取下一符號a#2+操作符F + > #, 進(jìn)OPTR棧, 取下一符號a#+3-3 分別寫出順序循環(huán)隊(duì)列隊(duì)列Q狀態(tài)為“空”還是“滿”的條件和計算隊(duì)列中元素個數(shù)的公式。第四章 設(shè)有模式串T1,T2，T1=aaab，T2=abcabaa，目標(biāo)串s為abc aaabbabcabaacbacba，（1）計

6、算模式串T1的next(j) 和nextval(j)函數(shù)的值,并（按照nextval(j) ）畫出KMP算法匹配過程。（2）計算模式串T2的next(j) 和nextval(j)函數(shù)的值,并（按照nextval(j) ）畫出KMP算法匹配過程。學(xué)號尾數(shù)為奇數(shù)做第（1）題；偶數(shù)做第（2）題第五章 5-1 設(shè)有一個二維數(shù)組Amn（按照列優(yōu)先存儲，m、n均大于5），假設(shè)A00存放位置在644(10)，A23存放位置在676(10)，每個元素占一個空間，問A44(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。5-2假二維數(shù)組A9´3´5´8，第一個元素的字節(jié)地址是

7、1000，每個元素占6個字節(jié)。問下列元素的存儲地址是什么？（1）a0000 （2）a8247 （3）按行優(yōu)先存儲（最左下標(biāo)優(yōu)先）時a3125的地址 （4）按照列優(yōu)先存儲（最右下標(biāo)優(yōu)先）時a1111的地址5-3矩陣(aij)n´n的壓縮存儲方式,我們把它們按行存放于一個一維數(shù)組B中:（1）設(shè)有一個n´n的下三角矩陣A，如圖(a)所示。為了節(jié)約存儲，只存對角線或?qū)蔷€以下的元素。若在一維數(shù)組B中從0號位置開始存放，則下三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。（2）設(shè)有一個n´n的上三角矩陣A，如圖(b)所示。為了節(jié)約存儲，只存對角線及對

8、角線以上的元素，若在一維數(shù)組B中從0號位置開始存放，則上三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。a11 a21 a22 a31 a32 a33 an1 an2 an3 ann 圖(a)0a11 a12 a13 a1n a22 a23 a2n a33 a3n ann圖(b) 圖(b)0 5-4 利用廣義表和tail操作寫出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pea

9、r), (banana), (orange)5-5 畫出廣義表L的存儲結(jié)構(gòu)圖并求出它的深度： L=( ( ), a,(b,c),( ),d),(e) ) 第六章 6-1 在結(jié)點(diǎn)個數(shù)為n (n>1)的各棵樹中，深度最小的樹的深度是多少？它有多少個葉結(jié)點(diǎn)？多少個分支結(jié)點(diǎn)？深度最大的樹的高度是多少？它有多少個葉結(jié)點(diǎn)？多少個分支結(jié)點(diǎn)？ 6-2 如果一棵度為k的樹有n1個度為1的結(jié)點(diǎn), 有n2個度為2的結(jié)點(diǎn), , nk個度為k的結(jié)點(diǎn), 試問有多少個度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）? 試推導(dǎo)之。6-3 如果一棵含有n個結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。試問該樹葉子結(jié)點(diǎn)的數(shù)目。6-4 使用

10、(1) 順序表示和 (2) 二叉鏈表表示法，分別畫出下圖所示二叉樹的存儲表示。（3）分別求出該二叉樹的先序、中序、后序遍歷序列。6-5 試分別找出滿足以下條件的所有二叉樹:(1) 二叉樹的前序序列與中序序列相同;(2) 二叉樹的中序序列與后序序列相同;(3) 二叉樹的前序序列與后序序列相同。6-6 請畫出右圖所示的森林所對應(yīng)的二叉樹,并分別按以下說明進(jìn)行線索化。（1）先序全線索化 （2）中序全線索化 （3）后續(xù)后繼線索化121131411921054315768 6-7 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。【解答】當(dāng)

11、前序序列為ABECDFGHIJ，中序序列為EBCDAFHIGJ時，逐步形成二叉樹的過程如下圖所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD6-8畫出和下列已知序列對應(yīng)的樹T:樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根次序訪問序列為：DIAEKFCJHBG。6-9畫出和下列已知序列對應(yīng)的森林F: 森林的先序訪問序列為：ABCDEFGHIJKL；森林的中序訪問序列為：CBEFDGAJIKLH。6-10 假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, c7, c8組成, 各字母在電文中出現(xiàn)的頻率分別為0.07, 0

12、.19, 0.02, 0.06,0.32, 0.03, 0.21, 0.10。試為這8個字母設(shè)計不等長Huffman編碼, 并給出該電文的總碼數(shù)。使用 07的二進(jìn)制表示形式是另一種編碼方案。對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。101001019214002030710628051106173260 10C5C7C2100110C8C410C1C6C3帶權(quán)路徑長度WPL=(0.02+0.03)*5+(0.06+0.07+0.10)*4+(0.32+0.19+0.21)*2=2.61.帶權(quán)路徑長度最短，是最優(yōu)方案。若等長C1至C8編碼分別為000111，平均長度為3，大于2.61。 c1 c2 c

13、3 c4 c5 c6 c7 c8 0010 10 00000 0001 01 00001 11 0011 二、算法設(shè)計題：1、 編寫遞歸算法，將二叉樹（用二叉鏈表作為二叉樹的存儲表示）中所有結(jié)點(diǎn)的左、右子樹相互交換。2、 編寫遞歸算法，計算二叉樹（用二叉鏈表存儲表示）中葉子結(jié)點(diǎn)的數(shù)目。3、 編寫按層次遍歷二叉樹的算法。第7章 圖7-1在n個頂點(diǎn)的無向完全圖中，邊的條數(shù)為（n(n-1)/2 ）。畫出4個頂點(diǎn)的無向完全圖。1234567-2 下面判斷下面的有向圖是強(qiáng)連通圖嗎？若不是強(qiáng)連通圖，有幾個強(qiáng)連通分量？ABCDEFABCDEF G1 G2 G3G1不是強(qiáng)連通圖，有6個強(qiáng)連通分量（每個頂點(diǎn)分別

14、是1個強(qiáng)連通分量）G2是強(qiáng)連通圖 (只有1個強(qiáng)連通分量，就是G2本身)56G3不是強(qiáng)連通圖，有3個強(qiáng)連通分量.：12347-3 給出上圖G3的鄰接矩陣、鄰接表、逆鄰接表。DA(給出圖G1的鄰接矩陣、鄰接表、逆鄰接表、鄰接多重表（十字鏈表）大家自己畫G3)(1) 鄰接矩陣EBFC310 A1 B2 C3 D4 E5 F(2) 鄰接表4254140 A1 B2 C3 D4 E5 F（逆鄰接表）30105312data fin fout(3) 鄰接多重表（十字鏈表）i j ilink jlink0 1 (A, B)0 A1 B2 C3 D4 E5 F0 3 (A, D)1 2 (B, C)1 4 (

15、B, E)2 5 (C, F)3 1 (D, B)3 4 (D, E)5 4 (F, E)7-4 用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點(diǎn)個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？用鄰接矩陣表示圖，矩陣元素的個數(shù)是頂點(diǎn)個數(shù)的平方(即n個頂點(diǎn)，矩陣是n×n)，與邊的條數(shù)無關(guān)。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)（無向圖非零元素的個數(shù)是邊數(shù)的2倍；有向圖非零元素的個數(shù)等于邊數(shù)）。【解答】7-5 有n（n>1）個頂點(diǎn)的無向連通圖至少有多少條邊？有n個頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說明。n個頂點(diǎn)的無向連通圖至少有n-1條邊，n個頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊。例如：7-6對于有n個頂點(diǎn)

16、的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點(diǎn)i和j之間是否有邊相連？任意一個頂點(diǎn)的度是多少？用鄰接矩陣表示無向圖時，因?yàn)槭菍ΨQ矩陣，對矩陣的上三角部分或下三角部分檢測一遍，統(tǒng)計其中的非零元素個數(shù)，就是圖中的邊數(shù)。如果鄰接矩陣中Aij 不為零，說明頂點(diǎn)i與頂點(diǎn)j之間有邊相連。此外統(tǒng)計矩陣第i行或第i列的非零元素個數(shù)，就可得到頂點(diǎn)i的度數(shù)。7-7對于如右圖所示的有向圖，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷不唯一，得到的深度優(yōu)先生成樹； 例如: 1

17、2345 或13425等(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷，12345，所得到的廣度優(yōu)先生成樹7-8利用普里姆（prim和克魯斯卡爾(Kruskal)算法，求下圖的最小生成樹。165192114269611181416141651416141614prim算法56511 656111416克魯斯卡爾(Kruskal)56115655611147-9 試對右圖所示的AOE網(wǎng)絡(luò)，解答下列問題。(1) 這個工程最早可能在什么時間結(jié)束。(2) 求每個事件的最早開始時間Vei和最遲開始時間Vli。(3) 求每個活動的最早開始時間e(i)和最遲開始時間l(i)。(4) 確定哪些活動是關(guān)鍵活動。畫出由所有關(guān)

18、鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。按拓?fù)溆行虻捻樞蛴嬎愀鱾€頂點(diǎn)的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l - e = 0? 來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。 1 ¶ 2 ¸ 3 · 4 ¹ 5 º 6 » Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6&g

19、t;<5, 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0此工程最早完成時間為43。關(guān)鍵路徑為<1, 3><3, 2><2, 5><5, 6>7-10以右圖為例，按Dijkstra算法計算得到的從頂點(diǎn)(A)到其它各個頂點(diǎn)的最短路徑和最短路徑長度。2185522ABCDE2102源點(diǎn)終點(diǎn)最短路徑最短路徑長度 A B(A,B)(A,B)(A,B)(A,B)10101010 C(A,C)(A,C)(A,C)(A,C)18181818 D

20、90;(A,B,D)(A,B,D)(A,B,D)¥151515 E ¾¾(A,B,D,E)(A,B,D,E)¥¥1717第八章 查找表習(xí)題8-1 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進(jìn)行折半查找時的二叉判定樹, 并計算查找成功的平均查找長度和查找不成功的平均搜索長度。8-2 設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉

21、排序樹。8-3將關(guān)鍵碼DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始為空的AVL樹（平衡二叉樹）中，畫出每插入一個關(guān)鍵碼后的AVL樹，并標(biāo)明平衡旋轉(zhuǎn)的類型。8-4設(shè)散列表為HT13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。(2) 采用雙散列法尋找下一個空位,

22、再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度。第九章 作業(yè)1、設(shè)待排序的排序碼序列為12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。(1) 直接插入排序(2) 希爾排序(增量為5,2,1)(3) 起泡排序(4) 快速排序(5) 直接選擇排序(6) 基數(shù)排序(7) 堆排序(8) 二路歸并排序【解答】(1) 直

23、接插入排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 1 12 21630281016*20 618 1 i = 2 212 1630281016*20 618 1 i = 3 212 16 30281016*20 618 1 i = 4 212 16 30 281016*20 618 2 i = 5 212 16 2830 1016*20 618 5 i = 6 21012162830 16*20 618 3 i = 7 210121616*2830 20 618 3 i = 8 210121616*202830 618 3 i = 9 2 610121616

24、*202830 18 8 2 610121616*18202830 (2) 希爾排序(增量為5,2,1)初始排列 0 1 2 3 4 5 6 7 8 9排序碼比較次數(shù) 12 21630281016*20 618 1+1+1+1+1 = 5 d = 5 10 216 6181216*203028 (1+1+2+1) + (1+1 d = 2+1+1) = 9 10 216 616*1218203028 1+1+3+1+3+1+1 d = 1+1+2 = 14 2 6 10 121616*18202830 希爾(shell)本人采取的增量序列為 ën/2û, ë

25、35;n/2û/2û, ëën/2û/2û/2û, ,1。一般地，增量序列可采用ënû, ëënûû, ëënûûû, , 1。大量實(shí)驗(yàn)表明，取=0.45454的增量序列比取其他的增量序列的優(yōu)越性更顯著。計算 ë0.45454nû 的一個簡單方法是用整數(shù)算術(shù)計算(5*n-1)/11。需要注意，當(dāng)a< 1/2時，增量序列可能不以1結(jié)束，需要加以判斷和調(diào)整。(3) 起泡排序初始排列 0 1 2

26、3 4 5 6 7 8 9 排序碼比較次數(shù) i = 0 12 21630281016*20 618 9 i = 1 2 12 61630281016*2018 8 i = 2 2 6 121016302816*1820 7 i = 3 2 6 10 121616*30281820 6 i = 4 2 6 10 12 1616*18302820 5 i = 5 2 6 10 1216 16*18203028 4 i = 6 2 6 10 121616* 18202830 3 2 6 10 121616*18202830 (4) 快速排序PivotPvtpos 0 1 2 3 4 5 6 7 8

27、9 排序碼比較次數(shù)pospospospos 120,1,2,3 12 2 1630281016*20 618 9pospos 60,1 6 2 10 12 281616*203018 2pospospospospos 284,5,6,7,8 2 6 10 12 281616*203018 5pospospos 18 4,5,6 2 6 10 12 181616*20 28 30 3pos 16*4 2 6 10 12 16*16 18 20 2830 1 2 6 10 1216* 16 18202830 左子序列遞歸深度為1，右子序列遞歸深度為3。(5) 直接選擇排序初始排列 0 1 2 3

28、4 5 6 7 8 9 排序碼比較次數(shù) i = 0 12 2 16 30 28 10 16* 20 618 9 i = 1 2 12 16 30 28 10 16* 20 618 8 i = 2 2 6 16 30 28 10 16* 20 1218 7 i = 3 2 6 10 30 28 16 16* 20 1218 6 i = 4 2 6 10 12 28 16 16* 20 3018 5 i = 5 2 6 10 12 16 28 16* 20 3018 4 i = 6 2 6 10 12 16 16* 28 20 3018 3 i = 7 2 6 10 12 16 16* 18 20

29、 3028 2 i = 8 2 6 10 12 16 16* 16 20 3028 1 2 6 10 12 16 16* 16 20 28 30 (6)基數(shù)排序 621630102816*201812按最低位分配r0 r1 r2 r3 r4 r5 r6 r7 r8 r962021816*1028163012f0 f1 f2 f3 f4 f5 f6 f7 f8 f92862101816*16122030收集按最高位分配18r0 r1 r2 r3 r4 r5 r6 r7 r8 r916*16286f0 f1 f2 f3 f4 f5 f6 f7 f8 f9123020210302820181610126216*收