数据结构单元练习(共22页).doc

《数据结构单元练习(共22页).doc》由会员分享，可在线阅读，更多相关《数据结构单元练习(共22页).doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上单元练习7一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）树结构中每个结点最多只有一个直接前驱。（）（2）完全二叉树一定是满二查树。（）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同

2、，对于这种情况应该做特殊处理。（）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。（）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。 二填空题（1） 在树中，一个结点所拥有的子树数称为该结点的 度 。（2） 度为零的结点称为 叶（或叶子，或终端） 结点。（3） 树中结点的最大层次称为树的 深度（或高度） 。（4） 对于二叉树来说，第i层上至多有 2i-1 个结点。（5） 深度为h的二叉树至多有 2h-1 个结点。（6） 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。（7） 有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。（8） 哈夫曼树是带权路

3、径长度 最小 的二叉树。（9） 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。（10） 某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC 。（11） 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。（12） 已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。（13） 由树转换成二叉树时，其根结点无 右子树 。（14） 采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。（15） 采用二叉链表存储的n个结点的二叉树，共有空指针 n+1 个。（16）

4、 前序为A，B，C且后序为C，B，A的二叉树共有 4 种。ACBABCABCACB（17）三个结点可以组成 2 种不同形态的树。（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i 。（19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。ABFGHDCE（20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。ABFGHDCE三选择题（1）树最适合用来表示（ D ）。 A有序数据元素 B无序数据元素 C元素之间无联系的数据 D元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（ D ）种。 A2 B3 C4 D5（3

5、）根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。 A3 B4 C5 D6（4）在一棵具有五层的满二叉树中，结点的总数为（ B ） A16 B31 C32 D33（5）具有64个结点的完全二叉树的深度为（ C ） A5B6 C7 D8（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ A ）。 A不发生改变 B发生改变 C不能确定 D以上都不对（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ C ）。 AA在B右方 BA是B祖先 CA在B左方 DA是B子孙（8）下列4棵树中，（ B ）不是完全二叉树。 A B C DABECDABCDABEFC

6、DABEGFDCD（9）如右图所示的二叉树，后序遍历的序列是（ D ）ABADECFGHI A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A（10）对于下边的二叉树，其中序序列为 （ A ）ADBEHAFCG BDBHEAFCG CABDEHCFG DABCDEFGH （11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列为（ D ）。 A ACBEDBDECABCDEABC DCEDBA（12）具有n（n1）个结点的完全二叉树中，结点i（2in）

7、的左孩子结点是（ D ）。A2iB2i+1C2i-1 D不存在（若2ilchild & t-rchild) k+; count(t-lchild); count(t-rchild);2. 求二叉树中值为最大的元素。int maxnode(BT t, int max) if (t) if (t-datamax) max=t-data;max=maxnode(t-lchild,max);max=maxnode(t-rchild,max);3将二叉树各结点存储到一维数组中。void create(BT t,int a ,int i) if (t) ai=t-data; create (t-lchil

8、d, a, 2*i); create (t-rchild, a, 2*i+1);4前序输出二叉树中各结点及其结点所在的层号。void preorderlevel (BT t,int h) / t的层数为h if (t!=NULL) printf (“%d,%d”,t-data, h); preorderlevel (t-lchild, h+1); preorderlevel (t-rchild, h+1);5. 求二叉树的宽度 思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BT *T) in

9、t front=-1,rear=-1; / 队列初始化 int flag=0,count=0,p; / p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值 if (T!=NULL) rear+; qrear=T; flag=1; p=rear; while (frontlchild!=NULL) rear+; qrear=T-lchild; count+; if (T-rchild!=NULL) rear+; qrear=T-rchild; count+; if (front=p) / 当前层已遍历完毕 if (flag-1) T=stacktop; top-; if (T-c

10、hild!=NULL|T-rchild!=NULL) / 交换结点的左右指针 temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; if (T-lchild!=NULL) top+; stacktop=T-lchild; if (T-rchild!=NULL) top+; stacktop=T-rchild; main() int I,j,k,l; printf(“n”); root=CreateBinTree(); Inorder (root);i=CountNode (root); j=CountLeafs (root);k=Depth (roo

11、t); l=Width (root); printf(“nThe Node s Number:%d”,i); printf(“nThe Leafss Number:%d”,j); printf(“nThe Depth is:%d”,k); printf(“nThe width is:%d”,l); Swap(root); Printf(“nThe swapTree is:”);Inorder(root);7解：int h=-1,lh=1,count=0;charx=c; / 赋初值Level (BinTree T,int h,int lh) / 求X结点在树只的层树 if (T=Null) h

12、=0; else if (T-data=x) h=lh; count=h; else h+; Level(T-lchild,h,lh); if (h=-1) Level(T-rchild,h,lh); main() BinTree *(*newroot);Printf(“n”);Root=CreateBinTree();Inorder(root);Printf(“n”);Level(root,h,lh);Printf(“%d”,count);模拟考题一 读程序，写出运行结果1二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。（用大写的英文字母表示，字母之间不要任何间隔符号，最后一个字母

13、后面也不要间隔符号）CFBDADGEtypedef struct BT datatype data; BT *lchild;BT *rchild;BT;void Preorder(BT *T) if (T!=NULL) coutdata; Preorder(T-lchild); Preorder(T-rchild); 解：ABCEDFG 先序遍历2二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。typedef struct BTCFBDADGE datatype data; / 定义结点BT *lchild;BT *rchild;BT;int BTD(BT *T) int ldep,

14、rdep;if (T=NULL)return 0;else ldep= BTD (T-lchild); rdep= BTD (T-rchild); if (ldeprdep)return ldep+1; elsereturn rdep+1;解：4 （求二叉树深度）3二叉树的结构如图所示，试写出执行下列算法后，count的值为多少？CFBDADGEtypedef struct BT datatype data; / 定义结点BT *lchild;BT *rchild;BT;int count=0;void Leafnum(BT *T) if (T!=NULL) if(T-lchild=NULL

15、& T-rchild=NULL)count+; Leafnum(T-lchild); Leafnum(T-rchild); 解：3 （求叶结点数） (2，3，4改为程序填空)二 程序填空1填空完成二叉树按层次遍历的程序typedef struct BT datatype data; / 定义结点BT *lchild;BT *rchild;BT;void Levelorder(BT *T) / 层次遍历 int i,j; BT *q100,*p; p=T; if ( p!=NULL ) i=1;qi=p;j=2; while (i!=j) p=qi;coutdata ; if ( p-lchil

16、d!=NULL ) qj= p-lchild ;j+; if (p-rchild!=NULL) qj= p-rchild ;j+; i+; 三 应用题1 将下列二叉树转换为森林。DABEGICFHJK解：DABIHDECFGJK2 画出和下列二叉树相应的森林。DABHCJEKGFIM解：（根右边的子树肯定是森林，而孩子结点的右子树均为兄弟）3 某二叉树的结点数据采用顺序存储，其结构如下：1234567891011121314151617181920EAFDHCGIB（1）画出该二叉树（2分）（2）写出结点值为D的父结点及左、右子树（3分）解：ADHFGECBI（1）（2） D的父结点为AD的左

17、子树为CD的右子树为空4 某二叉树的存储如下：12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）（2）写出该树的中序遍历的结点序列（2分）BDJHGACFEI解：（1） （2）中序遍历的结点序列：E C B H F D J I G A5 某二叉树的存储如下：12345678910lchild00237580101DataJHFDBACEGIrchild0009400000 其中根结点的指针为6，lchil

18、d、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）（2）写出该树的后序遍历的结点序列（2分）BDJHGACFEI解：（1） （2）后序遍历的结点序列：E C H F J I G D B A6 已知一棵二叉树结点的中序遍历序列为：DEBAFCHG，后序遍历序列：EDBFHGCA，试恢复该二叉树，并写出它的先序遍历的序列。解：恢复的二叉树BEGFDCHAD 先序遍历序列为：A B D E C F G H7 已知一棵二叉树的后序遍历序列为：ACDBGIHFE，中序遍历序列为：ABCDEFGHI，试恢复该二叉树，并写出它的层次遍历的序列。DEBAFIHGC答：

19、恢复的二叉树为：其层次遍历序列为：E B F A D H C G I8 已知一棵二叉树结点的先序遍历序列为：EBADCFHGJ，中序遍历序列为：DEBAFCHG，试恢复该二叉树，并写出它的后序遍历的序列。解：恢复的二叉树DEBAFIHGC 后序遍历序列：A C D B G I H F E9 已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的前序遍历的序列。ABCHDDFGEIJ解：前序遍历的序列：A B D E G H J C F I10 对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。*EGFD*B+*A