问答题

已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学2001年】

答案：正确答案：算法的基本设计思想：循环执行以下步骤：沿左分支向下，访问最左端第一个没有左子树的结点(中序遍历第一个结点)，然...

你可能感兴趣的试题

一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶予结点的个数。【上海大学1999年】

答案：正确答案：算法的基本设计思想：采用队列结构按层次遍历，遍历K层时记录叶子结点个数。算法的代码： int LeafKlev...

已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[L,n]和POST[L．n]中(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild，data，rchild)，其中data为数据域，lchild与rchild分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用NULL表示)。【北京航空航天大学2003年】

答案：正确答案：算法的基本设计思想：开始时考查整个中序序列和后序序列，将中序序列和后序序列的起始信息封装到结构体中，入栈。当栈...

已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学2001年】

答案：正确答案：算法的基本设计思想：循环执行以下步骤：沿左分支向下，访问最左端第一个没有左子树的结点(中序遍历第一个结点)，然...

写出中序线索二叉树的线索化过程(已知二叉树T)。【山东大学2000年】

答案：正确答案：算法的基本设计思想：递归地将左子树中序线索化，接着判断若没有左孩子，则左指针指向前驱结点，若前驱不空则给前驱加...

编写程序段，利用中序全线索树求其中任意结点p的前序后继结点，结果仍用p指出。设线索树不带头结点，其中序序列第一个结点的左标志和最后一个结点的右标志皆为0(非线索)，对应指针皆为空。【北京工业大学2000年】

答案：正确答案：算法的基本设计思想：若p有左子女，则左子女就是其前序后继；若p无左子女而有右子女，则p的右子女就是p的前序后继...

写出在中序线索二叉树里查找指定结点在后序下的前驱结点的算法。【河海大学1998年】

答案：正确答案：算法的基本设计思想：在后序序列中，若结点p有右子女，则右子女是其前驱；若无右子女而有左子女，则左子女是其前驱。...

已知中序线索二叉树T的右予树不空。设计算法，将s所指的结点作为T的右子树中的一个叶子结点插入进去，并使之成为T的右子树(中序序列)的第一个结点(同时要修改相应的线索关系)。【合肥工业大学2001年】

答案：正确答案：算法的基本设计思想：若使新插入的叶子结点s成为T右子树中序序列的第一个结点，则应在T的右子树中最左面的结点(设...

二叉树排序方法如下：1)将第一个数据放在树根。2)将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树。3)利用中序遍历打印排序结果。4)试用PASCAL或C语言编写二叉树的排序程序。【浙江大学1995年】

答案：正确答案：直接按照题目中思想编写程序即可。算法的代码： BiTree Creat(){ ／／生成并中序输出二叉排序树 s...

编程求以孩予一兄弟表示法存储的森林的叶了结点数。要求描述结构。【北京工业大学2000年】【北京交通大学2007】

答案：正确答案：算法的基本设计思想：当森林(树)以孩子一兄弟表示法存储时，若结点没有孩子(fch-NULL)，则它必是叶子结点...

以孩予一兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学1999年】

答案：正确答案：由孩子一兄弟链表表示的树，求深度的算法的基本设计思想：采用递归算法，若树为空，深度为0；若第一子女为空，深度为...

将由图3-2所示的三棵树组成的森林转换为二叉树。(只要求给出转换结果)【南京航空航天大学1998年】

答案：正确答案：森林转换为二叉树的三步： 1)连线(将兄弟结点相连，各树的根看作兄弟)。 2)切线(保留最左边子女为独生子女，...

已知一个森林的先序序列和后序序列如下，请构造出该森林。1)先序序列：ABCDEFGHIJKLMNO。2)后序序列：CDEBFHIJGAMLONK。【合肥工业大学2000年】

答案：正确答案：森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林，如图3-7所...

【计算题】
假定用于通信的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计赫夫曼编码。【上海海事大学1998年】

答案：

给定集合{15，3，14，2，6，9，16，17}。1)用口表示外部结点，用。表示内部结点，构造相应的Huffman树。2)计算它的带权路径长度。3)写出它的Huffman编码。【山东大学1998年】

答案：正确答案：1)如图所示

2)wpl=(2+3)*5+6*4+(9+14+15)*3十(16+17)...