⑶ 一棵二叉树的第i（i≥1）层最多有（ ）个结点；一棵有n（n>0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。
⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。
⑹ 具有100个结点的完全二叉树的叶子结点数为（ ）。 【解答】50
⑺ 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（ ） ⑼ 在具有n个结点的二叉链表中，共有（ ）个指针域，其中（ ）个指针域用于指向其左右孩子，剩下的（ ）个指针域则是空的。
⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（ ），分支结点总数为（ ）。 ⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子
⑺ 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。 A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化
⑻ 如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（ ）序列，T中结点的后序序列就是 T' 中结点的（ ）序列。 A 前序 B 中序 C 后序 D 层序
⑴ 在线索二叉树中，任一结点均有指向其前趋和后继的线索。
7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。 【解答】二叉树的构造过程如图5-12 所示。
8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
【解答】构造的哈夫曼树如图5-13所示。
树的带权路径长度为：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120
9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。
【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。
9．对于一棵具有n个结点的树，其所有结点的度之和为（ ）。
10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（ ）。
⑴ 设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边；若G为有向图，则至少有（ ）条边，至多有（ ）条边。
⑵ 任何连通图的连通分量只有一个，即是（ ）。
⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。
⑺ 图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）；图的广度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。
⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用Kruskal算法求最小生成树的时间复杂度为（ ）。
⑼ 如果一个有向图不存在（ ），则该图的全部顶点可以排列成一个拓扑序列。 ⑵ n个顶点的强连通图至少有（ ）条边，其形状是（ ）。 A n B n+1 C n-1 D n×(n-1)
E 无回路 F 有回路 G 环状 H 树状
⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。 A 1 B n/2 C n-1 D n
⑸ 图的生成树（ ），n个顶点的生成树有（ ）条边。 A 唯一 B 不唯一 C 唯一性不能确定 D n E n +1 F n-1
⑹ 设无向图G=(V, E)和G' =(V', E' )，如果G' 是G的生成树，则下面的说法中错误的是（ ）。 A G' 为 G的子图 B G' 为 G的连通分量
C G' 为G的极小连通子图且V = V' D G' 是G的一个无环子图
⑺ G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A 6 B 7 C 8 D 9
⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。 A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法
⑽ 下面关于工程计划的AOE网的叙述中，不正确的是（ ）?br /> A 关键活动不按期完成就会影响整个工程的完成时间
B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 ⑶ 图G的生成树是该图的一个极小连通子图
⑸ 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。 ⑹ 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 ⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。 ⑻ 在AOE网中一定只有一条关键路径?
6．证明：生成树中最长路径的起点和终点的度均为１。 【解答】用反证法证明。
设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。 同理可证起点v1的度不能大于1，只能为1。
11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。 【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。
假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。 4．十字链表适合存储（ ），邻接多重表适合存储（ ）。
8．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1
9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。
A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 10. 关键路径是AOE网中（ ）。
A 从源点到终点的最长路径 B从源点到终点的最长路径 C 最长的回路 D 最短的回路
⑴ 顺序查找技术适合于存储结构为（ ）的线性表，而折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。
⑵ 设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。
⑹ 在散列技术中，处理冲突的两种主要方法是（ ）和（ ）。 ⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（ ）。 ⑻ 与其他方法相比，散列查找法的特点是（ ）。 ⑴ 静态查找与动态查找的根本区别在于（ ）。
A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样
⑵ 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（ ）；在查找不成功的情况下，s和b的关系是（ ）。 A s=b B s>b C s
⑶ 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（ ），查找失败时的平均查找长度是（ ）。 A 37/12 B 62/13 C 3 9/12 D 49/13
⑻ 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置的键值（ ）。
A 一定都是同义词 B 一定都不是同义词 C不一定都是同义词 D 都相同
⑴ 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。 ⑵ 二叉排序树的查找和折半查找的时间性能相同。
⑶ 若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。 ⑷ 散列技术的查找效率主要取决于散列函数和处理冲突的方法。 ⑸ 当装填因子小于1时，向散列表中存储元素时不会引起冲突。
8．已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10 构造的开散列表如下：
平均查找长度ASL=(8×1+4×2)/12=16/12
5．将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T '中，则T与T'是相同的，这种说法是否正确？
7．在散列函数H(k)= k mod m中，一般来讲，m应取（ ）。 A 奇数 B 偶数 C 素数 D 充分大的数
⑵ 对n个元素进行起泡排序，在（ ）情况下比较的次数最少，其比较次数为（ ）。在（ ）情况下比较次数最多，其比较次数为（ ）。
⑸ 对n个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。 ⑹ 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（ ）。
⑻ 对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（ ）的结点开始。
⑶ 对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。 A 堆排序 B插入排序 C快速排序 D 直接选择排序
⑸ 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（ ），就平均时间而言，（ ）最佳。
A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序
⑹ 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。 A快速排序 B堆排序 C希尔排序 D 归并排序
⑸ 设有键值序列（k1, k2, …, kn），当i>n/2时，任何一个子序列（ki, ki+1,… , kn）一定是堆。 1．评价基于比较的排序算法的时间性能，主要标准是（ ）和（ ）。 5．排序趟数与序列的原始状态有关的排序方法是（ ）。 A 直接插入排序 B 简单选择排序 C 快速排序 D 归并排序
8. 如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？对于序列{57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7}，得到其第4个最小元素之前的部分序列{6,7,9,11}，使用所选择的排序算法时，要执行多少次比较？
【解答】采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度Ο(n+klog2n)，若k≤nlog2n，则得到的时间复杂性是Ο(n)。
对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下： 初始建堆：比较20次，得到6； 第一次调整：比较5次，得到7； 第二次调整：比较4次，得到9； 第三次调整：比较5次，得到11。