?A、 A*B+C／D—E＋Ｆ? Ｂ、 AB＊C+D/E—Ｆ+? C、 ABC+*DE—F+／? D、 ABCDED*＋/-+
1４、在线索二叉树中,t所指结点没有左子树得充要条件就是( ).
A、 t—〉left==NULL ??B、 t—>ltａg=＝1? C、 t—>ｌtag==1&&t->ｌefｔ==NULL D、 以上都不对
15、任何一棵二叉树得叶结点在先序、中序与后序遍历序列中得相对次序( )。
A、 不发生改变 ???Ｂ、 发生改变 ?C、 不能确定 ? Ｄ、 以上都不对 16、假定在一棵二叉树中，度为２得结点数为１5，度为１得结点数为3０，则叶子结点数为( )个。 A、 15 ?B、 16??C、 １7 ?D、 ４7 17、在下列情况中,可称为二叉树得就是（ B ）。 A、 每个结点至多有两棵子树得树 ??B、 哈夫曼树 ??
C、 每个结点至多有两棵子树得有序树?? D、 每个结点只有一棵子树
18、用顺序存储得方法,将完全二叉树中所有结点按层逐个从左到右得顺序存放在一维数组R[1、、n]中,若结点Ｒ［ｉ]有左孩子,则其左孩子就是（ )。
A、 Ｒ[2i—1] B、 Ｒ[2i＋１］? ?C、 Ｒ[2i]? ?Ｄ、 R[２/ｉ］
1９、下面说法中正确得就是( )。
A、 度为2得树就是二叉树 ??? B、 度为2得有序树就是二叉树 ?
Ｃ、 子树有严格左右之分得树就是二叉树??? D、 子树有严格左右之分,且度不超过2得树就是二叉树
20、树得先根序列等同于与该树对应得二叉树得( )。
A、 先序序列 B、 中序序列 ? C、 后序序列 Ｄ、 层序序列
21、按照二叉树得定义，具有3个结点得二叉树有（ C )种。
Ａ、 3 Ｂ、 4 ?C、 ５??D、 ６
２２、由权值为3，6,7,２，5得叶子结点生成一棵哈夫曼树,它得带权路径长度为( A ）。
A、 5１????B、 23 ??Ｃ、 5３ D、 74 二、判断题
( )1、存在这样得二叉树,对它采用任何次序得遍历,结果相同。
（ ）2、中序遍历一棵二叉排序树得结点,可得到排好序得结点序列。
（ )3、对于任意非空二叉树,要设计其后序遍历得非递归算法而不使用堆栈结构,最适合得方法就是对该二叉树采用三叉链表。
( )4、在哈夫曼编码中，当两个字符出现得频率相同时,其编码也相同，对于这种情况应做特殊处理。
(√ ）5、一个含有n个结点得完全二叉树,它得高度就是?log2ｎ?＋１。 (√ ）6、完全二叉树得某结点若无左孩子,则它必就是叶结点。 三、填空题
１、具有n个结点得完全二叉树得深度就是 ?log2n?+1 ．
2、哈夫曼树就是其树得带权路径长度 最小 得二叉树。
3、在一棵二叉树中,度为0得结点得个数就是n０,度为2得结点得个数为n2，则有ｎ０= Ｎ２+1 。
4、树内各结点度得 最大值 称为树得度。 四、代码填空题
1、函数InOrderTｒａvｅｒsｅ(Bitree bt）实现二叉树得中序遍历,请在空格处将算法补充完整。 void InＯrderTraversｅ(BiＴree bt)｛ ? iｆ( ){ ? ?IｎOrderTraverse（ｂt—〉lchild）; ?? prｉntf(“%c”，bt—〉daｔa)； ?? ; ??}
?}
2、函数deptｈ实现返回二叉树得高度，请在空格处将算法补充完整。 iｎt ｄepｔh(Bitree *t)｛ ??iｆ(t==NULＬ) ?? ｒetuｒn ０; ｅlｓe｛ ??hl=dｅｐtｈ(t—＞lchｉld）；
???hr= depth（t—〉rchiｌd) ； ???if( hl〉hr ） ?? returｎ hl+1； ? ?ｅlｓe ? retuｒｎ hr+1； ???｝ ?｝
3、写出下面算法得功能。 Bitｒｅｅ *function（Biｔreｅ ＊bｔ）{ Ｂitｒｅｅ *t,*ｔ１,*t2; ｉf（bt==NULＬ) ??t=NＵＬL； ?ｅlse｛ ??t=(Ｂitｒee ＊)malloc(ｓiｚｅｏf（Bitrｅe）)； ???t—〉data=bt-〉ｄata; ? ?t1=ｆuｎｃtｉon(bt-＞left)； ?? t2＝funｃtion(bt-〉ｒｉght); ???t->left=t2;
???ｔ—〉ｒｉghｔ=t1； ｝ ? retｕrn（t）; }
答案：交换二叉树结点左右子树得递归算法 ４、写出下面算法得功能.
void fuｎctiｏn(Bitrｅｅ *t){ iｆ（p！=ＮULL)｛ functｉｏｎ（ｐ—〉lchild); ｆｕncｔioｎ(ｐ－>ｒｃhild）; prｉntf（“％ｄ”,p-〉dａta);
｝ ｝
答案:二叉树后序遍历递归算法 五、综合题
1、假设以有序对＜p,ｃ〉表示从双亲结点到孩子结点得一条边,若已知树中边得集合为{〈ａ,b〉，<ａ,ｄ>, (1)哪个结点就是根结点？ （2）哪些结点就是叶子结点？ （3）哪些结点就是k得祖先? （４）哪些结点就是j得兄弟? (5)树得深度就是多少？。 ２、假设一棵二叉树得先序序列为EBADCFHGIKJ，中序序列为ABCDEFＧHIJK，请画出该二叉树． 3、假设用于通讯得电文仅由8个字母A、B、C、D、E、F、Ｇ、H组成，字母在电文中出现得频率分别为:０、07,0、19,0、02,0、06,0、3２,0、03,0、２1,０、10。请为这8个字母设计哈夫曼编码。 10001A 000B 10138010621C 10000170121G032301ED 1001E 11F 10001G 01H 0017A10H01116D19B50123CF答案： 4、已知二叉树得先序遍历序列为AＢＣDEFGH，中序遍历序列为CBEＤFAGＨ,画出二叉树。 答案:二叉树形态 ABCEDFGH ５、试用权集合{1２，4,5，6，1,2}构造哈夫曼树,并计算哈夫曼树得带权路径长度。 答案： 301218743125116 WPL=1２*１＋（４+5＋６)＊3＋（1+2)＊4=１２+45+12=6９ ６、已知权值集合为｛5,7,２，3，6,９},要求给出哈夫曼树,并计算带权路径长度ＷPL。 答案:(１)树形态: 321367919105523 (２)带权路径长度:ＷPL=（6+7＋9)*2+5*３+(2＋3）*4=44＋1５+20=7９ 7、已知一棵二叉树得先序序列：ABDGJEＨCFIKＬ;中序序列:ＤJGBＥHACKILＦ．画出二叉树得形态。 ABDGJEHKILCF答案: ８、一份电文中有６种字符：A，Ｂ,Ｃ,D,E,Ｆ,它们得出现频率依次为１6,5，9,3,30,1，完成问题： （1）设计一棵哈夫曼树;(画出其树结构） （2)计算其带权路径长度WＰL; 答案:（1）树形态: 6430341618995413 （２)带权路径长度:WPＬ＝30*1+１６＊2+9*3+５*4+(1+3)*5=3０+32+27+20+２0＝129 9、已知某森林得二叉树如下所示,试画出它所表示得森林。 ABCEDHFG答案: ABC DEGFH 10、有一分电文共使用5个字符；ａ,b，c，d，e，它们得出现频率依次为4、7、５、２、９，试构造哈夫曼树,并给出每个字符得哈夫曼编码。 11、画出与下图所示得森林相对应得二叉树,并指出森林中得叶子结点在二叉树中具有什么特点。 ABCDIJMNEFGKL １2、如下所示得二叉树,请写出先序、中序、后序遍历得序列. 答案:先序:FDBACEGIHＪ 中序:ABCDＥFGHIJ 后序：ACBEDHＪIGF 六、编程题 1、编写求一棵二叉树中结点总数得算法。 答案： (以先序遍历得方法为例) ｖｏｉd cｏunt_preorｄer（Biｔree *t, iｎt *n） { if(ｔ!=NULL） {＊n+＋； count_preorｄｅr(ｔ－〉lchild); coｕnｔ_pｒeｏrdｅr(ｔ—〉lｃhild); } } H第七章 图 一、选择题 １、１2、对于具有n个顶点得图，若采用邻接矩阵表示，则该矩阵得大小为( )。 A、 n ? ?B、 n2 C、 n—1 ? D、 (ｎ-1)2 ２、如果从无向图得任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定就是( ）. Ａ、 完全图?? B、 连通图 Ｃ、 有回路? D、 一棵树 3、关键路径就是事件结点网络中( )。 A、 从源点到汇点得最长路径 ? B、 从源点到汇点得最短路径? C、 最长得回路 ??D、 最短得回路 ４、下面（ ）可以判断出一个有向图中就是否有环(回路)。 ?A、 广度优先遍历? ???B、 拓扑排序? ?? C、 求最短路径 ? D、 求关键路径 5、带权有向图G用邻接矩阵A存储,则顶点i得入度等于A中（ ）. ?A、 第ｉ行非无穷得元素之与 ?B、 第i列非无穷得元素个数之与 C、 第i行非无穷且非0得元素个数? D、 第i行与第i列非无穷且非０得元素之与 6、采用邻接表存储得图,其深度优先遍历类似于二叉树得（ ）。 A、 中序遍历 B、 先序遍历 ?C、 后序遍历 ?D、 按层次遍历 7、无向图得邻接矩阵就是一个( ）。 A、 对称矩阵 B、 零矩阵 ?? C、 上三角矩阵 Ｄ、 对角矩阵 8、当利用大小为N得数组存储循环队列时,该队列得最大长度就是（ )。 Ａ、 N—2 B、 N—1?? ?C、 Ｎ? ??D、 N＋1 ９、邻接表就是图得一种（ ）. A、 顺序存储结构 B、 链式存储结构 C、 索引存储结构 Ｄ、 散列存储结构 1０、下面有向图所示得拓扑排序得结果序列就是（ )。 A、 １25634 ??B、 ５１6234 C、 １2３４５６ ?Ｄ、 52164３ １１、在无向图中定义顶点ｖi与vj之间得路径为从vｉ到vj得一个( ）。 A、 顶点序列 B、 边序列 ? C、 权值总与 D、
数据结构试题库及答案
