6.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。 A.不发生变化 B.发生变化 C.不能确定 D.以上都不对
7.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为 个。 A.15 B.16 C.17 D.47
8.若一棵二叉树采用二叉链表存储，要交换所有分枝结点的左右子的位置，则用 遍历最合适。 A.前序 B.中序 C.后序 D.按层次
9.在n个结点的线索二叉树中，线索的数目为 个。 A.n-1 B.n C. n+1 D.2n
10.若二叉树的中序遍历序列是abcdef，则 。
A.结点C有两个孩子 B.二叉树有两个度为0的结点 C.二叉树的高度为5 D.以上都不对
11.在任何一棵二叉树中，如果结点a有左孩子b和右孩子c，则在它的先序、中序和后序遍历序列中， 。 A.b一定在a的前面 B.a一定在c的前面 C.b一定在c的前面 D.a一定在b的前面 12.如果一棵二叉树结点的前序序列和后序序列相同，则该二叉树 。
A. 度为1 B.只有一个结点 C.每个结点都没有左孩子 D.每个结点都没有右孩子 13.在高度为h的完全二叉树中， 。
A.度为0的结点都在第h层上 B.第i（）层上的结点都是度为2的结点 C.第I（1≤i 14.用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带权路径长度值为 的Huffman树。 A.33 B.15 C.34 D.54 三．填空题 1.对于一个具有n个结点的二叉树，当它为一棵 二叉树时，具有最小高度，此高度为 ，当它为一棵单支树时具有最大高度，此高度为 。 2.对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段总数为 个。其中 个用于链接孩子结点， 个空闲。 3.一棵深度为k(k≥1)的满二叉树的结点总数为 ，一棵深度为k的完全二叉树的结点总数的最小值为 ，最大值为 。 4.有m个叶子结点的Huffman树，其结点总数为 。 5.由三个结点构成的二叉树，共有 种不同的结构。 6.由权值分别为3，9，6，2，5的5个叶子结点构成一棵Huffman树，则该树的带权路径长度为 。 7.用一维数组顺序存放一棵完全二叉树：ABCDEFGHIJKL，则后序遍历该二叉树的遍历序列为 。 8.深度为k（k≥1）的完全二叉树，其前k-1层共有 个结点。 9.若二叉树的一个叶子结点是某子树中序遍历序列的第一个结点，则它必然是该子树后序遍历序列中的 个结点。 10.若一个二叉树的叶子结点是某子树的中序遍历序列的中最后一个结点，则它必是该子树的 序列中的最后一个结点。 11.一棵n个结点的满二叉树有 个度为1的结点，有 个分支结点和 个叶子结点。 12.一棵具有n个结点的树，该树中所有结点的度之和为 。 13.深度为k（k≥1）的二叉树中最多有 个结点。最少有 个结点。 14.根据二叉树的 遍历序列和 遍历序列可唯一确定一棵二叉树。 15.二叉树的存储方法有 和 两种。 四．简答题 1.试画出具有3个结点的二叉树的所有结构图。 2.写出下图所求二叉树的前序、中序和后序遍历序列。 A B C D E F G H 11 3.已知某二叉树的前序遍历序列和中序遍历序列分别是EBADCFHGIKJ和ABCDEFGHIJK，请构造该二叉树。 4.已知叶结点的权值分别为2，3，6，8，9，11，构造Huffman树，给出Huffman编码，计算带权路径长度。 5.编写一个将二叉树中每个结点的左右孩子交换的算法。 6.二叉树采用链式存储结构，设计一个算法计算一棵给定二叉树的所有结点数。 7.假设二叉树采用链式结构，编写一处算法，求二叉树中的最大结点值。 8.假设二叉树采用链接存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点。 第七章 练习题 一．判断题 1.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（） 2.邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。（） 3.任何AOV网拓扑排序的结果都是惟一的。（） 4.若连通图上的各权值均不相同，则该图的最小生成树是唯一的。（） 5.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称的。（） 6.如果连通网中存在相同权值的边，则最小生成树不唯一。（） 7.在n个结点的无向图中，若边数>n-1，则该图必是连通图。（） 8.有回路的图不能进行拓扑排序。（） 9.一个图的广度优先搜索是唯一的。（） 10.在有向图中，所有顶点的出度之和等于所有顶点的入度之和。（） 11.邻接矩阵只存储了边的信息，没有存储顶点的信息。（） 12.对图的广度优先搜索遍历需要使用队列。（） 13.最小生成树是指边数最少的生成树。（） 14.关键路径一定是由权值最大的边构成的。（） 二．选择题 1.连通分量是 的极大连通子图。 A.无向图 B.有向图 C.树 D.图 2.有n个顶点的无向图的邻接矩阵是用 数组存储的。 A.一维 B.n行n列二维 C.任意行n列 D.n行任意列 3.无向图的边数为n条，以邻接表存储该图，则表中结点的个数是 个。 A. n B.n/2 C.2n D.n2 4.强连通分量是 的极大连通子图。 A.图 B.无向图 C.树 D有向图. 5.一个加权的无向连通图的最小生成树 。 A.有一棵或多棵 B.只有一棵 C.一定有多棵 D.可能不存在 6.无向图的邻接矩阵是一个 。 A.上三角矩阵 B.零矩阵 C.对称矩阵 D.对角矩阵 7.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是 。 A.完全图 B.连通图 C.有回路 D.一棵树 8.以下说法正确的是 。 A.一个具有n个顶点的无向完全图的边数为n(n-1) B.连通图的生成树是该图的一个极大连通子图 C.图的广度优先搜索是一个递归过程 D.在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量 9.关键路径是事件结点网络中的 。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 10.有n个顶点的有向图最多有 条边。 A.n B.n(n-1) C.n(n+1) D.n2 12 11.在一个有n个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为 。 A.s B.s-1 C.s+1 D.n 12.无向图有n个顶点，则其最多有 条边。 A.n(n-1) B.n2 C.n(n-1)/2 D.n(n+1) 13.在一个无向图中，所有的顶点的度之和等于边数的 倍。 A.1/2 B.1 C.2 D.4 14.具有8个顶点的无向图至少应有 条边才能确保是一个连通图。 A.5 B.6 C.8 D.7 15.若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是 。 A.无向图 B.完全图 C.有向图 D.不带权的图 三．填空题 1.一个无向图有n个顶点e条边，则所有的顶点的度的和为 。 2.在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 。而对于无向图而言等于该顶点的 。 3.如果含n个结点的图形成一个环，则它有 棵生成树。 4.G是一个非连通无向图，共有28条边，则该图至少有 个顶点。 5.具有n个顶点的无向图，边的总数最多为 个。 6.prim(普里姆)算法适用于求 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求的 网的最小生成树。 7.有向图的极大强连通子图称为 。 8.在一个具有n个顶点的无向完全图中，包含有 条边；在一具有n个顶点的有向完全图中，包含有 条边。 9.AOE网中，从源点到汇点路径上各活动的时间总和最长的路径称为 。 10.图的最常用的存储方法是 和 。 11.求最小生成树用prim（普里姆）算法的时间复杂度是 ； 12.n个顶点的强连通有向图G至少有 条边。 13.用邻接矩阵A[1..n][1..n]存储有向图G，其第i行的所有元素之和等于顶点i的 。 14.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 ，所有邻接表中的结点总数是 。 15.对n个顶点的连通图来说，它的生成树一定有 条边。 四．简答题 ABCEGH 图1 DF1.现有无向图如图1所示，请回答下列问题： （1）给出该图的邻接矩阵和邻接表。 （2）给出从A出发深度优先遍历和广度优先遍历序列。 （3）求出每个顶点的度、邻接点和边。 2.根据图2所求有向图，回答问题 13 v1v2v3v4 （1）该图是强连通图吗？如果不是，则给出其强连通分量。 （2）请给出两个有向环。 （3）给出每个顶点的度、出度、入度。 （4）给出其邻接表、邻接矩阵和逆邻接表。 3.已知一个无向图G的邻接矩阵如图所示，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索序列。 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 4.一个有向图G的邻接表存储如图所示，回答下列问题。 （1）画出其邻接矩阵存储 （2）写出图的所有强连通分量。 1 a 2 7 ∧ 2 b 3 ∧ 4 3 c 5 2 ∧ 4 d ∧ 5 h ∧ 6 i 9 ∧ 7 e 2 8 ∧ 8 g 6 ∧ 9 f 3 7 ∧ 5.给定如图所示的带权无向图。 9V15V311V07610V278V5V4 （1）画出该图的邻接表存储结构。 （2）根据图的邻接表存储结构，从顶点V0出发，分别调用DFS(深度优先搜索)和BFS（广度优先搜索）算法遍历该图，写出遍历序列。 （3）给出采用克鲁斯卡尔算法构造最小生成树的过程。 （4）画出该图的邻接矩阵。 14 （5）给出用普里姆算法求最小生成树的过程。 （5）普里姆算法求最小生成树过程如下： i k U cost[0] [1] [2] [3] [4] [5] Adj[0] [1] [2] [3] [4] [5] v-u (u 0,v0) 0 1 2 3 4 5 最小生成树如下： 9V0V17V2567V3V4V5 6.对如图所示的有向网，试利用狄杰斯特拉算法求出从源点A到其它各顶点的最短路径，并写出求解过程。E10B21510304D420AF1510C 答：计算最小路径过程如下表： shortest path i k S A B C D E F A B C D E F 初态 1 2 3 4 5 7.已知无向图如图所示，分别用克鲁斯卡尔算法和普里姆算法求其最小生成树。 15