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

1、第一章1、設(shè)n為正整數(shù)，利用大"O"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為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、按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 第二章2-7 針對(duì)帶表頭結(jié)點(diǎn)的單鏈表，試編寫(xiě)下列函數(shù)。(1) 定位函數(shù)Locate：在單鏈表中尋找第i個(gè)結(jié)點(diǎn)。若找到，則函數(shù)返回第i個(gè)結(jié)點(diǎn)的地址；若找不到，則函數(shù)返回NULL。(2) 求最大值函數(shù)max：通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。第三章 3-1.將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間Vm中，棧底分別處于數(shù)組

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

4、ypedef structint top2; /雙棧的棧頂指針和棧底指針dsType Vm;/棧數(shù)組 DoubleStack；初始化空雙棧算法：InitdStack(DoubleStack &ds ) /初始化空雙棧dsds.top0=-1;ds.top1=m;判?？账惴ǎ篿nt DStackEmpty(DoubleStack ds , int i) /判斷雙棧ds的第i（0或1）個(gè)棧是否為空，空則返回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)先法，畫(huà)出對(duì)如下中綴算術(shù)表達(dá)式求值時(shí)運(yùn)算符棧和操作數(shù)棧的變化。a + b * (c - d) e# （#表示結(jié)束符）步序掃描項(xiàng)項(xiàng)類(lèi)型 動(dòng)作OPND棧變化OPTR棧變化0F OPTR棧與OPND棧初始化, # 進(jìn)OPTR棧, 取第一個(gè)符號(hào)#1a操作數(shù)F a 進(jìn)OPND棧, 取下一符號(hào)a#2+操作符F + > #, 進(jìn)OPTR棧, 取下一符號(hào)a#+3-3 分別寫(xiě)出順序循環(huán)隊(duì)列隊(duì)列Q狀態(tài)為“空”還是“滿”的條件和計(jì)算隊(duì)列中元素個(gè)數(shù)的公式。第四章 設(shè)有模式串T1,T2，T1=aaab，T2=abcabaa，目標(biāo)串s為abc aaabbabcabaacbacba，（1）計(jì)

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

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

8、角線以上的元素，若在一維數(shù)組B中從0號(hào)位置開(kāi)始存放，則上三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。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操作寫(xiě)出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來(lái)：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pea

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

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

11、前序序列為ABECDFGHIJ，中序序列為EBCDAFHIGJ時(shí)，逐步形成二叉樹(shù)的過(guò)程如下圖所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD6-8畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T:樹(shù)的先根次序訪問(wèn)序列為：GFKDAIEBCHJ；樹(shù)的后根次序訪問(wèn)序列為：DIAEKFCJHBG。6-9畫(huà)出和下列已知序列對(duì)應(yīng)的森林F: 森林的先序訪問(wèn)序列為：ABCDEFGHIJKL；森林的中序訪問(wèn)序列為：CBEFDGAJIKLH。6-10 假定用于通信的電文僅由8個(gè)字母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個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼, 并給出該電文的總碼數(shù)。使用 07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。101001019214002030710628051106173260 10C5C7C2100110C8C410C1C6C3帶權(quán)路徑長(zhǎng)度WPL=(0.02+0.03)*5+(0.06+0.07+0.10)*4+(0.32+0.19+0.21)*2=2.61.帶權(quán)路徑長(zhǎng)度最短，是最優(yōu)方案。若等長(zhǎng)C1至C8編碼分別為000111，平均長(zhǎng)度為3，大于2.61。 c1 c2 c

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

14、是1個(gè)強(qiáng)連通分量）G2是強(qiáng)連通圖 (只有1個(gè)強(qiáng)連通分量，就是G2本身)56G3不是強(qiáng)連通圖，有3個(gè)強(qiáng)連通分量.：12347-3 給出上圖G3的鄰接矩陣、鄰接表、逆鄰接表。DA(給出圖G1的鄰接矩陣、鄰接表、逆鄰接表、鄰接多重表（十字鏈表）大家自己畫(huà)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í)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的平方(即n個(gè)頂點(diǎn)，矩陣是n×n)，與邊的條數(shù)無(wú)關(guān)。矩陣中非零元素的個(gè)數(shù)與邊的條數(shù)有關(guān)（無(wú)向圖非零元素的個(gè)數(shù)是邊數(shù)的2倍；有向圖非零元素的個(gè)數(shù)等于邊數(shù)）?！窘獯稹?-5 有n（n>1）個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說(shuō)明。n個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊，n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊。例如：7-6對(duì)于有n個(gè)頂點(diǎn)

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

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

18、鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間l，根據(jù)l - e = 0? 來(lái)確定關(guān)鍵活動(dòng)，從而確定關(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此工程最早完成時(shí)間為43。關(guān)鍵路徑為<1, 3><3, 2><2, 5><5, 6>7-10以右圖為例，按Dijkstra算法計(jì)算得到的從頂點(diǎn)(A)到其它各個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。2185522ABCDE2102源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度 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。試畫(huà)出對(duì)其進(jìn)行折半查找時(shí)的二叉判定樹(shù), 并計(jì)算查找成功的平均查找長(zhǎng)度和查找不成功的平均搜索長(zhǎng)度。8-2 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉

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

22、再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度。第九章 作業(yè)1、設(shè)待排序的排序碼序列為12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 試分別寫(xiě)出使用以下排序方法每趟排序后的結(jié)果。并說(shuō)明做了多少次排序碼比較。(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)越性更顯著。計(jì)算 ë0.45454nû 的一個(gè)簡(jiǎn)單方法是用整數(shù)算術(shù)計(jì)算(5*n-1)/11。需要注意，當(dāng)a< 1/2時(shí)，增量序列可能不以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*收