本软件可以根据您的二次函数而画出相应的图象，支持多条二次函数画在同一坐标轴上。能显示与坐标轴的交点，并且有动画等功能，是工程、解题的有力帮手。

1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。
2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A．15 B．16 C．17 D．47
3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。
4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。
5. 深度为5的二叉树至多有____个结点。
6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ ___。
7. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。
8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。 A. 正确 B. 错误
11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。
12. 在一非空二叉树的中序遍历序列中，根结点的右边____。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点
C. 只有左子树上的部分结点 D. 只有左子树上的所有结点
13. 如图6.1所示二叉树的中序遍历序列是____。

14. 一棵二叉树如图6.2所示，其中序遍历的序列为__ __。
15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。
A．a在b的右方 B．a在b的左方
C．a是b的祖先 D．a是b的子孙
17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。
A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构
18. 如图6.3所示的4棵二叉树，____不是完全二叉树。

19. 如图6.4所示的4棵二叉树，____是平衡二叉树。

20. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。
21. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 A. 正确 B. 错误
22. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。 A. 正确 B. 错误
23. 具有五层结点的二叉平衡树至少有____个结点。
24. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
25. 树最适合用来表示____。
A. 有序数据元素 B. 无序数据元素
C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
6.2 填空题（将正确的答案填在相应的空中）
1. 有一棵树如图6.5所示，回答下面的问题：
⑴ 这棵树的根结点是____；
⑵ 这棵树的叶子结点是____；
⑷ 这棵树的度是____；
⑸ 这棵树的深度是____；
⑹ 结点k3的子女是____；
⑺ 结点k3的父结点是____；

2. 指出树和二叉树的三个主要差别____、____、____。
3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是___ _。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__ __。
5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。
6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=____。
7. 一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。
8. 结点最少的树为____，结点最少的二叉树为____。
9. 现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。
10. 由如图6.7所示的二叉树，回答以下问题：
⑴ 其中序遍历序列为____；
⑵ 其前序遍历序列为____；
⑶ 其后序遍历序列为____；

1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。
3. 由如图6.7所示的二叉树，回答以下问题：
（1）画出该二叉树的中序线索二叉树；
（2）画出该二叉树的后序线索二叉树；
（3）画出该二叉树对应的森林。
4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。

5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。
6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?
7. 证明:一棵满k叉树上的叶子结点数n 和非叶子结点数n 之间满足以下关系:
1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。
2．试编写算法，对一棵二叉树,统计叶子的个数。
3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。
使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。
2. 树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0；
树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
树的结点无左、右之分，而二叉树的结点有左、右之分；
3. 树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。
8. 只有一个结点的树；空的二叉树
2. 二叉树如图6.12所示。

3. 中序线索二叉树如图6.13（左）所示；后序线索二叉树如图6.13（右）所示；
该二叉树转换后的的森林如图6.14所示。

4. 图6.8的树转化为一棵二叉树如下，图6.15：

5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为 。

6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ，

11．已知一有向图的邻接表存储结构如图7.2所示。

⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法
C. 宽度优先遍历算法 D. 深度优先遍历算法
15．关键路径是事件结点网络中 。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D.最短的回路
16．下面不正确的说法是 。
（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；
（2）AOE网工程工期为关键活动上的权之和；
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。
A.逆拓朴有序的 B.拓朴有序的 C.无序的
18．在图7.3所示的拓朴排列的结果序列为 。

19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
7.2 填空题（将正确的答案填在相应饿空中）
1．n个顶点的连通图至少____条边。
2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。
4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。

图7.4 图G的邻接表
5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。
6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。
7．如果含n个顶点的图形成一个环，则它有 棵生成树。
8．一个非连通无向图，共有28条边，则该图至少有 个顶点。
9．遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。
10．一个图的 表示法是唯一的，而 表示法是不唯一的。
11．有向图中的结点前驱后继关系的特征是 。
12．若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。
13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。
1．已知如图7.5所示的有向图，请给出该图的:
（1）每个顶点的入/出度；

2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树：

3．试列出图7.8中全部的拓扑排序序列。

4．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。

5．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：
(2)计算完成整个计划需要的时间。
(3)求出该AOE网的关键路径。
∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝

(2)完成整个计划需要18天。

1.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储
C. 压缩存储 D. 索引存储
2.对线性表进行二分查找时，要求线性表必须____。
A. 以顺序方式存储 B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序
D. 以链接方式存储，且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.
4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。
5.二分查找和二叉排序树的时间性能____。
6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。
如用二次探测再散列处理冲突，关键字为49的结点的地址是____。
8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。
9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 。
A.从第0个元素往后查找该数据元素
B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素
10．解决散列法中出现的冲突问题常采用的方法是 。
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。
A.必须大于等于原散列地址
B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小没有具体限制
12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。
A.静态查找表 B.动态查找表
C.静态查找表与动态查找表 D两种表都不适合
13.散列表的平均查找长度 。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关而与表的长度有关
D.与处理冲突方法无关而与表的长度无关
8.2 填空题（将正确的答案填在相应的空中）
1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。
2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。
3.折半查找的存储结构仅限于____，且是____。
4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。
5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；
6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 次查找可确定成功；查找47时，需进行 次查找成功；查找100时，需进行 次查找才能确定不成功。
7．二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。
8．一个无序序列可以通过构造一棵 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。
9．平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。
10． 法构造的哈希函数肯定不会发生冲突。
12．在散列存储中，装填因子 的值越大，则____； 的值越小，则____。
1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
2.含九个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？
3.试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70.如果此后删除50和68，画出每一步执行后2-3树的状态。
4. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。
5. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，注意边插入边平衡。

3. 顺序存储结构、有序的
（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）
7．结点个数n、生成过程
12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用____排序法。
3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B. 选择排序

二阶复微分方程双曲函数统解的三种驱动方式及三者之间关系，于力，李峰，用二阶复微分方程统解结构原理证明，单独给出位移初始值，或称为势能驱动，显式解为双曲余弦函数；单独给出速度初始值，或称为动