下载文档原格式
数据结构试卷带答案数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（ 1.C ）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。
(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（D）的逻辑结构。
(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（C）个。
(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B 需要的操作为（.A ）。
(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。
(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。
(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（B）种不同的形态。
(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（B ）的空间复杂度最大。
(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。
第一章测试1.数据结构的基本任务是（）。
A:数据结构的评价与选择B:数据结构的设计与实现C:数据结构的运算实现D:逻辑结构和存储结构的设计答案:B2.计算算法的时间复杂度是属于一种（）。
A:事前分析估算的方法B:事后分析估算的方法C:事后统计的方法D:事前统计的方法答案:A3.可以用（）定义一个完整的数据结构。
A:数据元素B:数据关系C:抽象数据类型D:数据对象答案:C4.数据的逻辑关系是指数据元素的（）。
A:存储方式B:数据项C:关联D:结构答案:C5.算法的计算量的大小称为计算的（）。
A:效率B:复杂性C:实现性D:难度答案:B6.算法的时间复杂度取决于（）。
A:问题的规模B:问题的规模和待处理数据的初态C:待处理数据的初态D:都不是答案:B7.数据元素是数据的最小单位。
（）A:对B:错答案:B8.数据结构是带有结构的数据元素的结合。
（）A:错B:对答案:B9.算法和程序没有区别，所以在数据结构中二者是通用的。
（）A:错B:对答案:A10.数据结构的抽象操作的定义与具体实现有关。
（）A:对B:错答案:B第二章测试1.下述哪一条是顺序存储结构的优点？（）。
A:存储密度大B:删除运算方便C:插入运算方便D:可方便地用于各种逻辑结构的存储表示答案:A2.下面关于线性表的叙述中，错误的是哪一个？（）。
A:线性表采用链接存储，便于插入和删除操作B:线性表采用顺序存储，必须占用一片连续的存储单元C:线性表采用链接存储，不必占用一片连续的存储单元D:线性表采用顺序存储，便于进行插入和删除操作答案:D3.线性表是具有n个（）的有限序列（n＞0）。
A:数据项B:表元素C:数据元素D:字符答案:C4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A:顺序表B:双链表C:带头结点的双循环链表D:单循环链表答案:A5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
《数据结构（C语言版第2版）》（严蔚敏著）第六章练习题答案第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。
（3）具有n个顶点的有向图最多有（）条边。
A．n B．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。
A．n B．2(n-1)C．n/2D．n2答案：B所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。
（7）下面（）算法适合构造一个稠密图G的最小生成树。
A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。
（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A．栈 B.队列 C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
《数据结构》填空作业题答案第1章绪论（已校对无误）1 •数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2 •程序包括两个内容：数据结构和算法。
3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure = （D, S）。
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7. 在树形结构中，数据元素之间存在一对多的关系。
8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是—对多或多对多。
14. 数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16. 数据元素可由若干个数据项组成。
17. 算法分析的两个主要方面是时间复杂度和空间复杂度。
18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
第一章测试1【单选题】(2分)图书馆的数目检索系统采用关系的数据结构。
A.树形B.图状C.集合D.线性2【单选题】(2分)是相互之间存在一种或多种特定关系的数据元素的集合。
A.数据项B.数据结构C.数据元素D.数据3【单选题】(2分)（）是一个值的集合和定义在这个值集上的一组操作的总称。
A.数据项B.数据类型C.数据元素D.数据结构4【单选题】(2分)算法的确定性是指（）A.算法中没有逻辑B.在任何情况下，算法不会出现死循环C.算法中的每一条指令必须有确切的含义D.当输入数据非法时，算法也能作出反应或进行处理第二章测试1【单选题】(2分)线性表中的数据元素有一个前驱多个后继。
A.错B.对2【单选题】(2分)用顺序结构存储，删除最后一个结点时，（）A.其它B.会移动其它结点位置C.可能会移动其它结点位置D.一定不会移动其它结点位置3【单选题】(2分)链表中逻辑上相邻的元素的物理地址__________相邻。
A.一定不B.必定C.其它D.不一定4【单选题】(2分)1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。
//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头A->next=qa;}else{qb=pb;pb=pb->next;()//将当前最小结点插入B表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}A.qa->next=A->nextB.qa->next=A;C.qb->next=A->nextD.qb->next=A;5【单选题】(2分)假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。
第6章树和二叉树习题解答一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）（√）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二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。
2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
数据结构考试题库含答案数据结构考试题库含答案Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】数据结构习题集含答案目录选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的（A ）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据结构是指（A ）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A ）。
A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B ）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B ）。
A、低B、高C、相同D、不好说10.算法的时间复杂度取决于（ C ）A 、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。
第一章概论一、选择题1、研究数据结构就是研究（ D ）。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（A）。
A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。
A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。
A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（C）。
for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（ D ）。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。
A. O(n)B. O(nlog2n) C. O(n2) D. O(log2n)8、下面程序段的时间复杂度为（ C ）。
i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n) D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。
A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（ C ）。
i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(√n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A ）。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（ A ）。
《数据结构》第2教学单元测试练习题一．选择1．将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）根? 右孩子?A.98B.99C.50D.482．以下说法错误的是( )A.一般在赫夫曼树中，权值越大的叶子离根结点越近B.赫夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的赫夫曼树共有2n-1个结点D.若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的赫夫曼树3．深度为6的二叉树最多有( )个结点A．64 B.63 C.32 D.314．以下说法正确的是( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树的度肯定等于2D.任何一棵二叉树的度可以小于25．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有( d )个结点。
根结点的左孩子上有( a )个结点。
A.n1-1B.n1C.n1+n2+n3D.n2+n3+n46.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0B.1C.2D.不存在这样的二叉树7．讨论树、森林和二叉树的关系，目的是为了( )A.借助二叉树上的运算方法去实现对树的一些运算B.将树、森林按二叉树的存储方式进行存储C.将树、森林转换成二叉树D.体现一种技巧，没有什么实际意义8.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是( )A.acbedB.deabcC.decabD.cedba9.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的( a ), 后序就是T2中结点的( b ) A.前序 B.中序 C.后序 D.层次序10．深度为5的二叉树至多有( )个结点。
A.16B.32C.31D.1011．以下说法错误的是( )A.存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同B.二叉树是树的特殊情形C.由树转换成二叉树，根结点右子树总是空的D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树12．下列序列中，符合堆定义的是（）A.(100,80,55,60,50,40,58,35,20)B.( 100,80,55,60,50,40,35,58,20)C.( 100,80,55,58,50,40,60,35,20)D. ( 100,70,55,60,50,40,58,35,20)13．算术表达式a+b*（c+d/e）转为后缀表达式后为( )A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++14．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )A.5B.6C.7D.8解析：总分支=1*4+2*2+3*1+4*1=15，则总结点=15+1=16 不为零的结点个数=4+2+1+1=8为零的结点=总的-不为零的=16-8=815．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )A.9B.11C.15D.不确定16．设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有( )个结点.A.13B.12C.26D.2517．设给定权值总数有n 个,其哈夫曼树的结点总数为( )A.不确定B.2nC.2n+1D.2n-118．二叉树的第I层上最多含有结点数为( )A.2IB.2I-1-1C.2I-1D.2I -119．一个具有1025个结点的二叉树的高h为( )A.11 B．10 C.11至1025之间 D.10至1024之间20．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A.2hB.2h-1C.2h+1D.h+1 21．对于有n 个结点的二叉树, 其高度为( )A.nlog2nB.log2nC.⎣log2n⎦|+1D.不确定22．在一棵高度为k的满二叉树中，结点总数为( )A.2k-1B.2kC.2k-1D.⎣log2k⎦+123．高度为 K的二叉树最大的结点数为( )A.2kB.2k-1C.2k -1D.2k-1-124．一棵树高为K的完全二叉树至少有( )个结点A.2k–1B.2k-1–1C.2k-1D.2k25．利用二叉链表存储树，则根结点的右指针是( )A.指向最左孩子B.指向最右孩子C.空D.非空26．二叉树先序遍历：EFHIGJK；中序遍历: HFIEJKG 。
该二叉树根的右子树的根是( )A.EB.FC.GD.H27．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。
A或B都不全。
由本题可解答44题。
28．n个结点的线索二叉树上含有的线索数为( )A.2nB.n－lC.n＋lD.n线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。
29．由3 个结点可以构造出( a )棵不同的树, ( d )棵不同的二叉树A.2B.3C.4D.530.分别以下列序列构造二叉查找树，与用其它三个序列所构造的结果不同的是( )A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110) 二．填空1．二叉树由_(1)根结点__，__(2)左子树_，_(3)右子树__三个基本单元组成。
2．在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null _____。
3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ N2+1____4．高度为8的完全二叉树至少有___64 ___个叶子结点。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_ 99_____。
6．一个有2001个结点的完全二叉树的高度为_ 11 __。
7．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为___69___。
8．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_4 _____。
9．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为__⎣n/2⎦____。
10．8层完全二叉树至少有_ 128(第七层满，加第八层１个) _____个结点，拥有100个结点的完全二叉树的最大层数为__7__。
11．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为__21____。
12． n（n>1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)2 __。
它共有_(2)n-1 __个叶子结点和_(3) 1 __个非叶子结点，其中深度最大的那棵树的深度是_(4) n __，它共有_(5)_ 1 _个叶子结点和_(6) n-1__个非叶子结点。
(思考：二叉树呢？) 13．每一棵树都能唯一的转换为它所对应的二叉树。
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_(1) FEGHDCB __。
设上述二叉树是由某棵树（或森林）转换而成，则第一棵树的先根次序序列是_(2)_ BEF14．二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树结点的前序序列为_(1) EACBDGF __,则该二叉树对应的树林包括_(2) 2__棵树。
15．二叉树的先序序列和中序序列相同的条件是_任何结点至多只有右子女的二叉树_____。
16．具有n个结点的满二叉树，其叶结点的个数是__(n+1)/2____。
17．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69 ____。
18．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1) 80__，字符c的编码是_(2) 001（不唯一）__。
19．线索二叉树的左线索指向其(1) 前驱,右线索指向其(2) 后继.20．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-1个结点。
21.由2012个结点构造完全二叉树，所得叶子有1006 个，2013个结点构造完全二叉树，所得叶子有1007 个三．判断1．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树( X )2．如果二叉树中某结点的度为1，则说该结点只有一棵子树( √)3．已知一棵树的先序序列和后序序列，一定能构造出该树( √) 二叉树的先序和后序不可4．设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点( X )5．若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反( √)6．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法( √ )7．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法( X )8．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（X）。
9．二叉树是度为2的有序树。
×10．完全二叉树一定存在度为1的结点。
×11．对于有N个结点的二叉树，其高度为log2n。
×12．深度为K的二叉树中结点总数≤2k-1。
√13．二叉树的遍历结果不是唯一的.√只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
14．二叉树的遍历只是为了在应用中找到一种线性次序。
√15．完全二叉树中，若一个结点没有左孩子，则它必是树叶。
√16．树形结构中元素之间存在一个对多个的关系。
√17．完全二叉树的存储结构通常采用顺序存储结构。
√18．将一棵树转成二叉树，根结点没有左子树；×右孩子19．在二叉树中插入结点，则它不再是二叉树了。
×20．树与二叉树是两种不同的树型结构。
√四．解答应用题1. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。
