若n个结点的二叉树采用二叉链表存储，则空闲指针域的个数为 个。

用二叉链表法(link-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（）

用类Pascal语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存储，左指针定义为lchild，右指针定义为rchild。【燕山大学2000七、2(8分)】

二叉树以二叉链表存储，若指针p指向二叉树的根结点，经过运算s=p；while(s-＞rchild)s=s-＞rchild后，则(  )。

  A．s指向二叉树的最右下方的结点 B．s指向二叉树最左下方的结点

  C．s指向根结点  D．s为NULL

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

（57）

A. m+2

B. m+1

C. m

D. m-1

（58）

A. s－>right指向的结点一定是s所指结点的直接后继结点

B. s－>left指向的结点一定是s所指结点的直接前驱结点

C. 从s所指结点出发的right链可能构成环

D. s所指结点的left和right指针一定指向不同的结点

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

（57）

A. m+2

B. m+1

C. m

D. m-1

（58）

A. s－>right指向的结点一定是s所指结点的直接后继结点

B. s－>left指向的结点一定是s所指结点的直接前驱结点

C. 从s所指结点出发的right链可能构成环

D. s所指结点的left和right指针一定指向不同的结点

A．错误

B．正确

用链表(lchild-rchild表示法)存储的包含n个结点的二叉树，结点的2n个指针域中有n+l个空指针。()

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

A.2m-1

B.2m

C.2m+1

D.4m