大數(shù)據(jù)結構作業(yè)(3)

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

2、ABFG: H G E D C A B F 2比較總數(shù)=54(2)移至前端自組織線性表啟發(fā)式規(guī)則：ABCDEFGH比較次數(shù)D:DABCEFGH 4H:HDABCEFG 8H:HDABCEFG 1G:GHDABCEF 8H:HGDABCEF 2E : EHGDABCF 7G: G E H D A B C F 3H:HGEDABCF 3G: G H E D A B C F 2H:HGEDABCF 2E: EHGDABCF 3C:CEHGDABF 7E:ECHGDABF 2H:HECGDABF 3G: G H E C D A B F 4比較總數(shù)=59(3)轉置自組織線性表啟發(fā)式規(guī)則:ABCDEFGH

3、比較次數(shù)D:ABDCEFGH 4H: A B DC E F H G 8H:ABDCEHFG 7G:ABDCEHGF 8H:ABDCHEGF 6I: ABDCEHGF 6G:ABDCEGHF 7J: ABDCEHGF 7G:ABDCEGHF 7K: ABDCEHGF 7E:ABDECHGF 5C: A B D C E H G F 5E:ABDECHGF 5H:ABDEHCGF 6G:ABDEHGCF 7比較總數(shù)=959.8編寫一個算法，實現(xiàn)頻率計數(shù)自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實現(xiàn)。特別是編寫一個函數(shù)FreqCount,它把要檢索的值作為輸入，并且相 應地調整線性表。如果值不在線性表

4、中，就把它添加到線性表的最后，其頻率計 數(shù)是1。算法思想：按順序訪問記錄，每訪問一條記錄，該記錄的訪問數(shù)加1 ,如果該記錄的訪 問數(shù)已經大于它前面記錄的訪問數(shù),這條記錄就在線性表中與前面的記錄交換。偽代碼：template <class Elem>void FreqCount(Elem A, int count)(int n = 0;while (int val = GETNEXTO) != DONE)(for (i=0; i<n; i+)if (Ai = val) break;else if (i 二二 n)(An = val;countn+ = 1;elsecounti

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

6、t(Elem AQ)(int n = 0;while (int val = GETNEXTQ) != DONE)(for (i=0; i<n; i+)if (Ai = val) break;if (i = n) An = val;while (i > 0)swap(Ai, A0);)910編寫一個算法，實現(xiàn)轉置自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組 實現(xiàn)。特別是編寫一個函數(shù)transpose ,它把要檢索的值作為輸入，并且相應 地調整線性表。如果值不在線性表中，就把它添加到線性表的最后。算法思想：按順序訪問記錄，把找到的記錄與它在線性表中的前一條記錄交換位置。偽代碼：templ

7、ate <class Elem>void tanspose(曰em A)(int n = 0;while (int val = GETNEXTQ) !二 DONE) (for (i=0; i<n; i+)if (Ai = val) break;if (i = n) An = val;While (i != 0)swap(Ai, Ai-1);)*設散列函數(shù)為h(K) = K mod 7,閉散列表的地址空間為。，6,開始時 散列表為空 用線性探查法解決沖窕請畫出依次插入鍵值23,14, 9, 6, 30,12, 18后的散列表。h(23)=2 h (14)=0 h(9)=2 h(

8、6)=6 h(30)=2 h(12)=5 h(18)=40141182233943051266916使用閉散列，利用雙散列方法解決沖突，把下面的關鍵碼插入到一個有13 個槽的散列表中(槽從。到12編號1使用的散列函數(shù)H1和H2在下面定義。 給出插入8個關鍵碼值后的散列表。一定要說明如何使用H1和H2進行散列。 函數(shù)Rev(k)顛倒10進制數(shù)k各個位的數(shù)字，例如，Rev(37)=73 , Rev(7)=70 Hl(k)=k mod 130H2(k)=(Rev(k+l) mod 11)0加碼：2,8,31,2019,18,53,27Hl(2)=2H2=3放在位置2Hl=8H2=9放在位置8Hl(3

9、1)=5 H2(31)二 1 放在位置 5Hl(20)=7 H2(20)二 1 放在位置 7Hl(19)=6H2(19)=2放在位置6H1Q8)=5 H2(18)二3 放在位置5，但位置5已經有數(shù)據(jù)，5+3=8 ,置8也有數(shù)據(jù)8+3=11,放在位置11Hl(53)=l H2(53)=l 放在位置 53Hl(27)=l H2(27)=5 放在位置1，但位置1已經有數(shù)據(jù)，1+5=6 , 位置6也有數(shù)據(jù)，6+5=11，位置11也有數(shù)據(jù)，11+5=3,放在位置3015322327453161972088910111812第11章圖的作業(yè)11.3 (a)畫出圖1L26所示圖的相鄰矩陣表示。1234561

10、0202103531520511 1015 1132103(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(11)-> 6(10) -> 5 ->3(15)-> 4(11)->6(3)-> 6-> 1(2) -> 4(10) -> 5(3) ->11.4對于圖11.26所示的圖，給出從頂點1開始DFS

11、樹。115對于圖11.26所示的圖，給出從頂點1開始BFS樹118對于圖1126中的圖，給出從頂點4出發(fā)，使用Dijkstra最短路徑算法產生的最短路徑表。請像圖11.18所示那樣，每處理一個頂點時給出相應D值。123456初始OOOOOO0OOOO處理4205CXD01110處理2155801110處理3155801110處理5155801110處理6155801110處理1155801110頂點4到頂點1的最短路徑為15 ;頂點4到頂點2的最短路徑為5 ;頂點4到頂點3的最短路徑為8 ;頂點4到頂點4的最短路徑為0 ;頂點4到頂點5的最短路徑為11;頂點4到頂點6的最短路徑為10。1112

12、編寫一個算法確定一個有|V|個頂點的有向圖是否包含回路。算法的時間 代價應該是© (|V| + |E|1算法思想：用廣度優(yōu)先拓撲排序的方法，首先訪問所有的邊，計算指向每個頂點的邊數(shù), 將所有沒有先決條件的頂點放入隊列，然后開始處理隊列，當從隊列中刪除一個 頂點時，把它打印出來，同時將其所有相鄰頂點的先決條件計數(shù)減1 ,當某個相 鄰頂點的計數(shù)為0時，就將其放入隊列，如果還有頂點未被打印，而隊列已經為 空，則圖中包含回路。偽代碼：void topsort (Graph*G/Queue)(int Count G->n();int v,w;for (v=0;v<G->n()

13、;v+) Countv=0;for (v=0;v<G->n();v+)for (w=G->first(v); w<G->n; w=G->next(vfw)Countw + +;for (v=0;v<G->n();v+)if (Countv = =0;)Q->enqueue(v);while (Q->length()!=0)(Q->dequeue(v);printout(v);for (w=G->first(v); w<G->n(); w=G->next(v;w)Countw"if (Countw

14、 =0)Q->enqueue(w);) 11.13編寫一個算法確定一個有|V|個頂點的無向圖是否包含回路。算法的時間 代價應該是。(|V|X算法思想：用深度優(yōu)先搜索的方法，如果遇到已經訪問過的結點，則說明該無向圖包含 回路。偽代碼：void DFS(int map, int a, int dep)(if(dep>l && a = v)(Printout("有環(huán)路)return;)for(i=0;i<N;i + +)(if(mapai = 1)DFS(map, i, dep+);)void main()(DFS(map, v, 1);)1115對于圖1

15、1.26所示的圖，給出使用Floyd的每對頂點間最短路徑算法的結果。O-path12345610100020002210035000030030001500420500011105000015110362000010301-path 12 3 4 5 610100020002210035001230030001500420500011105000015110362120010302-path123456101013150022100350012313308151541558011105000015110362121510303-path 12 3 4 5 6101013152822100351

16、812313308151541558011105281815110362121510304-path123456101013152622100351612313308151541558011105261615110362121510305-path 123456101013152622100351612313308151541558011105261615110362121510306-path 1234561010131252210035161231330815154125801110551615110362121510301118對于圖H.26中的圖，給出從頂點3開始使用Prim的MST算法時各個邊的訪問順序，并給出最終的MST0各個邊的訪問順序：(3,2)( 2,4)( 2,1)(1,6)( 6,5 )最終MST:1119對于圖1126中的圖，