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

在程式語言中有所謂的早期繫結（early binding）和晚期繫結（late binding）， 請詳述這兩個繫結的差異性和使用時機點，並以C++程式語言說明如何達 成晚期繫結的功能。（20 分）

函式之間的呼叫，其參數的傳送可分為那幾種？請詳述之；並以任何一種 程式語言撰寫兩個整數對調的情形，並加以說明最後處理的結果。需註明 使用的程式語言。（20 分）

程式語言中有一重要的主題是指標（pointer）。何謂指標？其功用為何？ int a = 100；並詳述⑴int *ptr = &a；⑵int *fn(int a)；⑶int(*fn)(int a)； ⑷int *arr[3]；⑸int(*arr)[3]。（30 分）

程式語言中有一重要的主題是指標和參考（reference），它們當用來撰寫 鏈結串列或樹狀結構的問題。我們將它用來處理鏈結串列，假設有一單向 鏈結串列（singly linked list）之節點中有三個項目，分別是id（整數型態）、 score（浮點數型態）以及next（指標或參考型態），如下圖所示： id score next 今有一節點名為ptr，試分別撰寫將此ptr 節點加入於已含有多個節點的單 向鏈結串列之尾端，以及刪除鏈結串列尾端節點的片段程式。可以任何程 式語言撰寫之，但請註明使用的程式語言。（30 分）

9 10 11 12 13 14 15 值 + * / ㈢請根據右下圖完成下面C 程式實作(I)~(V)之鏈結串列的表示，其中 btree 為指向一個二元樹的指標變數。（5 分） (I) node { (II) ; (III) ; (IV) ; } treeNode_t; typedef (V) tree_t; tree_t btree; btree data left right data left right data left right 三、給定正整數二維陣列，起點為其中數值最大的點。從起點開始移動，求 經過點的數值之加總。移動規則：⑴從相鄰的點（上、下、左、右）選 擇一個最大的值移動；⑵走過的點不能重複。 ㈠請完成遞迴程式與非遞迴程式（I~XI）空格，使以下C 程式均能執行 出下列結果。（22 分） path= 88, 42, 31, 18, 23, 21, 68, 36, 55, 77, 66, 63, 28, 33, 52, sum=701 ㈡請比較遞迴與非遞迴程式記憶體空間使用狀況。（3 分） #include <stdio.h> #define maxN 30 const int NV = -1; int max(int x, int y){int r = x>y？(I) ; return r;} int findR(int m[maxN][maxN], int x, int y, int sum){ int mi = max(max(m[x+1][y],m[x-1][y]),max(m[x][y+1],m[x][y-1])); sum += m[x][y]; printf("%d, ", m[x][y]); m[x][y] = NV; if (mi == NV) return (II) ; if (m[x+1][y] == mi) return findR(m, (III) , sum); if (m[x-1][y] == mi) return findR(m, (IV) , sum); if (m[x][y+1] == mi) return findR(m, (V) , sum); if (m[x][y-1] == mi) return findR(m, (VI) , sum); } int findI(int m[maxN][maxN], int x, int y, int sum){ while(1){ int mi = max(max(m[x+1][y],m[x-1][y]),max(m[x][y+1],m[x][y-1])); sum += m[x][y]; printf("%d, ", m[x][y]); m[x][y] = NV; if (mi == NV) (VII) ; else if (m[x+1][y] == mi) (VIII) ; else if (m[x-1][y] == mi) (IX) ; else if (m[x][y+1] == mi) (X) ; else (XI) ; } return sum; } int main(){ int x=0, y=0, mi=NV, n=5, m=6; int map[maxN][maxN]={{NV, NV, NV, NV, NV, NV, NV}, {NV, 11, 15, 23, 18, 31, NV}, {NV, 31, 68, 21, 88, 42, NV}, {NV, 19, 36, 52, 33, 28, NV}, {NV, 12, 55, 77, 66, 63, NV}, {NV, NV, NV, NV, NV, NV, NV}}; // 邊界都是NV for (int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= m ; j++){ if (mi < map[i][j]){ mi = map[i][j]; x=i; y=j; } } } printf("path= "); printf("sum=%d\n",findR(map, x, y, 0)); return 0; } 四、敘述統計學上中位數和平均數均為數據資料的集中趨勢，中位數是將一 組數值資料由小到大排列，最中間的數值為中位數。若有奇數個資料， 則取最中間的數值為中位數，例如1, 2, 3, 3, 4, 6, 7, 7, 21 的中位數是4； 若有偶數個資料，則取最中間兩個數值的平均為中位數，例如1, 2, 3, 3, 4, 6, 7, 7, 8, 21 的中位數是（4+6）/2=5。算術平均數是將一組數值加總， 除以這組數值的個數，例如1, 2, 3, 3, 4, 6, 7, 7, 21 的算術平均數=54/9=6。 以下C++程式輸出：4, 6, 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <iostream> #include <algorithm> using namespace std; class Compute{ public: void setData(int *, int); (I) =0; protected: int *data, d_size; }; class ComputeMedian: public Compute{ public: double getNum(); }; class ComputeMean: public Compute{ public: double getNum(); }; void Compute::setData(int *d, int s){ data = d; d_size = s; sort(data, data+d_size); } double ComputeMedian::getNum(){ if ( (II) ==1) return data[d_size/2]; else return (data[ (III) ]+data[1+d_size/2])/2.0; } double ComputeMean::getNum(){ double sum=0, avg=0; for (int i=0; i<d_size; i++) sum = sum + data[i]; return ( (IV) ); } class Report { public: Report(int *d, int s){ data = d; d_size = s; } void setCompute(Compute *c) { cp = c; } void report(){ cp-> (V) ; cout<<cp->getNum()<<", "; } private: int *data, d_size; Compute *cp; }; int main(){ int data[10] ={6, 7, 1, 21, 2, 3, 4, 3, 7}; Report r(data, 9); Compute *cp1 = new ComputeMedian(); Compute *cp2 = new ComputeMean(); r.setCompute(cp1); r.report(); r.setCompute(cp2); r.report(); return 0; } ㈠請完成程式碼（I~V）使程式正常運作。（15 分） ㈡請根據程式碼完成下面UML 類別圖的關係連線，並說明此設計對模 組耦合性（Coupling）的影響。（10 分） {abstract} Compute -data -d_size +setData() +getNum(){abstract} ComputeMean +getNum() ComputeMedian +getNum() Report -data -d_size +setCompute() +report()