数据结构1800例题与答案之树和二叉树(3)

序序列进行排序的过程。【西安电子科技大学1999软件 一、4（2分）】 43．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。【重庆大学 2000 一、9】 44．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。【武汉大学 2000 一、2】 45．先根次序周游树林正好等同于按______周游对应的二叉树；后根次序周游树林正好等同于______周游对应的二叉树。【山东大学 1999 二、１ (４分)】 46. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。【中国人民大学 2001 一、4 （2分）】

47．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。

【厦门大学 2002 六、1 （4分）】

48．具有n个结点的满二叉树，其叶结点的个数是______。【北京大学 1994】

49．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过______中间结点（不含后继及x本身）

【南京理工大学 2000 二、8（1.5分）】

50．线索二元树的左线索指向其______，右线索指向其______。

【哈尔滨工业大学 2000 二、3 (2分)】

51．设y指向二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子)

x^.ltag:= (1)___; x^.lchild:= (2)___; y^.ltag:= (3)___; y^.lchild:= (4)___; x^.rtag:= (5)___; x^.rchild:= (6)___;

IF (x^.lchild<>NIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___; 【南京理工大学 1997 三、7 （9分）】 52．哈夫曼树是______。【北京理工大学 2001 七、4 （2）】【 长沙铁道学院 1998 二、3 (2分)】

53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。

【西安电子科技大学2001软件 一、3 （2分）】【厦门大学 2002 六、2（4分）】 54．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。【南京理工大学 1999 三、6（4分）】

55．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。【中国矿业大学2000 一、7（3分）】

56．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。

【西安电子科技大学1999软件 一、2（2分）】

57．①二叉树用来表示表达式，因为需要保存各子树的值，修改二叉树的结点结构为(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意义同前，Val用来存放以该结点为根的子树的值，值的类型依具体情况而定。为了简便起见，算法假定所考虑的表达式只有+，-，*，/ 四种二目运算，且已表示成相应的二叉树。算法所计算的表达式值放在根结点的Val域中。

PROC Postorder-eval(t:ptrType) BEGIN IF (t!=NULL)

BEGIN (1)_______; (2)_______;

CASE t^.data:

‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK;

‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK; ‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK; ‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK; otherwise: (3)___; BREAK; ENDCASE END END;

②PROC Delete(x:datatype,A:tree) BEGIN tempA:= (4)___;

WHILE (tempA^.Item!=x) AND (tempA!=NULL) DO

IF (x

ELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点，r为tempA的父亲

IF (6)___ return(x);

IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL) BEGIN t:=tempA; q:=tempA^.Rchild;

WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END;

t^.Lchild:= (7)___; //删去q

q^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild;

IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempA

END; ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item

ELSE r^.Rchild:=tempA^.Lchild

ELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item

ELSE r^.Lchild:=tempA^.Rchild

ELSE //tempA为树叶

IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULL END; 【中山大学 1999 四、 (20分)】

58．下面的类PASCAL语言递归算法的功能是判断一棵二叉树（采用二叉链表存贮结构）是否为完全二叉树。请把空缺的两部分补写完整。（提示：利用完全二叉树结点序号性质）

TYPE link=^node;

node=RECORD key:keytype; l,r:link; END;

VAR all:boolean; n:integer; root:link; FUNC num(t:link):integer; BEGIN (1)______END;

PROC chk(t:link;m{t 所指结点应有序号}:integer)

BEGIN (2)_______END;

BEGIN {建二叉树，其根由root指出 }

n:=num(root);{求结点数} all:=true; chk(root,1); IF all THEN writeln（‘该树为完全二叉树！’）ELSE writeln （’该树非完全二叉树！’）

END； 【北京工业大学 1997 二、2 (10分)】

59．将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。

typedef struct node

{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q;

if (bt){ADDQ(Q,bt);

while(!EMPTY(Q))

{p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q;

if(p->lchild) (4)___; if(p->rchild) (5)___; }

} }//【北京科技大学 2000 二、(10分)】

60．设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node

{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } /*call form :if(t!=NULL) count(t);*/ 【上海大学 2000 一、3 (10分)】

61 …… 此处隐藏：5203字，全部文档内容请下载后查看。喜欢就下载吧 ……