提高组解答

11.2.1　提高组解析

一、单项选择题

二、问题求解

三、阅读程序

同普及组

四、完善程序

1．同普及组

2．过程makeTree（pointer & s）（Pascal中为maketree（var s: pointer））的功能是参照已知列表生成一棵M叉树，其中列表字符串由全局变量buf给出，简单变量i指向当前要处理的字符。从该过程的结构中看到，除对当前节点有一个循环控制它的子树的构造外，没有对当前节点的子树的构造有特别的构造过程的代码，所以该过程是一个构造子树的递归过程，通过递归调用构造当前节点（子树根节点）的所有子树。按列表的构成规则，首先是子树根节点的值，过程makeTree得先为子树的根节点向系统申请存储空间，所以①应填s＝new node（new（s））。根节点有了空间后，列表字符串的当前字符的值就是根节点的值。接着过程为根节点的子节点预置空值。如节点值之后接有字符（′,′说明该节点有子树。由于有多棵子树，过程中用循环控制对子树的构造。在第一棵子树的列表之前有字符左括号，其他子树的列表之前有逗号，所以过程在构造每棵子树前，列表字符指针i都要加1，接着采用递归调用自己构造子树。所以②应填makeTree（pointer & s）（Pascal为maketree（. substree［k］））。若子树之后遇字符右括号，则表示当前节点不再有更多的子树，过程跳出构造子树循环。根据约定，子树之间用逗号分隔，若子树的后继字符是逗号，表示还有后续子树，需继续循环，所以③应填buf［i］＝＝; （′Pascal中为buf［i］＝;′）。需要注意的是为了把递归调用后求得的子树带回调用程序，递归过程makeTree的形式参数必需使用变量形式参数（引用）。

过程walkTree（pointert）完成与过程makeTree相反的工作，由已知M叉树的根节点指针，输出该树的列表字符串。由过程walkTree的结构知，它与过程makeTree一样，也是采用递归算法，实现一棵子树的列表输出。对于一棵非空的子树，过程walkTree首先输出子树根节点的值，所以④应填cout＜＜t－＞val（Pascal中为write（. val））。过程接着判断当前节点是否有子树，若子树的第一个子节点指针为空，说明该节点没有子节点，过程结束转换而返回；否则，先输出左括号，并逐一对该节点的各子树做转换输出工作。对各子树的转换用递归实现，提供的实参是子树根节点的指针，所以⑤应填walkTree（t－＞subTree［i］）（Pascal中为walktree（. subtree［i］））。每棵子树转换输出后，若还有更多的子树，过程输出逗号；若不再有更多的子树，过程输出右括号，结束全部转换输出工作。

11.2.2　提高组参考答案

一、单项选择题

1．D　2．B　3．D　4．A　5．C　6．D　7．D　8．C　9．A　10．C　11．D12．B　13．D　14．C　15．C　16．C　17．B　18．C　19．A　20．D

二、问题求解

1．518＋1＋3＋243＝9＋27＋729。

2．

三、阅读程序

（1）1000。　　（2）69。　　（3）495。　　（4）151。

四、完善程序

1．Pascal答案

（1）rest＞0　或　rest＜＞0

（2）k＝start

（3）dec（rest）

（4）a［（k＋n）％ m］:＝temp　或　a［（start＋n）％ m］:＝temp

（5）inc（start）

C＋＋答案

（1）rest＞0　或　rest!＝0

（2）k＝＝start

（3） －－rest

（4）a［（k＋n）％ m］＝temp　或　a［（start＋n）％ m］＝temp

（5）＋＋start

2．Pascal答案

（1）new（s）

（2）maketree（. subTree［k］）

（3）str1［i＋p］＝str2［k＋p］

（4）p＝j

（5）walktree（. subtree［i］）

C＋＋答案

（1）s＝new node

（2）makeTree（s－＞subTree［k］）

（3）str1［i＋p］＝＝str2［k＋p］

（4）p＝＝j

（5）walkTree（t－＞subTree［i］）