[開課學院]:資電學院 (ex:金融學院,商學院,理工學院,資電學院,建設學院,文學院...) [開課系所]:資訊 (ex:中文系,外文系,電機系,財稅系..) [課程名稱]:資料結構 [老師名稱]:戴嬋玲 老師 [開課學期]:971 [類型]:97-1期中考 ex:(第n次)小考/98-2期中考/98-2期末考 1. 以下的 java 函數 int zero_count(int a[])計算陣列 a 中的 0 有多少個。請採用 表列方式，以 N 的函數寫出下列程式片段的步驟計數值(step count)，並以 Big-O notation 寫出其時間複雜度。 (15%) (Big O 定義如下：若且為若 f(n) = O(g(n))，則存在大於0的常數 c 與 n0，使得對 所有的 n值， n >= n0 時，f(n) <= cg(n)均成立。) static int zero_count(int a[]) { int count = 0; for (int i=0 ; i < a.length ; i++) /*a.length表示陣列的資料個數 N*/ { if (a[i] == 0) count = count + 1; } return count; } 2. 證明 2+4+8...+2^N = O(2^N) (10%) 3. A為二維的陣列(array)，A[4][2]的位址為1978，A[2][3]的位址為1986，假設每一個 元素佔兩個的 bytes，則 A 的列數(row)是多少？ (10%) 提示：請先判斷陣列是以列序或行序儲存。 4. 以陣列定義 stack 的結構如下： (20%) #define MAX_STACK_SIZE 10 typedef struct{ int key; }element; element stack[MAX_DEQUE_SIZE] (a) 寫出堆疊的 add_stack. 函數 (b) 寫出堆疊的 stack_full 函數 5. 設運算元均為單一字元或數字，運算符號有~,+,-,x,/,(,)，其中~代表負號。關於中 序(intfix)運算式轉換成後序(postfix)： (25%) (a) 定義上述運算符號的 ICP(in_coming precedence) 和 ISP(in_stack precedence )。 (b) 規定轉換過程中若遇到 precedence相同的符號，則先將堆疊中的符號取出。寫出 下列運算式的後序表示法，必須同時寫出轉換過程用的 STACK 之內容： i. a+bxc/(d/(e-f)+3) ii. (~b+(bx~4xaxc)*(1/2))/(2xa) 6. 陣列(array)與鏈結串列(linked list)結構均可視為有序串列(ordered list)，請就 存取資料及記憶體配置兩方面說明它們有何差異？ (10%) 7. 若五個字元A,B,C,D,E依序輸入，利用堆疊來重排其順序時，寫出不可能產生的順序。 (10%) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.134.237.201 ※ 編輯: MOTG 來自: 140.134.237.201 (03/14 16:33)