(完整word版)數(shù)據(jù)結(jié)構(gòu)應(yīng)用題總結(jié)

1、a + b*c-d-e/f中序遍歷：二廣 abcd-* + ef/-后序遍歷：戶(hù)后-+/a*efb-cd層次遍歷：將樹(shù)轉(zhuǎn)換成二叉樹(shù)加線(xiàn)：在兄弟之間加一連線(xiàn)抹線(xiàn)：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°GEAHCBDFJGAEABHBFCICDJD森林轉(zhuǎn)換成二叉樹(shù)1.將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù);2.將每棵轉(zhuǎn)換后的二叉樹(shù)依次連接成為右子二叉樹(shù)轉(zhuǎn)換成森林抹線(xiàn)：1.將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線(xiàn)，及沿右分支搜索到的所有右孩子間連線(xiàn)全部抹掉，使之變成孤立的無(wú)右孩子二叉樹(shù)；2.將孤立的二叉樹(shù)轉(zhuǎn)換成樹(shù)這是剛開(kāi)始的森林上面3個(gè)是樹(shù)轉(zhuǎn)化成的二叉

2、樹(shù)構(gòu)造Huffman樹(shù)w=5, 29, 7, 8, 14, 23, 3, 11)二二）。深度優(yōu)先遍歷深度遍歷：vin V2 =V4 = vs nV5 nV3 nV6 nV7V172 W4V8V5 V3a V6* V7廣度遍歷廣度遍歷：vi=> V2 =>V3 n V4 =>V5 nv6 nv7 nv8最小生成樹(shù)普里姆(Prim)算法:克魯斯卡爾(Kruskal)算法:拓?fù)渑判蛟谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止(2)(1)C5C5z拓?fù)湫蛄?，C1-C2 (3)拓?fù)湫蛄校珻l

3、-C2-< (5)1石撲序列：C1-C2-C3-C4(9)拓?fù)湫蛄?C1-C2-C3-C4-C10-C11(11)Z_C3拓?fù)湫蛄校篊1-C2-C3-C4(4)拓?fù)湫蛄?C1-C2-C3-C4-C5-C7 (6)30-C5c 領(lǐng)下拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C5-C7-C9C1°(8)卷領(lǐng)(10)-C5-C7-C9 拓?fù)湫蛄校珻1-C2-C3 -C4-C5-C7-.C -C10-C11-C6拓?fù)湫蛄校?Cl-C2-C3-C4-C5-C7-O-C10-C11-C&-C12C8(12)拓?fù)湫蛄校篊1C2.C3-C4-C5-C7-C9-C10-C11-

4、C6-C12C4拓?fù)湫蛄惺?Cl -C2-C3-C4-C5-C7-C9-CW-C11-C6-C12-CS 或 ；C9-C10-C11-C6-C1-C12 -C 4-C2- C3-C5- -C 7 -C &一個(gè)40 V網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏年P(guān)鍵路徑見(jiàn)筆記11哈希表的建立，處理沖突方法例 表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17, 60, 29的記錄, H(key尸key MOD 11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38, 按三訕處施沖突的方法，將它填入表中0123456789 10383860172938突突突沖快 沖沖沖不沖(1) H(38)=3SMOD 11=5 Hl=(5+1) MOD

5、11=6 H2=(5+2) MOD 11=7 國(guó)=(5+3) MOD 11=8()H(38>=38 MOD 11=5Hi=(5+12) MOD 11=6 沖突Hz=(5-12) MOD 11=4 不沖突(3) H(3S尸38 MOD 115 沖突 設(shè)偽隨機(jī)數(shù)序列為9,則： Hi=(5+9) MOD 11=3 不沖突開(kāi)放定址法:例已知一組關(guān)鍵字(19,14,23,1.68,20,84,27,55,11,10.79) 哈希函數(shù)為二 口出個(gè)尸kev MOD 13,哈希表長(zhǎng)為m-16, 設(shè)每個(gè)記錄的直找就率同等H(19 尸 6H( 14)=1皿23戶(hù)10H( )=1 沖突，H1-(1+1)MOD

6、16=2H(n 尸 11H(10)=10H(6S)=3H(20>=7H(84 尸 627)=1沖突，H1=(6+1)MOD15=7 沖突，H2=(6+2)MOD16=8 沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD16=4沖突，H1=(3+1)MOD16=4 沖突，H2=(3+2)MOD16=5沖突，Hl =(1 (R1)MOD 16-11 沖突，H2=(l(R2)MOD 112沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD164 沖突，H4=(1+4)MOD16=5沖突

7、，H5=(1+5)MOD16=6 沖突，H6=(1+6)MOD16=7 而突，H7=(1+7)MOD16=8 沖突，H8=(1+8)MOD16=9ASL=(1*6+2+3*3+44- )/12=2.5(1)用線(xiàn)性探測(cè)再散列處理沖突，即MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514168275519208479231110用鏈地址法處理沖突:關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)ASL=(1*6+2*4+3+4)/12=1.7512二叉排序樹(shù)的建立左邊都是小的，右邊都是大于等于的例（10, 18, 3, 8, 12, 2, 7, 313堆排序1）堆排序需解決的兩個(gè)問(wèn)題：如何由一個(gè)無(wú)序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？2）第二個(gè)問(wèn)題解決方法一一篩選方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱(chēng)這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”|徐出：13 |輸出二13©|輸出：13 27|輸出土 13 27 3苫輸出士 13 X 38 49 50 輸出：11 27 33 49 50 輸出: 13 27 38 49 50 653）第一個(gè)問(wèn)題解決方