試題一：
閱讀下列說明和C函數(shù)代碼，將應(yīng)填入  (n)  處的字句寫在的對應(yīng)欄內(nèi)。
[說明]
對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個節(jié)點，且每個節(jié)點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。
設(shè)二叉樹采用二叉鏈表存儲，節(jié)點類型定義如下：
typedef struct BtNode{
ElemType data；    /*節(jié)點的數(shù)據(jù)域，ElemType的具體定義省略*/
struct BtNode * lchild * rchild；  /*節(jié)點的左、右孩子指針域*/
}BtNode，*BTree；
在函數(shù)InOrder()中，用棧暫存二叉樹中各個節(jié)點的指針，并將棧表示為不含頭節(jié)點的單向鏈表(簡稱鏈棧)，其節(jié)點類型定義如下：
typedef struct StNode{    /*鏈棧的節(jié)點類型*/
BTree elem；          /*棧中的元素是指向二叉鏈表節(jié)點的指針*/
struct StNode*link；
}StNode；
假設(shè)從棧頂?shù)綏５椎脑貫閑n、en-1…、e1，則不含頭節(jié)點的鏈棧示意圖如圖5-1所示。

[C函數(shù)]
int  InOrder(BTree root)        /*實現(xiàn)二叉樹的非遞歸中序遍歷*/
{
BTree ptr；                 /*ptr用于指向二叉樹中的節(jié)點*/
StNode*q；                  /*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點指針*/
StNode*stacktop=NULL；      /*初始化空棧的棧頂指針stacktop*/
Ptr=root；                  /*ptr指向二叉樹的根節(jié)點*/
while (  (1)  | | stacktop !=NULL) {
while (ptr!=NULL)  {
q=(StNode*)malloc(sizeof (StNode))；
if  (q= =NULL)
return-1；
q-＞elem=ptr；
(2)  ；
stacktop=q；            /*stacktop指向新的棧頂*/
ptr=  (3)  ；    /*進入左子樹*/
}
q=stacktop；
(4)  ；        /*棧頂元素出棧*/
visit(q)；              /*visit是訪問節(jié)點的函數(shù)，其具體定義省略*/
ptr=  (5)  ；    /*進入右子樹*/
free(q)；               /*釋放原棧頂元素的節(jié)點空間*/
}
return 0；
}/*Inorder*/

查看答案

試題二：

閱讀下列說明和Java代碼，回答下列問題。

[說明]

某咖啡店賣咖啡時，可以根據(jù)顧客的要求在其中加入各種配料，咖啡店會根據(jù)所加入的配料來計算費用。咖啡店所供應(yīng)的咖啡及配料的種類和價格如表2-9所示。

表2-9 咖啡及配件的種類和價格

現(xiàn)采用裝飾器(Decorator)模式來實現(xiàn)計算費用的功能，得到如圖2-15所示的類圖。

[Java代碼]

import java.util.*:

______ class Beverage {               //飲料

String description = "Unknown Beverage";

public ______ () {  return description;  }

public ______;

}

abstract class CondimentDecorator extends Beverage {        //配料

______;}

class Espresso extends Beverage {           //蒸餾咖啡

private final int ESPRESSO_PRICE = 25;

public Espresso()  {    description="Espresso";  }

public int cost()  {    return ESPRESSO_PRICE;   }

}

class DarkRoast extends Beverage {               //深度烘培咖啡

private finalint DARKROAST_PRICE = 20;

public DarkRoast() { description = "DarkRoast";  }

public int cost() { return DARKROAST PRICE;  }

}

class Mocha extends CondimentDecorator {        //摩卡

private final int MOCHA_PRICE = 10;

public Mocha (Beverage beverage) { this.beverage = beverage; }

public String getDescription() { returnbeverage.getDescription0 +",Mocha"; }

public int cost() {  return MOCHA_PRICE + beverage.cost();  }

}

class Whip extends CondimentDecorator  {     //奶泡

private finalint WHIP_PRICE = 8;

public Whip(Beverage beverage) {  this.beverage = beverage;  }

public  String getDescription() {  returnbeverage.getDescription() +", Whip";  }

public int cost() {  return WHIP_PRICE + beverage.cost();  }

}

public class Coffee {public static void main(String args[])  {

Beverage beverage = new DarkRoast(); beverage=new Mocha(______);

beverage = new Whip (______);

System.out.println(beverage.getDescription() +"￥"+beverage.cost());

}

}

編譯運行上述程序，其輸出結(jié)果為：DarkRoast，Mocha，Whip ￥38

查看答案