数据结构(树与图部份)练习题
一、填空题
1.不考虑顺序的3个结点可组成种不同形态的树，种不同形态的二叉树。
2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数
为：。
3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。
4.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是；结点i
的左孩子结点的编号是，结点i的右孩子结点的编号是。
5.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是______；结点i的
左孩子结点编号是______，右孩子结点编号是______。
6.在有n个叶子结点的Huffman树中，总的结点数是：______。
7.图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限
集合，E(G)是______的有限集合。
8.遍历图的大体方式有优先搜索和优先搜索两种方式。
9.图的遍历大体方式中是一个递归进程。
10.n个极点的有向图最多有条弧；n个极点的无向图最多有条边。
11.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是。
12.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。
二、单项选择题
1.树型结构的特点是：任意一个结点：（）
A、可以有多个直接前趋
B、可以有多个直接后继
C、至少有1个前趋
D、只有一个后继
2. 如下图所示的4棵二叉树中，（ ）不是完全二叉树。
A B C D
3. 深度为5的二叉树最多有（ ）个结点。
A 、16
B 、32
C 、31
D 、10 4. 64个结点的完全二叉树的深度为：（ ）。
A 、8
B 、7
C 、6
D 、5
5. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行
编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（ ）。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中，所有极点的度之和等于边数的（ ）倍。 A 、1/2 B 、1 C 、2 D 、4
7. 设有13个值，用它们组成一棵Huffman 树，则该Huffman 树中共有( )个结点。 A 、13 B 、12 C 、26 D 、25
8. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结
点及右孩子结点的编号别离为( )。
A 、2,14
B 、2,15
C 、3,14
D 、3,15
9. 若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x ，它的双亲结
点及左孩子结点的编号别离为( )。
A 、2,11
B 、2,10
C 、3,9
D 、3,10
10. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行
编号，根结点编号为1，则编号最大的非叶结点的编号为：
A 、48
B 、49
C 、50
D 、51 11. 无向图的邻接矩阵是一个( )。 A 、对称矩阵 B 、零矩阵 C 、上三角矩阵 D 、对角矩阵 12. 由64个结点组成的完全二叉树，其深度为：( )。 A 、8 B 、7 C 、6 D 、5
13. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结
点及右孩子结点的编号别离为( )。
A 、2,14
B 、2,15
C 、3,14
D 、3,15 14. 图示二叉树的中序遍历序列是：（ ）
A 、abcdgef
B 、dfebagc
C 、dbaefcg
D 、defbagc 15. 图示二叉树的后序遍历序列是：（ ）
A 、ABCDEFGH
B 、BDAFEHG
C C 、DBFHGECA
D 、HGFEDCBA
16. 邻接表是图的一种（ ）。
A 、顺序存储结构
B 、链式存储结构
C 、索引存储结构
D 、散列存储结构 17. 给定有向图如右图所示，则该图的一个强连通分量是：（ ）。 A 、{A,B,C,F} B 、{B,C,F} C 、{B,C,D,F} D 、{C,D,E,F}
18. 已知一个有向图的邻接矩阵表示，要删除所有从第i 个结点发出的边，应该： A 、将邻接矩阵的第i 行删除 B 、将邻接矩阵的第i 行元素全部置为0 C 、将邻接矩阵的第i 列删除 D 、将邻接矩阵的第i 列元素全部置为0
三、判断题
1. （ ）非线性数据结构可以顺序存储，也可以链接存储。
2. （ ）非线性数据结构只能用链接方式才能表示其中数据元素的彼此关系。
3. （ ）完全二叉树必然是满二叉树。
4. （ ）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
5. （ ）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。
6. （ ）度为1的有序树与度为1的二叉树是等价的。
7. （ ）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。 8. （ ）已知一棵二叉树的先序序列和后序序列，就必然能构造出该二叉树。 9. （ ）在霍夫曼树中，权值最小的结点离根结点最近。
10.
( )对任意一个图，从它的某个极点动身进行一次深度优先或广度优先遍历可访问到该图的每一个极点。
A B D C E F G H
11.（）线性数据结构可以采用顺序存储结构或链式存储结构，而非线性数据结构只能
采用链式存储结构。
12.（）二叉树中的叶子结点就是二叉树没有左、右子树的结点。
13.（）若是一棵树中某结点的度为1，则该结点仅有一棵子树。
14.（）在有向图中，若存在有向边
15.（）对任意一个图，从它的某个极点动身进行一次深度优先或广度优先遍历后，并
非必然能访问到该图的每一个极点。
16.（）用邻接矩阵法存储一个图时，在不考虑紧缩存储的情况下，所占用的存储空间
大小只与图中结点个数有关，而与图的边数无关。
四、简答题
1.什么叫有序树？什么叫无序树？有序树和二叉树的不同是什么？
2.什么叫完全二叉树？什么叫满二叉树？它们之间的关系是什么？
3.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？
五、综合题
1.如图所示的两棵二叉树，别离给出它们的顺序存储结构。
第1棵树
第2棵树
2.已知一棵二叉树的中序、后序序列别离如下：
中序：D C E F B H G A K J L I M
后序：D F E C H G B K L J M I A
要求：⑴画出该二叉树；
⑵写出该二叉树的先序序列。
3.一棵二叉树的先序、中序和后序序列别离如下，其中有一部份未显示出来，试求出空
格处的内容，并画出该二叉树。
先序：_ B _ F _ I C E H _ G
中序：D _ K F I A _ E J C _
后序：_ K _ F B H J _ G _ A
4.将下图中的树转化为二叉树，并写出转换后的二叉树的后序遍历序列。
5.将下图所示的树转换成二叉树，并写出转换后二叉树的先序、中序、后序遍历结果。
6.将下列一棵二叉树进行前序遍历、中序遍历、后序遍历，并转化为树。
7.写出下面二叉树的先序、中序、后序遍历结果，并将它转换为树。
8.别离写出下图所示二叉树的先序、中序和后序遍历序列。
9.写出下图中的二叉树先序和后序遍历序列。
10. 输入一个正整数序列{100，50，302，450，66，200，30，260}，成立一棵二叉排序树，
要求：⑴ 画出该二叉排序树；
⑵ 画出删除结点302后的二叉排序树。
11. 按给出的一组权值{4，5，7，8，11}，成立一个霍夫曼树，并请计算出该树的带权路
径长度WPL 。
12. 以{5,9,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度
(WPL)。
13. 以{4,7,10,15,23}作为叶子结点的权值构造一棵Huffman 树，并求出其带权路径长度。 14. 以{5,6,7,8,9,10,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权
路径长度(WPL)。
15. 以{10,12,16,21,30}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长
度(WPL)。
16. 如右所示的有向图，请给出它的：
（1）
（2） 邻接矩阵； （3） 邻接表；
（4） 强连通分量。
17.
已知一棵二叉树的中序和先序序列如下，求该二叉树的后序序列，并将它转换为树。 先序结果：A,B,E,F,C,D,G,H,I 中序结果：E,F,B,C,G,H,I,D,A
18. 已知一棵二叉树的中序和后序遍历结果如下所示，求该二叉树的先序遍历序列。 中序结果：E,F,B,C,G,H,I,D,A 后序结果：F,E,I,H,G,D,C,B,A
19. 请给出按自左向右的顺序依次将关键字为{30，5，20，23，9，27，6，14，45，22}的
记录插入到一个初始时为空的二叉排序树后所成立的二叉排序树。
20. 请将序列51，17，60，32，6，10，23，3，80，40，44，7排列为二叉排序树。 21. 请将序列28，55，06，33，161，81，91，11，25，56，57，02排列为二叉排序树。 22. 构造插入序列为{10，18，3，8，12，2，7，13}的二叉排序树，（要求进程）。 23. 请给出下面的二叉树的先序、中序和后序遍历结果。
24.请给出下面的有向图的邻接矩阵、邻接表形式的存储结构，并计算出每一个极点的入
度和出度。
25.已知某无向图的邻接表存储结构如下图所示，（1）请画出此无向图，（2）给出无向图
的邻接矩阵表示。
第六章树 一．名词解释： 1 树 2。结点的度 3。叶子 4。分支点 5。树的度 6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树 11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树 16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树 21 哈夫曼树 二、填空题 1、树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。 对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2、一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B 的________ 3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。 4、二叉树第i(i>=1)层上至多有______个结点。 5、深度为k(k>=1)的二叉树至多有______个结点。 6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉 树，但反之不然。 8、具有n个结点的完全二叉树的深度为______。 9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有： （1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。 （3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 10.二叉树通常有______存储结构和______存储结构两类存储结构。 11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL. 13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。 17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL) {if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } } 18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。 19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：
习题六树和二叉树 6.1 单项选择题 1. 如图8.7所示的4棵二叉树，_C___不是完全二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__。 A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B__。 A. 正确 B. 错误
5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。 A. 正确 B. 错误 6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B _。 A. 正确 B. 错误 7. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。 A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列___B _。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是D____。 A. acbed B. decab C. deabc D. cedba 10．设a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在b 前的条件是 B 。 A ．a 在b 的右方 B ．a 在b 的左方 C ．a 是b 的祖先 D ．a 是b 的子孙 图8.9 一棵二叉树
11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。B A ．15 B ．16 C ．17 D ．47 12.某二叉树的前序遍历结点访问顺序是abdgcefh ，中序遍历的结点访问顺序是dgbaechf ，则其后序遍历的结点访问顺序是D ___ _。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__B __。 A. 正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6 16. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论___A _是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 图8.10 一棵二叉树
数据结构(树与图部份)练习题 一、填空题 1.不考虑顺序的3个结点可组成种不同形态的树，种不同形态的二叉树。 2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数 为：。 3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。 4.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是；结点i 的左孩子结点的编号是，结点i的右孩子结点的编号是。 5.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是______；结点i的 左孩子结点编号是______，右孩子结点编号是______。 6.在有n个叶子结点的Huffman树中，总的结点数是：______。 7.图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限 集合，E(G)是______的有限集合。 8.遍历图的大体方式有优先搜索和优先搜索两种方式。 9.图的遍历大体方式中是一个递归进程。 10.n个极点的有向图最多有条弧；n个极点的无向图最多有条边。 11.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是。 12.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。 二、单项选择题 1.树型结构的特点是：任意一个结点：（） A、可以有多个直接前趋 B、可以有多个直接后继 C、至少有1个前趋 D、只有一个后继
2. 如下图所示的4棵二叉树中，（ ）不是完全二叉树。 A B C D 3. 深度为5的二叉树最多有（ ）个结点。 A 、16 B 、32 C 、31 D 、10 4. 64个结点的完全二叉树的深度为：（ ）。 A 、8 B 、7 C 、6 D 、5 5. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（ ）。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中，所有极点的度之和等于边数的（ ）倍。 A 、1/2 B 、1 C 、2 D 、4 7. 设有13个值，用它们组成一棵Huffman 树，则该Huffman 树中共有( )个结点。 A 、13 B 、12 C 、26 D 、25 8. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结 点及右孩子结点的编号别离为( )。 A 、2,14 B 、2,15 C 、3,14 D 、3,15 9. 若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x ，它的双亲结 点及左孩子结点的编号别离为( )。 A 、2,11 B 、2,10 C 、3,9 D 、3,10 10. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点编号为1，则编号最大的非叶结点的编号为： A 、48 B 、49 C 、50 D 、51 11. 无向图的邻接矩阵是一个( )。 A 、对称矩阵 B 、零矩阵 C 、上三角矩阵 D 、对角矩阵 12. 由64个结点组成的完全二叉树，其深度为：( )。 A 、8 B 、7 C 、6 D 、5 13. 若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x ，它的双亲结 点及右孩子结点的编号别离为( )。 A 、2,14 B 、2,15 C 、3,14 D 、3,15 14. 图示二叉树的中序遍历序列是：（ ）
图练习： 1．图中有关路径的定义是（）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度 遍历是一个递归过程 9．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图 进行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 10. 关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路
一、填空题 1. 一完全二叉树共有500个结点，则在该二叉树中有 个度为2的结点。 2. 设某二叉树的前序遍历序列为:ABCDEFGHI ，中序遍历序列为:BCAEDGHFI ，则该二叉树的后序遍历序列是 。 3. 对于一个稀疏图，在求该图对应的最小生成树时，Prim 算法和kruskal 算法哪一个算法效率更高 。 4. 对于一个n 个结点的满二叉树，假设该树有m 个树叶，深度为h ，则 h= 。 5. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 ，至多为 。 6. 一棵有n 个结点的满二叉树有_ _ 个叶子，该满二叉树的深度为_ __。 7. 设F 是由T1,T2,T3三棵树组成的森林,与F 对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉 树B 的左子树中有__ _个结点。 8. 一颗含有101个结点的完全二叉树存储在数组A[1..101]中，若A[k]为叶子结点，则k 的最小值是 。 9. 一颗深度为h 的完全二叉树上的结点总数最小值为 ，最大值为 。 二、选择题 1. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T 中的叶子数为（ ）。 A ．5 B ．6 C ．7 D ．8 1. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（ ）。 A ．G 中有弧
第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为 ( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ ） A ．5 B ．6 C ．7 D ．8 【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 【南京理工大学2000 一、 17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T 。其余结点分成为m （m>0）个(（2）) 的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个 不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定 义为1，其他结点的层数等于其父结点所在层数加上1。令T 是一棵二叉树，Ki 和Kj 是T 中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi 和λKj ，当关系式│ λKi-λKj │≤1一定成立时，则称T 为一棵（(5)）。供选择的答案： （1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1 个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 （5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院1999二、 2(5分）】 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 【北京工商大学2001一.7(3 分)】 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2
数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74
E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右 子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A ．不确定 B ．2n C ．2n+1 D ．2n-1 7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ） A ．?logn ?+1 B ．logn+1 C ．?logn ? D ．logn-1 9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1= 数据结构练习题 一、单项选择题 1、以下数据结构中哪一个是非线性结构？（C） A. 队列 B. 栈 C. 二叉树 D. 线性表 线性结构：向量列表堆栈队列 非线性结构：树形图形 2、栈中元素的进出原则是（B ） A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出 3、队列中元素的进出原则是（ A ） A. 先进先出 B. 后进先出 C. 队空则进 D. 队满则出 4、从逻辑上可以把数据结构分为（C）两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造性结构 5、在一颗二叉树上第三层的节点数最多为（ B ）。 A.2 B.4 C.6 D.8 6、由权值分别为11，8，6，2，5的叶子结点生成一颗哈夫曼树，它的带权路径长度为（A ）。 A.71 B.23 C.48 D.53 7、串是一种特殊的线性表，其特殊性体现在（ B ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符 8、（ B?? ）遍历方法在遍历它的左子树和右子树后再遍历它自身。 A．先序遍历 B. 后序遍历 C. 中序遍历 D. 层次遍历 9、判断一个循环队列( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针,则为满队列的条件是( C )。 A． front== rear B．front!= rear C． front==( rear+1) % m0 D． front!=( rear+1) % m0 10、设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 11、下列说法正确的是(A) A．数据是数据元素的基本单位 B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 一、单选题 1、树最适合用来表示（）。 A.元素之间具有分支层次关系的数据 B.有序数据元素 C.元素之间无联系的数据 D.无序数据元素 正确答案：A 2、在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是（）。 A.5 B.4 C.3 D.2 正确答案：B 3、下列陈述中正确的是（）。 A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中每个结点最多只有两棵子树，并且有左右之分 D.二叉树中必有度为2的结点 正确答案：C 4、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为（）。 A.2h-1 B.2h+1 C.h+1 D.2h 正确答案：A 解析： A、除根之外，每层只有两个结点，且互为兄弟。 5、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为（）。 A.2h-1 B. 2h+1-1 C. 2h-1-1 D. 2h+1 正确答案：A 解析： A、构成完全二叉树。 6、具有n(n>0)个结点的完全二叉树的深度为（）。 A.⌊ log2(n)⌋ +1 B.⌈log2(n)⌉ C.⌊ log2(n)⌋ D.⌈log2(n)+1⌉ 正确答案：A 7、具有32个结点的完全二叉树有（）个叶子结点。 A.16 B.14 C.15 D.17 正确答案：A 解析： A、对结点按层序编号，32号结点的双亲结点编号为16，则17至32号结点都为叶子，共16个。 8、一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有（）结点。 A.81 B.78 C.80 D.79 正确答案：A 解析： A、完全二叉树的叶子结点只能在最下两层，要使结点最多，这棵二叉树深度 为7，前6层结点数共为63，第6层有32个结点，其中叶子为23个，非叶子为9个，它们的度都为2，第7层只有18个结点，故整棵二叉树结点数为81. 9、具有3个结点的二叉树有（）种。 A.6 B.3 C.5 D.4 正确答案：C 10、若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为（）。 A.15 B.10 C.9 D.不确定 正确答案：B 11、一棵二叉树有35个结点，则所有结点的度之和为（）。 A.16 B.35 C.34 D.33 正确答案：C 12、二叉树是非线性数据结构，所以（）。 A.顺序存储结构和链式存储结构都能存储 B.顺序结构和链式结构都不能使用 C.它不能用链式存储结构存储 第七章 图 一、选择题 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】 3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4 分)】 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、 6(2分）】 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A ．0 B ．1 C ．n-1 D ．n 【北京邮电大学 2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A ．1/2 B ．2 C ．1 D ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学 1999一、14】 A ．5 B ．6 C ．8 D ．9 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点 序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A ．邻接矩阵 B ．逆邻接表 C ．邻接多重表 D ．十字链表 E ．邻接 表 【北京工业大学 2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101 010 A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 1、一颗二叉树的括号表示为“1(2(4，5(6，7))，3)”）。设N代 表二叉树的根，L代表根节点的左子树，R代表根节点的右子树。若 遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（）。 A.NRL B.RLN C.LRN D.RNL 正确答案：D 2、若二叉树（每个节点值为单个字符）的中序遍历序列是abcdef，且c为根节点，则（）。 A.二叉树有两个度为0的节点 B.二叉树的高度为5 C.节点c有两个孩子 D.以上都不对 正确答案：C 解析： C、从中序序列看出，节点c的左右子树均不空。 3、若知道一棵二叉树的（），便可以唯一确定该二叉树。 A.中序序列 B.先序和后序序列 C.中序和后序序列 D.先序序列 正确答案：C 4、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能 是（）。 A.ADCFEG B.ABCDEFG C.DACEFBG D.CABDEFG 正确答案：B 解析： B、当一棵二叉树所有节点的左子树为空时，先序遍历序列 和中序遍历序列相同。先序序列和中序序列可以确定一棵二叉树， 这里由选项A、C和D的中序序列无法确定一棵二叉树。 5、一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（） A.FEDCBA B.CBEFDA C.CBEDFA D.不确定 正确答案：B 6、某棵二叉树中，X节点有左孩子Y节点，则在其先序遍历中 （）。 A.访问Y节点后，接着遍历Y节点的左子树，然后访问X节点 B.访问X节点后，接着遍历Y节点的左子树，然后访问Y节点 C.访问Y节点后立即访问X节点 D.访问X节点后立即访问Y节点 正确答案：D 解析： D、其先序遍历序列为…XY…。 7、关于二叉树（含2个以上的节点）的先序遍历序列中，以下正确 的是（）。 A.先序遍历序列的最后一个节点是根节点 B.先序遍历序列的最后一个节点一定是叶子节点 C.以上都不对 D.先序遍历序列的第一个节点一定是叶子节点 正确答案：B 解析： B、先序遍历过程是：NLR，最后访问的节点的L、R均为空，所以为叶子节点。 8、若一棵完全二叉树中每个节点值为单个字符，其后序遍历序列为CDBFGEA，则其先序遍历序列是（）。 A.ABCDEFG 第6章-数据结构习题题目及答案-树和二叉树-参考答案 一、基础知识题 6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。 【解答】设度为m的树中度为0,1,2,,m的结点数分别为 n0,n1,n2,,nm，结点总数为n，分枝数为B，则下面二式成立 n=n0+n1+n2++nm(1)n=B+1=n1+2n2++mnm+1(2) 由(1)和(2)得叶子结点数n0=1+ 即：n0=1+(1-1)某4+(2-1)某2+(3-1)某1+(4-1)某1=8 6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。 【解答】因为在任意二叉树中度为2的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n,度为1的结点数为n1，则 n=n0+n1+n2n=2n0+n1-11002=2n0+n1 由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501. 注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9 层是满二叉树，第10层都是叶子，虽然解法也对，但步骤多且复杂，极 易出错。 6.3一棵124个叶结点的完全二叉树，最多有多少个结点。 【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。 6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶 子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉 树有501个结点，结果如何？请写出推导过程。 【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子 数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数 是249。若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。 6.5某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二 叉树的总结点数是多少。 【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。 6.6求一棵具有1025个结点的二叉树的高h。 【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-1<1025<211-1，故1025个结点的二叉树最低高为11。 6.7一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉 树最少有多少结点。 【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最 少结点数是2h-1。 6.8将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全 三叉树的高度是多少。 【解答】设含n个结点的完全三叉树的高度为h，则有 <2n< 数据结构——树练习 注：“[]”为向上取整，“{}”为向下取整。 一、填空题 1、二叉树第i(i>=1)层上至多有__2^(i-1)___个结点。 2、深度为k(k>=1)的二叉树至多有___2^k -1__个结点。 3、具有n个结点的完全二叉树的深度为__log2(n+1)____。 4、具有n个结点的二叉树中,一共有____2n___个指针域,其中只有____n-1___个用来指向结点的左右孩子，其余的___n+1_____个指针域为NULL。 5、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的___第一个_____个结点。 6、在____先序____遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 7、具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是____n/2____，编号最小的分支结点序号是___1____，编号最大的叶子结点序号是_____n__，编号最小的叶子结点序号是__n/2 +1_____。 8、先根遍历树和先根遍历与该树对应的二叉树，其结果___相同____（填“相同”或“不同”）。 9、由____一颗树___转换成二叉树时，其根结点的右子树总是空的。 10、若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为___n-1____。 11、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为___n-2m+1___个。 12、现有按中序遍历二叉树的结果为ABC，问有____5__种不同形态的二叉树可以得到这一遍历结果 13、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有____12___个叶子结点。 二、单选题 1、1．以下说法错误的是( 1. ) ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种"分支层次"结构 ⑤任何只含一个结点的集合是一棵树 2.以下说法错误的是( 4 ) ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好 一、单项选择题 1．深度为h的二叉树所含的叶结点个数最多为。 A．2h B．h C．2h D．2h-1 2．设二叉树的先序遍历序列为ABCDE，则二叉树的中序遍历序列不可能是。 A．EDCBA B．ABCDE C．ADEBC D．ABDEC 3．具有12个记录的序列，采用直接插入排序最少比较次数为________。 A．11 B．12 C．132 D．144 4．含有n个顶点的无向连通图，至少包含的边数为________。 A．n B．n-1 C．n(n-1) D．n(n-1)/2 5．在有15个元素的顺序表中，删除一个元素时，平均移动元素的次数为________。 A．14 B．7 C．15 D．8 6．在有11个数据元素的有序表中，采用折半查找，查找长度为4的元素个数为________。 A．2B． 3 C．4 D．5 7．栈操作的原则是 _________。 A．先进先出B．后进先出C．栈顶插入D．栈顶删除 二、填空题 1．有向图G采用邻接矩阵存储，其第i行所有元素之和等于顶点i的______________。 2．快速排序在最坏情况下的时间复杂度为_____________。 3．n个结点的完全二叉树中，从上至下、从左至右进行编号，根结点的编号为1，则最大的分支结点的编号为___________。 4．已知数组A[10..20][5..10]按列优先存储，每个元素占有4个存储单元，且A[10][5]的地址为2000（十进制），则A[15][8]的地址为________________。 5．已知循环队列用数组 A[0..m-1] 存放元素，已知其头、尾指针分别是front 和rear ，则队列中元素个数为。 6．有n个叶结点的哈夫曼树中，总结点个数为。 7．Ｇ为无向图，如果从Ｇ的某个顶点出发进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是_________图。 8．有n（n>0）个结点的二叉树，采用二叉链表作为存储结构，则二叉链表中非空指针的个数为________。 三、判断题 1.（）在顺序表中读取第i个元素所花费的时间与i无关。 2.（）数组可以看成线性表的推广，因此可以对它进行插入和删除运算。 3.（）线性表在采用链式存储时，其部分地址是连续的。 4.（）已知二叉树的层次序列和中序序列，可以唯一的确定一棵二叉树。 5.（）一个带权图的最小生成树是唯一的。 6.（）简单选择排序得比较次数与序列的初始状态无关。 7.（）用邻接矩阵表示图所用的存储空间大小与图的边数成正比。 8.（）对n个元素的有序表用直接插入排序方法进行排序，时间复杂是O(n)。 9.（）在用线性探测法解决冲突所构造的散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。 10.（）在AOE-网中，任何一个关键活动的提前完成，都可以缩短工程的完成时间。 四、应用题 1、已知散列函数为H（i）=⎣⎦2/i，i为后面关键字中第一个字母在字母表中的序号，关键字序列为：Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct， Nov，Dec，散列地址空间为0~13，试用拉链法构造散列表，计算等概率查找成功时的平均查找长度。 2、已知一棵二叉树的先根序序列和中根序序列分别为ABCDEFGHIK和BDCAGFHEKI， （1）画出此二叉树的形态。 （2）画出此二叉树的顺序存储结构图。 第六章树和二叉树 一、判断题 ( t )01、若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 ( f )02、二叉树中每个结点的两棵子树的高度差等于1。 (t )03、二叉树中每个结点的两棵子树是有序的。 ( f )04、二叉树中每个结点有两棵非空子树或有两棵空子树。( f )05、二叉树中所有结点个数是2k-1-1，其中k是树的深度。 (f )06、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 ( f )07、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 (t )08、用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 (t)09、具有12个结点的完全二叉树有5个度为2的结点。( f )10、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。 ( f )11、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。 ( t )12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 二、填空题 01、由3个结点所构成的二叉树有_5_种形态。 02、一棵深度为6的满二叉树有____个分支结点和____个叶子。 03、一棵具有257个结点的完全二叉树，它的深度为____。 04、设一棵完全二叉树有700个结点，则共有____个叶子结点。 05、设一棵完全二叉树具有1000个结点，则此完全二叉树有____个叶子结点，有____个度为2的结点，有____个结点只有非空左子树，有____个结点只有非空右子树。 06、一棵含有n个结点的k叉树，可能达到的最大深度为____，最小深度为____。 07、二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按LRN次序)和中序法(也称对称序法，即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是____。 08、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是____。 三、选择题 ( )01、树最适合用来表示__。 A)有序数据元素 B)无序数据元素 C)元素之间具有分支层次关系的数据 D)元素之间无联系的数据( )02、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为__个。 A)15 B)16 C)17 D)47 ( )03、假定一棵三叉树的结点数为50，则它的最小高度为__。 A)3 B)4 C)5 D)6 ( )04、在一棵二叉树上第5层的结点数最多为__。 A)8 B)16 C)15 D)32 ( )05、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有子树，则左子树是结点__。 A)R[2i+1] B)R[2i] C)R[i/2] D)R[2i-1] ( )06、在一棵具有k层的满三叉树中，结点总数为__。 A)(3k-1)/2 B)3k-1 C)(3k-1)/3 D) 3k ( )07、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为__。 A)29 B)37 C)46 D)44 ( )08、具有n(n>0)个结点的完全二叉树的深度为。 A)⎡log2(n)⎤ B)⎣log2(n)⎦ C)⎣log2(n)⎦+1 D)⎡log2(n)+1⎤( )09、由n个数据元素构造的哈夫曼树，共有( )个结点。A)n-1 B)2n-1 C)2n D)2n+1 ( )10、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序__。 A)不发生改变 B)发生改变 C)不能确定 D)以上都不对 ( )11、设a,b为一棵二叉树上的两个结点，在中序遍历中，a 在b前面的条件是__。 A)a在b的右方 B)a在b的左方 C)a是b的祖先 D)a是b的子孙 ( )12、如图所示，其中__不是完全二叉树。 ( )13、在线索二叉树中，t所指结点没有左子树的充要条件是__。 A)t->lchild==NULL B)t->ltag==1 C)t->ltag==1 && t->lchild==NULL D)以上都不对 ( )14、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__。 A)2h B)2h-1 C)2h+1 D)h+1 ( )15、以下说法中错误的是__。 A)哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近 B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点 C)已知二叉树的前序遍历和后序遍历并不能惟一地确定这棵数据结构练习题
数据结构(树)习题与答案
数据结构图练习题(附答案).doc
数据结构(树和二叉树)练习题与答案2
第6章-数据结构习题题目及答案-树和二叉树-参考答案
数据结构——树习题
数据结构练习题
数据结构习题与答案--树和二叉树
相关主题
文本预览