基本練習題 1. 要將中序式轉成後序式, 需要用到何種資料結構? (A) 堆疊 (B) 佇列 (C) 堆積 (D) B 樹答 :(A) 2. 下列何者不是堆疊的應用場合?(A) 運算式轉換 (B) 工作排程 (C) 副程式的呼叫與返回 (D) 後序式的求值答 :(B) 3. 一個原來為空的堆疊, 經過 Push(1),Push(2),Pop(),Push(3),Pop(),Push(4) 則 堆疊中的資料由上而下順序是 (A)4321 (B)1234 (C)41 (D)14 答 :(C) 4. 許多行程共用 CPU 資源, 需要用到何種資料結構來協助排程 (scheduling)? (A) 堆疊 (B) 佇列 (C) 堆積 (D) B 樹 答 :(B) 5. 一個原來為空的佇列, 經過 Enqueue(1), Enqueue(2), Dequeue(), Enqueue(3), Dequeue(), Enqueue(4) 則佇列中的資料由前而後順序是 (A)4321 (B)1234 (C)43 (D)34 答 :(D) 6. 如果 A=5, B=6, C=2, D=3, E=2, F=9, G=3, 則後序式 A B C / D E * + F G / 答 :2 - 的值為何? 7. 完成 2 個及 3 個圓盤的河內塔遊戲, 分別需要幾次搬移?(A) 4,8 (B) 3,7 (C) 2,3 答 :(B) (D)3,4 8. 將下列中序式轉成後序式 A. A + ( B / C D ) * E F / G B. ( A + B ) * ( C D ) / E C. A + B * C ( E + F ) 答 : (A) A B C / D E * + F G / - (B) A B + C D - * E /
(C) A B C * + E F + - 9. 將第 8 題之中序式轉成前序式 答 : (A) - + A * - / BCDE / F G (B) / * + A B C D E (C) - + A * B C + E F 10. 將第 8(A) 題之中序式, 以運算子堆疊的方式轉成後序式, 記錄堆疊及後序 答 : 式變化的情況 A + ( B / C D ) * E F / G 處理之中序式句元 處理動作 運算子堆疊 1. 運算元 A 規則 2. 直接輸出至後序式 A 2. 運算子 + 規則 3. 必須使用堆疊 堆疊規則 3. Push + A 3. 運算子 ( 規則 3. 必須使用堆疊 ( 堆疊規則 3. 直接 Push + A 4. 運算元 B 規則 2. 直接輸出至後序式 ( + AB 規則 3. 必須使用堆疊 / 5. 運算子 / 堆疊規則 3. / 的優先序比 ( 大, 故 Push / ( + AB / 6. 運算元 C 規則 2. 直接輸出至後序式 ( + ABC 7. 運算子 - 規則 3. 必須使用堆疊 堆疊規則 3. 的優先序比 / 小, 故 Pop 得到 / 並輸出到後序式 接著 Push 8. 運算元 D 規則 2. 直接輸出至後序式 規則 3. 必須使用堆疊 9. 運算子 ) 堆疊規則 2. 一直 Pop, 直到遇見 (, 兩者一同抵銷 規則 3. 必須使用堆疊 10. 運算子 * 堆疊規則 3. * 的優先序比 + 大, 故 Push / 11. 運算元 E 規則 2. 直接輸出至後序式 - ( + - ( + ABC/ 後序式 ABC/D * + * + + ABC/D- ABC/D- ABC/D-E
規則 3. 必須使用堆疊 堆疊規則 3. 的優先序比 * 小, 故 Pop 得到 * 並輸 12. 運算子 - 出到後序式 的優先序不 - ABC/D-E*+ 比 + 大, 故 Pop 得到 + 並輸出到後序式 接著 Push 13. 運算元 F 規則 2. 直接輸出至後序式 - ABC/D-E*+F 14. 運算子 / 規則 3. 必須使用堆疊 堆疊規則 3. / 的優先序比 - 大, 故 Push / / - ABC/D-E*+F 15. 運算元 G 規則 2. 直接輸出至後序式 規則 4. 中序式已經讀完, 因此將堆疊中剩餘的運算子依序 Pop 到後序式 / ABC/D-E*+FG 進階練習題 1. 如果 A=5, B=6, C=2, D=3, E=2, F=9, G=3, 將基本練習題第 8 題的後序式, 答 : 以運算元堆疊求值 ABC/D-E*+FG/- ABC/D-E*+FG/- 處理句元處理動作運算元堆疊 1. 運算元 A 規則 2. 直接 Push A (=5) 2. 運算元 B 規則 2. 直接 Push 3. 運算元 C 規則 2. 直接 Push 3. 運算子 / 規則 3. 作兩次 Pop, 先 Pop 出來的 C 為第二運算元, 後 Pop 出來的 B 為第一運算元, 執行 B/C, 設為 X,Push(X) 4. 運算元 D 規則 2. 直接 Push 5. 運算子 - 規則 3. 作兩次 Pop, 先 Pop 出來的 D 為第二運算元, 後 Pop 出來的 X 為第一運算元, 執行 X-D, 設為 Y,Push(Y) 6. 運算元 E 規則 2. 直接 Push B (=6) A (=5) C (=2) B (=6) A (=5) X (=3) A (=5) D (=3) X (=3) A (=5) Y(=0) A (=5) E (=2) Y (=0) A (=5)
7. 運算子 * 8. 運算子 + 規則 3. 作兩次 Pop, 先 Pop 出來的 E 為第二運算元, 後 Pop 出來的 Y 為第一運算元, 執行 Y*E, 設為 Z,Push(Z) 規則 3. 作兩次 Pop, 先 Pop 出來的 Z 為第二運算元, 後 Pop 出來的 A 為第一運算元, 執行 A+Z, 設為 T,Push(T) 9. 運算元 F 規則 2. 直接 Push 10. 運算元 G 規則 2. 直接 Push 11. 運算子 / 11. 運算子 規則 3. 作兩次 Pop, 先 Pop 出來的 G 為第二運算元, 後 Pop 出來的 F 為第一運算元, 執行 F/G, 設為 W,Push(W) 規則 3. 作兩次 Pop, 先 Pop 出來的 W 為第二運算元, 後 Pop 出來的 T 為第一運算元, 執行 T W, 設為 Q,Push(Q) Z (=0) A (=5) T (=5) F (=9) T (=5) G (=3) F (=9) T (=5) W (=3) T (=5) Q(=2) 規則 4. 後序式已經讀完, 堆疊只剩一個元素, 即為結果 Q(=2) 2. 如果 MAX_ITEM=10, 請畫出環狀佇列變化的情形, 每個變化都必須標出 front 和 rear 的值 Enqueue(A), Enqueue(B), Enqueue(C), Dequeue(), Enqueue(D), Dequeue(), Dequeue(), Enqueue(E) 答 : [3] [4] [5] [3] [4] [5] [2] [6] [1] A [7] [0] [8] [9] (a) front = 0, rear = 1 [2] B [6] [1] A [7] [0] [9] [8] (b) front = 0, rear = 2
[2] [3] B C [4] [5] [6] [2] [3] B C [4] [5] [6] [1] A [7] [1] [7] [0] [9] [8] [0] [9] [8] (c) front = 0, rear = 3 (d) front = 1, rear = 3 [2] [3] B C [4] D [5] [6] [2] [3] C D [4] [5] [6] [1] [7] [1] [7] [0] [9] [8] [0] [9] [8] (e) front = 1, rear = 4 (f) front = 2, rear = 4 [2] [3] D [4] [5] [6] [2] [3] [4] D E [5] [6] [1] [7] [1] [7] [0] [9] [8] [0] [9] [8] (g) front = 3, rear = 4 (h) front = 3, rear = 5 程式題 1. 請寫出 4.2 節之 Top_Item 函式 答 :
int Top_Item(STACK *S, char *X) // peek the top item of stack S, if Stack is empty return FALSE if(is_empty(s)) return FALSE; *X = S->item[S->top]; return TRUE; 2. 請寫出一個完整程式, 重複接受鍵盤輸入 Push 及 Pop 根據輸入做堆疊的 Push 及 Pop, 最後將堆疊元素由下而上依序印出 答 : #include <stdio.h> #define MAX_ITEM 9 #define FALSE 0 #define TRUE 1 typedef struct tagstack int Item[MAX_ITEM]; /* 資料欄位 */ int Top; STACK; int IsFull(STACK *S) if (S->Top == (MAX_ITEM-1)) return TRUE; else return FALSE; int Push(STACK *S,int X) if(isfull(s)) return FALSE; S->Top=S->Top+1; S->Item[S->Top]=X; return TRUE; int IsEmpty(STACK *S) if(s->top == -1)
else return return TRUE; FALSE; int Pop(STACK *S,int *X) if(isempty(s)) return FALSE; *X=S->Item[S->Top]; S->Top--; return TRUE ; void PrintStack( STACK *S) int i; if ( IsEmpty(S) ) printf("\n 堆疊為空 \n"); return ; printf("\n 堆疊內容由上到下 : \n"); for (i=s->top;i >= 0;i--) printf("%d ",S->Item[i]); printf("\n"); void main(void) int choose,flagcontinue=true; int data; STACK S; S.Top=-1; while(flagcontinue==true) PrintStack(&S); printf("\n(1)push 資料 (2)POP 資料 (0) 結束 : "); scanf("%d",&choose); switch(choose) case 0: FlagContinue = FALSE; /* 結束程式 */
case 1: printf(" 請輸入欲 PUSH 之資料 =>"); scanf("\n%d",&data); if(push(&s,data) == FALSE) printf(" 堆疊已滿,PUSH 失敗 "); case 2: if(pop(&s,&data) == FALSE) printf(" 堆疊已空,POP 失敗 "); else printf("pop 出 : %d",data); default: printf(" 選項錯誤 "); 3. 請寫一完整程式符合下列條件 A. 能輸入中序式轉成後序式 B. 能將後序式加以運算求值 C. 運算子必須有 +, -, *, /, ^ ( 次方 ) 五種 答 : #include <stdio.h> #include <math.h> #define MAX_OP 6 #define operator(c) ((c=='+') (c=='-') (c=='*') (c=='/') (c=='^'))?1:0 #define operands(c) ((c)>='a' && (c)<='z')?1:0 #define MAX_ITEM 100 typedef struct stk int item [MAX_ITEM]; int top; STACK; STACK S; char op[max_op]='(','+','-','*','/', ^ ); char prio[max_op]=0,1,1,2,2,3;
char op_value[26]=10,30,6,9,8,11,12,13,7,8,22,56,77,76, 55,56,43,40,13,19,18,16,46,52,61,63; void in_to_post(); void push(); void pop(); int post_evaluate(); main() int i; char infix[max_item]; char postfix[max_item]; S.top=-1; printf(" 請輸入中序式, 例如 (a+b)*c-d/e :"); scanf("%s",infix); in_to_post(infix,postfix); printf(" 中序式 => %s \n 後序式 => %s",infix,postfix); printf("\n 若 =>"); for(i=0;i <26;i++) printf("%c=%d, ",(i+'a'),op_value[i]); printf("\n 上式之結果 = %d\n",post_evaluate(postfix)); void push(),pop(); int priority(); void in_to_post(char *infix,char *postfix) int i,j,,element; char token; i=j=0; while((token=infix[i])!= '\0') i=i+1; if(operands(token)) postfix [j++]=token; else if(token == '(') push(token); else if(token == ')') while (S.top >= 0) pop(&(int)element);
if(element == '(') postfix [j++]=element; else if(operator(token)) while(s.top >= 0) element=s.item[s.top]; if(priority(token) <= priority (element)) pop(&(int)element); postfix[j++]=element; else push(token); while(s.top >= 0) pop(& element); postfix[j++]=element; postfix[j]='\0'; void push(int x) if (S.top < MAX_ITEM-1) S.top++; S.item[S.top]=x; void pop(int *x) if (S.top >= 0) *x=s.item[s.top]; S.top--; int priority(int c)
int i=0; for(;i < MAX_OP;i++) if(op[i] == c) return(prio [i]); return(-1); int post_evaluate(char *postfix) char token; int evaluate(),op1,op2,result,i=0; while((token=postfix[i])!= '\0') i=i+1; if(operands(token)) push(op_value[token-'a']); else if(operator(token)) pop(&op2); pop(&op1); result=evaluate(token,op1,op2); push(result); pop (&result); return(result); int evaluate(char optr,int op1,int op2) int result; switch(optr) case '+':result=op1+op2; case '-':result=op1-op2; case '*':result=op1*op2; case '/':result=op1/op2;
case '^':result=pow(op1,op2); return(result); 4. 請寫非遞迴版的階層函式, 寫一完整程式呼叫並印出結果來驗證 答 : #include <stdio.h> #include <stdlib.h> long fact(int n) int i; long f=1; for (i=1; i<=n;i++) f = f * i; return(f); void main(void) int n; printf("please input a number less than or equal to 12 => "); scanf("%d",&n); /* 讀入數字 */ if(n > 12) /* 因大於 12 之階乘超出 long 所能表示之範圍 */ printf("the Answer is too large,overflow..."); exit(1); if(n < 0) /* 小於零之數不合法 */ printf("input error,number must > 0"); exit(1); printf("%d! = %ld\n",n,fact(n)); 5. 請寫一完整程式呼叫 hanoi 函式, 印出結果, 以便更加清楚其遞迴性 答 : #include<stdio.h> #include<stdlib.h>
void main(void) int n; void hanoi(); printf("please input number =>"); scanf("%d",&n); /* 讀入數字 */ if(n > 100) /* 因大於 24 之遞迴數列超出 unsigned int 所能表示之範圍 */ printf("the number n is too large,end"); exit(1); if(n < 0) /* 小於零之數不合法 */ printf("input error,number must > 0"); exit(1); hanoi(n,'a','b','c'); printf(" 結束 \n"); /* 把 n 個盤子, 從 form 柱, 經由 by 柱, 搬往 to 柱 */ void hanoi(int n, char from, char by, char to) if(n > 0) hanoi(n-1, from, to, by); printf("move no. %d disk from '%c' to '%c' \n",n, from, to); hanoi(n-1, by, from, to); 6. 請寫出鏈結佇列的 Enqueue 和 Dequeue 函式 答 : #include <stdio.h> #include <stdlib.h> #define FALSE 0 #define TRUE 1 typedef struct listnode int data; /* 資料欄位 */
struct listnode *next; NODE; typedef struct taglistqueue NODE *front,*rear; ListQueue; void PrintListQueue(ListQueue *LQ) NODE *p; for (p=lq->front; p!= NULL; p=p->next) printf("%d ",p->data); int Enqueue(ListQueue *LQ,int X) NODE *p; if((p=(node*)malloc(sizeof(node)))==null) return FALSE; p->data=x; p->next=null; if ( LQ->rear!= NULL ) LQ->rear->next=p; else LQ->front =p; LQ->rear = p; return TRUE; int Dequeue(ListQueue *LQ,int *X) NODE *p=lq->front; if(p ==NULL) return FALSE; *X = p->data; LQ->front=p->next; free(p); return TRUE;
void main(void) int choose; int data; ListQueue Q; Q.front=Q.rear=NULL; while(1) printf("\n 佇列內容由前到後 : \n"); PrintListQueue(&Q); printf("\n(1)enqueue 資料 (2)Dequeue 資料 (0) 結束 : "); scanf("%d",&choose); switch(choose) case 0: exit(0); /* 結束程式 */ case 1: printf(" 請輸入欲 Enqueue 之資料 =>"); scanf("\n%d",&data); if(enqueue(&q,data) == FALSE) printf(" 記憶體配置不成功,Enqueue 失敗 "); case 2: if(dequeue(&q,&data) == FALSE) printf(" 佇列已空,Dequeue 失敗 "); else printf("dequeue 出 : %d",data); default: printf(" 選項錯誤 "); 7. 請寫非遞迴版的 Fibonacci 函式, 並寫一完整程式呼叫該函式印出結果來驗證 答 : #include<stdio.h> #include<stdlib.h> unsigned int Fib (int n)
int i,fn,fn_1,fn_2; if (n==0) return 0; if (n==1) return 1; Fn_1=1; Fn_2=0; for(i=2; i<=n; i++) Fn = Fn_1 + Fn_2; Fn_2 = Fn_1; Fn_1 = Fn; return Fn; void main(void) int n; printf("please input number =>"); scanf("%d",&n); /* 讀入數字 */ if(n > 46) //* 因大於 46 之數列超出 unsigned int 所能表示之範圍 printf("the answer will be too large,end"); exit(1); if(n < 0) //* 小於零之數不合法 printf("input error,number must > 0"); exit(1); printf("fib(%d) = %d\n",n,fib(n)); 8. 另一個有名的遞迴定義是艾克曼函式 ( Ackerman s function) 定義是 : n+1, 若 m = 0 Ackerman(m,n) = Ackerman(m-1,1), 若 n = 0 Ackerman(m-1, Ackerman(m,n-1)), 其他 當 m 和 n 均不為 0 時,A(m,n) 可由 A(m,n-1) 而來 ( 至少 n 少 1 了 ) 而 n 為 0 時,A(m,0) 變為 A(m-1,1), 一直到 m 為 0 時,A(0,n) 便有了確定值 n+1 請實作 Ackerman s function( 只要將數學定義直接翻譯成 C/C++ 語言即可,
即使沒有完全弄清楚這複雜的定義 ) 答 : int Ackerman( int m, int n) int i; if ( m == 0 ) return ( n+1 ); if ( n == 0 ) return ( Ackerman(m-1, 1) ) ; i = Ackerman( m, n-1 ); return ( Ackerman(m-1, i ) ) ;