Microsoft Word - 勘誤表.doc

Size: px

Start display at page:

Download "Microsoft Word - 勘誤表.doc"

练霄印
4 years ago
Views:

1 最新資料結構分類題庫講義勘誤表 P- 勘誤表例題解答 () 例題解答 () () () P- P-6 P- () () + + = 例題題目 Program. c for (k = ; k > ; k++) fact * = k; retur fact; Program. d for (i = ; i < ; i++) { for (j = ; j >= i + i; j ) { 例題解 :()()() 例題 6 解答第三行 () = θ( lg ) () () () + + = 例題題目 Program. c for (k = ; k ; k++) fact * = k; retur fact; Program. d for (i = ; i < ; i++) { for (j = ; j >= i; j ) { 例題解 :()()()() 例題 6 解答第三行 () = θ() k ()

2 最新資料結構分類題庫講義勘誤表頁數修正前修正後例題解答例題解答 () = + +, () = () = + = + = + + = + + = + P-8 = = + ( ) = = lg lg ( () + lg + lg ) = = 例題 8 例題 8 P-9 解 : () () 解 : () () 例題 0 題目最後一行例題 0 題目最後一行 P- x = x (%) x = x i(%) 例題題目例題題目 Ω() ad θ() actually are set of Ω() ad θ() actually are set of P-6 fuctios. ut we ofte say Ω() + fuctios. ut we ofte say Ω() + 0(). θ(). 例題解答例題解答 P- 解 :() 解 :() 例題題目第四行例題題目第四行 P-0 for (j = ; j ; j++) for (j = i; j ; j++) 例題解答最後一行例題解答最後一行 P- 因此,order 順序為 :(b) < (a) = (e) < 因此,order 順序為 :(b) < (a) = (e) < (d) < (g) < (c) (f)(d) < (c) < (g) 例題題目 P- 頁第四行例題題目 P- 頁第四行 P- out < < ove disk from out < < ove disk from 例題解答最後加上二行例題解答最後加上二行 P-9 = =

3 最新資料結構分類題庫講義勘誤表例題解答 () = 6, x = 6 P- () 外層 while loop 執行 θ () 次例題解答 () x = 6 = 8 () θ (,log log ) 內層之 while loop 執行 θ (lg ) 次共執行 θ ( lg ) 次例題 6 解答倒數第二行 P- () () = θ(lg ) 例題 66 解答第七行刪 prit P-0 prit P(list ext); 例題 6 解答 P- 解 : 乙例題 88 解答 P-6 / log log log, log( ) (log ). (.6) / 例題 9 解答步驟 : 同取 log, 去掉常數, 比較大小 > 000 (log) ()! > 000 > (.00) P-6 log log > 000 () 000 (log)(loglog) > (log ) > log log > 例題 6 解答倒數第二行 () () = θ() 例題 66 解答第七行 P(list ext); 例題 6 解答解 : 丙例題 88 解答 / log log log, log( ) (log ). / (.6) 例題 9 解答 h > log > log (log log ) > log log

4 最新資料結構分類題庫講義勘誤表頁數修正前修正後例題 9 解答例題 9 解答 i = i = i = j = to = k = P-68 O( ) j = to to j = k = ( ) k = k = ( ) i j = i= j= k= 0 i= j= O( ) 例題解答全刪例題解答若 rear 在 frot 之後, 則 = rear = (rear frot)% frot + P- 若 rear 在 frot 之前, 則 = rear + frot + = (rear frot) mod + 例題題目 () 第三行例題題目 () 第三行 P-6 { Ptroode irstell; { Ptroode irstell; P- P-6 例題題目第五行. 00p (ot ed of file) 例題解答倒數第三行前插入一行 { (stack top) ; 例題 6 解答 P- ()() ()() ()() 例題題目第四行 P- x = 0 x = 0 例題解答 () () * P- ( + = i= i j i(i + ) i = O( ) i= 例題題目第五行. loop (ot ed of file) 例題解答倒數第三行前插入一行 { ew_item=stack item[stack top]; (stack top) ; 例題 6 解答 ()() ()() ()() 例題題目第四行 x = 0 z = 0 例題解答 () () *

5 最新資料結構分類題庫講義勘誤表例題解答 () 例題解答 () () () P- ( / + (+)* P-9 P-9 P- 例題 8 題目最後一行 a &&b c!(e>f) (6%) 例題題目第二行插入 8 keys,,,, 例題 6 解答 () 圖形刪掉右圖例題 8 題目最後一行 a &&b c!(e>f) (6%) 例題題目第二行插入 8 keys,,, 8,, 例題 6 解答 () 圖形刪掉右圖 9 8 例題 8 解答第五行 P- pritf ( item); 例題 0 題目第二行, 0, 0,, 解答修改解 : P- 例題 8 解答第五行 pritf ( item); 例題 0 題目第二行 0, 0, 0,, 解答修改解 :

6 6 最新資料結構分類題庫講義勘誤表頁數修正前修正後 P 例題題目最後一行 P- uigue? If ot, use the 例題解答 () 第二行 P-9 Iorder: 0, 0, 0, 0, 例題 9 題目倒數第二行 P- (), 99, 8,, 9. 例題題目最後一行 P- of height h? (0%) 例題 6 題目 () 0 P 例題題目最後一行 uique? If ot, use the 例題解答 () 第二行 Iorder: 0, 0, 0, 0, 例題 9 題目倒數第二行 (), 99, 8,, 6. 例題題目最後一行 of height? (0%) 例題 6 題目 ()

7 最新資料結構分類題庫講義勘誤表例題 8 題目及解答題目第三行 () ode is i ad i +. 例題 8 題目及解答題目第三行 () ode i is i ad i +. P- 解答解 :()() 解答解 :()() ote:() 假設不考慮有無左右子點存在的話例題 9 解答第一行例題 9 解答第一行 P- ifix: + = $ ifix: + $ 例題 0 題目最後一行 P- max heap obtaied i 例題 0 解答 () 例題 0 題目最後一行 mi heap obtaied i 例題 0 解答 () P 例題題目 () 刪 the deleted from 例題題目 () 刪 the deleted from ()Please desig a algorithm to ()Please desig a algorithm to reorgaize your data structure reorgaize your data structure i i 8() after the ruig process () after the ruig process is P-0 is completed ad deleted from completed ad deleted from the the deleted from the scheduler. scheduler. (e.g. J is deleted from (e.g. J is deleted from the the scheduler) (8%) scheduler) (8%) 例題解答例題解答 Ifo 之功能在於計算其 free 之 ode Ifo 之功能在於計算其 tree 之 eaf 個數 P- 數 ( 除了 root 之外 ) Ifo (tree ) 會傳回 : Ifo (tree ) 會傳回 : Ifo (tree ) 會傳回 :6 Ifo (tree ) 會傳回 :

8 8 最新資料結構分類題庫講義勘誤表例題題目圖修改例題題目圖修改 root root left right left right P- 例題 6 解答 ()Preorder: IJK P- ()Iorder: IJK ()Postorder: IJK 例題 9 題目倒數第二行 P- fields efthikd, ata, 例題 9 解答 ()preorder () { if ( ull) P- preorder ( Righthild); prit ( ata); preorder ( efthild); 例題解答圖修改例題 6 解答 ()Preorder: IJK ()Iorder: IJK ()Postorder: IJK 例題 9 題目倒數第二行 fields efthild, ata, 例題 9 解答 ()Iorder () { if ( ull){ Iorder ( efthild); prit ( ata); Iorder ( Righthild); 例題解答圖修改 P- P- J P 例題解答第一行若 m 為之 qcestor J P 例題解答第一行若 m 為之 acestor

9 最新資料結構分類題庫講義勘誤表 9 頁數修正前修正後例題 9 題目例題 9 題目 P-6 What the maximum umber What is the maximum umber 例題 0 解答圖修改例題 0 解答圖修改 or or P-8 or or or or 例題題目第三行 P- to (with o repeats), 例題 8 題目第三行 P-6 b = b b, for k= 0 k k 例題 8 解答 () 第三行 ()it b(it ) P-6 { it um=0; if (==0) retur 0; 例題 9 解答第 ~ 行有 6 8 = 個 ode P- 共有種結構 + () 令為之 ode 數, R 為 R 之 ode 數, 則令 > R : 例題題目第三行 to 9 (with o repeats), 例題 8 題目第三行 b = b b, for k= 0 k k 例題 8 解答 () 第三行 ()it b(it ) { it um=0; if (==0) retur ; 例題 9 解答第 ~ 行必為 full biary tree 共有種結構 () 令為之 ode 數, R 為 R ode 數, 且 > R : 之

10 0 最新資料結構分類題庫講義勘誤表頁數修正前修正後例題 9 解答例題 9 解答共有 9 6 共有 9 6 種結種結構構 () 種 ( 若設 root 之 height 為 0) 如下 :() P-6 P-8 R 有, 6,,,,,, ()0 種, full biary tree 高為 h 之 () 6 ode 數為 h 例題 99 解答 () 最後九行例題 99 解答 () 最後九行 algorithm oected-ompoets () Kruskal s algo for each edge (u,v) () quivalece pairs do if id (u) id (v) the Uio (u, v) algorithm Same-ompoet (u, v) if id(u) = id (v) the retur rue ; else retur alse ; 例題 09 解答最後一行 P-89 () 課本附錄有例題解答 () 正確 P-9 ()()()()() 例題 09 解答最後一行 () 參考例例題解答 () 考慮只有兩個點的 omplete iary ree, 此時 =, = < 不會成立 ()()()()

11 最新資料結構分類題庫講義勘誤表例題 0 解答 () 圖修改例題 0 解答 () 圖修改 P P6- P6-6 6 例題題目第一行例題題目第一行 omplete the followig epth- omplete the followig epth- irst irst Search paeudocode, Search pseudocode, 例題解答第二行 6, d[u] < d[v] 例題 6 題目圖修改例題解答第二行 6, d[u] > d[v] 例題 6 題目圖修改 P6- P6-8 P6-9 P6-0 P6-0 I J K 例題 9 解答倒數第二行 max flow = 例題 0 解答第一行 () W[i, j] k [i, j] = i( k [i, j], k [i, k] + k [k, j]) 例題題目倒數第三行 simple cycle t edges if k if k = 0 > I J K 例題 9 解答倒數第二行 max flow = 例題 0 解答第一行 () W[i, j] k [i, j] = i( k [i, j], k [i, k] + k [k, j]) if k if k 例題題目倒數第三行 simple cycle edges 例題題目第四行刪字例題題目第四行 problem for this problem. owever, problem. owever, the algorithm is the algorithm is = 0

12 最新資料結構分類題庫講義勘誤表例題題目第三行例題題目第三行 P6- Usig the deoth-first Usig the depth-first 例題 9 題目圖修改例題 9 題目圖修改 0 0 P P6-9 例題題目插入一字 ive the adjacecy graph 例題解答第二行 P6- ()()( = 9) P6-9 例題 8 解答修改 Selected ist [a] [b] [c] [d] [e] [f] [z] a 0 {a c {a,c d 0 8 {a,d,c b 8 {a,b,c,d f 8 6 {a,b,c,d,f z 8 6 e 例題題目插入一字 ive the adjacecy multi lists graph 例題解答第二行 ()()(!! = 6條 ) 例題 8 解答修改 Selected ist [a] [b] [c] [d] [e] [f] [z] a 0 {a c {a,c d 0 {a,d,c b {a,b,c,d f 6 {a,b,c,d,f z 6 e P6-9 P-9 P- 例題 9 解答 () 第九行 () ist (w) = ist(s)+ ; 例題題目第二行 to aboid such coditio. (%) 例題 6 解答 () 圖形修改 6 Keap 例題 9 解答 () 第九行 () ist (w) = ist(u)+ ; 例題題目第二行 to avoid such coditio. (%) 例題 6 解答 () 圖形修改 6 Xeap

13 最新資料結構分類題庫講義勘誤表例題 6 第一行 P- Pass: 例題 6 第一行 Pass: 例題解答例題解答 P9- 解 :() 解 :()()() 例題解答例題解答 P9- 有次 ollisio 0 desity為 : 有次 ollisio 9 desity為 : 例題 9 題目第三行例題 9 題目第三行 P9- quadratic for (b ) / ) quadratic for i (b ) / ) 例題 () 圖修改例題 () 圖修改 () () P0-8 : lack : Red 8 : Red : lack 例題解答第七行例題解答第七行 wjile (x data[i + ] > while (x data[i + ] > 0 P0-6 0 i++ i++ 例題 6 解答圖修改 P0-8 6 例題 6 解答圖修改 : 黑 : 紅

14 最新資料結構分類題庫講義勘誤表例題 8 解答例題 8 解答 9~ 的圖全刪 9 圖為下 P 例題 9 解答圖修改 P 9 例題 9 解答圖修改 P P0- R P0-, O U 例題 0 題目倒數第二行 Usig this code, jow may 例題圖修改,,0,, a,, 則 Red-lack ree 如下 : P0-6 0 : Red poiter : lack poiter, O R U 例題 0 題目倒數第二行 Usig this code, how may 例題圖修改,,0,, 9,, 則 Red-lack ree 如下 : 0 : Red poiter : lack poiter 9 9 P0-8 P0- 例題題目第二行 each ort ode cotais 另圖說字修改 igure of problem 例題題目第二行 each iteral ode cotais 另圖說字修改 igure of problem 例題 9 解答 () 對 biary search tree 做 iorder 例題 9 解答 () 對 biary search tree 做 RV 追蹤 traversal 即可得到一 sorted traversal 即可得到一由大到小之 sequece sorted sequece

15 最新資料結構分類題庫講義勘誤表例題題目第二行例題題目第二行 () () P0- ISS, Z, SUII, ISS, Z, ISUII, 例題解答圖修改例題解答圖修改 () () P0- I J J I V O J V I V O I R J J 例題解答最後加一行例題解答最後加一行 P = 90 例題 6 題目例題 6 題目刪兩字 Isert (a) 0; (b) 0, 80, 90; (c) 0, Isert (a) 0; (b) 0, 80, 90; (c) 0, 80, P0-80, 90, 00 ito the followig -- 90, 00 ito the followig - tree, tree, ad show the -- tree ad show the - tree results? (0%) results? (0%) 例題解答最後四行例題解答最後四行 h h 總 ode 數 = + m + m + + m 總 ode 數 = + m + m + + m h+ h (m ) (m ) = = m m () 欲使一 -tree 有最多 key 值, 則 () 欲使一 -tree 有最多 key 值, 則此 P0- 此 -tree 需 full 且每一 ode 均有 -tree 需 full 且每一 ode 均有 m m 個 key 個 key h+ h (m ) (m ) 最大 key 數為 : (m ) 最大 key 數為 : (m ) m m = m h + = m h 例題題目圖修改例題題目圖修改 P0-9 J R I O V R J R I J I V O V I K S U V I K S U V

16 6 最新資料結構分類題庫講義勘誤表例題 8 解答例題 8 解答 P0- = = 例題 9 題目第一行例題 9 題目第一行 ()ive a what-case ruig ()ive a worst-case ruig P0-6 例題 9 解答第一行例題 9 解答第一行解 :()()O() i 分攤成本解 :()()O(og ), O() 例題 6 題目第二行刪例題 6 題目第二行刪 P0- 欲放入的值依序為 9 欲放入的值依序為 9 ; ; 例題解答 () 例題解答 () P0- ()iary search tree:ug 為 ()iary search tree:vg 為例題 8 圖修改例題 8 圖修改 P

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446>

<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446> : 2 = 3 4? 0 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time (computational theory) ( ) 5 6 (C-) int min, max; float degree, b; char ch, token; /,,,