→ MOTG :最後一題寫出3個 03/14 16:34
[開課學院]:資電學院 (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)