试题一：
阅读下列说明和C函数代码，将应填入  (n)  处的字句写在的对应栏内。
[说明]
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储，节点类型定义如下：
typedef struct BtNode{
ElemType data；    /*节点的数据域，ElemType的具体定义省略*/
struct BtNode * lchild * rchild；  /*节点的左、右孩子指针域*/
}BtNode，*BTree；
在函数InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类型定义如下：
typedef struct StNode{    /*链栈的节点类型*/
BTree elem；          /*栈中的元素是指向二叉链表节点的指针*/
struct StNode*link；
}StNode；
假设从栈顶到栈底的元素为en、en-1…、e1，则不含头节点的链栈示意图如图5-1所示。

[C函数]
int  InOrder(BTree root)        /*实现二叉树的非递归中序遍历*/
{
BTree ptr；                 /*ptr用于指向二叉树中的节点*/
StNode*q；                  /*q暂存链栈中新创建或待删除的节点指针*/
StNode*stacktop=NULL；      /*初始化空栈的栈顶指针stacktop*/
Ptr=root；                  /*ptr指向二叉树的根节点*/
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是访问节点的函数，其具体定义省略*/
ptr=  (5)  ；    /*进入右子树*/
free(q)；               /*释放原栈顶元素的节点空间*/
}
return 0；
}/*Inorder*/

查看答案

试题二：

阅读下列说明和Java代码，回答下列问题。

[说明]

某咖啡店卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如表2-9所示。

表2-9 咖啡及配件的种类和价格

现采用装饰器(Decorator)模式来实现计算费用的功能，得到如图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());

}

}

编译运行上述程序，其输出结果为：DarkRoast，Mocha，Whip ￥38

查看答案