数据结构——二叉树错题集
本文最后更新于1365天前,其中的信息可能已经有所发展或是发生改变。

2-11

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

遍历顺序 ,令所有遍历中的 根==NULL 遍历顺序都是 左右,即左节点先于右节点,不会改变顺序;

 2-xx

先序序列遍历为 a b c d 的二叉树有多少个?

14

运用卡特兰算式 , n = 4 ,ans = C(n,2*n)/(n+1) = 14

1-5:若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。 

 é”™è¯¯ï¼š

特例: A-B-C 一条线上,C是根节点;

中序遍历:ABC

前序遍历:CBA

2-2

如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最少为:


这不就是满树(h0 = h-1) 节点数 + 1吗

这道题目是 k+k1 +k2+…..kh-2   å…±æœ‰ h-1 个元素

1*(kh-1-1)/(k-1) + 1,选A?

NONONO,读题可知:

最少的情况是根节点加上根节点的k个孩子,加上根节点的第一个孩子的k个孩子,再加上”””,以此类推;

1+k+k+k+k+k (加 h-1 个) ,答案就是(h-1)*k+1,嗯,没有,选D;

( âˆš ï¼‰9.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。

(正确。用二叉链表存储包含n个结点的二叉树,结点共有2n个链域。由于二叉树中,除根结点外,每一个结点有且仅有一个双亲,所以只有n-1个结点的链域存放指向非空子女结点的指针,还有n+1个空指针。)即有后继链接的指针仅n-1个。

( âˆš ï¼‰10. ã€–01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5 

2.  ã€è®¡ç®—机研2000】 ä¸€æ£µæ·±åº¦ä¸º6的满二叉树有 n1+n2=0+ n2= n0-1=31  ä¸ªåˆ†æ”¯ç»“点和 26-1 =32  ä¸ªå¶å­ã€‚

注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。

3. ä¸€æ£µå…·æœ‰ï¼’57个结点的完全二叉树,它的深度为   9    ã€‚

( æ³¨ï¼šç”¨Ã« log2(n) Ã»+1= Ã« 8.xx Ã»+1=9

4. ã€å…¨å›½ä¸“升本统考题】设一棵完全二叉树有700个结点,则共有  350  ä¸ªå¶å­ç»“点。

答:最快方法:用叶子数=[n/2]=350 

http://blog.sina.com.cn/s/blog_8ba111f10100vkm3.html

5. è®¾ä¸€æ£µå®Œå…¨äºŒå‰æ ‘具有1000个结点,则此完全二叉树有 500  ä¸ªå¶å­ç»“点,有  499   ä¸ªåº¦ä¸º2的结点,有   1   ä¸ªç»“点只有非空左子树,有  0    ä¸ªç»“点只有非空右子树。

答:最快方法:用叶子数=[n/2]=500 ï¼Œn2=n0-1=499。 å¦å¤–,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.

6. ã€ä¸¥é¢˜é›†6.7③】 ä¸€æ£µå«æœ‰n个结点的k叉树,可能达到的最大深度为  n  ï¼Œæœ€å°æ·±åº¦ä¸º 2 ã€‚

答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层),但不包括n=0或1时的特例情况。教材答案是“完全k叉树”,未定量。)

树和二叉树练习题及解答

7. ã€96程试题1】  äºŒå‰æ ‘的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按    L R N     æ¬¡åºï¼‰å’Œä¸­åºæ³•ï¼ˆä¹Ÿç§°å¯¹ç§°åºæ³•ï¼Œå³æŒ‰L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是       F E G H D C B         ã€‚ è§£ï¼šæ³•1:先由已知条件画图,再后序遍历得到结果;

法2:不画图也能快速得出后序序列,只要找到根的位置特征。由前序先确定root,由中序先确定左子树。例如,前序遍历BEFCGDH中,根结点在最前面,是B;则后序遍历中B一定在最后面。

法3:递归计算。如B在前序序列中第一,中序中在中间(可知左右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同样处理,则问题得解。

8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为    O(n)   ã€‚

答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。

9. ã€è®¡ç®—机研2001】 ç”¨5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是    33   ã€‚

解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33

树和二叉树练习题及解答

         (15)

(9)        (6)               ï¼ˆæ³¨ï¼šä¸¤ä¸ªåˆå¹¶å€¼å…ˆåŽä¸åŒä¼šå¯¼è‡´ç¼–码不同,即哈夫曼编码不唯一)

 4    5    3     (3)             ï¼ˆæ³¨ï¼šåˆå¹¶å€¼åº”排在叶子值之后)

1        2

(注:原题为选择题:A.32            ï¼¢ï¼Ž33         ï¼£ï¼Ž34       ï¼¤ï¼Ž15)

三、单项选择题(每小题1分,共11分)

( C  ï¼‰1. ä¸å«ä»»ä½•ç»“点的空树         ã€‚

(A)是一棵树;                         ï¼ˆï¼¢ï¼‰æ˜¯ä¸€æ£µäºŒå‰æ ‘;  

(C)是一棵树也是一棵二叉树;           ï¼ˆï¼¤ï¼‰æ—¢ä¸æ˜¯æ ‘也不是二叉树

答:以前的标答是B,因为那时树的定义是n≥1

( C  ï¼‰2.二叉树是非线性数据结构,所以             ã€‚

(A)它不能用顺序存储结构存储;           ï¼ˆï¼¢ï¼‰å®ƒä¸èƒ½ç”¨é“¾å¼å­˜å‚¨ç»“构存储;   

(C)顺序存储结构和链式存储结构都能存储;  ï¼ˆï¼¤ï¼‰é¡ºåºå­˜å‚¨ç»“构和链式存储结构都不能使用 

( C ï¼‰3. ã€–01年计算机研题〗 å…·æœ‰n(n>0)个结点的完全二叉树的深度为         ã€‚

(A) Ã©log2(n)ù   (ï¼¢) Ã« log2(n)û   (ï¼£) Ã« log2(n) Ã»+1     (D) Ã©log2(n)+1ù

注1:éx Ã¹è¡¨ç¤ºä¸å°äºŽx的最小整数;ë xû表示不大于x的最大整数,它们与[ ]含义不同!

注2:选(A)是错误的。例如当n为2的整数幂时就会少算一层。似乎ë log2(n) +1û是对的?

( A  ï¼‰4.把一棵树转换为二叉树后,这棵二叉树的形态是           ã€‚

(A)唯一的                          ï¼ˆï¼¢ï¼‰æœ‰å¤šç§

(C)有多种,但根结点都没有左孩子    ï¼ˆï¼¤ï¼‰æœ‰å¤šç§ï¼Œä½†æ ¹ç»“点都没有右孩子

5. ã€94程P11】  ä»Žä¾›é€‰æ‹©çš„答案中,选出应填入下面叙述   ï¼Ÿ   å†…的最确切的解答,把相应编号写在答卷的对应栏内。

树是结点的有限集合,它A  æ ¹ç»“点,记为T。其余的结点分成为m(m≥0)个  B   

的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的  C    ã€‚

供选择的答案

A:  â‘ æœ‰0个或1个    â‘¡æœ‰0个或多个      â‘¢æœ‰ä¸”只有1个      â‘£æœ‰1个或1个以上 

B:   â‘ äº’不相交      â‘¡ å…è®¸ç›¸äº¤         â‘¢ å…è®¸å¶ç»“点相交    â‘£ å…è®¸æ ‘枝结点相交

C: â‘ æƒ            â‘¡ ç»´æ•°             â‘¢ æ¬¡æ•°ï¼ˆæˆ–度)      â‘£ åº

答案:ABC=1,1,3

6. ã€95程P13】  ä»Žä¾›é€‰æ‹©çš„答案中,选出应填入下面叙述   ï¼Ÿ   å†…的最确切的解答,把相应编号写在答卷的对应栏内。

二叉树 A  ã€‚在完全的二叉树中,若一个结点没有  B   ï¼Œåˆ™å®ƒå¿…定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的  C   ï¼Œè€ŒN的右子女是它在原树里对应结点的  D    ã€‚

供选择的答案

A: â‘ æ˜¯ç‰¹æ®Šçš„æ ‘   â‘¡ä¸æ˜¯æ ‘的特殊形式   â‘¢æ˜¯ä¸¤æ£µæ ‘的总称   â‘£æœ‰æ˜¯åªæœ‰äºŒä¸ªæ ¹ç»“点的树形结构 

B:   â‘ å·¦å­ç»“点   â‘¡ å³å­ç»“点  â‘¢ å·¦å­ç»“点或者没有右子结点    â‘£ å…„弟

C~D: â‘ æœ€å·¦å­ç»“点         â‘¡ æœ€å³å­ç»“点    â‘¢ æœ€é‚»è¿‘的右兄弟        â‘£ æœ€é‚»è¿‘的左兄弟

       â‘¤ æœ€å·¦çš„兄弟     â‘¥ æœ€å³çš„兄弟

答案:A=           B=         C=          D=           

答案:ABCDE=2,1,1,3

四、简答题(每小题4分,共20分)

1. ã€ä¸¥é¢˜é›†6.2①】一棵度为2的树与一棵二叉树有何区别?

答:度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。即,在一般树中若某结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分。

树和二叉树练习题及解答

2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表,root为根指针,结点结构为:(lchild,data,rchild)。其中lchild,rchild分别为指向左右孩子的指针,data为字符型,root为根指针,试回答下列问题:

1. å¯¹ä¸‹åˆ—二叉树B,执行下列算法traversal(root),试指出其输出结果;

2. å‡å®šäºŒå‰æ ‘B共有n个结点,试分析算法traversal(root)的时间复杂度。(共8分)

树和二叉树练习题及解答

二叉树B

解:这是“先根再左再根再右”,比前序遍历多打印各结点一次,输出结果为:A B C C E E B A D F F D G G

特点:①每个结点肯定都会被打印两次;②但出现的顺序不同,其规律是:凡是有左子树的结点,必间隔左子树的全部结点后再重复出现;如A,B,D等结点。反之马上就会重复出现。如C,E,F,G等结点。

时间复杂度以访问结点的次数为主,精确值为2*n,时间渐近度为O(n).

3. ã€–01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列,分别是:

前序遍历序列:D,A,C,E,B,H,F,G,I;  ä¸­åºéåŽ†åºåˆ—:D,C,B,E,H,A,G,I,F,

试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解:方法是:由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合,可继续确定root的左右孩子。将他们分别作为新的root,不断递归,则所有元素都将被唯一确定,问题得解。

点击数:152

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇