X=?c?;y=?k?;
Push(S,x); Push(S,?a?); Push(S,y); Pop(S,x); Push(S,?t?); Push(S,x); Pop(S,x); Push(S,?s?);
while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }
答：输出为“stack”。
2. 【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){
Queue Q; Init Queue (Q); Char x=?e?; y=?c?;
EnQueue (Q,?h?); EnQueue (Q,?r?); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,?a?);
while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); }
答：输出为“char”。
3. 【严题集3.13②】简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){ Stack S; int d; InitStack(S);
while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); };
while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }
答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。 六、算法设计（每小题5分，共15分。至少要写出思路）
1. 【李春葆及严题集3.19④】假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编
写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。
答：用堆栈st进行判定，将 ( 、 [ 或 { 入栈，当遇到 } 、 ] 或 ) 时，检查当前栈顶元素是否是对应的( 、 [ 或 {，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括号正确配对，否则不配对。
编程后的整个函数如下（李书P31—32）
#define m0 100 /*m0为算术表达式中最多字符个数*/ correct(exp,tag) char exp[m0]; int tag;
{char st[m0]; int top=0, i=1; tag=1;
while (i<=m0 && tag)
{if (exp[i]= = ?(?||exp[i]= =?[?||exp[i]= =?{?） /*遇到?(?、?[?或?{?，则将其入栈*/ {top++;
st[top]=exp[i]; }
if (exp[i]= =?)? ) /*遇到?)? ，若栈顶是?(?，则继续处理，否则以不配对返回*/ if(st[top]= =?(? ) top--;
6
else tag=0;
if (exp[i]= =? )? ) /*遇到? ]? ，若栈顶是?[?，则继续处理，否则以不配对返回*/ if(st[top]= =?[ ?] top--; else tag=0;
if (exp[i]= =?)? ) /*遇到? }? ，若栈顶是?{?，则继续处理，否则以不配对返回*/ if(st[top]= =?{? top--; else tag=0; i++;
}
if(top>0)tag=0; /*若栈不空，则不配对*/ }
严题集对应答案： 3.19
Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配 {
InitStack(s);
for(p=str;*p;p++) {
if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') {
if(StackEmpty(s)) return ERROR; pop(s,c);
if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR;
if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配 } }//for
if(!StackEmpty(s)) return ERROR; return OK;
}//AllBrackets_Test
2001级通信6班张沐同学答案（已上机通过）
#include
void correct(enum Boolean &tag);
//原来的定义是void correct(struct Stack* head,enum Boolean &tag);
typedef struct Stack { char data; struct Stack *next; };
struct Stack *head,*p;
enum Boolean{FALSE,TRUE}tag;
void main() {
7
head=(struct Stack*)malloc(sizeof(struct Stack)); head->data='S'; head->next=NULL; // head's data has not been initialized!! correct(tag); if(tag) printf(\ else printf(\}
void push(char x) { p=(struct Stack*)malloc(sizeof(struct Stack)); if(!p) printf(\ else { p->data=x; p->next=head; head=p; } }
// if you define the \
//Debug will show that the Push action doesn?t take effection
void pop() { if(head->next==NULL) printf(\ else { p=head; head=head->next; free(p); } }
//void correct(struct Stack* head,enum Boolean &tag) void correct(enum Boolean &tag) { int i; char y; printf(\ for(i=0;y!='\\n';i++) { scanf(\ if((y==')'&&head->data=='(')||(y==']'&&head->data=='[')||(y=='}'&&head->data=='{')) pop(); else if((y=='(')||(y=='[')||(y=='{')) push(y);
/*调试程序显示，y并没有被推入堆栈中。即head->data的值在Push中显示为y的值，但是出Push函数。马上变成Null。*/
8
else continue; } if(head->next==NULL) //原来的程序是if(head ==NULL) tag=TRUE; tag=TRUE; else tag=FALSE; }
/*总结： 由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/
2. 【统考书P60 4-15】假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。
解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两种见简答题）； 思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1； 若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。
3.【严题集3.31③】试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 答：编程如下：
int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {
InitStack(S);InitQueue(Q); while((c=getchar())!='@') {
Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 }
while(!StackEmpty(S)) {
Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; }
return OK;
}//Palindrome_Test
第6章 树和二叉树 自测卷解答
一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）
（ √ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ × ）2.二叉树中每个结点的两棵子树的高度差等于1。 （ √ ）3.二叉树中每个结点的两棵子树是有序的。
（ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于
其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）
（ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）
（ × ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1） （ √ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为
空指针。
（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。
9
（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5
二、填空（每空1分，共15分）
1． 由３个结点所构成的二叉树有 5 种形态。
2. 【计算机研2000】 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。 （ 注：用? log2(n) ?+1= ? 8.xx ?+1=9
4. 【全国专升本统考题】设一棵完全二叉树有700个结点，则共有 350 个叶子结点。
答：最快方法：用叶子数＝[n/2]＝350
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6. 【严题集6.7③】 一棵含有n个结点的k叉树，可能达到的最大深度为 n ，最小深度为 2 。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7. 【96程试题1】 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。 解：法1：先由已知条件画图，再后序遍历得到结果；
法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。
法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。
8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为 O(n) 。 答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。
9. 【计算机研2001】 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33 (15) (9) (6) （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) （注：合并值应排在叶子值之后）
1 2
（注：原题为选择题：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15）
三、单项选择题（每小题1分，共11分）
（ C ）1． 不含任何结点的空树 。
（Ａ）是一棵树; （Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树
答：以前的标答是B，因为那时树的定义是n≥1
（ C ）2．二叉树是非线性数据结构，所以 。
（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;
10