一些資料結構問題

1. 河內塔結構中,當有 n 個套環需要移動時,請說明,需要移動的次數為何,並且以 n=3 為例子說明之。

2. 請利用括弧法,將下列中序算術式轉換為前序與後序表示式,並繪圖表示之。 (A+B)*D+E/(F+A*D)+C

3. 考慮環狀佇列的 front 與 rear 標示位置,請說明何者為滿溢狀況,何者空佇列,並請說明原因。

1 Answer

Rating
  • Favorite Answer

    第一題請參閱

    http://tw.knowledge.yahoo.com/question/question?qi...

    第二題步驟如下,針對Postfix(後序)依各運算子權限大小的執行順序括出,各運算子取代離自己最近的右括弧,而左括弧消除;針對Prefix(前序)則也是一樣,差別在於各運算子取代離自己最近的左括弧,而右括弧消除。

    圖片參考:http://imgcld.yimg.com/8/n/AC00866445/o/1511110500...

    所以對於Prefix的流程就不附上了,只付解答,請自行練習。 第三題可實做環狀佇列,且有Front與Rear指標的資料結構如下…利用Circular Array,且格數只用n-1格。利用Circular Array,且格數只用n格。分述如下…注意,以下為演算法。 Circular Array(使用n-1格)

    圖片參考:http://www.programacion.com/cursos_descargas/jap_d...

    ADDQ(Q, item){ Rear = (Rear+1)%n; if(Rear==Front) then "Q is full" (內定有個Rear減一) else Q[Rear] = item;} DeletQ(Q){ if(Front==Rear) then "Q is empty" else{ Front = (Front+1)%n; item = Q[Front]; return item;}}分析:因為front格不用,所以只用了n-1格,若真用了此格,則會造成當rear==front成立時,無法區分出Queue空或Queue滿情況。

    Circular Array(使用n格)請參上圖。新增一個Tag of Boolean: true if queue is full; false, otherwise.ADDQ(Q, item){if((Rear==Front) and (Tag==true)) then "Q is full"else{ Rear = (Rear+1)%n; Q[Rear] = item; if(Rear==Front) then Tag = true; }} DeletQ(Q){ if((Front==Rear) and (Tag==false)) then "Q is empty" else{ Front = (Front+1)%n; item = Q[Front]; if(Front==Rear) then Tag = false; return item;}}分析:當中皆多了一條針對Tag是否要改變的額外if測試敘述,故Time會比前例久一點,但此法使空間得以充分利用。

    2011-11-05 15:34:34 補充:

    補充第一題次數,主要程式碼如下

    hanoi ( num-1 , a , c , b );//從a移動n-1盤到b

    printf("%d %c -> %c \n" , num,a, c );//移動一盤子到c

    hanoi ( num-1 , b , a , c);//從b移動n-1盤到c

    如此可推出時間函式為: T(n) = T(n-1)+1+T(n-1) = 2T(n-1)+1,其中,T(1) = 1

    利用展開代入法(請自行google)解出 T(n) = 2^n-1

    若將盤數n=3代入,符合T(3) = 2^3-1 = 7

    故盤數3從a移到c所需次數為7次

    Source(s): 請高抬貴手別刪除,感謝~有問題再提問
Still have questions? Get your answers by asking now.