一棵深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中，则n至少是 才能确保正确存储。

已知一棵高度为k具有n个结点的二叉树，按顺序方式存储： (1)编写用先根遍历树中每个结点的非递归算法； (2)编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学1997六(20分)】

●试题三

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明3．1】

假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数deleteklist(LinkList head)的功能是删除表中所有数值相同的多余元素，并释放结点空间。

例如：链表初始元素为：

(7，10，10，21，30，42，42，42，51，70)

经算法操作后变为：

(7，10，21，30，42，51，70)

【函数3．1】

void deleteklist(LinkList head)

{

LinkNode*p，*q；

p=head->next；

while(p!=head)

{

q=p->next；

while( (1) )

{

(2) ；

free(q)；

q=p->next；

}

p=p->next；

}

}

【说明3．2】

已知一棵完全二叉树存放于一个一维数组T［n］中，T［n］中存放的是各结点的值。下面的程序的功能是：从T［0］开始顺序读出各结点的值，建立该二叉树的二叉链表表示。

【函数3．2】

#include<istream．h>

typedef struct node {

int data；

stuct node leftChild，rightchild；

}BintreeNode；

typedef BintreeNode*BinaryTree；

void ConstrncTree(int T［］，int n，int i，BintreeNode*＆ptr)

{

if(i>=n) (3) ；∥置根指针为空

else

{

ptr=-(BTNode*)malloc(sizeof(BTNode))

ptr->data=T［i］；

ConstrucTree(T，n，2*i+1， (4) )；

ConstrucTree(T，n， (5) ，ptr->rightchild)；

}

}

main(void)

{/*根据顺序存储结构建立二叉链表*／

Binarytree bitree；int n；

printf("please enter the number of node:＼n％s"；n)；

int*A=(int*)malloc(n*sizeof(int))；

for(int i=0；i＜n；i＋＋)scanf("％d，A+i)；/*从键盘输入结点值*/

for(int i=0；i＜n；i＋＋)printf("％d"，A［i］)；

ConstructTree(A，n，0，bitree)；

}

设一棵二叉树的深度为k，则该二叉树中最多有()个结点。

A、2k-1

B、2k

C、2k-1

D、2k-1

一棵树高为k的完全二叉树至少有( )个结点。【南京理工大学1998一、3(2分)】

A．2k-1

B．2k-1一1

C．2k-1

D．2k

考查任何一棵高度为h的二叉树T，设其中深度为k的叶节点有n_k个，0≤k≤h。

a)试证明：

b)以上不等式取等号的充要条件是什么?

一棵二叉树以二叉链表来表示，求其指定的某一层k(k＞1)上的叶子结点的个数。【上海大学1999三、1(18分)】

已知一棵含有n个结点的树中，只有度为k的结点和度为0的叶子结点，则该树中含有的叶子结点个数为【 】。

由二叉树的先序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的先序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。 define MAX 100 typedef struet Node{ char info； struct Node*llink．*rlink； }TNODE； char pred[MAXj，inod[MAXj； main(int argc，int**argv){ TNODE*root： if(argc<3) exit(0)； strcpy(pred，argv[1])； strcpy(inod，argu[2])； root=restore(pred，inod，strlen(pred))； postorder(root)； } TNODE*restore(char*ppos，char*ipos，int n){ TNODE*ptr： char*rpos； int k； if(n<=0) return NULL； ptr->info= (1) for( (2) ；rpos (3) ptr->llink=restore(ppos+1， (4) ，k)； ptr->rlink=restore( (1) +k，rpos+1，n一1一k)； return ptr； } postorder(TNODE*ptr){ if(ptr==NULL) exit(0)； postorder(ptr->llink)； postorder(ptr->rlink)； printf(“c”，ptr->info)； }