第六章 树和森林

1. 二叉树的第k层节点数最多为（2^k-1）。
2. 将森林F 转换为对应的二叉树T，F中叶结点的个数等于（）
   【答】二叉树变森林方法为右孩子A变兄弟节点。若该孩子节点A有左孩子，则带着左孩子一起分离形成独立的树。若无左孩子，则成为孤立节点。
3. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有（2n）个指针域，其中有（n-1）个指针域是存放了地址，有（n+1）个指针是空指针。
4. 设某棵二叉树中度数为0的节点数N0，度数为1的节点数N1，则，该二叉树中度数为2的节点数为（N0-1）；若采用二叉链表作为存储结构，则二叉树中共有（2N0+N1）个空指针。
5. 具有 10个叶结点的二叉树中有 ( )个度为2的结点。
   A.8 B.9 C.10 D.11
   【答】B

• 假设在二叉树中度为0的结点有n0个，度为1的结点有n1个，度为2的结点有n2个，
• 则总的结点数n=n0+n1+n2；总的分支数B=n1+2n2。
• 又因为B=n-1，所以在二叉树中 n2=n0-1。

7. 设给定权值总数有n个，其哈夫曼树的结点总数为（)。
   A.不确定 B. 2n C. 2n+1D. 2n-1
   【答】D

• 已知叶子结点数为n，则根据上题得到度为2的结点数为n-1。
• 而在哈夫曼树中只有度为0的结点和度为2的结点，所以结点总数为:2n-1。

8. 一个具有1025个结点的二叉树的高度h可能为（)。
   A.8 B.9 C.12 D.1026
   【答】C
   根据二叉树的性质3，含有n个结点的二叉树的高度范围在⌈log2(n+1)⌉到n之间。所以具有1025个结点的二叉树的高度最小为11，最大为1025。因此，只有C符合要求。
9. 一棵二叉树高度为h，所有结点的度 或为0或为2，则这棵二叉树最少有(2h-1）个结点。

• 要达到结点数最少，且所有结点的度为0或为2，则这棵二叉树中，除第一层只有一个根结点外，其他h-1层都只有2个结点，所以总结点数为2h-1。

10. 一棵二叉树的先序序列为ABCDEFG，它的中序序列可能是（)。
    A. CABDEFG B.ABCDEFG C. DACEFBG D. ADCFBEG
    【答】B
    如果二叉树的先序序列为 ABCDEFG,则以答案A、C、D选项作为中序序列都无法构造出相应的二叉树。
11. 将一棵树 t 转换二叉树 h ，则t的后根遍历等于h的（）。
    A.先序遍历B.中序遍历C.后序遍历D.层次遍历
    【答】B
12. 一棵非空二叉树的先序序列与后序序列正好相反，则该二叉树一定满足（）
    A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶子结点 D.是任意一棵二叉树
    【答】C

• 如果一棵二叉树只有一个叶子结点，则说明这棵二叉树中除叶子结点外其他结点有且只有唯一的孩子(左孩子或右孩子)结点。对于这样的二叉树，其先序序列和后序序列一定正好相反。
• 再来看有多个叶子结点的情况，以有2个叶子结点的二叉树为例(可以推广到有更多叶子结点的情况)，证明其先序序列与后序序列不能正好相反。设二叉树有两个叶子结点B和C，它们有离它们最近的共同祖先A(B在A的左子树，C在A的右子树)。根据先序遍历的定义，在先序序列中这3 个结点相对次序为A、…、B、…、C；根据后序遍历的定义，在后序序列中这3个结点相对次序为B、.、C、…A。可见，在先序序列和后序序列中，叶子结点B、C之间相对次序不变。所以，对于有2个叶子的二叉树，其先序序列不会是后序序列逆序。

13. 在二叉树的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）
    A.都不相同C.完全相同B.先序和中序相同，而与后序不同屿 D.中序和后序相同，而与先序不同
    【答】C
14. 一棵根结点没有左子树的二叉树在先序线索化后，其中空的指针域有（）个。
    A.不确定 B.0 C. 1 D.2
    【答】D

• 在线索二叉树中，空指针最多2个，且只可能出现在序列的第一个元素结点和最后一个元素结点(其他结点的指针要么指向左右孩子，要么作为线索指向前驱或后继)。
• 因为，第一个元素没有前驱，则当其没有左孩子时，其左指针为空(前驱线索也不存在)；最后一个元素没有后继，则当其没有右孩子时，其右指针为空(后继线索也不存在)。
• 而在二叉树的先序遍历中，第一个被访问的结点一定是根结点，最后被访问 的结点一定是叶子结点。现在，根结点没有左子树，所以有2个空指针。其一是根结点的左指针，其二是先序序列最后一个结点的右指针。

15. 从一个空堆开始依次插入34、46、19、12、17、25、38、 25、20,则最后建立的最小堆序列中最后一个元素的值为（)。
    A.46 B.25 C.20 D.以上都不是
    【答】B

• 按照最小堆插入算法，最后得到的最小堆序列为:12、17、25、20、19、34、38、46、 25.所以，选择B。

16. 对于有n个结点的二叉树，其高度为logg2n。(错)
    根据二叉树的性质3，有n个结点的二叉树，其高度最小值为⌈log2(n+1)⌉，最大值为n。
17. 一棵树的叶结点在先根序历和后根序历中，相对位置不变。(对)
18. 对后序线索树进行后序遍历时必须用栈。(错)

• 当二叉树中任何结点至多只有左子树时，每个结点的右指针都作为线索指向其后继结点。此时，从后序序列的第一个结点开始，通过后继线索就可以完成后序遍历。

19. 对先序线索树可以不用栈实现先序遍历。(对)
20. 在完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（对)

• 在完全二叉树中，由于同一层上结点是连续分布的。因此，如果一个结点没有左孩子，则其必定没有右孩子。所以，它一定是叶子结点。

21. 一棵树的叶子数一定等于其对应二叉树的叶子数。(错)

• 根据树转换为二叉树的规则，二叉树中结点的左指针用于指向其树中第一个孩子结点，右指针用于指向其树中下一个兄弟结点。因此，二叉树中叶子结点，在对应树中必定没有孩子结点(是叶子)且没有下一个兄弟。

22. 非空的二叉树一定满足：某结点p若有左孩子，则在中序序列中p的前驱结点一定没有右孩子。（对）
    如果一个结点有左子树，根据中序遍历的定义，该结点的前驱结点一定是其左子树按中序遍历最后被访问的结点。而对一棵子树进行中序遍历最后访问的结点一定没有右子树。所以，这个叙述是正确的。
23. 在中序线索树中，每一非空的线索均指向其祖先结点。（对）

• 根据中序遍历的定义，在中序序列中，一个结点的前驱结点不可能在它的右子树中，只能在其左子树或祖先结点中。
• 如果一个结点有左子树，则其左指针将作为孩子指针指向其左孩子；否则，其左指针将作为前驱线索，指向其前驱结点，它只能在祖先结点或者为空(中序序列的第一个结点没有前驱)。
• 同样，一个结点的右指针作为后序线索（没有右子树)时，其后继结点一定在其祖先结点中。

24. 二叉树中序线索化后，不存在空指针域。（错)

• 应该说对非空二叉树线索化后一定存在两个空指针域。根据中序遍历的定义，在二义树的中序序列中，第一个结点一定没有左孩子，最后一个结点一定没有右孩子。
• 所以，对于中序序列的第一个结点来说，其左指针一定是空的(它没有左孩子，也没有前驱结点):对于中序序列的最后一个结点来说，其右指针一定是空的(它没有右孩子，也没有后继结点)。而其他的左指针要么指向左孩子结点，要么指向前驱结点:其他的右指针要么指向右孩子结点，要么指向后继结点。

25. 哈夫曼树的结点个数不可能是偶数。(对）
    根据哈夫曼树的构造算法，在哈夫曼树中只有度为2和度为0的结点。又由于在一棵二叉树中度为2的结点数一定比度为0的结点数少1。所以，在有n个叶子结点的哈夫曼树中，总结点数为2*n-1，它一定是奇数。
26. 具有 256个结点的完全二叉树的深度为（9）
27. 一棵有20个结点的二叉树，其叶子结点有8个，则度为1的结点有（5）个。
    叶子结点有8个，则度为2的结点有7个。所以，度为1的结点数为:20-8-7=5。
28. 设F是由T、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2和 n3，则二叉树B的根结点的左子树中有()个结点，根结点的右子树中有() 个结点。
    【答】n-1, n2+n3
29. 设一棵完全二叉树的叶子结点数为k，最后一层结点数为2，则该二叉树的高度为（）。
    【答】log2(k-1)+2

• 设完全二叉树的高度为h。由于最后一层上有2个结点，且叶子总数为k，所以最后第二层（(h-1)层)上的结点数为k-1。又因为二叉树第(h-1)层上的结点总数为2^h-2，因此，这棵二叉树的高度h为 10g2(k-1)+2。

30. 一棵二叉树的先序序列为 BEFCGDH，中序序列为 FEBGCHD，则它的高度为(4)。
31. 已知完全二叉树的第7层有 10 个叶子结点，则整个二叉树的结点数最多是（235）
    根据已知:完全二叉树的第7层有10个叶子结点，且整个二叉树的结点数要达到最大值。因此，该二叉树的高度为8，且比高度为8的满二叉树少20 个叶子结点(使第7层有10个叶子结点)。所以，二叉树的结点数为:2⁸-1-20=235。
32. 树的先根序列和其对应二叉树的（）序列相同；后根序列和对应二叉树的（）序列相同。
    【答】先序，中序
33. 设一棵后序线索树的高为50，结点x是树中的一个结点，其双亲为结点y，y的右子树高度是31x是y的左孩子，则确定x的后继最多需经过（）个中间结点(不含后继及x本身)。
    【答】31

• 由于x是y的左孩子，根据后序遍历的定义，x的后继应为y的右子树中按后序遍历第一个访问的结点，而此结点为y的右子树中最左下的叶结点。
• 所以，确定x的后继需要经过x的双亲y，再找y的右子树中最左下的叶结点。由于y的右子树高度是31，所以确定x的后继最多需经过31个中间结点。

34. 一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有（）个。
    【答】16

• 设满二叉树的高度为h，则它的结点总数为2^h-1。
• 已知满二叉树的结点个数为20到40之间的素数，因此，符合要求的结点数为31，满二叉树的高度为5。所以，叶子结点数为16。

35. 一棵有n个叶子结点的完全二叉树，其最底层结点数 >=2，则此二叉树的深度为（）。
    【答】⌈log2(n+1)⌉
    设完全二叉树中有m个度为1的结点。已知：二叉树中有n个叶子结点，则度为2的结点数为n-1。所以这棵二叉树的结点总数为2n+m-1，其中m的值为0或1。
    根据二叉树的性质3，其高度为⌈log2(2n+m)⌉。又因为最底层结点数大于等于2，且叶子数n不等于2的幂，因此⌈log2(2n+m)⌉=⌈log2(n)⌉=⌈log2n⌉。
36. 已知一棵二叉树的中序序列为GLDHBEIACJFK，后序序列为 LGHDIEBJKFCA
    (1)画出这棵二叉树；(2)将它转换为对应的森林。
    
37. 如图1-7所示，将三棵树组成的森林转换为二叉树(只要求给出转换结果)。

36. 设集合中元素为{0,1,2,3,4,5,6,7,8,9, 10, 11, 12, 13, 14, 15,16}，按下面三个要求，分别给出下列有关并查集的操作序列的运算结果:union(1, 2)，union(3,4), union(3,5),union(1,7), union(3,6),union(8, 9),union(1, 8), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(16, 0), union(14,16), union(1, 3), union(1, 14)。
    要求:
    (1)对于 union(i,j)，以i作为j的双亲。
    (2)按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲。
    (3)按和j为根的树的结点个数实现union(i，j)，结点个数多者为结点个数少者的双亲。
    

第七章 图

1. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为，则e=（d/2）。
2. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（错）如果有回路
3. 带权无向图的最小生成树是唯一的。（对）
4. 设某强连通图中有n个顶点，则该强连通图中至少有（n )条边。
5. 有n个顶点的连通无向图，其边的个数至少为（A. n-1）
6. 用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是（)。
   A.逆拓扑有序 B.拓扑有序 C.无序的 D.递增有序
   【答】C
   首先，这里的递增有序概念不清，肯定排除在外。
   拓扑有序是指如果顶点U到顶点V有一条弧，则在拓扑序列中U一定在V之前；
   而逆拓扑有序指如果顶点U到顶点V有一条弧，则在拓扑序列中U一定在V之后。
   DFS（深度优先遍历)是一个递归算法，在遍历的过程中，先访问的顶点先入栈(栈是先进后出)，但它不能保证某个顶点的所有前驱顶点一定比它先访问(先入栈)。所以，输出的顶点序列不会是拓扑有序，也不能保证是逆拓扑有序。
7. 关键路径是AOE网络中（A.从源点到汇点的最长路径)。
8. 无向图G=(V,E)，其中:V={a, b, c, d, e,f}，E={(a,b),(a,e) ,(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
   A. a, b, e, c, d, f B. a, c, f, e, b, d C. a, e, b, c, f,d D.a, e, d, f, c,b
   【答】D
9. 对于有n个顶点e条边的无向网，采用邻接表存储时，构造最小生成树的Prim算法的时间复杂度为（）
   A.O(n) B.O(n+e) C. O(n²) D. O(n³)
   【答】C

• 在 Prim算法中，主要有两个并列的for循环。对于有n个顶点e条边的无向网，
• 算法第一个for循环执行n-1次对辅助数组 closearc[]进行初始化；
• 第二个for循环是个二重嵌套循环，外循环执行n-1次把n-1个顶点加入U中，每加入一个顶点到U，有两个并列的for循环分别实现查找具有最小权值的边和修改辅助数组 closearc[]，它们的时间复杂度均为O(n)，所以整个算法的时间复杂度为O(n²)

10. 对于有n个顶点e条边的有向网，求解最短路径的Floyd算法的时间复杂度为（）。
    A.O(n) B.O(n+e) C. O(n²) D. O(n³)
    【答】D

• 在 Floyd算法中，主要有两个并列的for循环。对于有n个顶点e条边的有向网，
• 算法第一个for循环是个二重嵌套循环，内外循环都执行n-1次，完成 path[][]数组和 dist[][]数组的初始化。
• 第二个for循环是个三重嵌套循环，3个循环都执行n-1次，通过 path[][]数组和 dist[][]数组的修改，求出任意两点之间的最短路径，
• 所以整个算法的时间复杂度为 O(n³)。

11. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（)。
    A.G中有弧<Vi,Vj> B.G中有一条从Vi到Vj的路径 C.G中没有弧<Vi,Vj> D.G中有一条从Vj到Vi的路径
    【答】D
    根据拓扑排序算法，如果G中有一条从顶点V到顶点U的路径，则在拓扑序列中顶点V一定在顶点U之前。
12. 用邻接表表示图，对于有n个顶点e条边的有向网，拓扑排序算法时间复杂度为（)。
    A. O(n) B. O(n+e) C. O(nn) D.O(nn*n)
    【答】B

• 根据拓扑排序算法，对于用邻接表表示的有n个顶点e条边的有向网，
• 算法的第一个for循环是搜索入度为零的顶点建立链栈，其所需要的时间是O(n)。
• 在拓扑排序的过程中，如果网络中没有回路，则网络中所有顶点都需要进一次栈，出一次栈，所需要的时间也是O(n)。
• 顶点入度减一的运算共执行了e次。所以拓扑排序算法的时间复杂度为O(n+e)。

13. 下列关于AOE 网的叙述中，不正确的是()。
    A.关键活动推迟完成，就一定会影响整个工程的完成时间
    B.任何一个关键活动提前完成，那么整个工程将会提前完成
    C.所有的关键活动提前完成，那么整个工程将会提前完成
    D.某些关键活动提前完成，那么整个工程会提前完成
    【答】B

• 关键路径是AOE 网中从起点到终点路径长度最长的路径，在一个AOE网中可以有多条关键路径。
• 任何一个关键活动推迟完成，必然使其所在的关键路径的长度增加，所以一定会影响整个工程的完成时间。
• 如果一个AOE网中有多条关键路径，其中部分关键活动是所有关键路径共同拥有的，另外一些关键活动是不同关键路径分别拥有的，则当某一不同关键路径分别拥有的关键活动提前完成时，整个工程将不会提前完成；当某一所有关键路径共同拥有的关键活动提前完成时，整个工程将会提前完成。当然，所有的关键活动提前完成时，AOE 网中从起点到终点路径长度最长的路径一定缩短，所以整个工程将会提前完成。

14. 有e条边的无向图，在邻接表中有2e边结点。（对）
15. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（错）
    有向图中顶点V的度等于其邻接矩阵中第Ⅴ行中的1的个数与第V列中的1的个数之和。
16. 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
    （对）
17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（对）
18. 一个有向图的邻接表和逆邻接表中弧结点的个数可能不等。(错）
19. 用不同的求最小生成树的算法，最后得到的生成树一定是相同的。（错）
20. 任何有向图的结点都可以排成拓扑序列，但拓扑序列不唯一。（错）
    只有无环有向图的结点才可以排成拓扑序列，而且拓扑序列不一定唯一。
21. 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑序列必定存在。（对)
    若一个有向图的邻接矩阵对角线以下（或以上)的元素均为零，则该有向图一定无环。因此，该有向图一定可以进行拓扑排序。
22. 在AOE图中，关键路径上某活动的时间延长w，则整个工程的完成时间也就随之延长w。(对）
23. 设无向图G有n个顶点和e条边，每个顶点V的度为di (1<=i<=n),则 e=（∑di /2）
    由于一条边依附两个顶点，所以在计算顶点的度时每条边会被计算2次，因此边的数目等于所有顶点度之和的一半。（握手定理）
24. G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
    【答】9

• 8个顶点的完全无向图有8*（8-1）/2=28条边，因此有28条边的一个非连通无向图至少有9个顶点。

25. 有n个顶点的有向图中，如果要使任意两点间可以互相到达，则至少需要（）条弧。
    【答】n

• 对于有n个顶点的有向图，可以用n条弧组成一个有向环，使图中任意两点都可以相互到达。如果只有n-1条弧，则无法让n个顶点构成环，因此也不可能使任意两点都可以相互到达。

26. 在有n个顶点的有向图中，每个顶点的度最大可达（ 2(n-1) ） 。
    每个顶点有n-1个入度和n-1个出度。
27. 有n个顶点的连通无向图的邻接矩阵至少有（）个非零元素。
    【答】2(n-1)

• 有n个顶点的连通无向图至少有n-1条边，每条边在邻接矩阵中有两个1(非零元素)表示。所以，有n个顶点的连通无向图的邻接矩阵至少有2(n-1)个非零元素。

28. 已知一个无向图G=(V, E)，其中V={a, b, c, d, e}, E={(a,b), (a,d),(a,c), (d,c), (b,e)}。现用某种图的遍历方法从顶点a开始遍历图，得到的遍历序列为abecd，则采用的是（）遍历方法。
    【答】深度优先
    对该图从顶点a出发进行深度优先遍历可以得到的顶点序列有以下4个:a、b、 e、 c、d; a、 b、e、 d、c; a、 c、d、 b、 e; a、d、c、 b、 e。
29. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需（队列）存放被访问的结点以实现遍历。
30. 求图的最小生成树有两种算法，（Kruskal）算法适合于求稀疏图的最小生成树。
31. 求从某源点到其余各顶点的 Dijkstra算法，在图的顶点数为10时，用邻接矩阵表示图时计算时间约为 10ms。则在图的顶点数为40时，其计算时间约为（）。
    【答】160ms。

• Dijkstra 算法的时间复杂度为O(n²)，因为当图的顶点数为10时，该算法计算时间约为10ms，也就是说 10²K=10ms，所以K=0.1ms。现在图的顶点数为 40，则40²K=160ms。

32. 设有向图有n个顶点和e条边，进行拓扑排序时，其时间复杂度为（ O(n+e) ）。
33. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
    
34. 画出图 所示的无向图的邻接多重表，使得其中每个无向边结点中第一个顶点序号小于第二个顶点序号，且每个顶点的各邻接边的链接顺序为它所邻接到的顶点序号由小到大的顺序。列出深度优先和广度优先搜索遍历该图所得顶点序列和边的序列。
    
    
35. 如图所示的有向图，请给出该图的
    (1)每个顶点的入/出度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表；(5)十字链表。
    
    
    3.请对图1-19所示的无向带权图:
    (1)写出它的邻接矩阵，并按 Prim算法求其最小生成树:
    (2)写出它的邻接表，并按Kruskal 算法求其最小生成树。
    
    
    
    

第八章 查找

1. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3] 的比较列的下标依次为（9，4，2，3）。
2. 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为()
   【答】6.5
   
3. 设顺序表长n，顺序查找的平均比较次数（(n+1)/2）。
4. 设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（log2n +1）。
5. 设查找表中有100个元素，如果用二分法查找方法查找数据元紊，则最多需要比较（7）次就可以断定数据元素X是否在查找表中。
6. 设有序顺序表中有n个数据元素，则第i个位置上插入一个数据元素需要移动（n+1-i）个数据元素，删除第i个位置上插入一个数据元素需要移动（n-i）个数据元素。
7. 在二叉排序树中插入一个结点的时间复杂度为O(log2n)。
8. 向一棵B树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度（增加1）。
9. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ C.O (log2n) ）
10. 下面关于折半(二分)查找的叙述正确的是（)。
    A.表中元素必须有序，但表可以顺序方式存储，也可以链表方式存储
    B.表中元素必须有序，而且表中元素只能从小到大排列
    C.表中元素必须有序且必须是整型、实型或字符型
    D.表中元素必须有序，且表只能以顺序方式存储
    【答】D

• 折半(二分)查找是根据区间中间位置元素与被查元素进行比较来确定下一步动作的，所以它对查找表有两个要求：其一是查找表元素必须有序(可以递增，也可以递减)；其二查找表只能顺序存储，不能链式存储。

12. 具有12个元素的有序表，在等概率查找情况下，折半查找的平均查找长度为（）。
    A.3.1 B.4 C.2.5 D.5
    【答】A

• 根据折半查找构造的查找树第一层只有1个结点，第二层有2个结点，第三层有4个结点，第四层有5个结点，所以在等概率查找情况下平均查找长度为(11+22+34+45)/12。

13. 当采用分块查找时，数据的组织方式为（）
    A.数据分成若干块，每块内数据有序
    B.数据分成若干块，每块内数据不必有序，但块间必须有序，按每块内最大(或最小)的数据组成索引块
    C.数据分成若干块，每块内数据有序，按每块内最大(或最小)的数据组成索引块
    D.数据分成若干块，每块(除最后一块外)中数据个数需相同
    【答】B
14. 二叉排序(查找)树的查找效率与该树的（C.树型）有关。
    A.高度答案:CB.结点的多少C.树型D.结点的位置

• 对于有n个结点的二叉排序树，当树的高度为n时(相当于单支树)其查找效率最低；当树的高度为log2n 时其查找效率最高。
• 所以，二叉排序树的查找效率不能只从高度或者只从结点数分析，而是与和树的高度及结点数都相关的树型有关。

15. 分别按下列序列构造二叉排序树，其中与其他3 个序列所构造的结果不同的是（）。
    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)
    【答】C

• 序列C构造的二叉排序树的先序序列为:100,60，80, 90,120,110,130；而其他3个序列构造的二叉排序树的先序序列都为:100,80, 60,90,120,110,130。

16. 在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为А，并已知插入后A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（D.RR）型调整以使其平衡。
    A. LL B.LR C. RL D.RR
    由于插入后A的左孩子的平衡因子为0，右孩子的平衡因子为1，所以插入结点是在A的右孩子的右子树上。因此要进行RR平衡旋转。
17. 下列关于m阶B-树的说法错误的是（）
    A.根结点至多有m棵子树 B.所有叶子都在同一层次上
    C.非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树 D.根结点中的数据是有序的
    【答】C
    根据B-树的定义，根结点至少有2个孩子，除根以外的非叶子结点(失败结点)至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树。
18. 设有一组记录的关键字为19，14,23,1,68, 20，84, 27, 55, 11，10, 79%散列函数为H(key)-key%13，用链地址法处理冲突，则散列地址为1的链中有（）个记录。
    A.1 B.2 C.3 D.4
    【答】D 因为散列函数为H(key) =key%13，{0,13,26,39,52,65,78,…}所以得到14、1、27、79。
19. 设散列表长为14，散列函数是H(key)=key % 11，用二次探测再用散列法处理冲突，表中已有4个数据的关键字为15，38, 61, 84。现要将关键字为49的数据插入表中，则它存放的位置为（） A.8 B.3 C. 5 D.9
    【答】D
    在插入关键字为49的数据前散列中有4个数据分别在4、5、6、7位置。根据散列函数H(key) =key% 11，关键字为49的数据其散列地址为5，发生冲突；根据二次探测再散列法处理冲突，求得再散列地址为6，又发生冲突；第2次再散列求得散列地址为4，还是冲突；第3次再散列求得散列地址为9，没有冲突。
20. 负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（）
    【答】对
21. 在有序表中，对于查找同一元素来说，折半查找的效率总比顺序查找高。（）
    【答】错
22. 在索引顺序表中实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
    【答】对
    索引顺序表进行分块查找，在等概率查找情况下，其平均查找长度 ASL=ASLindex + ASLSubLit。其中 ASLindex表示确定所在块的平均查找长度，ASLsubLit表示块内平均查找长度。
23. 在等概率情况下，二叉排序树查找成功的平均查找时间总是小于用顺序查找的平均查找时间。()
    【答】错

• 当有n个结点的二叉排序树的高度为n时，在等概率情况下其平均查找时间与有n个元素的顺序表查找一样。

24. 在二叉排序树中插入一个新结点，它总是插到叶结点的下面。
    【答】错。
    例如，一个结点有右子树但没有左子树，如果插入的元素关键字比该结点的关键字小，则被插入元素作为该结点的左孩子插入。
25. 一棵二叉排序树的先序序列一定是有序序列。（错）
26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与原二叉排序树一定相同。
    【答】错
    例如，被删除结点有左右子树，删除该结点后用其左子树中最大值代替该结点中的元素，再次插入该元素时，其必然被插入原结点的右子树中，因此前后两棵树不相等。当然，如果被删除结点是叶子结点，则再次插入后，前后两棵树相等。
27. 在Β-树的插入算法中，通过结点的向上“分裂”来代替专门的平衡调整。（）
    【答】对

• 在B-树的插入算法中，当被插入结点中的数据元素超过允许的最大值时，总是分裂结点的中间位置上的关键字。因此，无论按何次序插入关键字序列，树都是平衡的。

28. B+树既能进行索引查找，又能进行顺序查找。（对）
29. 散列表的地址区间为0~17，散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59 依次存储到散列表中，元素 59存放在散列表中的地址为8。
    【答】错
    在插入59之前，关键字为26、25、72、38、8、18的数据元素分别在9、8、4、38、10、1位置。H(59)=8，由于在8、9、10位置都有元素，11 位置空闲，所以根据线性探测法处理冲突59应该放在11位置。
30. 顺序查找有n个元素的顺序表，若查找成功，则比较关键字的次数最多为（n）次；当使用监视哨时，若查找失败，则比较关键字的次数为（n+1）。
    查找成功时，关键字比较次数最多的情况是待查元素和顺序表里的n个元素都进行了比较，最后一次比较确定查找成功:查找失败，则待查元素需要与顺序表里的n个元素以及监视哨元素都进行比较。
31. 在有序表(8,11,15,19,25,26,30,33,42,48,50) 中，折半查找关键字为20的元素，需进行的关键字比较次数为（3）
    第一次与区间中间元素26进行比较，第二次与元素15 进行比较，第三次与元素19进行比较，最后确定区间中没有元素，查找失败。
32. 在高度为4的3阶B-树中，最多有（）个数据元素。
    【答】26

• 在高度为4的3阶B-树中，叶子结点(失败结点)在第4层，非叶子结点有3层，第一层只有1个结点，第二层有3个结点，第三层有9个结点，每个非叶子结点中最多有2个数据元素，所以该3阶B-树中最多的数据元素数目为:(1+3+9)*2。
• 在有些教材中定义的Β-树中不包括失败结点，此时本题求解时需要增加第四层27个结点，因此B-树中不包括失败结点时答案应该是80。

33. 在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是（）；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是（）。
    【答】m-1, ⌈m/2⌉-1

• 在m阶B-树中一个结点（非失败结点)最多有m棵子树，因此结点中数据元素最多有m-1个。
• 若在某结点中插入一个新关键字而引起该结点分裂，说明该结点中数据元素数目在插入前已经达到最大值。在m阶B-树中一个元素结点(非根结点)最少有⌈m/2⌉-1棵子树，因此结点中数据元素最少有⌈m/2⌉-1个。
• 若在某结点中删除一个关键字而导致结点合并，说明该结点不是根结点，且结点中数据元素数目在删除前己经达到最小值。

34. 散列表是通过将关键字按选定的（）和（），把元素按关键字转换为地址进行存储的线性表。
    【答】散列(哈希)函数，处理冲突的方法
35. 假定有k个关键字互为同义词，若用线性探测处理冲突，把这k个关键字存放到散列表中，至少要进行（）次探测。
    【答】k(k+1)/2

• 插入第1次数据元素至少需要1 次探测，插入第2 次数据元素至少需要2次，…插入第k次数据元素至少需要k次探测，所以总共至少需要进行k(k+1)/2探测。

36. 具有n个关键字的3阶Β树的查找路径长度不会大于（）。
    【答】⌈log2(n+1)⌉+1

• 在3阶B-树中，每个数据元素结点至少有1个数据元素、2棵子树，所以具有n个关键字的3阶B树的高度为⌈log2(n+1)⌉+1 (包括失败结点)。
• 因此，当查找失败时，查找路径长度达到最大值 10g2(n+1]+1。

37. 在一棵有n个结点的二叉排序树中进行查找，平均时间复杂度的上限(即最坏情况平均时间复杂度)为（）。
    【答】O(n)

• 在最坏情况下一棵有n个结点的二叉排序树的高度为n，所以其平均时间复杂度为O(n)。

38. 有144个数据元素，若采用分块查找法，且每块长度为 8，则平均查找长度为（）
    【答】14或者7.85

• 有144个数据元素，每块长度为8，所以总共有18个块。
• 如果以顺序查找确定块，则ASL=ASLindex+ ASLSubLit (18+1)/2+(8+1)/2=14
• 如果以折半查找确定块，则 ASL= ASLindex t ASLSubLit=log2(18+1)-1+(8+1)/2=7.85。
  10.高度为8的平衡二叉树的结点数至少有（）个。
  【答】54
• 设h(k)为高度等于k的平衡二叉树的结点极小值。
• 显然h(1)=1,h(2)=2,并且有h(k+2)=h(k+1)+h(k)+1。
• 所以，h(3)=h(2)+h(1)+1=4,…,h(8)=h(7)+h(6)+1=54。

39. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。
    
    【答】j+1；hashtable[j].key==k。
40. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
    
    【答】n-i，r[j+1]=r[j]
41. 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtable 中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0.
    
    【答】hashtable[i]=0;hashtable[k]=s
42. 散列表的地址空间为[0…12]，散列函数为H(k)=3*k mod 13，并用线性探测处理冲突，则对关键字序列22,41, 53,46,30,13,1,67,51。
    (1)构造散列表，画示意图。
    (2)计算装填因子。
    (3)计算在等概率情况下查找成功的平均查找长度。
    (4)计算在等概率情况下查找不成功的平均查找长度。
    
43. 试从空树开始，画出按以下关键码顺序:25、11、57、32、48、63、50、74、69建立3阶B树(2-3树)的过程(每插入一个关键字画出一棵树形)。然后删除57 和25，请画出每一步执行后2-3树的状态。
    建立2-3树的过程如图1-32(a)所示，删除57后的结果如图1-32 (b)所示，再删除O025后的结果如图1-32©所示。
    

第九章 排序

1. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（ O(log2n)），整个堆排序过程的时间复杂度为（O(nlog2n)）。
2. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ 堆排序）。
3. 下列四种排序中( A快速排序 )的空间复杂度最大。
   A快速排序 B冒泡排序 C希尔排序D 堆
4. 快速排序中最坏的时间复杂度（O(n²)），平均时间复杂度（O(log2n)）。
5. 试问:对初始状态如下(长度为n)的各序列进行直接插入排序时，至多需进行多少次关键字间的比较(要求排序后的序列按关键字自小至大顺序有序)?
   (1)关键字（(自小至大)顺序有序:(key1 <key2 <…＜<keyn)；
   【答】每趟进行1次比较，总共进行n-1趟插入，所以需要进行n-1次关键字比较。
   (2)关键字(自大至小)逆序有序:(key 1>key2>…>keyn)；
   【答】第1趟进行1次比较，第2趟进行2次比较…第i趟进行i次比较，总共进行n-1趟插入，所以总共需要进行n(n-1)/2次关键字比较。
   (3)序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序： (key,1<key3 <…, key2 <key4<…);
   【答】题目要求比较次数的最大值，因此所有序号为偶数的关键字比序号为奇数的关键字都小。对于序号为奇数（2i+1)的数据元素，它只要进行1次比较；对于序号为偶数(2i+2)的关键字，它要和前面i个原先奇数序号的数据元素比较，还要和原先序号为2i的元素进行比较。所以总的关键字比较次数为：（n-1+ Σ(i=1~⌊n/2⌋) i）。
   (4)前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序:
   (key1<key2<…<key⌊n/2⌋，,key⌊n/2⌋+1>…>keyn)。
   【答】题目要求比较次数的最大值，因此所有序号为偶数的关键字比序号为奇数的关键字都小。对于序号为奇数(2i+1)的数据元素，它只要进行1次比较；对于序号为偶数(2i+2)的关键字，它要和前面2i+1个数据元素比较。所以总的关键字比较次数为:（⌊n/2⌋-1+ Σ(i=⌊n/2⌋+1 ~n) i）。
6. 对长度为n的数据元素序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
   (1)当n=7时，在最好情况下需进行多少次比较?请说明理由。
   (2)对n=7给出一个最好情况的初始排列实例。
   【答】(1)快速排序的最好情况是每一趟排序都能将给定元素放在子序列的中间位置。对长度为7的数据元素序列，将给定元素放在中间位置需要进行6次比较。对其前后两个长度为3的数据元素序列，将给定元素放在中间位置各需要进行2次比较。所以，对长度为7的数据元素序列进行快速排序，最好情况下要进行10次比较。
   (2)对n=7时，一个最好情况的初始排列实例如下:(61, 32, 104,57, 98, 77,45)。
7. 下面四种排序法中，排序趟数与序列的原始状态有关的排序方法是（).
   A.插入排序B.选择排序C.冒泡排序D.基数排序
   【答】C

• 对于有n个数据元素的序列，插入排序和选择排序总是需要进行n-1趟排序，它们和序列的初始状态无关。
• 基数排序根据关键字上每一位数字进行分配和回收，所以排序趟数也与序列的初始状态无关。
• 在冒泡排序的一趟排序过程中，如果没有进行数据元素交换，说明序列已经有序，不需要进行下一趟排序。所以，冒泡排序在最好情况下(初始序列已经有序)只需要进行一趟排序:在最坏情况下(例如，初始序列逆序)需要进行n-1趟排序，所以冒泡排序的排序趟数与序列的初始状态有关。

8. 下面四种排序方法中，排序过程中的比较次数与序列的原始状态无关的是()。
   A.选择排序B.插入排序快速排序D.堆排序
   【答】A

• 对于有n个数据元素的序列，选择排序第1趟总是要进行n-1次比较，挑选出序列中最小(或最大)的数据元素，然后在剩下n-1个数据元素中进行n-2次比较，选取关键字最小(整个数据表中次小)的数据元素，如此重复(如第i趟，i=1,n-1)，总是在当前剩下的n-i+1个待排序数据元素中进行n-i比较，选出关键字最小的数据元素，作为有序序列的第i个数据元素。所以，选择排序的比较次数与序列的原始状态无关。
• 插入排序的比较次数与序列的原始状态有关，在最好的情况下(即在排序前数据元素已经按关键字大小从小到大排好序)，每趟插入只需与前面有序序列的最后一个数据元素进行一次比较，其总的关键字比较次数为n-1；而在最坏情况下，即第i趟插入时，待插入元素必须与前面i个数据元素都进行比较，则总的关键字比较次数 n(n-1)/2。
• 快速排序的比较次数与序列的原始状态有关，最好情况是每次划分把待排序序列分成左右两半长度相同的子序列；最坏情况是每次划分把枢纽元素放置在序列的两端，不同情况下数据元素的比较次数是不同的。
• 在堆排序中主要涉及初始建堆和n-1趟排序过程中堆的调整，而在初始建堆和排序过程中堆的调整时进行的关键字比较次数与序列的原始状态有关。

9. 数据序列(2.1,4.9,8.10,6,20)只能是下列排序算法中()的两趟排序后的结果。
   A.快速排序B.冒泡排序 C.选择排序D.插入排序
   【答】A

• 冒泡排序和选择排序进行两趟排序后，最后(或最前)2个元素一定是序列中最大(或最小)的2个元素而且有序;
• 插入排序进行两趟排序后，前面3个元素一定有序。显然，题目所给的序列不满足上述要求。
• 而快速排序进行两趟排序后，一定至少有2个数据元素放置在排序后的目标位置，且在其左边的元素都不大于该元素，在其右边的元素都不小于该元素。题目所给的序列正好有2个元素(4和20)满足此要求。

10. 下列排序算法中，()不能保证每趟排序至少能将一个元素放到其最终的位置上。
    A.快速排序B.希尔排序C.堆排序D.冒泡排序
    【答】B

• 根据快速排序、堆排序和冒泡排序的算法思想，它们每一趟都至少让一个元素放到其最终的位置上；
• 而希尔排序有可能会在最后一趟排序(间距d=1)时，才让所有元素放到其最终的位置上。

11. 在下列排序方法中，空间复杂度为O(n)的是（）
    A.希尔排序B.堆排序C.选择排序D.归并排序
    【答】D

• 根据希尔排序、堆排序和选择排序的算法思想，它们在排序过程中只需要1个辅助空间用于数据元素的交换，所以它们的空间复杂度为O(1)。
• 而归并排序需要一个和原待排序序列长度一样的辅助数组用于两路归并，所有其空间复杂度为O(n)。

12. 下列排序中，在待排序数据已有序时，花费时间反而最多的是（C.快速排序）
    A.冒泡排序B.希尔排序C.快速排序D.堆排序
13. 就平均性能而言，目前最好的内排序方法是（D.快速排序）
    A.冒泡排序B.希尔排序C.交换排序D.快速排序

• 快速排序是目前基于比较的内部排序中平均性能最好的排序方法，当待排序的关键字随机分布时，快速排序的平均时间最短。

14. 如果只想得到10000 个元素组成的序列中第5个最小元素之前的部分排序的序列，用(C.堆排序)方法最快。
    A.冒泡排序B.快速排列C.堆排序D.简单选择排序

• 冒泡排序一般需要5趟排序才能找到序列中第5小的元素，总的比较次数为:9999+9998+9997+9996+9995。
• 快速排列如果每次划分把序列分成左、右2个长度相同的子表，则大概需要进行11趟才能找到序列中第5小的数据元素。
• 简单选择排序完成这个务的时间和冒泡排序一样。
• 堆排序在初始建立最小堆后，只需要进行5趟选择、调整就可以完成这个任务，而且5 趟选择、调整所进行的关键字比较次数最多是100 次(10000结点的完全二叉树的高度)。建堆是需要时间的，也就是比较次数很多。但一般都是忽略初始建堆的，真正的计算肯定会说明的。

15. 下列排序方法中，(D.插入排序)可能会出现下面情况:在最后一趟开始之前，所有元素都不在其最终的位置上。
    A.堆排序B.冒泡排序C.快速排序D.插入排序

• 根据堆排序、冒泡排序和快速排序的算法思想，它们每一趟都至少让一个元素放到其最终的位置上;
• 而插入排序有可能会在最后一趟排序(最后插入的是序列中的最小值)时，才让所有元素放到其最终的位置上。

16. 在执行某个排序算法过程中，出现了元素朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）
    【答】错

• 有些稳定排序方法(例如，冒泡排序)，在排序过程中也会出现元素朝着最终排序序列位置相反方向移动。

17. 对有n个数据元素的数据表，简单选择排序算法在最好情况下的时间复杂度为O(n)。（）
    【答】错

• 对有n个数据元素的数据表，简单选择排序没有最好和最坏情况之分，它都需要进行n-1趟选择。
  第1趟选择需要进行n-1次关键字比较，第2趟选择需要进行n-2次关键字比较.….第i趟选择（i=1, …,n-1)需要进行n-i次关键字比较。
• 所以，时间复杂度总是为O(n²)。

18. 对有n个数据元素的数据表，在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（）
    【答】错

• 快速排序在待排序数据已有序时，每次划分只得到一个比上一次少一个数据元素的子表(另一个子表为空)，此时它已退化成冒泡排序，其时间复杂度为O(n²)。

19. 在基数排序时，最高位优先分配法比最低位优先分配法简单。（）
    【答】错

• 基数排序通过“分配”和“收集”来实现排序，它分为LSD 和 MSD两种方式。
• LSD排序方式由关键字的最右边位(低位)开始，先按关键字的最低位把所有元素分配到不同的“子桶”，然后依次把每个“子桶”中元素全部回收，完成一趟“分配”和“回收”:第2趟再按关键字的次低位把所有元素分配到不同的“子桶”，然后依次把每个“子桶”中元素全部回收……如此反复，在最后一趟“分配”“收集”完成后，所有数据元素就按其关键字的值从小到大排序好了。
• 而 MSD 则相反，由关键字的最左边位(高位)开始，是由高位开始进行“分配”，但在“分配”之后并不把所有元素立即“收集”到一起，而是把每个“子桶”中的元素按照下一高位的值分配到“子子桶”中如此不断“分配”，在完成最低位数的“分配”后，再把所有元素依次“收集”到一起。
• 由此可见，最高位优先分配法的实现要比最低位优先分配法复杂。

20. 在任何情况下，归并排序都比简单插入排序快。（）
    【答】错

• 当序列基本有序的情况下，简单插入排序要比归并排序快。但平均性能归并排序都比简单插入排序好。

21. 对有n个数据元素的数据表进行排序，堆排序所需要的附加存储空间为O(log2n)。（）
    【 答】错

• 在堆排序过程中，只需要1个辅助空间用于数据交换，所以它的空间复杂度为O(1)。

22. 影响外排序的时间因素主要是内存与外设交换信息的次数。（）
    【答】对

• 外部排序一般用于大文件(数据量很多)的排序，当待排序的文件很大时，无法将整个文件的所有记录同时调入内存进行排序，只能将所有数据以文件形式存放在外存，进行排序时根据可用内存的大小，将外存上含有n个记录的文件分成若干长度为t的子文件(或段)；再利用内部排序的方法，对每个子文件中的t个记录进行内部排序后存储在外存，这些经过排序的子文件(段)通常称为顺串(run)，这样在外存上就得到了m个顺串(m=[n/t])；最后，对这些顺串进行归并，使顺串的长度逐渐增大，直到所有的待排序的记录归并到一个顺串为止。
• 因此，外排序的时间主要由每个子文件进行内部排序的时间和内存与外设交换信息所需要的时间组成。由于内存的访问速度大约是磁盘的25万倍，所以影响外排序的时间主要是内存与外设交换信息的次数。

23. 有数据元素(98、36、 -9、0、47、23、1、8、10、7)，进行二路归并排序，则第1趟归并后数据元素的排列次序为（）
    【答】36、98、-9、0、23、47、1、8、7、10 （没有说明，就按非递归来做）
24. 在简单选择排序、折半插入排序、希尔排序和快速排序这四种排序方法中，（）是稳定的排序方法。
    【答】折半插入排序
25. 堆排序的算法时间复杂度为（）
    【答】O(nlog2n)
26. 基数排序的空间复杂度为（）
    【答】O(radix)
    10.在快速排序、堆排序、归并排序和直接插入排序这四种排序方法中，若需在O(nlog2n)的时间内完成排序，且要求排序是稳定的，则可选择的排序方法是（）
    【答】归并排序
27. 设有一组初始记录关键字序列(K1,K2,…,Kn)，要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K，右半部分的每个关键字均大于等于K1。
    
28. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。
    
    【答】i<j && r[i].key<x.key ，r[i]=x
29. 设计在链式结构上实现简单选择排序算法。
    
30. 设计将所有奇数移到所有偶数之前的算法。
    
31. 设关键字序列(k1,k2,…,kn-1)是堆，设计算法将关键字序列(k1,k2,…, kn-1,x)调整为堆。