下载文档原格式
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、树形结构不具备这样的特点：（）A.每个节点可能有多个后继（子节点）B.每个节点可能有多个前驱（父节点）C.可能有多个内节点（非终端结点）D.可能有多个叶子节点（终端节点）2、二叉树与度数为2的树相同之处包括（）。
A.每个节点都有1个或2个子节点B.至少有一个根节点C.至少有一个度数为2的节点D.每个节点至多只有一个父节点3、一棵完全二叉树有999个结点，它的深度为（）。
A．9B．10C．11D．124、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;5、对于一棵具有n个结点、度为5的树来说，（）A.树的高度至多是n-3B.树的高度至多是n-4C.树的高度至多是nD.树的高度至多是n-56、在顺序队列中，元素的排列顺序（）。
A.由元素插入队列的先后顺序决定B.与元素值的大小有关C.与队首指针和队尾指针的取值有关D.与数组大小有关7、串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若8、顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（）。
A．5和1B．2和4C．1和5D．4和29、一棵完全二叉树上有1001个结点，其中叶子结点的个数为（）。
A．250B．500C．254D．50110、已知一个有向图如下图所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（）。
A．adbefc B．adcefb C．adcebf D．adefbc11、在一个带权连通图G中，权值最小的边一定包含在G的（）。
三年级学而思树形图练习题树形图是一种用来表示数据或者概念之间关系的图表，它能够以直观的方式展示信息的层级结构。
在三年级学习过程中，学而思为学生们准备了一些有趣的树形图练习题，既可以帮助学生巩固知识，又能提高他们的逻辑思维能力。
下面是一些三年级学而思树形图练习题：练习题一：请根据以下信息，绘制出相应的树形图：主题：动物一级分支：哺乳动物、鸟类、爬行动物二级分支：哺乳动物-猫、狗、兔子，鸟类-鸽子、鹦鹉、鸭子，爬行动物-蛇、龟、蜥蜴练习题二：请根据以下信息，绘制出相应的树形图：主题：水果一级分支：红色水果、黄色水果、绿色水果二级分支：红色水果-苹果、草莓、樱桃，黄色水果-香蕉、柠檬、芒果，绿色水果-西瓜、绿苹果、绿柠檬练习题三：请根据以下信息，绘制出相应的树形图：主题：交通工具一级分支：陆上交通工具、水上交通工具、空中交通工具二级分支：陆上交通工具-汽车、自行车、公交车，水上交通工具-轮船、帆船、快艇，空中交通工具-飞机、直升机、热气球练习题四：请根据以下信息，绘制出相应的树形图：主题：四季一级分支：春季、夏季、秋季、冬季二级分支：春季-开花、蝴蝶、阳光，夏季-游泳、冰淇淋、太阳伞，秋季-丰收、枫叶、平安果，冬季-下雪、雪人、圣诞树练习题五：请根据以下信息，绘制出相应的树形图：主题：食物一级分支：主食、蔬菜、水果二级分支：主食-米饭、面条、馒头，蔬菜-青菜、胡萝卜、番茄，水果-橙子、苹果、葡萄以上是一些三年级学而思树形图练习题，通过练习这些题目，学生们可以加深对不同概念之间关系的理解，同时也能提高他们的绘图和思维能力。
希望同学们能够认真思考、仔细绘制，享受学习的乐趣！。
第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。
（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（√）3.数据元素是数据的最小单位。
（×）4.数据的逻辑结构和数据的存储结构是相同的。
（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）7.数据的存储结构是数据的逻辑结构的存储映象。
（√）8.数据的物理结构是指数据在计算机内实际的存储形式。
（√）9.数据的逻辑结构是依赖于计算机的。
（×）10.算法是对解题方法和步骤的描述。
（√）二、填空题1.数据有逻辑结构和存储结构两种结构。
2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。
3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
4.树形结构和图形结构合称为非线性结构。
5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。
6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。
7.数据的存储结构又叫物理结构。
8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
9.线性结构中的元素之间存在一对一的关系。
10.树形结构中的元素之间存在一对多的关系。
11.图形结构的元素之间存在多对多的关系。
12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。
13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。
14.算法是一个有穷指令的集合。
15.算法效率的度量可以分为事先估算法和事后统计法。
16.一个算法的时间复杂度是算法输入规模的函数。
17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。
18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）。
一、基础知识题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=86.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个结点仅有一个孩子，则该二叉树的总结点数是多少。
第5章习题答案一、选择1．以下说法错误的是 ( )A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2，以下说法错误的是 ( BC )A.二叉树可以是空集B.二叉树的任一结点都有两棵子树（是“最多有”两棵子树）C.二叉树与树具有相同的树形结构(二叉树的孩子必有左右之分,只有一个孩子时也要分出左右,而树即使是有序树, 只有一个孩子时部分左右)D.二叉树中任一结点的两棵子树有次序之分3、以下说法错误的是( )A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好4、以下说法错误的是 ( )A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫树5．深度为6的二叉树最多有( )个结点 ( )A.64B.63C.32D.316．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( )A.42B.40C.21D.207．设二叉树有n个结点，则其深度为( )A.n-1B.nC.5floor(log2n)D.无法确定注：完全二叉树才能确定其深度。
8．设深度为k的二叉树上只有度为0 和度为2 的节点，则这类二叉树上所含结点总数最少（）个A.k+1B.2kC.2k-1D.2k+1注：单支数含结点个数最少，但题目规定该二叉树中不存在度为1的结点。
所以，在单支树的基础上把结点补齐，使之度数为2 或 0,结果就是有2k-1个结点。
第六章树一．名词解释：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.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。
第7章树和森林树形结构是一类重要的非线性结构。
树形结构的特点是结点之间具有层次关系。
本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。
重点提示：●树的存储结构●树的遍历●树和森林与二叉树之间的转换7-1 重点难点指导7-1-1 相关术语1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。
要点：树是一种递归的数据结构。
2．结点的度：一个结点拥有的子树数称为该结点的度。
3．树的度：一棵树的度指该树中结点的最大度数。
如图7-1所示的树为3度树。
4．分支结点：度大于0的结点为分支结点或非终端结点。
如结点a、b、c、d。
5．叶子结点：度为0的结点为叶子结点或终端结点。
如e、f、g、h、i。
6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。
7．兄弟结点：具有同一父亲的结点为兄弟结点。
如b、c、d；e、f；h、i。
8．树的深度：树中结点的最大层数称为树的深度或高度。
9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。
10．森林：是m棵互不相交的树的集合。
7-1-2 树的存储结构1．双亲链表表示法以图7-1所示的树为例。
（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。
（2）存储示意图:-1 data:parent:（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。
下面的存储是不正确的：-1 data:parent:2．孩子链表表示法（1）存储思想：将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。
数据结构——树习题解答1、单词查找树（word.pas）【问题描述】在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表中。
为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：（1）根节点不包含字母，除根街店为每一个节点都包含一个大写英文字母；（2）从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。
单词列表中的每个单词，都是该单词查找树某个节点所对应的单词；（3）在满足上述条件下，该单词查找树的节点数最少。
要求：对一个确定的单词列表，请统计对应的单词查找树的结点数（包括根节点）.输入：输入文件名为word.in，该文件为一个单词列表，每行仅包含一个单词和一个换行/回车符。
每个单词仅由大写字母组成，长度不超过63个字符。
文件总长度不超过32K，至少有一行数据。
输出：输出文件名为word.out，该文件仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。
【样例输入】AANASPASASCASCIIBASBASIC【样例输出】13【题解】首先要对建树的过程有一个了解。
对于当前被处理的单词和当前树：在根节点的子节点中找单词的为第一位字母，若存在则进而在该节点的子节点中寻找第二位……，如此直到单词结束，既不需要在该书中添加节点；若单词的第n个字母不能找到，即将单词的第n个字母及其后的字母依次加入单词查找树中。
但本题只是问你结点总数，而非建树方案，且有32K大小的单词文件，所以应该考虑能不能通过不建树就直接算出结点数。
为了说明问题本质，我们定义单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则定义单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。
可见，将一个单词加入单词树的时候，须加入的节点数等于该单词树中已有的单词的差得最小值。
单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。
数据结构课后习题及解析第六章第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
习题1一、单项选择题1. 数据结构是指（）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低B.高C.相同D.不好说8. 数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953C.1964D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10. 计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库二、填空题1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。
习题六树和二叉树一、单项选择题1．以下说法错误的是( A )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是( D )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（A ）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示( C )A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（ D ）。
A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）A．250 B．500 C．254 D．505 E．以上答案都不对8．二叉树的第I层上最多含有结点数为（ C ）A．2I B．2I-1-1 C．2I-1D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（B ）。
A．指向最左孩子B．指向最右孩子C．空D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。
李春葆编著：数据结构（C语言篇）――习题与解析（修订版）清华大学出版社五、数组与稀疏矩阵单项选择题1.常对数组进行的两种基本操作是。
A.建立与删除B.索引和修改C.查找和修改D.查找与索引2.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 1 个字节；M的第8列和第5 行共占 2 个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的3元素的起始地址一致。
1 A.90 B.180 C.240 D.5402 A.108 B.114 C.54 D.603 A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]3.二维数组M的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素的元素的起始地址一致。
A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]4.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元素是。
A. 80B. 120C. 240D. 2705.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为。
A. SA+141B. SA+144C. SA+222D. SA+2256.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为。
A. SA+141B. SA+180C. SA+222D. SA+2257.稀疏矩阵一般的压缩存储方法有两种，即。
A. 二维数组和三维数组B. 三元组与散列C. 三元组与十字链表D. 散列和十字链表8.若用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点。
数据结构基本概念练习题1、选择练习题1）执行下面程序段时，执行S语句的次数为-------for(int I=1;I<=n;I++)for(int j=1;j<=I;j++)S;(A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2答案：D2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。
下列______不属于算法的五个特性之一。
(A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性答案：D3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
(A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表答案：A4）下面的叙述正确的是（）(A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比;(B) 线性表在链式存储时，查找第i个元素的时间同i的值无关;(C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比;(D) 以上说法都不对.答案：A5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
(A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表答案：B6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。
(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;答案：C7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
数据结构第四章树和二叉树习题04 树和二叉树【单选题】1. 下列选项中不属于树形结构逻辑特征的是（C）。
A、有的结点有多个直接后继 B、有的结点没有直接后继 C、有的结点有多个直接前驱 D、有的结点没有直接前驱2. 下列叙述中错误的是（B）。
A、树的度与该树中结点的度的最大值相等B、二叉树就是度为2的有序树C、有5个叶子结点的二叉树中必有4个度为2的结点D、满二叉树一定是完全二叉树3. 一棵二叉树中第6层上最多有（C）个结点。
A、2 B、31C、32D、644. 一棵高为k的二叉树最少有（B）个结点。
A、k-1 B、kC、k+1D、2k-1E、2k-15. 一棵高为k的二叉树最多有（C）个结点。
A、k+1 B、2k-1 C、2k-1 D、2k E、2k+16. 一棵高为k的完全二叉树最少有（B）个结点。
A、2k-1-1 B、2k-1 C、2k-1 D、2k7. 一棵高为k的完全二叉树最多有（C）个结点。
A、2k-1-1 B、2k-1 C、2k-1 D、2k8. 一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（D）个。
A、4 B、5 C、6 D、79. 含1000个结点的完全二叉树的高度为（B）。
A、9 B、10 C、11 D、1210. 设完全二叉树T中含有n个结点，对这些结点从0开始按层序进行编号，若编号为i的结点有左孩子，则左孩子的编号为（D）。
A、2(i-1)B、2i-1C、2iD、2i+1E、2(i+1)11. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（D）。
A、-A+B*C/DE B、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE12. 已知一棵二叉树的先序序列为abdegcfh，中序序列为dbgeachf，则该二叉树的后序序列为（B）。
A、gedhfbca B、dgebhfca C、abcdefgh D、acbfedhg13. 先序遍历与中序遍历所得遍历序列相同的二叉树为（D）。
数据结构树和二叉树习题及答案集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。
第6章 树【例6-1】写出如图6-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。
解：（1）叶子结点有：B 、D 、F 、G 、H 、I 、J 。
（2）非终端结点有：A 、C 、E 。
（3）每个结点的度分别是：A 的度为4，C的度为2，E 的度为3，其余结点的度为0。
（4）树的深度为3。
【例6-2】一棵度为2的树与一棵二叉树有什么区别？解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。
【例6-3】树与二叉树有什么区别？解：区别有两点：（1）二叉树的一个结点至多有两个子树，树则不然；（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。
【例6-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。
解：如图6-2(a)所示，具有3个结点的树有两种不同形态。
如图6-2(B )所示，具有3个结点的二叉树有以下五种不同形态。
【例6-8】如图6-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。
图6-2(a)图6-2(b)A B C D EF G H I J 图6-1a b cdefg图6-3解：（2）该二叉树的二叉链表表示如图6-4所示。
【例6-9】试找出满足下列条件的所有二叉树：（1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。
解：（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。
【例6-10】如图6-5所示的二叉树，要求：（1）写出按先序、中序、后序遍历得到的结点序列。
（2）画出该二叉树的后序线索二叉树。
解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA （2）其后序线索二叉树如图6-6所示。
bac de f图6-5图6-6图6-4【例6-11】将图6-7所示的树转换为二叉树。
解：第一步，加线。
第二步，抹线。
第三步，旋转。
过程如图6-8所示。
【例6-12】将如图6-9所示的二叉树转换为树。
A 图6-7BCDEFGHI K L MJ A B CDEFH IJ 图6-9A图6-8(a) 第一步 加线B C D E F G H I K L MJ A 图6-8(b) 第二步 抹线 B C DE F G H I K L MJA B图6-8(c) 第三步 旋转C F DKG ELH MIJ解： 第一步，加线。
第二步，抹线。
第三步，调整。
过程如图6-10所示。
【例6-13】将如图6-11所示的森林转换成二叉树。
解： 步骤略，结果如图6-12所示。
【例6-14】假定用于通信的电文由8个字符A 、B 、C 、D 、E 、F 、G 、H 组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。
解： 根据题意，设这8个字母对应的权值分别为（5，25，4，7，9，12，30，8），并且n=8。
（1）设计哈夫曼树的步骤如图6-13所示。
C DE F G ABH ILJ K图6-12 第一步： 25 5 4 7 9 12 30 8 第二步：25 7 9 12 30 5498 图6-11 C D EF G A B HILJKAB D HC F E J I B A CDEF H I J 第一步 第二步 第三步BA C D E F H I J 图6-10第三步：25 79 12 305 498 15第四步： 25 79 12 30815 549 18第七步：25 30954 9187128 1527 4357 第八步：25 9549 18 43 307 12 8 152757100 图6-13第五步：25 791230815 549 1827第六步：25 30954 91843712815 27（2）设计哈夫曼编码利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：A:0011B:01C:0010D:1010E:000F:100G:11H:1011习题6一、单项选择题1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A. 4B. 5C. 6D. 72.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。
A. 15B. 16C. 17D. 473.假定一棵三叉树的结点数为50，则它的最小高度为（）。
A. 3B. 4C. 5D. 64.在一棵二叉树上第4层的结点数最多为（）。
A. 2B. 4C. 6D. 85.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。
A. R[2i+1]B. R[2i]C. R[i/2]D. R[2i-1]6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A. 24B. 48C. 72D. 537.线索二叉树是一种（）结构。
A. 逻辑B. 逻辑和存储C. 物理D. 线性8.线索二叉树中，结点p没有左子树的充要条件是（）。
A. p->lc=NULLB. p->ltag=1C. p->ltag=1 且p->lc=NULLD. 以上都不对9.设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。
A. n在m右方B. n在m 左方C. n是m的祖先D. n是m的子孙10.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。
A. 中序B. 前序C. 后序D. 层次序11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（）存储结构。
A. 三叉链表B. 广义表C. 二叉链表D. 顺序12.下面叙述正确的是（）。
A. 二叉树是特殊的树B. 二叉树等价于度为2的树C. 完全二叉树必为满二叉树D. 二叉树的左右子树有次序之分13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。
A. 不发生改变B. 发生改变C. 不能确定D. 以上都不对14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。
A. 1B. 2C. 3D. 415.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。
A. 是完全二叉树B. 不是完全二叉树C. 是满二叉树D. 不是满二叉树二、判断题1.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。
（）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。
（）3.线索二叉树是一种逻辑结构。
（）4.哈夫曼树的总结点个数（多于1时）不能为偶数。
（）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。
（）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。
（）7.根据任意一种遍历序列即可唯一确定对应的二叉树。
（）8.满二叉树也是完全二叉树。
（）9.哈夫曼树一定是完全二叉树。
（）10.树的子树是无序的。
（）三、填空题1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。
2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。
5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。
6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。
7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。
8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
9. 由三个结点构成的二叉树，共有____种不同的形态。
10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。
12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。
13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。
14. 哈夫曼树是指________________________________________________的二叉树。
15. 空树是指________________________，最小的树是指_______________________。
16. 二叉树的链式存储结构有______________和_______________两种。
17. 三叉链表比二叉链表多一个指向______________的指针域。
18. 线索是指___________________________________________。
19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。
20. 本节中我们学习的树的存储结构有_____________、___________和___________。
四、应用题1. 已知一棵树边的集合为{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点g的双亲？（4）哪些是结点g的祖先？（5）哪些是结点g的孩子？（6）哪些是结点e的孩子？（7）哪些是结点e的兄弟？哪些是结点f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树深度是多少？2. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。
