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

[单项选择]

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

（6）处填（）。
A. m+2
B. m+1
C. m
D. m-1

[填空题]【说明】
下面的程序构造一棵以二叉链表为存储结构的二叉树算法。
【函数】
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]

[简答题]给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。

[简答题][说明]
二叉树的二叉链表存储结构描述如下：
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);

[简答题]

CREATE(X,LBT,RBT);

[填空题]在有n个结点的二叉链表中，值为非空的链域的个数为 [1] 。

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

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

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

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

[单项选择]

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

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

[填空题]在一棵二叉排序树中，按 【5】 遍历得到的节点序列是有序序列。