資訊處理 94 年程式語言考古題

考慮下列程式片段： S1: procedure P(L) /* L 唯一串數字*/ S2: 若L 的長度為2, 則return 此二數字之和 S3: L1 = L 的前半部分 /* if L=1234，L1=12 */ S4: L2 = 將L 分成四部分，為第2 及第3 部分之組合 /* if L=1234，L2=23 */ S5: L3 = L 的後半部分 /* if L=1234，L3=34 */ S6: return(P(L1)+P(L2)+P(L3)) ㈠若L=876543219（長度為8），則最後return 之結果為何？（10 分） ㈡若S2 的計算時間與L 的長度無關，而S3 到S5 的計算時間則與L 的長度有關。若 L 的長度為N，則P(L)的計算時間複雜度為何？（10 分）

下述文法會產生二進位數字，試說明其產生數字之值為3 之倍數。（20 分） <C> → <C> 0 | <A> 1 | 0 <A> → <B> 0 | <C> 1 | 1 <B> → <A> 0 | <B> 1

考慮下列C++程式片段： class B { public: virtual char f( ) { return ‘B’; } char g( ) { return ‘B’; } char testF( ) { return f( ); } char testG( ) { return g( ); } } class D: public B { char f( ) { return ‘D’; } char g( ) { return ‘D’; } } main( ) { D d; print d.testF( ), d.testG( ); } 請說明其動態繫結（dynamic binding）執行之情形。（20 分） 94 年交通事業鐵路人員、公路人員升資考試試題 代號： 級 別： 員級晉高員級 科 別： 公路：資訊管理、資訊處理

㈠何謂資料抽象形態（abstract data type）？（10 分） ㈡假設已有一資料抽象形態stack，試說明下列程式片段中每一指令之功能。（10 分） void main( ){ int top_one; stack stk; stk.push(42); stk.push(17); top_one = stk.top(); … }

C語言的參數傳遞為以值傳遞（passed by value），若需達到以址傳遞（passed by address） 則必須利用些技巧（如"&"）。考慮下列程式片段，並求出swap()執行後變數left 及 right 的值各為多少？ ㈠void main( ){ int left = 2, right = 5; swap(left, right); } void swap(int a, int b){ int temp; temp = a; a = b; b = temp; }（10 分） ㈡void main( ){ int left = 2, right = 5; swap(&left, & right); } void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp; } （10 分）