1. 志明打算就客戶服務開發一個語音互動(IVR)系統， 顧客可透過電話鍵盤與系統進行互動。 (a) 志明利用下列瀑布模式來開發IVR 系統。 (i) 應在哪個階段進行unit單元測試? (ii) 應在哪個階段進行system系統測試? (iii) 系統測試與用戶acceptance驗收測試的主要分別是什麼? (iv) 虛線箭頭的用意是什麼? 要求 實施 設計 單元 測試 實施 整合 系統 測試 整合 　　系統測試：是由開發人員進行， 用戶驗收測試：是由用戶使用真實數據進行。 $$$ 用戶驗收 測試 維護 檢討及改進前一個階段 2014 DSE ICT 2D

在IVR 系統中，顧客可以按數字鍵 或 來選取兩個模組中的其中一個; 他也可以按數字鍵離開此系統。此系統的流程圖如下展示: 30% 1 25% 2 40% 3 (b) (i) 若顧客按數字鍵， 整個流程需要作出多少次比較? (ii) 假設按數字鍵、、 和其他數字鍵的 百分率分別為30%、25%、40% 和5%。 完成下列流程圖，將預期的比較次數減至最少。 3次 2014 DSE ICT 2D

在IVR 系統中，模組2 將顧客連繫至客戶經理。顧客數目 > 客戶經理數目。 志明考慮採用一隊列queue，以儲存等候名單內顧客的資料。circular queue 此隊列以一個以指數由 0至n-1 的陣列Q[] 及兩個整數變量Qfirst 和Qlast 表示。 現有兩個子程式PUSH 和POP。 PUSH (i) 將電話線i 加入此隊列的末端， 而POP () 會傳回此隊列的首項，並會將此項從隊列中移除。 Q[]、Qfirst、Qlast 和n 均是全程變量。 Qfirst Qlast (c) (i) 為什麼志明採用隊列queue(而非堆疊stack) 來儲存等候名單內顧客的資料? Waiting list 因為服務是以先進先出FIFO方法處理。 2014 DSE ICT 2D

init(): Qfirst = Qlast = 0; queueFull(): (Qlast+1)%n==Qfirst Enqueue Dequeue void PUSH(int i){ Q [Qlast] = i; Qlast = (Qlast +1) %n; } int POP(){ int Rvalue; if( ){ Rvalue = -1; }else{ Rvalue = ; Qfirst = ; } return Rvalue; Qfirst == Qlast init(): Qfirst = Qlast = 0; queueFull(): (Qlast+1)%n==Qfirst queueEmpty(): Qlast==Qfirst Q[Qfirst] (Qfirst+1)%n (ii) Qfirst 和Qlast 的初始值均是0。試完成POP。 (iii)當POP() 傅回-1，這樣代表什麼? (d) 根據上述PUSH 的實施。 (i) 此隊列最多可儲存多少項? 請以n 表示。 (ii) 若等候名單內顧客的數目超越(d)(i) 內的數值， 會有什麼事情發生? Qfirst 隊列是空的。Empty queue 70 n-1 60 Qlast 有部分顧客記錄不能經POP()取得。/ 隊列上部分元素被改寫。 2014 DSE ICT 2D

無論是任何i 值，A 的第(i,i) 個元素均是false。 2. 志偉利用指數為i 和j 的雙陣列A，來表示一個由n個方塊組成的迷宮。唯有true和false 是A 內的值。只有當方塊i 能直接接達方塊j，A 的第(i,j) 個元素才會是true。 無論是任何i 值，A 的第(i,i) 個元素均是false。 A[i][j] (a) 例如下列迷宮由6 個方塊組成，方塊1可直接接連方塊4 但不能直接接達其他方塊。 true false (i) 當i = 2 填上下列A內的元素。 A[i][j] j 1 2 3 4 5 6 i false true : 2014 DSE ICT 2D

i<j i>j A[i][j] j 1 2 3 4 5 6 i false true false false true true (ii) A 內有多少個元素? n² 或 36 (ii) 設n = 6。志偉認為他可使用A內的15個元素，便可儲存迷宮的所有資料。 試說明他的想法。 志偉觀察到 方塊i 不可直接接達方塊i， 如果方塊i能直接接連方塊j， 方塊j也能直接接達方塊i。 當i=j，元素的值必為false，不用儲存。 當i>j，因A(i,j)=A(j,i)，所以不用儲存。 需要儲存的元素為i<j， 總數是 (36-6)2 = 15。 (b) (i) A內第(i,j)個元素 和第(j,i) 個元素的關係是什麼? 它們的值是相同。A(i,j)=A(j,i) 2014 DSE ICT 2D

現有一個函數 isNeighbor(i,j)， 當方塊i 能直接接達方塊j 時，便傳回true，否則傳回false。 志偉定義另一個函數 twoNeighbors(i,j)，當有一方塊P，可使方塊i能直接接達方塊P，而方塊P 能直接接達方塊j ，並且i≠j，此函數便傳回true 否則傳回false。 // i  P  j (c) 利用(a) 內由6 個方塊組成的迷宮:   (i) 舉出兩個參數(x,y)，可使twoNeighbors 傳回true twoNeighbors (_x_,_y_) (ii) 完成下列twoNeighbors 的算法。 (1,5),(2,4),(2,6),(3,5),(4,6) twoNeighbors(i,j) RESULT ← ( ) 如果i≠j 設p 由1至6執行 RESULT ← RESULT OR (isNeighbor( ) AND isNeighbor( )) 傳回 RESULT false (或0) P,i P,j if( isNeighbor(P,i) AND isNeighbor(P,i) ) 傳回 TRUE 2014 DSE ICT 2D

(d) 志偉決定選用物件導向語言，來編寫此迷宮的流動應用程式mobile app。 試以流動應用程式的一個特性來說明他的選擇。 流動應用程式 需要一個很短的開發生命周期life-cycle。 物件導向語言中的函數庫，可幫助縮短開發生命周期(再用性re-use) 3. 小明建構了下列鏈表來儲存學生的英文姓名，並以陣列來顯示此鏈表。 在此鏈表中，有一指示標Next 儲存下一個節點的地址。 首個節點儲存了「START」。 地址 內容 Next START 3 1 Ben 4 2 Kate -1 Amy Jade 5 Elle   : (a) (i)順序寫出「START」 後兩個節點的內容。 (ii) 小明利用「-1」來表示一個空指示標pointer。 除了「-1」外，舉出小明可採用的數值範圍。 (START Amy Jade Elle) 負數(-999) / 大於陣列大小的數字(e.g.9999) (iii) 包括首個節點「START」，此鏈表共有多少個節點(node)? 4 2014 DSE ICT 2D

地址 內容 Previous Next 1 2 地址 內容 Previous Next 1 2 3 4 小明加建另一個指示標Previous 而設計了LL1。 在每一個節點內， Previous指向之前一個節點，如下列例子所示: 地址 內容 Previous Next START -1 3 1 John 4 2   Susan Fiona 小明設計了兩個操作DELETE及INSERT。 (START Susan John Fiona) DELETE (n) 會刪除第n 個節點， INSERT (n, sname) 會在第n 個節點後加入一個節點，其內容為sname。 首個節點儲存了START。 (b) 小明順序執行下列操作來更新以上LL1 的例子。 INSERT (4 , 'Mary') DELETE (3) 在下方更新LL1。 (START Susan John Fiona Mary) 地址 內容 Previous Next START 1 2 3 4 -1 3 4 3 4 -1 2 John Mary Susan Fiona 可忽略 2014 DSE ICT 2D

(c) 舉出在設計內加建了Previous 的一個優點和一個缺點。 優點：可以從兩個方向遍歷traverse鏈表linked-list。 缺點：需要更多儲存空間。 (d) 小明修改LL1而設計了LL2，他採用PTR 來取締Previous 及Next。 每個節點的PTR 儲存Previous 及Next 內地址的總和(即PTR = previous + Next)。 例如:就下列LL1 其對應的LL2 會是: LL2 地址 內容 Previous Next START -1 3 1 John 4 2   Susan Fiona 5 地址 內容 PTR START 2 1 John 7   3 Susan 4 Fiona 5 (START Susan John Fiona) 2014 DSE ICT 2D

(i) 在下列LL2，順序寫出START 後三個節點的內容。 地址 內容 PTR START 1 Candy 3 2 Ben Amy 6 4 Lee 7 5 Daisy 地址 內容 Previous Next START 1 Candy 2 Ben 3 Amy 4 Lee 5 Daisy -1 1 3 4 -1 1 5 5 2 3 4 (START Candy Amy Daisy …) (ii) 採用LL2 的好處是什麼? 減少儲存空間。 2014 DSE ICT 2D

4. 陳先生進行字串string樣式pattern分析工作。 (a) 考慮下列包括字串ST 的算法。 st[i] st[n-i+1] st[1] st[8] st[2] st[7] st[3] st[6] st[4] st[5] 4. 陳先生進行字串string樣式pattern分析工作。 (a) 考慮下列包括字串ST 的算法。 check ← TRUE n ← ST 的長度 設 i 由1 至n 執行 如果ST第i個字符≠ST第(n-i+1)個字符 check ← FALSE 傳回check check=1; n = strlen(ST); // 8 for(i=1; i<=n; i++){ if(ST[i]!=ST[n-i+1]) check=0; } return check; (i) 以下列不同ST 的字串值，空運行此算法。寫出其相關的傳回值。 ST check i  n-i+1 ACGT GACTTCAG ACGCA FALSE 1-4, 2-3 TRUE 1-8, 2-7, 3-6, 4-5 1-5, 2-4, 3-3 (iii) 重寫此循環首句語句，以改善此算法的效率。 設 i 由 ____ 至 ____ 執行 (ii) 此算法有什麼目的? 它檢驗字串ST 是否廻文palindrome。 (由左至右讀, 由右至左讀, 都相同) 1 n/2 2014 DSE ICT 2D

已知有一個子程式 MyLen 可傳回輸入字串的長度(strlen)。 陳先生打算編寫一個字程式IsSub (T1, T2) 以檢查T2 是不是T1 的子字串。substring (b) 試完成IsSub 的算法。 (e.g. T1="mouse and cat", T2="use")  i=1  j=1,2,3 i 1 2 3 4 5 6 7 8 9 T1 m o u s e a n d c t T2   IsSub(T1, T2) i ← 1 r ← FALSE 當(r是 ) 及 MyLen(T1)MyLen(T2)+1 ≥ i)，便執行 j ← ( ) r ← TRUE 當( > j) 便執行 j ← j+1 如果T1 第( )個字符≠T2第 j 個字符 i ← i+1 傳回r 13 3 FALSE MyLen(T2) i+j-1 2014 DSE ICT 2D

T pos n substr AACTTGGTAC T1 T2 T1和T2中最長相同子字串 子字串的長度 AACTTGGTAC (c) 陳先生完成了IsSub(T1, T2) 的編碼。他也編寫另一個子程式MyCopy。   void MyCopy (char T[] , char substr[] , int pos , int n) 複製T 的子字串至substr，而pos 是此子字串的開始位置，n則是此子字串的長度。 字符陣列的指數由0 開始。例如: strncpy (substr, T+pos , n); T pos n substr AACTTGGTAC 2 4 CTTG 陳先生打算找出兩個字串中 最長相同子字串的長度。例如: T1 T2 T1和T2中最長相同子字串 子字串的長度 AACTTGGTAC AAGACTG ACT 3 2014 DSE ICT 2D

假設有兩個全程變量n1 和n2，分別儲存 MyLen(T1) 和 MyLen(T2)， 而n1 >= n2。編寫子程式void LongSub (char T1[], char T2[])， 以顯示T1 和T2 中最長相同子字串的長度。 void LongSub (char T1[], char T2[]) { int i, j, found=0; char temp[50]; i = n2; while (!found && i>=1) { j = n2 - i + 1; while (!found && j>=1) { MyCopy(T2, temp, j, i); if (IsSub(T1, temp)) { found = 1; printf("The length is %i\n", i); } j--; i--; T1(n1=10) AACTTGGTAC T2(n2=07) AAGACTG  i=7 ﹒宣告 ﹒初始他旗標(FOUND) /最大長度值 ．任何循環loop： 1 至T2 的字串長度(n2) ．檢查T2 所有子字串(迴圈檢查 1+2+3+... +n2) ．呼叫IsSub 時不包含正確的參數 ．完全正確 2014 DSE ICT 2D

(n1=10) T1=AACTTGGTAC (n2=07) T2=AAGACTG i 1 2 3 4 5 6 7 8 9 T1 A C T 1 2 3 4 5 6 7 8 9 T1 A C T G T2    (n1=10) T1=AACTTGGTAC (n2=07) T2=AAGACTG  i 1 2 3 4 5 6 7 8 9 T1 A C T G T2     A G C T  A G C T   A G C T A G C T  A G C T 2014 DSE ICT 2D