[简答题]以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。

[简答题]试编写一个非递归算法．实现求以二叉链表存储的二叉树中q结点的祖先。

[简答题][说明]
二叉树的二叉链表存储结构描述如下：
typedef struct BiTNode
datatype data;
struct BiTNode *lchild, * rchild; /*左右孩子指针*/
BiTNode,* BiTree;
对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作：
(1) 访问该元素所指结点；
(2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行，当队列为空时，二叉树的层次遍历结束。
下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。
[函数]
void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/
BiTree Queue[MAXNODE];
int front,rear;
if(bt= =NULL)return;
front=-1;
rear=0;
queue[rear]= (1) ;
while(front (2) )
(3) ;
Visit(queue[front]-＞data); /*访问队首结点的数据域*/
if(queue[front]—＞lchild!：NULL)
rear++;
queue[rear]= (4) ;

if(queue[front]-＞rchild! =NULL)
rear++;
queue[rear]= (5) ;

[多项选择]假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

[多项选择]假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上个结点的值。

[简答题]

DELLEFT(BT,X).

[简答题]

PARENT(BT,X);

[填空题]【说明】
下面的程序构造一棵以二叉链表为存储结构的二叉树算法。
【函数】
BTCHINALR *createbt ( BTCHINALR *bt )

BTCHINALR *q;
struct node1 *s [30];
int j,i;
char x;
printf ( "i,x =" ); scanf ( "%d,%c",&i,&x );
while (i!=0 && x!=’$’)
q = ( BTCHINALR* malloc ( sizeof ( BTCHINALR )); //生成一个结点
(1) ;
q-＞1child = NULL;
q-＞rchild = NULL;
(2) ;
if( (3) ;)
j=i/2 //j为i的双亲结点
if(i%2==0
(4) //i为j的左孩子
else
(5) //i为j的右孩子

printf ( "i,x =" ); scanf ( "%d,%c",&i,&x );
return s[1]

[简答题]

CREATE(X,LBT,RBT);

[简答题]要求二叉树按二叉链表形式存储，并且：
(1)写一个建立二叉树的算法。
(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。

[简答题]二叉链表为存储结构，写出二叉树宽度的算法。所谓宽度，是指二叉树的各层上，具有结点数最多的那一层上的结点总数。

[简答题]设有一棵二叉树以二又链表作为存储结构，结点结构为：1child | data | rchild，其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符(即’0’＜=da-ta＜=’9’)。

[单项选择]

n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为 (45) 个，其中 (46) 个用于链接子结点， (47) 个空闲着。

（45）处填（）。
A. n
B. n-1
C. n+l
D. n-2

[填空题]100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有_________个。

[单项选择]在一棵二叉树的二叉链表中，空指针数等于非空指针数加（）。
A. 2
B. 1
C. 0
D. -1

[简答题]已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成请简述原因。

[单项选择]

一个具有m个节点的二叉树，其二叉链表节点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (6) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有节点进行如下操作：若节点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱节点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继节点。假设指针s指向中序(先序、后序)线索二叉树中的某节点，则 (7) 。

（7）处填（）。
A. s→right指向的节点一定是s所指节点的直接后继节点
B. s→left指向的节点一定是s所指节点的直接前驱节点
C. 从s所指节点出发的right链可能构成环
D. s所指节点的left和right指针一定指向不同的节点