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

有一函式如下，試問其平均時間複雜度為何？（25 分） Function A(n) { int a = 0; int b = 0; for (int i = 0; i < n; i++) { a++; } printf("Hello"); for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { b++; } } printf("World"); }

請寫一個Python 語言函式（function），reverse_sentence（s），回傳所傳 送進去的字串，逐字翻轉（reverse）結果。例如reverse_sentence（“abc def”） 回傳“def abc”。（20 分）

閱讀以下Java 程式，列出數學式以說明變數e 在計算什麼？接著撰寫 遞迴（recursive）程式public static double etx（int accuracy, int x） 來計算前述變數e 的值，撰寫時必須使用etx 規定的參數與資料型 態。（25 分） import java.util.Scanner; public class EtoX { public static void main( String[] args ) { Scanner input = new Scanner( System.in ); int number = 1; int accuracy; int factorial = 1; int x; double e = 1.0; double exponent = 1.0; x = input.nextInt(); accuracy = input.nextInt(); while ( number < accuracy ) { exponent *= x; factorial *= number; e += exponent / factorial; number++; } // end while loop System.out.printf( "x: %d%ne: %f%n", x, e ); } // end main } // end class EtoX

請指出下列程式碼不合理之處。（25 分） #include<stdio.h> #include<stdlib.h> int main() { int s ,t; scanf("%d%d", &s,&t); while (s < 30) { if (s < 100 || s >50) { t++; } else if (s > 60 && s<-1) { t++; } else if (s > 10 && s < 100) { t--; } else t++; } system("pause"); return 0; }

根據下列之C 語言程式，回答下列問題。（每小題5 分，共15 分） 若參數的傳遞方式是傳值（pass by value），程式執行所輸出數字為何？ 若參數的傳遞方式是傳參考（pass by reference），程式執行所輸出數字 為何？ 若參數的傳遞方式是傳值與結果（pass by value-result），程式執行所輸 出數字為何？ void add (int x, int y) { x += x; y += y; } void main() { int a[2] = {1, 3}; add (a[0], a[1]); printf (“%d %d\n”, a[0], a[1]); }

下列為資料結構List 的Java 程式，而ListTest 為測試類別（class）， 試回答以下問題：（35 分） ⑴ListTest 中”List<Integer> list = new List<>();”會先後呼叫那些 methods？傳送那些參數值？結果新物件list 的屬性值為何？ ⑵執行ListTest.java 後會列印出什麼？ ⑶撰寫public T removeFromBack() throws EmptyListException。 class ListNode<T> { T data; ListNode<T> nextNode; ListNode(T object) { this(object, null); } ListNode(T object, ListNode<T> node) { data = object; nextNode = node; } T getData() ListNode<T> getNext() } // end class ListNode<T> public class List<T> { private ListNode<T> firstNode; private ListNode<T> lastNode; private String name; public List() { this("list"); } public List(String listName) { name = listName; firstNode = lastNode = null; } public void insertAtFront(T insertItem) public void insertAtBack(T insertItem) public T removeFromFront() throws EmptyListException public T removeFromBack() throws EmptyListException public boolean isEmpty() public void print() { if (isEmpty()) { System.out.printf("Empty %s%n", name); return; } System.out.printf("The %s is: ", name); ListNode<T> current = firstNode; while (current != null) { System.out.printf("%s ", current.data); current = current.nextNode; } System.out.println(); } } // end class List<T> public class EmptyListException extends RuntimeException { public EmptyListException() { this("List"); } public EmptyListException(String name) { super(name + " is empty"); } } // end class EmptyListException public class ListTest { public static void main(String[] args) { List<Integer> list = new List<>(); try { list.insertAtFront(-1); list.insertAtFront(99); list.print(); int removedItem = list.removeFromFront(); removedItem = list.removeFromFront(); list.print(); removedItem = list.removeFromFront(); list.print(); } catch (EmptyListException emptyListException) { emptyListException.printStackTrace(); } } } // end class ListTest

試問下列程式碼的輸出為何？（25 分） #include <iostream> using namespace std; class A { public: int testa; A() :testa(100) { } virtual void f() { cout << "apple" << endl; } void g() { cout << "banana" << endl; } }; class B : public A { public: B() :testb(300) {} void f() { cout << "cat" << endl; } void g() { cout << "dog" << endl; } int testb; }; int main() { B b; A *a = &b; a->g(); a->f(); cout << a->testa << endl; cout << b.testb << endl; system("pause"); return 0; }

定義一個由以下符號所組成的運算式。 二元運算子： *, +, ->, <-> 一元運算子：～ 變數：X, Y, Z 括號：(, ) 運算子的優先順序（precedence）依序為～,{*, +}, {->, <->}， 運算都是由左至右（left-associative），括號必須左右對稱且先左後右。 合法的運算式有如：X, Y, ~Y+~X,(Y*X<->Z*X), ~~Y 或 (~(X))->(Z)。而不合法的運算式則如：X~, Z->YZY 或*X)Y+Z(。 請完成以下BNF grammar，用以產生所有合法的運算式，但不會產生 不合法的運算式。（15 分） <var> ::= X | Y | Z <factor> ::= ? | ? | ? <term> ::= ? | ? | ? <exp> ::= ? | ? | ? 請畫出Y*X->Z 的剖析樹（parse tree）。（5 分）

下列程式Stack<T>繼承上題的List<T>。試撰寫Stack 中的建構子Stack ()，以及兩個主要methods: push(…)與pop()。（25 分） public class Stack<T> extends List<T> { public Stack() public void push(T object) public T pop() throws EmptyListException } // end class StackInheritance

試問下列程式碼的輸出為何？（25 分） #include<stdio.h> #include<stdlib.h> int main() { int i, k1 = 0, k2 = 0, k3 = 0; char a[] = "aA123bd45YH*#*"; for (i = 0; a[i] != '\0'; i++) if ((a[i] >= 'a' && a[i] <= 'z') || (a[i] >= 'A' && a[i] <= 'Z')) k1++; else if ((a[i] >= '0') && (a[i] <= '9')) k2++; else k3++; printf("%d,%d,%d\n", k1, k2, k3); system("pause"); return 0; }

下列為資料庫中STAFF 資料表，包含ID, DEPT, EXAM1, EXAM2, LEVEL 等5 欄位，請依序寫出指定的SQL 指令。（每小題5 分，共20 分） ID DEPT EXAM1 EXAM2 LEVEL A3452 E_Car 45 72 3 A4152 A_Boat 45 54 2 A2451 E_Car 51 89 4 . . . 寫出「列出所有DEPT（不可重複）」的SQL 指令。 寫出「列出ID, DEPT, LEVEL，但要按照ID 字母順序排序」的SQL 指令。 寫出「列出EXAM1 成績由高至低人員的ID 及EXAM1 成績，同分時 EXAM2 成績較高者優先列出」的SQL 指令。 寫出「能依DEPT 順序，將該DEPT 所有人員的DEPT, ID, EXAM1, EXAM2 資料列出」的SQL 指令。

下列Python 程式的執行結果為何？（15 分） class Shape: def __init__(self, x, y): self.x = x self.y = y self.description = "unknown" def area(self): return self.x * self.y def perimeter(self): return 2 * self.x + 2 * self.y def describe(self, text): self.description = text class Square(Shape): def __init__(self, x): self.x = x self.y = x class DoubleSquare(Square): def __init__(self, y): self.x = 2 * y self.y = y def perimeter(self): return 2 * self.x + 3 * self.y rectangle = Shape(100, 45) print(rectangle.perimeter()) dictionary = {} dictionary["DoubleSquare"] = DoubleSquare(5) dictionary["Rectangle"] = Shape(600,45) dictionary["Square"] = Square(20) print(dictionary["Square"].area()) dictionary["DoubleSquare"].describe("Double square") print(dictionary["Rectangle"].description)

下列問題請用Scheme/Lisp 程式語言來回答。 請只用cons 函式來建出s-expression (A (B) C)。（5 分） 請只用list 函式來建出s-expression (A (B) C)。（5 分） 給定x 為變數且已執行(setf x ‘(A (B) C))，請只用car 及cdr 函式來 從x 中取得B。（5 分） 請寫一個遞迴函式sumall 用以加總一個串列（list）中所有數字。例如 （sumall nil）回傳0，（sumall ‘(100)）回傳100，（sumall ‘(1 2 3 4 5)） 回傳15。（10 分）