程序员习题

程序员习题

1）经过以下栈运算后，x的值是_____________。

InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);

A. a

B. b

C. 1

D. 0

2) 经过以下栈运算后，StackEmpty(s)的值是___________。

InitStack(s); Push(s,a); Push(s,b); Pop(s,x); Pop(s,y);

A. a

B. b

C. 1

D. 0

3) 设一个栈的输入序列为A,B,C,D, 则借助一个栈所得到的输出序列不可能是

___________.

A). A.B.C.D B) D.C.B.A

C). A.C.D.B D). D.A.B.C

4) 一个栈的进栈序列是a.b.c.d.e, 则栈的不可能的输出序列是___________’

A.edcb

B.decba

C.dceab

D. abcde

5) 已知一个栈的进栈序列是1,2,3,……,n,其输出序列的第一个元素是i，则第j个出栈元素是_______________’

A.j

B.n-I

C.z-i+1

D.不确定

6）已知一个栈的进栈序列是1,2,3,…..,n, 其输出序列是p1,p2,……,pn, 若p1=n, 则p1的值是_____________.

A.I Bn-I Cn-i+1 D 不确定

7）设n个元素的进栈序列为p1,p2,p3,……,pn, 其输出序列为1,2,3,……,n, 若pn=1,则pi(1<=i<=n-1)的值___________.

A.n-i+1

B.I

C.I

D. 有多种可能

8）栈是一种具有_________________特性的线性表。

9) 顺序栈和链栈的区别仅在于_____________的不同？

10) 如果栈的最大长度难以估计，那么最好使用__________________栈。

11）一个栈的输入序列是12345，则栈的输出序列12345可不可能出现。

12）判定一个顺序栈st为（元素个数最多为Maxsize）空的条件为_____________.

A.st.top==-1;

B.st.top!= -1;

C.st.top!=Maxsize;

D.st.top==Maxsize;

13) 判定一个顺序栈st为（元素个数最多为Maxsize）满的条件为______________.

A.st.top!=-1;

B.st.top= = -1;

C.t.top!=Maxsize-1;

D.st.top== axsize-1;

14)递归模型f(n=f(n-1)+n (n>1)的递归出口是___________.

A..f(1)=0

B.f(1)=1

C.f(0)=1

D.f(n)=n 15) 经过以下队列运算后，队头的元素是____________.

InitQuue(qu); enQueue(qu,’a’); enQueue(qu,’b’); enQueue(qu,’c’); deQueue(qu);

A.a

B.b

C.1

D.0

16) 元素A,B,C,D顺序连续进入队列qu后，队头元素是____________,队尾元素是_______.

A.A

B.B

C.C

D.D

17) 一个队列的入列序列为1234，则队列可能的输出序列是______________.

A.4321

B.1234

C.1432

D. 3241

18) 队列是一种具有___________特性的线性表。

19）顺序队和连队的区别仅在于______________的不同。

20）如果队列的最大长度难以估计，则最好使用_____________.

21）环形队列qu的队满条件是_______________.

A. (qu. rear+1)%maxSize == (qu.front+1)%MaxSize

B. (qu. rear+1)%MaxSize==qu.front+1;

C. (qu.rear+1)%MaxSize==qu.front+1;

D. qu.rear==qu.front

22) 最适合用作列队的列表是__________.

A. 带队首指针和队尾指针的循环单连表

B. 带队首指针和队尾指针的非循环单链表

C. 只带队首指针的循环单链表

D. 只带队尾指针的循环单链表

23）最不合适用做链队的链表是

A.只带队首指针的非循环双链表。

B．只带队首指针的循环双链表。

C. 只带队尾指针的循环双链表。

D. 只带队尾指针的循环单链表。

24）.假设一个练队的队尾和队首指针分别为rear front则判断队空的条件是

A front==rear

B front!==NULL

C rear!==NULL

D front==NULL

25)用单链表表示的链队的队头在链表的_______位置

A. 链头

B．链尾

C．链中

D．以上都可以

26）用单链表表示的链队的队尾在链表的_______位置

A. 链头C．链中

B．链尾D．以上都可以

27）对于链队在进行删除操作时

A 仅修改头指针

B仅修改尾指针

C 头尾指针都要修改

D头尾指针可能都要修改

填空题

1．若用带表头结点的单链表表示则队列为空的标志是_______.

2．若用不带表头结点的单链表表示则创建一空队列的所要执行的操作是_______.

3．若用带头结点的单链表表示则创建一空队列的所要执行的操作是_______.

4．已知链队的头尾指针分别是f和r则将值x如队的操作是

P=(QNode *)malloc (sizeof(QNode));p->data=x; _____________;________;_________; 5．表达式23+（（12*3-2）/4+34*5/7）+108/9的后缀表达式是_____________________ 6．;

程序：

1．有如下算法：

Void print (int w)

{

Int i;

If (w!=0)

{

Print(w-1);

For (i=1;i<=w;i++)

Printf(“%d”,w);

Printf(“\n”);

}}

调用语句print（4）的结果_______。

2．有如下递归过程：

Void reverse（int m）

{printf(“%d”,n%10);

If (n/10!=0) reverse(n/10);

}

调用语句reverse(582)的结果是________。

3.递归函数sum(int a[], int n)的返回值是数组a[]的前n个元素之和。

Int sum(int a[], int n)

{if(n>0) return_______;

Else ________;

}

4. 递归函数int dec(int a[], int n)判断数组a[]的前n个元素是否递增，递增返回0；int dec(int a[], int n)

{if(n<=1)________;

If(a[0]

Else ________;

}

5. 递归函数invert (int a[], int k)将指定数组中的前k 个元素逆置

Void invert (int a[], int k)

{int t;

If(_______){invert(____________);

T=a[0];

A[0]=a[k-1];a[k-1]=t;

}

}

6. int dec(int n)的功能是计算n!.如调用dec(6)后函数的反回值是120

int dec(int n){if (n<2)_________;

else return(________);

}

7.递归函数int fib(int n)的功能是计算fibonacci 数列的第n 项

int fib(int n){ if (n==0)________;

else if(_________) return 1;

else _________;

}

判断：

1）栈低元素是不能删除的元素。

2）顺序栈中元素值的大小是有序的。

3）在n个元素进栈后，他们的出栈顺序和进栈顺序正好相反。

4）栈顶元素和栈底元素有可能是同一元素。

5）若用s[1]~s[m]表示顺序栈的存储空间，则对栈的进栈，出栈操作最多只能进行m次。6）栈是一种对进栈，出栈操作总次数做了限制的线性表。

7）对顺序栈进行进栈，出栈操作，不涉及元素的前后移动问题。

8）栈是一种对进栈，出栈操作的次序做了限制的线性表。

9）空栈没有栈顶指针。

10) 栈和队列都是限制存取端的线性表。

11）队列是一种对进队列，出队列操作的次序做了限制的线性表。

12）n个元素进队列的顺序和出队列的顺序总是一致的。

13）顺序队中有多少元素，可以根据队首指针的值和队尾指针的值来计算。

14）若用“队首指针的值和队尾指针的值相等”作为环形顺序队为空的标志，则在设置一个空队时，只需给队首指针和队尾指针赋同一个值，不管什么值都可以。

15）无论是顺序队还是链队，进队，出队操作的时间复杂度都是O(1).

解答题：

1）设有一个数列的输入顺序为123456，若采用栈结构，并以A和D分别表示进栈和出栈操作，试问通过进栈和出栈操作的合法序列。

（1）能否得到输出序列为325641的序列？

（2）能否得到输出序列为154623的序列？

2）说说线性表，栈和队列的异同。

3）设栈s和队列q的初始状态都为空，元素a,b,c,d,e和f依次通过栈s，一个元素出栈后既进入队列q，若6个元素出队的序列是bdcfea, 则栈s的容量至少应该存多少个元素？

程序题：

1>写出下列程序字段的输出结果（栈的元素类型SElemType为char）

Void main()

{Stack S;

Char x,y;

InitStack(S);

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(!StackEmty(S)){pop(S,y);printf(y);}

Printf(x);

}

2>简述以下算法的功能（栈的元素类型SElemType为int）

Status algo2(Stack S,int e)

{Stack T;int d;

InitStack(T);

While(!StackEmpty(S))

{pop(S,d);

If(d!=e)push(T,d);

}

While(!StackEmpty(S))

{pop(T,d);

Push(S,d);

}

}

3>写出以下程序段的输出结果（队列中元素类型QElemType为char）

Void main()

{Queue Q; InitQueue(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);

}

4>函数MultibaseOutput(long n,int B)的功能是：将一个无符号十进制数n转换成B （2<=B<=16）进制整数并输出。该函数先将转换过程中得到的各位数字入栈，转换结束后把B进制从栈中输出。有关操作的各函数功能见相应函数中的注释。C代码中的符号常量及栈的类型定义如下：

#define MAXSIZE 32

Typedef struct {

Int *elem ;/*栈的存储区*/

Int max;/*栈的容量，即栈中最多能存放的元素个数*/

Int top;/*栈的指针*/

}Stack;

C代码

Int InitSack(Stack *s,int n)

{S->elem=(int * )malloc(n*sizeof(int));

If(S->elem==NULL) return -1;

S->max=n;

_____________=0;

Return 0;

} `

Int push(Stack *S,int item )/*将整数item压入栈中*/

{if(S->top==S->max){printf(*Stack is full!\n);

Return -1;

}

_____________=irem;

Return 0;

}

Int StackEmpty(Stack S)

{

Return(!S.top)?1:0;/*判断栈是否为空*/

}

Int pop(Stack *S)栈顶元素出栈*/

{

If(S->top){printf(“pop an empty stack!\n”);

Return -1;

}

Return __________;

}

Void MultibaseOutput(long n,int B)

{

Int m;Stack S;

If(InitStack(&S,MAXSIZE)){printf(“Failure!\n”);

Return;

}

Do{if(push(&S,________)){printf(“Failure!\n”);

Return;}

N=________;

}while(n!=0);

While(!StackEmpty(S))/*输出B进制数*/

{m=pop(&S);

If(m<10)printf(“%d”,m);/*小于10，输出数字*/

Else printf(“%c”,m+55);/*大于或等于10，输出相应的字符*/

}

Printf(“\n”);}

8.编写一个实现串的置换操作Replace（char *S,T,V)的算法

int Replace(StringType &s,StringType T,StringType V)//将串中S中所有子串T替换V并返回置换次数

{

}//Replace

9.编写算法,从串s中删除所有和串t相同的子串.

int Delete_SubString(StringType *s,StringType t) /从串s中删除所有与t相同的子串,并返回删除次数

{

}//Delete_SubString

11.编写算法,实现串的基本操作StrAssign(char *T,chars)

void StrAssign(StringType &T,char chars &#)//用字符数组chars给串T附值

{

}//StrAssign

12.编写算法,实现串的基本操作StrCompare(S,T).

char StrCompare(StringType s,StringType t)//串的比较,s>t时返回正数,s=t时返回0,s

{

}//StrCompare

13.编写算法,实现串的基本操作Replace(char *S,T,V).

bool repl(SString &News, SString S, SString T,SString V)

{

}//repl

14.编写算法,求串s所含不同字符的总数和每种字符的个数。

15.假设以结点大小1(且附设头结点)的连表结构表示串,试编写实现下列六种串的基本操作:

StrAssign,StrCopy,StrCompare,StrLenght,ConCat和SubString的函数.

6．2 典型例题解析

6．1一棵完全二叉树第6层有7个结点，则共有（）个结点，其度为1的结点有（）个，度为0的结点有（）个，编号最大的非叶子结点是（），编号最小的叶子结点是（）。

6．2 试回答下面的问题：

已知一棵满二叉树的结点个数为20~40的数，试问此二叉树的叶子结点有多少个？

有n个结点的二叉树，已知叶子结点的个数为n0，

写出求度为1的结点的个数n1计算公式；

若此数是高度为h的完全二叉数，写出n为最小的公式；

若二叉数中仅有度为0和度为2的结点，写出该二叉数结点个数n的公式。

（3）已知一棵度位m的树中有n1 个度为1的结点，n2个度为2的结点，……,Nm 个度为m的结点,问该树有多少个叶子结点?

6．3.已知有一棵二叉树的中序遍历序列为DBEHAFCIG，后序遍历是DHEBFIGCA，试画出该二叉树，并给出该二叉树的的前序序列。

6．5设二叉树用二叉链表表示，设计算法：

（1）求二叉树的高度；

（2）求二叉树的度为2的结点数；

6．6试编写算法判断二叉树T是否是完全二叉树；

（1）若给定的二叉树采用顺序表作为存储结构；

（2）若给定的二叉树采用二叉链表作为存储结构。

6．7．对以二叉链表存储的非空而叉树，从右向左依次释放所有的叶子结点，释放的同时，把结点存放到一个数组中。要求：

（1）用文字写出实现上述过程的基本思想。

（2）写出算法，

6．8．试以二叉树链表的存储结构，编写按层次顺序遍历二叉树的算法。

6．9假设二叉树以二叉链表为存储结构，编写求任一指定结点所在的层次。

6．11设计算法，统计一棵二叉树中所有结点的数目及非叶子结点的数目。

6．14已知以二叉链表表示的二叉树中有值为x，y，z的三个结点，试编写算法判断x是否为y和z的共同祖先。

6．16假设二叉树的存储结构为二叉链表，试编写C语言的函数，其功能是交换二叉树中各结点的左子树和右子树。

6．18已知一棵二叉树用二叉链表存储，root指向根结点，p指向树中任何一结点。试编写算法输出从root~p路径上的结点。

6．20编写一个算法，利用叶子结点中的空指针域，将所有叶子结点链接为一个带有头结点的单链表，算法返回头结点的地址。

6．21假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

6.3 习题及参考答案

1.已知一棵树边的集合为{,,,,,,,,,,,}, 请画出这棵树,并回答下列问题:

(1)哪个是根结点?

(2)哪些是叶子结点?

(3)哪些是结点G的双亲?

(4)哪些是结点G的祖先?

(5)哪些是结点G的孩子?

(6)哪些是结点E的子孙?

(7)哪些是结点E的兄弟?哪些是结点F的兄弟?

(8)结点B和N的层次号分别是什么?

(9)树的深度是多少?

(10)以结点C为根的子树的深度是多少?

2.一棵度为2的树与一棵二叉树有何区别?

3.试分别画出具有3个结点的树和3个结点的二叉树的所有不同的形态.

4.一棵深度为H的满K叉树有如下性质:第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次顺序从1开始全部结点编号,问:

(1)各层的结点数目是多少?

(2)编号为p的结点的父结点(若存在)的编号是多少?

(3)编号为p的第i的儿子结点（若存在）的编号是多少？

(4)编号为p的结点有右兄弟的条件是什么?其右兄弟的编号是多少?

5.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点,...nk个度为k的结点,问该树中有多少个叶子结点?

6.已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,试求该树含有叶子结点的数目.

7.一棵含有n个结点k叉树,可能达到的最大深度和最小深度各为多少?

9．对题3所得各种形态的二叉树，分别写出前序，中序和后序遍历的序列。

10．假设n和m为二叉树中两结点，有“1”，“0”或“￠“（分别表示肯定，恰恰相反或者

11．找出所有满足下列条件的二叉树：

（1）他们在先序遍历和中序遍历时，得到的结点访问序列相同；

（2）他们在后序遍历和中序遍历时，得到的结点访问序列相同；

（3）他们在先序遍历和后序遍历时，得到的结点访问序列相同；

12．请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。

19.画出和下列已知序列对应的树T：

树的先根次序访问序列为GFKDAIEBCHJ；

树的后根次序访问序列为DIAEKFCJHBG。

21.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK.

请画出该树.

22.假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.

请画出该树.

29.编写递归算法,在二叉树中求位于先序序列中第K个位置的结点的值.

30.编写递归算法,计算二叉树中叶子结点的数目.

30.编写递归算法,将二叉树中所有结点的左,右子树相互交换.

32.编写递归算法:求二叉树中以元素值为X的结点为根的子树的深度;

33.编写递归算法:对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间.

34.编写复制一棵二叉树的非递归算法.

35.编写按层次顺序(同一层从左至右)遍历二叉树的算法.

36.在二叉树中,*root为根结点,*p和*q为二叉树中两个结点,试编写求距离它最近的共同祖先的算法.

41.试编写算法,求给定二叉树上从根到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列),若这样的路径存在多条,则输出路径终点(叶子结点) 在"最左"的一条.

42.已知一棵完全二叉树存于顺序表sa中,sa.elem[https://www.wendangku.net/doc/ff7483872.html,st]中存放各结点的数据元素.

试编写算法由此顺序存储结构建立该二叉树的二叉链表.

43.为二叉链表的结点增加DescNum域.试编写一算法,求二叉树的每个结点的子孙数目并且存入其DescNum域，请给出算法的时间复杂度。

44.试写一算法,在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继(假设二叉树的根结点未知).并讨论实现此算法对存储结构有何要求?

45.试写一算法,在后序后继线素二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并没给出）。并讨论实现算法对存储结构有什么要求？

四：算法设计题

1．社设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将元素S插入到线性表的适当位置，以保持线性表的有序性，并且给出算法的时间复杂度。

2．针对下面的问题，设计算法，要求算法的时间复杂度均为O（n）。

（1）已知数组A[n]的元素类型为整型,设计算法调整A,使其左边的所有元素小于零,右边的元素大于零。

（2）设计算法，将一个带头结点的单链表A分解为两个具有相同结构的单链表B和C，其中B 链表的结点为A链表中值小于零的结点，而C链表的结点为A 链表中值大于等于零的结点（假设单链表A的元素类型为整型）。要求：B和C链表利用A链表的结点。3．已知数组A[n]的元素类型为int。设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O（n）。

4．已知一个顺序存储的线性表的元素以非递减有序排列，编写删除表中多余的值相同的元素的高效算法。

5．已知一个顺序存储的线性表，编写删除表中值大于minx且小于maxy（包括minx和maxy）的所有元素的高效算法。

6．已知单链表的头指针为head，数据域为字符型，请编写算法，判断该链表的前n个字符是否中心对称。例如：abba，abcba都是中心对称。

7．编写一个函数将一个单链表复制一个拷贝。

8．已知有两个单链表A 和B，其头指针分别为ｆｉｒｓｔ和ｓｅｃｏｎｄ，编写一个算法，从单链表A 中删除自第i个元素起的共m 个元素，然后将他们插入到单链表B的第j个元素之前。

9．已知线性表的元素按照值递增有序排列，并以带头结点的单链表作为存储结构。试编写一高效算法，删除表中所有值大于Mink且小于Maxk的元素（若表中存在这样的元素），同时释放被删除结点的空间，并分析你的算法的时间复杂度。[说明]：Mink和Maxk是给定的两个数值，他们的值可以和表中的元素相同，也可以不同。

10．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）。

（1）确定在序列中比正整数X大的数有几个（相同的数只计算一次）。

（2）将单链表中比小的偶数从单链表中删除。

（3）将比正整数x 大的偶数从单链表中删除。

11．已知指针ｆｉｒｓｔ和ｓｅｃｏｎｄ和分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将表second的首结点连在first的最后一个结点之后。假设指针third指向连接后的链表的头结点，分析你的算法时间复杂度。

14．已知两个链表A 和B ，其元素值递增排序。请编写算法，将A 和B 合成一个递减有序（相同的元素只保留一个）的链表C，并要求利用原表结点。

15．设有一个由正整数组成的无序链表，编写完成下列功能的算法：

（1）找出最小值结点，且打印该数值；

（2）若该数值是奇数，则将其与直接后继结点的数值交换；

（3）若该数值是偶数，则将其直接后继结点删除；

16．已知A和B 为非递减排列的无头结点单链表（同一表中可能有相同的元素），试编写算法，构建一个新的单链表C，存如A 和B 中的公共元素。要求：C链表中的元素值各不相同且递增有序。

17．已知first．ｓｅｃｏｎｄ和ｔｈｉｒｄ为指向三个非递减有序单链表的头指针，现要求对表ｆｉｒｓｔ做如下操作：

删去那些在ｓｅｃｏｎｄ表中出现又在ｔｈｉｒｄ表中出现的元素。试编写实现上述操作的算法（要求释放表ｆｉｒｓｔ中的无用空间结点），并分析你的算法的时间复杂度。（:注意：题中没有特

别指明表中的元素各不相同。）

5．二叉树采用二叉链表存储结构，试设计算法计算一棵二叉树的各结点的子孙个数。7．给定一棵用二叉链表表示的二叉树，其data域为数值型数据。编写算法，计算每层结点data 域数值大于k的结点个数，并输出这些结点的data域的数值和序号。

10．一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。

11．给定一棵用二叉链表表示的二叉树，试编写一个递归算法，求二叉树的最大和最小路径长度。

13．已知一棵二叉树的前序遍历和中序遍历，编写算法建立对应的二叉树。

14．在二叉树中查找枝为x的结点，试设计输出值为x的结点的所有祖先的算法，假设值为x的结点不多余1个。

6.2.17

若一棵n个结点二叉树以二叉链表作为存储结构，下面的非递归算法，功能是交换二叉树中各结点的左子树和右子树。请在空白出填入正确的语句。

V oid InitStack((linkstackk & *s)

{

__________(1)________;

s->next=NULL;

}

int Empty(LinkStack *s)

{

if(______(2)_____) return 1;

else return 0;

}

BTNode * Gettop(LinkStack *s)

{

_________(3)_______;

}

BTNode *Pop(LinkStack *s)

{

LinkStack *p;

BTNode *q;

p=s->next;

q=p->data;

___(4)___;

___(5)___;

return q;

}

void Push(LinkStack *s,BTNode *r)

{

LinkStack *p;

p=(LinkStack

*)malloc(sizeof(LinkStack));

p->data=x;

____(6)___;

s->next=p;

}

void BTLink_Exchange(BTNode *T)

{

BTNode *p=T, *q;

LinkStack *s;

InitStack(s);

do

{

while(p!=NULL)

{

q=p->lchild;

p->lchild=p->rchild;

p->rchild=q;

______(7)______;

p=p->lchild;

}

if(______(8)______)

{

p=Pop(s);

_____(9)_______;

}

}while(____(10)____)

}

6.3.2.假设二叉树T有n个结点，我们按前序将树T的所有结点存放数组data[]的前n 个元素中，

值为data[i]结点相应的指针right[i]指向该结点的右孩子结点存放在data[]中存放的位置，

若该结点没有右孩子结点，则置right[i]为-1。

我们称二叉树的这种存储方法为按前序且附带一个指向右孩子结点的指针的顺序存储。

在下面的程序段中:

函数create（）将二叉树按照上述的顺序存储转换成附加两个分别指向左孩子结点，右孩子结点的指针的链接存储。

程序中利用一个栈（Stack）帮助我们对二叉树T实现上述的存储转换。

#define MAXSIZE 100

char data[MAXSIZE];

int right[MAXSIZE];

BTNode * CreateTree(char data[],int right[], int n)

{

int top=0,i=n,j;

while(--i>=0)

{

p=(BTNode *)malloc(sizeof(BTNode));

p->data=data[i];

if(_____(1)_____)

p->lchild=NULL;

else

{

for(j=0;j

if(jlchild=NULL;

else

_________(3)________;

}

if(_______) p->rchild=NULL;

else

________(4)_________;

________(5)_________;

}

return p;

}

6.3.3.具有n个结点的完全二叉树,已经顺序存储在一维数组A[n]中，下面算法是将A 中顺序存储变成二叉链表存储的完全二叉树.请在空缺处填入适当的语句,以完成上述算法.

Elemtype A[n];

void CreatTree(BTNode *T, int i)

{

_______(1)________;

T->data=A[i];

if(____(2)______);

CreatTree(____(3)____);

else

r->lchild=NULL;

if(______(4)_____)

CreatTree(_____(5)______);

else

r->rchild=NULL;

} void BTNode(ar a,BTNode *p) {

int j;

j=______(6)_____; CreatTree(p,j);

}