问题 填空题

已知一棵含有n个结点的树中,只有度为k的结点和度为0的叶子结点.则该树中含有的叶子结点个数为______。

答案

参考答案:((k-1)×n+1)/k

解析:设这棵树中叶子结点数为n0,度数为k的结点数为nk,总结点数为n,则
n=n0+nk 式(1)
设树的总入度为m。由于在树中除了根结点外,其余每一个结点都有唯一的一个分支进入,则树的总结点数为
n=m+1 式(2)
又由于树中这m个进入分支分别由非叶子结点射出,在这棵树中,只有度为k的结点和度为0的叶子结点,所有全部都由度为k的结点射出,而且射出分支总数与总的进入分支数相等地,即
m=k·nk 式(3)
由式(1)、(2)、(3)可以得到n0=((k-1)×n+1)/k。

填空题

[说明]

某游戏公司现欲开发一款面向儿童的模拟游戏,该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表下表所示。

为支持将来能够模拟更多种类鸭子的特征,采用策略设计模式(strategy)设计的类图如图5-1所示。

其中,Duck为抽象类,描述了抽象的鸭子,而类RubberDuck、MallardDuck、CottonDuck和RedHeadDuck分别描述具体的鸭子种类,方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征;类FlyBehavior与QuackBehavior为抽象类,分别用于表示抽象的飞行行为与发声行为;类FlyNoWay与FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为;类Quack、Squeak与QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。

[C++代码]

# include<iostream>

using namespace (1) ;

class FlyBehavior

public : (2) fly()=0;

;

class QuackBehavior

public: (3) quack()=0;

Class FlyWithWings :public F1yBehavior

public: void fly()cout<<"使用翅膀飞行!"<<endl;

;

class FlyNoWay :public FlyBehavior

public: void fly()cout<<"不能飞行!">>endl;

;

class Quack :public QuackBehavior

public: void quack()cout<<"发出\’嘎嘎’\声!"<<endl;

;

class Squeak :public QuackBehavior

public: void quack()cout<<"发出空气与橡皮摩擦声!"<<endl;

;

class QuackNOWay :public QuackBehaVior

public: void quack()cout<<"不能发声!"<<endl;

;

C1ass Duck

protected:

FlyBehavior * (4) ;

QuackBehaVior * (5) ;

public:

VOid fly() (6) ;

VOid quack() (7) ; ;

virtual void display()=0;

;

class RubberDuck: public Duck

public:

RubberDuck()

flyBehavior=new (8) ;

quackBehavior=new (9) ;

~RubberDuck()

if (!flyBehavior) delete flyBehaVior;

i f(!quackBehavior)delete quackBehavior;

Void display() /*此处省略显示橡皮鸭的代码*/

//其他代码省略

(1)处填()。

判断题