資訊處理 95 年程式設計概要考古題
題目為考試當年公告版本，實務標準請以現行規範為準。
設輸入為一串整數數列，請從中找出一個長度最長的遞增子串列，當此子串列不唯 一時，選取其中和最大的子串列。例如：當輸入串列為9、15、7、6、11、12、4 時， 輸出為9、11、12 。請以C、C++、JAVA 或VB（Visual Basic）中任一程式語言作 答。（20 分）
請利用迴圈控制指令，由外部資料檔讀入欲反轉字串，將此字串反轉後，印出此字 串。請以C、C++、JAVA 或VB（Visual Basic）中任一程式語言作答。（20 分）
數學上有一種費氏級數（Fibonacci numbers），其定義如下： ⎩ ⎨ ⎧ > − + − = = 2 ), 2 ( )1 ( 2 ,1 ,1 ) ( n if n Fib n Fib n if n Fib 請說明產生n = 500 的費氏級數適合使用遞迴（recursive）演算法或疊代（iteration） 演算法？寫出你的答案與理由。（20 分）
請由小至大列出下述函數之複雜度：1000000, nlogn, n2, (3/2)n, loglogn, n2logn。寫出 你的答案與理由。（20 分）
考慮下列程式片段： S1: procedure P(L) /* L 為一串數字*/ S2: 若L 的長度為2，則return 此二數字之和 S3: L1 = L 的前半部分 /* if L=1234, L1=12 */ S4: L2 = L 的後半部分 /* if L=1234, L2=34 */ S5: L3 =將L 分成四部分，第2 及第3 部分之組合/* if L=1234, L3=23 */ S6: return (P(L1)+P(L2)+P(L3)) 若L=87654321（長度為8），則最後return 之結果為何？（20 分）