③字符构成的集合 ④字符构成的序列
第三、四章练习题
3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?
(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
3.2链栈中为何不设置头结点?
3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
3.4指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;
while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1
(2) SeqStack S1, S2, tmp; DataType x;
...//假设栈tmp和S2已做过初始化
16
while ( ! StackEmpty (&S1)) {
x=Pop(&S1) ; Push(&tmp,x); }
while ( ! StackEmpty (&tmp) ) {
x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }
(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T);
while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) {
i=Pop(&T); Push(S,i); } }
(4)void Demo3( CirQueue *Q) { // 设DataType 为int 型
17
int x; SeqStack S; InitStack( &S);
while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s)) { x=Pop(&S); EnQueue( Q,x );} }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, i , n= 0;
... // 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ;
EnQueue( &Q1, x) ; EnQueue( &Q2, x);}
18
第六章 树
一．名词解释：
1 树 2。结点的度 3。叶子 4。分支点 5。树的度 6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树 11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树 16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树 21 哈夫曼树 二、填空题 1、
树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前
趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2、
一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则
称A是B的________ 3、
一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有
______
的二叉树、同时有______的二叉树五种基本形态。 4、 5、 6、 7、
二叉树第i(i>=1)层上至多有______个结点。 深度为k(k>=1)的二叉树至多有______个结点。
对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是
______二叉树，但反之不然。 8、 9、
具有n个结点的完全二叉树的深度为______。
如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点
19
X有：
（1） 若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。
（2） 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号
为______。 （3） 若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 10.二叉树通常有______存储结构和______存储结构两类存储结构。
11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL. 13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。
15．二叉树有不同的链式存储结构，其中最常用的是________与________。 16．可通过在非完全二叉树的“残缺”位置上增设“________”将其转化为完全二叉树。 17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } }
18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。
20