1考虑如图所示的铁道交换网路在图右边为编号1

1考虑如图所示的铁道交换网路在图右边为编号1 1.考慮如圖所示的鐵道交換網路。在圖右邊為編號1,……,n的火車廂。每一車廂被拖入堆疊,並可在任何時候將它拖出。舉例而言,如果n=3,我們可以拖入1,拖入2,拖入3,而後再將車廂拖出,產生新的車廂順序3,2,1。 (1).假如n=3,可以得到的車廂編號的可能排列為何, (2).假如n=6,有沒有可能達到325641的車廂編號排列,或者154236,或者154623, ch04-3 解答: (1).當n=3時,可能的排列有五種:123,132, 213,231,321。不可能的排列有一種,即是312。 (2).同樣依據堆疊先進後出的原則,所以325641的車廂順序是可以達到的。至於154236的編號順序,在輸入154之後則無法繼續輸出。而對於154623,在輸出1546後,則無法繼續輸出2。 2.何謂「堆疊機」(Stack Machine), 解答: 是一種採用空位址(zero-address)指令,與增加(push)和刪除(pop)兩種運算指令的計算機。 3.有一個空堆疊,假設PUSH(x)指令會將資料放入堆疊,POP(x)指令會將資料輸出。假設有ABCDE五筆資料以PUSH放入堆置,並執行某些POP指令,下列何者為不可能的輸出,(A)ABCDE(B)EDCBA(C)EABCD(D)ABDEC 1 解答:C 4.請說明在遞迴應用中,所謂Divide and Conquer(切割征服)的意義。 解答:是一種遞迴的應用,例如二分搜尋、合併排序(Mergesort)都是運用Divide and Conquer的方法。也就是將問題分成許多小問題,再將問題逐步分成兩部份,如此遞迴進行,直到小到可以解決問題為主。最後再將結果利用遞迴兩兩合併直到完成。 5.一個遞迴式A定義如下: n+1 if m=0 A(m,n)= A(m-1,1) if n=0 A(m-1,A(m,n-1)) ofherwise 請問A(1,2)與A(2,1)的值為何, 解答:4,5。 6. 試述「尾歸遞迴」 (Tail Recursion)的意義。 解答:所謂「尾歸遞迴」 (Tail Recursion)就是程式的最後一個指令為遞迴呼叫,因為每次呼叫後,再回到前一次呼叫的第一行指令就是return,所以不需要再進行任何計算工作,因此也不必保存原來的環境資訊(如參數儲存、控制權轉移)。例如N!的遞迴式。 7.假設一佇列(Queue)儲存於全長為N之密集串列(Dense List)Q內,HEAD、TAIL 分別為其開始及結尾指標,均以ni1其為空。現欲加入一新資料(New Entry),處理可分為以下步驟,請依序回答空格部分。 (a) 依序按條件填入下列的空格: 1. 若(1),則表Q已存滿,無法做插入動作。 2. 若HEAD為nil,則表Q內為空,可取HEAD=1,TAIL=(2)。 2 3. 若TAIL=N,則表(3)須將Q內由HEAD 到TAIL位置之資 料,移至到(4)之位置,並取TAIL=(5),HEAD=1。 (b)TAIL=TAIL+1。 (c)new entry移入Q內之TAIL處。 (d)結束插入動作。 解答:(a)TAIL-HEAD+1=N (b)0 (c)已到密集串列最右邊,無法加入(d)TAIL-HEAD+1 (e)N-HEAD+1 8.佇列除了能以陣列的方式來實作外,試以C++鏈結串列來實作佇列的加入與刪除節點演算法。 解答: ?加入節點演算法 01 void enqueue(int value) { 02 QueueByLinkedList node; //建立節點 03 node=(QueueByLinkedList)malloc(sizeof(QueueNode)); 04 node->data=value; 05 node->next=NULL; 06 //檢查是否為空佇列 07 if (rear==NULL) 08 front=node; //新建立的節點成為第1個節點 09 else 10 rear->next=node; //將節點加入到佇列的尾端 11 rear=node; //將佇列的尾端指標指向新加入的節點 12 } 13 //方法dequeue:佇列資料的取出 ?刪除節點演算法 01 nt dequeue() 02 { 03 int value; 04 //檢查佇列是否為空佇列 05 if (!(front==NULL)) 06 { 07 if(front==rear) rear=NULL; 08 value=front->data; //將佇列資料取出 09 front=front->next; //將佇列的前端指標指向下一個 10 return value; 11 } 12 else return -1; 13 } 3 9.請將下列中序算術式轉換為前序與後序表示式。 (a)(A+B)*D+E/(F+A*D)+C (b)A?B?C (C)A?-B+C 解答: (a) pj-03 前序式:++*+ABD/E+F*ADC pj-04 後序式:AB+D*EFAD*+/+C+ (b) pj-05 前序式: ?A?BC pj-06 後序式:ABC?? (C) pj-07 前序式:+ ?A-BC pj-08 後序式:AB-?C+ 10.請將A-B*(C+D)/E以前序法及後序法表示。 解答:-A/*B+CDE(前序),ABCD+*E/-(後序) 4 11.請將下列中序式,改成前序式與後序式。 (a) A**B**C (b) A**B-B+C (c) (A&B)orCor『(E>F) 解答: (a) **A**BC(前序)、ABC****(後序) (b) +**A-BC(前序)、AB-**C+(後序) (c) oror&ABC『>EF(前序)、AB&CorEF>『or(後序) 12.以下哪一個算術式不符合前序表示法的語法規則?(A)+++ab*cde(B)-+ab+cd*e (C)+a*-+bcde(D)+-**abcde 解答:各位可以利用括號轉換法逐一檢查,如果能順利轉換成中序式,就表示這個前序式符合語法規則。我們可以發現(B)並不符合,正確表示法應為*-+ab+cd 才符合前序式的規則。 13.請問後序式abc-d+/ea-*c*的值為何?(a=2、b=3、c=4、d=5、e=6) 解答:8(轉為後序式後,再帶入相關值即可) 14.將下面的中序法轉成前序與後序算術式::以下皆用堆疊法: A/B?C+D*E-A*C 解答: 中序轉前序 讀入字元 堆疊內容 輸出 C Empty C * * C 5 A * AC - - *AC E - E*AC * *- E*AC D *- DE*AC + +- * DE*AC(不要pop, 號,請注意) C +- C* DE*AC C* DE*AC , ?+- B B C* DE*AC ?+- / /+- , B C* DE*AC A /+- A, B C* DE*AC None Empty -+/ A, B C* DE*AC 中序轉後序 讀入字元 堆疊內容 輸出 None Empty None A Empty A / / A B / AB AB , ?/ C ABC ?/ + + ABC?/ D + ABC?/D * *+ ABC?/D E *+ ABC?/DE - - ABC?/DE*+ A - ABC?/DE*+A * *- ABC?/DE*+A C *- ABC?/DE*+AC None ABC?/DE*+AC* 15.請設計一中序式轉後序式的C++程式。 解答: 01 /* 02 [名稱]:ex04_01.cpp 03 [示範]:將數學式子由中序表示法轉為後序表示法 04 */ 05 #include 06 #include 6 07 #include 08 using namespace std; 09 #define MAX 50 10 char infix_q[MAX]; //用來存放中序表示法的佇列 11 //運算子優先權的比較,若輸入運算子小於堆疊中運算子 12 //,則傳回值為1,否則為0 13 int compare(char stack_o, char infix_o) 14 { 15 //在中序表示法佇列及暫存堆疊中,運算子的優先順序表, 16 //其優先權值為INDEX/2 17 char infix_priority[9] ; 18 char stack_priority[8] ; 19 int index_s=0, index_i=0; 20 infix_priority[0]='q';infix_priority[1]=')'; 21 infix_priority[2]='+';infix_priority[3]='-'; 22 infix_priority[4]='*';infix_priority[5]='/'; 23 infix_priority[6]='^';infix_priority[7]=' '; 24 infix_priority[8]='('; 25 stack_priority[0]='q';stack_priority[1]='('; 26 stack_priority[2]='+';stack_priority[3]='-'; 27 stack_priority[4]='*';stack_priority[5]='/'; 28 stack_priority[6]='^';stack_priority[7]=' '; 29 while (stack_priority[index_s] != stack_o) 30 index_s++; 31 while (infix_priority[index_i] != infix_o) 32 index_i++; 33 return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0); 34 } 35 //中序轉前序的方法 36 void infix_to_postfix() 37 { 38 int rear=0, top=0, flag=0,i=0; 39 char stack_t[MAX]; 40 for (i=0; iD)) or C