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

1、第9章 檢索的作業(yè)9.6 假定值A(chǔ)到H存儲在一個自組織線性表中，開始按照升序存放。對于9.2小節(jié)建議的三種自組織啟發(fā)式規(guī)則，按照下面順序訪問線性表，給出結(jié)果線性表和需要的比較總數(shù)。 D H H G H E G H G H E C E H G(1) 頻率計數(shù)自組織線性表啟發(fā)式規(guī)則： A B C D E F G H 比較次數(shù)D: D A B C E F G H 4H: D H A B C E F G 8H: H D A B C E F G 2G: H D G A B C E F 8H: H D G A B C E F 1E：H D G E A B C F 7G: H G D E A B C F 3

2、H: H G D E A B C F 1G: H G D E A B C F 2H: H G D E A B C F 1E: H G E D A B C F 4C: H G E D C A B F 7E: H G E D C A B F 3H: H G E D C A B F 1G: H G E D C A B F 2比較總數(shù)=54(2)移至前端自組織線性表啟發(fā)式規(guī)則： A B C D E F G H 比較次數(shù)D: D A B C E F G H 4H: H D A B C E F G 8H: H D A B C E F G 1G: G H D A B C E F 8H: H G D A B

3、C E F 2E：E H G D A B C F 7G: G E H D A B C F 3H: H G E D A B C F 3G: G H E D A B C F 2H: H G E D A B C F 2E: E H G D A B C F 3C: C E H G D A B F 7E: E C H G D A B F 2H: H E C G D A B F 3G: G H E C D A B F 4比較總數(shù)=59(3)轉(zhuǎn)置自組織線性表啟發(fā)式規(guī)則： A B C D E F G H 比較次數(shù)D: A B D C E F G H 4H: A B D C E F H G 8H: A B D

4、C E H F G 7G: A B D C E H G F 8H: A B D C H E G F 6E：A B D C E H G F 6G: A B D C E G H F 7H: A B D C E H G F 7G: A B D C E G H F 7H: A B D C E H G F 7E: A B D E C H G F 5C: A B D C E H G F 5E: A B D E C H G F 5H: A B D E H C G F 6G: A B D E H G C F 7比較總數(shù)=959.8 編寫一個算法，實現(xiàn)頻率計數(shù)自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實現(xiàn)。特別

5、是編寫一個函數(shù)FreqCount，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線性表的最后，其頻率計數(shù)是1。算法思想： 按順序訪問記錄，每訪問一條記錄，該記錄的訪問數(shù)加1，如果該記錄的訪問數(shù)已經(jīng)大于它前面記錄的訪問數(shù)，這條記錄就在線性表中與前面的記錄交換。 偽代碼： template <class Elem>void FreqCount(Elem A, int count) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break

6、; else if (i = n) An = val; countn+ = 1; else counti+; while (i > 0) && (counti > counti-1) swap(Ai, Ai-1); swap(counti, counti-1); 9.9 編寫一個算法，實現(xiàn)移至前端自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實現(xiàn)。特別是編寫一個函數(shù)MoveToFront，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線性表的開始位置。算法思想： 按順序訪問記錄，每找到一個記錄就把它放到線性表的最前面，而把其他記錄后退一個

7、位置。偽代碼：template <class Elem>void MoveToFront(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break; if (i = n) An = val; while (i > 0) swap(Ai, A0); 9.10 編寫一個算法，實現(xiàn)轉(zhuǎn)置自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實現(xiàn)。特別是編寫一個函數(shù)transpose，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線

8、性表的最后。算法思想：按順序訪問記錄，把找到的記錄與它在線性表中的前一條記錄交換位置。偽代碼：template <class Elem>void tanspose(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break; if (i = n) An = val; While (i != 0) swap(Ai, Ai-1); * 設(shè)散列函數(shù)為h(K) = K mod 7, 閉散列表的地址空間為0, , 6, 開始時散列表為空, 用線性探查法解決沖突

9、, 請畫出依次插入鍵值23, 14, 9, 6, 30, 12, 18后的散列表。 h(23)=2 h(14)=0 h(9)=2 h(6)=6 h(30)=2 h(12)=5 h(18)=401411822339430512669.16 使用閉散列，利用雙散列方法解決沖突，把下面的關(guān)鍵碼插入到一個有13個槽的散列表中（槽從0到12編號）。使用的散列函數(shù)H1和H2在下面定義。給出插入8個關(guān)鍵碼值后的散列表。一定要說明如何使用H1和H2進行散列。函數(shù)Rev(k)顛倒10進制數(shù)k各個位的數(shù)字，例如，Rev(37)=73，Rev(7)=7。H1(k)=k mod 13。H2(k)=(Rev(k+1)

10、mod 11)。關(guān)鍵碼：2,8,31,20,19,18,53,27H1(2)=2 H2(2)=3 放在位置2H1(8)=8 H2(8)=9 放在位置8H1(31)=5 H2(31)=1 放在位置5H1(20)=7 H2(20)=1 放在位置7H1(19)=6 H2(19)=2 放在位置6H1(18)=5 H2(18)=3 放在位置5，但位置5已經(jīng)有數(shù)據(jù)，5+3=8，位 置8也有數(shù)據(jù)8+3=11，放在位置11H1(53)=1 H2(53)=1 放在位置53H1(27)=1 H2(27)=5 放在位置1，但位置1已經(jīng)有數(shù)據(jù)，1+5=6，位 置6也有數(shù)據(jù)，6+5=11，位置11也有數(shù)據(jù)， 11+5=

11、3，放在位置3 015322327453161972088910111812 第11章 圖的作業(yè)11.3 (a)畫出圖11.26所示圖的相鄰矩陣表示。1 2 3 4 5 6 10 20 210 3 5 3 15 20 5 11 10 15 11 32 10 3123456 (b)畫出這個圖的鄰接表表示。1 -> 2(10) -> 4(20) -> 6(2) -> 2 -> 1(10) -> 3(3) -> 4(5) -> 3 -> 2(3) -> 5(15) -> 4 -> 1(20) -> 2(5) -> 5

12、(11) -> 6(10) -> 5 -> 3(15) -> 4(11) -> 6(3) -> 6 -> 1(2) -> 4(10) -> 5(3) -> 11.4 對于圖11.26所示的圖，給出從頂點1開始DFS樹。42163511.5 對于圖11.26所示的圖，給出從頂點1開始BFS樹42163511.8 對于圖11.26中的圖，給出從頂點4出發(fā)，使用Dijkstra最短路徑算法產(chǎn)生的最短路徑表。請像圖11.18所示那樣，每處理一個頂點時給出相應(yīng)D值。123456初始0處理420501110處理2155801110處理315580

13、1110處理5155801110處理6155801110處理1155801110頂點4到頂點1的最短路徑為15；頂點4到頂點2的最短路徑為5；頂點4到頂點3的最短路徑為8；頂點4到頂點4的最短路徑為0；頂點4到頂點5的最短路徑為11；頂點4到頂點6的最短路徑為10。11.12 編寫一個算法確定一個有|V|個頂點的有向圖是否包含回路。算法的時間代價應(yīng)該是（|V|+|E|）。算法思想：用廣度優(yōu)先拓撲排序的方法，首先訪問所有的邊，計算指向每個頂點的邊數(shù)，將所有沒有先決條件的頂點放入隊列，然后開始處理隊列，當(dāng)從隊列中刪除一個頂點時，把它打印出來，同時將其所有相鄰頂點的先決條件計數(shù)減1，當(dāng)某個相鄰頂點的

14、計數(shù)為0時，就將其放入隊列，如果還有頂點未被打印，而隊列已經(jīng)為空，則圖中包含回路。偽代碼：void topsort (Graph*G,Queue) int Count G->n(); int v,w; for (v=0;v<G->n();v+) Countv=0; for (v=0;v<G->n();v+)for (w=G->first(v); w<G->n; w=G->next(v,w) Countw+; for (v=0;v<G->n();v+)if (Countv=0;) Q->enqueue(v); while (

15、Q->length()!=0) Q->dequeue(v);printout(v);for (w=G->first(v); w<G->n(); w=G->next(v,w) Countw-; if (Countw=0) Q->enqueue(w); 11.13 編寫一個算法確定一個有|V|個頂點的無向圖是否包含回路。算法的時間代價應(yīng)該是（|V|）。算法思想：用深度優(yōu)先搜索的方法，如果遇到已經(jīng)訪問過的結(jié)點，則說明該無向圖包含回路。偽代碼：void DFS(int map, int a, int dep) if(dep>1 && a

16、= v) Printout("有環(huán)路"); return; for(i=0;i<N;i+) if(mapai = 1) DFS(map, i, dep+); void main() DFS(map, v, 1);11.15 對于圖11.26所示的圖，給出使用Floyd的每對頂點間最短路徑算法的結(jié)果。0-path1 2 3 4 5 6 0 10 20 210 0 3 5 3 0 15 20 5 0 11 10 15 11 0 3 2 10 3 01234561-path1 2 3 4 5 6 0 10 20 210 0 3 5 12 3 0 15 20 5 0 11 1

17、0 15 11 0 3 2 12 10 3 01234562-path1 2 3 4 5 6 0 10 13 15 210 0 3 5 1213 3 0 8 15 1515 5 8 0 11 10 15 11 0 3 2 12 15 10 3 01234563-path1 2 3 4 5 6 0 10 13 15 28 210 0 3 5 18 1213 3 0 8 15 1515 5 8 0 11 1028 18 15 11 0 3 2 12 15 10 3 01234564-path1 2 3 4 5 6 0 10 13 15 26 210 0 3 5 16 1213 3 0 8 15 1

18、515 5 8 0 11 1026 16 15 11 0 3 2 12 15 10 3 012345651 2 3 4 5 6-path 0 10 13 15 26 210 0 3 5 16 1213 3 0 8 15 1515 5 8 0 11 1026 16 15 11 0 3 2 12 15 10 3 01234561 2 3 4 5 66-path 0 10 13 12 5 210 0 3 5 16 1213 3 0 8 15 1512 5 8 0 11 10 5 16 15 11 0 3 2 12 15 10 3 012345611.18 對于圖11.26中的圖，給出從頂點3開始使用Prim的MST算法時各個邊的訪問順序，并給出最終的MST。各個邊的訪問順序：（3,2）（2,4）（2,1）（1,6）（6,5）最終MST：42163511.19 對于圖11.26中的圖，給出使用Kauskal的MST算法