32.二叉树

7.3补充练习题及参考答案7.3.1单项选择题1.对于一棵具有n 个结点、度为4的树来说,_____________.A.树的高度最多是n-3B.树的高度最多是是n-4C.第i 层上最多有4(i-1)个结点D.至少在某一层上正好有4个结点答:这样的树中至少有一个结点的度为4,也就是说,至少有一层中有4个或以上的结点,因此树的高度最多是n-3。

本题的答案为A 。

2.度为4、高度为h 的树_____________.A.至少有h+3个结点B.最多有4h -1个结点C.最多有4h 个结点D.至少有h+4个结点答:与上小题分析相同,本题的答案为A 。

3.对于一棵具有n 个结点、度为4的树来说,树的高度至少是_____________.A.)]2([log 4nB.)]13([log 4-nC.)]13([log 4+nD.)]12([log 4+n答:由树的性质4可知,具有n 个结点的m 次树的最小高度为)]1)1(([log +-m n m 。

这里m=4,因此最小高度为)]13([log 4+n 。

本题的答案为C 。

4.在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为_____________个。

A.4B.5C.6D.7答：3n =2，2n =1，1n =2，001235n n n n n n +=+++=，n=度之和+1=33n +22n +1n +1=11， 所以65110=-=n 。

本题的答案为C 。

5.若一棵有n 个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数 是_____________。

A.n(k 一1)/kB.n-kC.(n+1)/kD.(nk 一n+1)/k答:m=k,有k n n n +=0,度之和=n-1=k kn ,k n n k /)1(-=,所以0n =n-k n =n-(n-1)/k=(nk-n+1)/k.本题的答案为D 。

二叉树,树,森林遍历之间的对应关系一、引言在计算机科学中，数据结构是非常重要的知识点之一。

而树这一数据结构，作为基础的数据结构之一，在软件开发中有着广泛的应用。

本文将重点探讨二叉树、树和森林遍历之间的对应关系，帮助读者更加全面地理解这些概念。

二、二叉树1. 二叉树的定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空，也可以是一棵空树。

2. 二叉树的遍历在二叉树中，有三种常见的遍历方式，分别是前序遍历、中序遍历和后序遍历。

在前序遍历中，节点的访问顺序是根节点、左子树、右子树；在中序遍历中，节点的访问顺序是左子树、根节点、右子树；在后序遍历中，节点的访问顺序是左子树、右子树、根节点。

3. 二叉树的应用二叉树在计算机科学领域有着广泛的应用，例如用于构建文件系统、在数据库中存储有序数据、实现算法中的搜索和排序等。

掌握二叉树的遍历方式对于理解这些应用场景非常重要。

三、树1. 树的定义树是一种抽象数据类型，由n(n>0)个节点组成一个具有层次关系的集合。

树的特点是每个节点都有零个或多个子节点，而这些子节点又构成了一颗子树。

树中最顶层的节点称为根节点。

2. 树的遍历树的遍历方式有先根遍历、后根遍历和层次遍历。

在先根遍历中，节点的访问顺序是根节点、子树1、子树2...；在后根遍历中，节点的访问顺序是子树1、子树2...，根节点；在层次遍历中，节点的访问顺序是从上到下、从左到右依次访问每个节点。

3. 树的应用树广泛用于分层数据的表示和操作，例如在计算机网络中的路由算法、在操作系统中的文件系统、在程序设计中的树形结构等。

树的遍历方式对于处理这些应用来说至关重要。

四、森林1. 森林的定义森林是n(n>=0)棵互不相交的树的集合。

每棵树都是一颗独立的树，不存在交集。

2. 森林的遍历森林的遍历方式是树的遍历方式的超集，对森林进行遍历就是对每棵树进行遍历的集合。

3. 森林的应用森林在实际编程中经常用于解决多个独立树结构的问题，例如在数据库中对多个表进行操作、在图像处理中对多个图形进行处理等。

二叉树基础知识讲解嘿，朋友们！今天咱来聊聊二叉树这个神奇的玩意儿。

二叉树啊，就像是一棵特别的大树，不过它可不像咱平常看到的大树那样枝繁叶茂、随心所欲地长。

你想啊，二叉树它有个特点，每个节点最多就俩孩子，就像咱人啊，最多也就俩胳膊。

这俩孩子还分左右呢，左边一个右边一个，多有意思！二叉树在计算机的世界里那可是大有用处啊！它就像一个超级整理大师，能把一堆乱七八糟的数据整理得井井有条。

比如说，咱要找个什么东西，在二叉树里找可比在一堆乱麻里找容易多了吧！它的结构也很巧妙呢！有的节点在上面，有的在下面，就像一个大家庭，有长辈有晚辈。

而且啊，通过那些连接的线，它们之间都有着特别的关系。

这是不是很像咱家里的亲戚关系网呀？二叉树的遍历也是很有讲究的哦！什么前序遍历、中序遍历、后序遍历，听起来是不是很玄乎？其实啊，就是从不同的角度去看看这棵树。

前序遍历就像是先看上面再看下面，中序遍历呢就有点像从中间开始看，后序遍历就是最后再看上面。

咱再想想，二叉树不就跟咱生活中的很多事情一样嘛！有时候咱得有条理地去做事，不能瞎搞一气。

就像二叉树，它的结构那么清晰，让我们能很容易地找到需要的东西。

而且二叉树还特别稳定呢！只要你一开始把它构建好了，它就乖乖地在那，不会随便出乱子。

这多让人放心啊！不像有些东西，一会儿变一个样，让人摸不着头脑。

那要是二叉树变得很大很大了呢？那可就更厉害了呀！它能处理超多的数据，就像一个超级大脑，什么都能记住。

你说，这二叉树是不是很神奇？它虽然看起来简单，但是里面蕴含的智慧可不少呢！它能帮我们解决好多问题，让我们的计算机世界变得更加精彩。

所以啊，可别小瞧了这二叉树哦！它真的是计算机领域里的一个宝贝呢！。

数据结构与算法一选择题1．算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2．下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)3. 连续存储设计时，存储单元的地址（）。

A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4. 下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表6．下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）(^.相当于—>)A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;9．下列排序算法中，其中（）是稳定的。

复习题集一判断题（×）1．线性表在物理存储空间中也一定是连续的。

（×）2．顺序存储方式只能用于存储线性结构。

（√）3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（×）5．二叉树的度为2。

（√）6．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）7．二叉树中每个结点的两棵子树的高度差等于1。

（√）8．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（）9．在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。

（）10．计算机处理的对象可以分为数据和非数据两大类。

（）11．数据的逻辑结构与各数据元素在计算机中如何存储有关。

（）12．算法必须用程序语言来书写。

（）13．判断某个算法是否容易阅读是算法分析的任务之一。

（）14．顺序表是一种有序的线性表。

（）15．分配给顺序表的内存单元地址必须是连续的。

（）16．栈和队列具有相同的逻辑特性。

（）18．树形结构中每个结点至多有一个前驱。

（）19．在树形结构中，处于同一层上的各结点之间都存在兄弟关系。

（）20．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。

（）21．如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。

（）22．顺序查找方法只能在顺序存储结构上进行。

（）23．折半查找可以在有序的双向链表上进行。

（）24．满二叉树中不存在度为1的结点。

（）25．完全二叉树中的每个结点或者没有孩子或者有两个孩子。

（）26．对n个元素知心快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。

（）27．在有向图中，各顶点的入度之和等于各顶点的出度之和。

一、选择题（）1. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：A) 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C) 删除第i个结点（1≤i≤n）B) 在第i个结点后插入一个新结点（1≤i≤n）D) 将n个结点从小到大排序（C）2. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）3. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（B）4. 计算机算法必须具备输入、输出和等5个特性。

“数据结构”期末考试试题一、单选题（每小题2分,共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行( )。

A． HL＝ps p一〉next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl;p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有( ）。

A。

n—l条有向边 B.n条有向边C.n(n-1)／2条有向边 D。

n（n一1）条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( ）。

A。

O（1) B.O（n)C.O（1Ogzn)D.O（n2）4．由权值分别为3，8,6,2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( ）。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为（ )参数，以节省参数值的传输时间和存储参数的空间。

A。

整形 B。

引用型C。

指针型 D。

常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为（）。

A．O(n） B．O(1)C．O（n2） D．O(10g2n）二、填空题（每空1分，共28分）1．数据的存储结构被分为——、——、——和-—四种.2．在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．—-中缀表达式 3十x*(2.4／5—6）所对应的后缀表达式为—-——。

4．在一棵高度为h的3叉树中,最多含有—-结点。

5．假定一棵二叉树的结点数为18,则它的最小深度为-—，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定-—该结点的值，右子树上所有结点的值一定-—该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整,直到被调整到——位置为止。

数据结构⼊门-树的遍历以及⼆叉树的创建树定义：1. 有且只有⼀个称为根的节点2. 有若⼲个互不相交的⼦树，这些⼦树本⾝也是⼀个树通俗的讲：1. 树是有结点和边组成，2. 每个结点只有⼀个⽗结点，但可以有多个⼦节点3. 但有⼀个节点例外，该节点没有⽗结点，称为根节点⼀、专业术语结点、⽗结点、⼦结点、根结点深度：从根节点到最底层结点的层数称为深度，根节点第⼀层叶⼦结点：没有⼦结点的结点⾮终端节点：实际上是⾮叶⼦结点度：⼦结点的个数成为度⼆、树的分类⼀般树：任意⼀个结点的⼦结点的个数都不受限制⼆叉树：任意⼀个结点的⼦结点个数最多是两个，且⼦结点的位置不可更改⼆叉数分类：1. ⼀般⼆叉数2. 满⼆叉树：在不增加树层数的前提下，⽆法再多添加⼀个结点的⼆叉树3. 完全⼆叉树：如果只是删除了满⼆叉树最底层最右边的连续若⼲个结点，这样形成的⼆叉树就是完全⼆叉树森林：n个互不相交的树的集合三、树的存储⼆叉树存储连续存储(完全⼆叉树)优点：查找某个结点的⽗结点和⼦结点(也包括判断有没有⼦结点)速度很快缺点：耗⽤内存空间过⼤链式存储⼀般树存储1. 双亲表⽰法：求⽗结点⽅便2. 孩⼦表⽰法：求⼦结点⽅便3. 双亲孩⼦表⽰法：求⽗结点和⼦结点都很⽅便4. ⼆叉树表⽰法：把⼀个⼀般树转化成⼀个⼆叉树来存储，具体转换⽅法：设法保证任意⼀个结点的左指针域指向它的第⼀个孩⼦，右指针域指向它的兄弟，只要能满⾜此条件，就可以把⼀个⼀般树转化为⼆叉树⼀个普通树转换成的⼆叉树⼀定没有右⼦树森林的存储先把森林转化为⼆叉树，再存储⼆叉树四、树的遍历先序遍历：根左右先访问根结点，再先序访问左⼦树，再先序访问右⼦树中序遍历：左根右中序遍历左⼦树，再访问根结点，再中序遍历右⼦树后续遍历：左右根后续遍历左⼦树，后续遍历右⼦树，再访问根节点五、已知两种遍历求原始⼆叉树给定了⼆叉树的任何⼀种遍历序列，都⽆法唯⼀确定相应的⼆叉树，但是如果知道了⼆叉树的中序遍历序列和任意的另⼀种遍历序列，就可以唯⼀地确定⼆叉树已知先序和中序求后序先序：ABCDEFGH中序：BDCEAFHG求后序：这个⾃⼰画个图体会⼀下就可以了，⾮常简单，这⾥简单记录⼀下1. ⾸先根据先序确定根，上⾯的A就是根2. 中序确定左右，A左边就是左树(BDCE)，A右边就是右树(FHG)3. 再根据先序，A左下⾯就是B，然后根据中序，B左边没有，右边是DCE4. 再根据先序，B右下是C，根据中序，c左下边是D，右下边是E，所以整个左树就确定了5. 右树，根据先序，A右下是F，然后根据中序，F的左下没有，右下是HG，6. 根据先序，F右下为G，然后根据中序，H在G的左边，所以G的左下边是H再来⼀个例⼦，和上⾯的思路是⼀样的，这⾥就不详细的写了先序：ABDGHCEFI中序：GDHBAECIF已知中序和后序求先序中序：BDCEAFHG后序：DECBHGFA这个和上⾯的思路是⼀样的，只不过是反过来找，后序找根，中序找左右树简单应⽤树是数据库中数据组织⼀种重要形式操作系统⼦⽗进程的关系本⾝就是⼀棵树⾯向对象语⾔中类的继承关系哈夫曼树六、⼆叉树的创建#include <stdio.h>#include <stdlib.h>typedef struct Node{char data;struct Node * lchild;struct Node * rchild;}BTNode;/*⼆叉树建⽴*/void BuildBT(BTNode ** tree){char ch;scanf("%c" , &ch); // 输⼊数据if(ch == '#') // 如果这个节点的数据是#说明这个结点为空*tree = NULL;else{*tree = (BTNode*)malloc(sizeof(BTNode));//申请⼀个结点的内存 (*tree)->data = ch; // 将数据写⼊到结点⾥⾯BuildBT(&(*tree)->lchild); // 递归建⽴左⼦树BuildBT(&(*tree)->rchild); // 递归建⽴右⼦树}}/*⼆叉树销毁*/void DestroyBT(BTNode *tree) // 传⼊根结点{if(tree != NULL){DestroyBT(tree->lchild);DestroyBT(tree->rchild);free(tree); // 释放内存空间}}/*⼆叉树的先序遍历*/void Preorder(BTNode * node){if(node == NULL)return;else{printf("%c ",node->data );Preorder(node->lchild);Preorder(node->rchild);}}/*⼆叉树的中序遍历*/void Inorder(BTNode * node){if(node == NULL)return;else{Inorder(node->lchild);printf("%c ",node->data );Inorder(node->rchild);}}/*⼆叉树的后序遍历*/void Postorder(BTNode * node){if(node == NULL)return;else{Postorder(node->lchild);Postorder(node->rchild);printf("%c ",node->data );}}/*⼆叉树的⾼度树的⾼度 = max(左⼦树⾼度，右⼦树⾼度) +1*/int getHeight(BTNode *node){int Height = 0;if (node == NULL)return 0;else{int L_height = getHeight(node->lchild);int R_height = getHeight(node->rchild);Height = L_height >= R_height ? L_height +1 : R_height +1; }return Height;}int main(int argc, char const *argv[]){BTNode * BTree; // 定义⼀个⼆叉树printf("请输⼊⼀颗⼆叉树先序序列以#表⽰空结点:");BuildBT(&BTree);printf("先序序列：");Preorder(BTree);printf("\n中序序列：");Inorder(BTree);printf("\n后序序列：");Postorder(BTree);printf("\n树的⾼度为：%d" , getHeight(BTree));return 0;}// ABC##DE##F##G##。

在下列排序方法中，空间复杂性为O(n)的方法为( )。

A.快速排序B.直接插入排序C.堆排序D.归并排序答案:D标准答案：D您的答案：题目分数：1.0此题得分：0.02．第5题在循环双链表的p所指结点之后插入s所指结点的操作是( )。

A.p-> next=s; s-> prior=p; p-> next-> prior=s; s-> next=p-> next;B.p-> next=s; p-> next-> prior=s; s-> prior=p; s-> next=p-> next;C.s-> prior=p; s-> next=p-> next; p-> next=s; p-> next-> prior=s;D.s-> prior=p; s-> next=p-> next; p-> next-> prior=s; p-> next=s; 答案:D标准答案：D您的答案：题目分数：1.0此题得分：0.03．第6题与邻接表表示相比，邻接矩阵表示更适合( )。

A.无向图B.有向图C.稠密图D.稀疏图答案:C标准答案：C您的答案：题目分数：1.0此题得分：0.0给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是( )。

A.AB.BC.CD.D答案:C标准答案：C您的答案：题目分数：1.0此题得分：0.05．第14题栈操作的原则是( )。

A.先进先出B.后进先出C.栈底删除D.以上都不是答案:B标准答案：B您的答案：题目分数：1.0此题得分：0.06．第15题若下图表示某广义表，则它是一种( )。

A.线性表B.纯表C.再入表D.递归表答案:C标准答案：C您的答案：题目分数：1.0此题得分：0.07．第23题栈和队列都是( )。

A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构答案:A标准答案：A您的答案：题目分数：1.0此题得分：0.08．第24题以下叙述错误的是( )。