37. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是 ( (b), c), ( ( (d) ) )。
38. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。
39. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
40. 二叉树是一棵无序树。
41. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
b42. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
43. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。
44. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。
45. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。
46. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。
47. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。
48. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。
49. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。
50. 线索二叉树中的每个结点通常包含有5个数据成员。
51. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。
52. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。
26
53. 进行折半搜索的表必须是顺序存储的有序表。
54. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。
55. 假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。
56. 假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。
57. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。
58. 对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。
59. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。
60. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。
61. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。
62. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。
63.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
64. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
65. 邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。
66. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。
67. 强连通分量是有向图中的极大强连通子图。
68. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
69. 有回路的有向图不能完成拓扑排序。
27
70. 在AOE网络中一定只有一条关键路径。
71. 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。
72. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。
73. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。
74. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。
75. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。
76. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。
77. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。
78. 如果有向图中各个顶点的度都大于2，则该图中必有回路。
79. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
80. 图的广度优先搜索算法通常采用非递归算法求解。
81. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。
82. 直接选择排序是一种稳定的排序方法。
83. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。
84. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。
85. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。
86. 若用m 个初始归并段参加 k 路平衡归并排序，则归并趟数应为?log2m?。
87. 堆排序是一种稳定的排序算法。
88. 任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O(nlog2n)。
28
89. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。
90. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m 互质。
91. 一棵3 阶B树是平衡的3 路搜索树，反之，一棵平衡的3 路搜索树是3 阶B树。
92. 闭散列法通常比开散列法时间效率更高。
93. 一棵 m 阶 B 树中每个结点最多有 m-1 个关键码，最少有 ?m/2?-1个关键码。
94. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
95. 在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。
96. 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。
97. AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。
98. 在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。
99. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。
100. 从一棵B树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。
填空题参考解答
1. 信息 2. 存储结构 3. 非线性 4. 链接 5. 数据结构 6. 数据封装 7. 有穷性 8. 继承
9. 实例 10. 操作（或服务）11. 数据类型 12. 派生（或子） 13. 下标（或顺序号）14. 静态 15. 动态 16. 两个
17. LOC(0,0)+(i*n+j)*d 18. 相等19. n(n+1)/2 20. (2n-I-1)*I/2+J 21. 值 22. 数据元素 23. 16 24. 链式（或链接） 25. 顺序 26. 删除 27. 指针域 28. 分配 29. 不一定 30. 前驱 31. 表头指针 32. 删除
33. 前趋结点和后继结点34. 链接指针 35. 存储 36. p->llink
37. 后出先进 38. 先进先出 39. 栈顶指针 40. 队头（或队首）
29
41. 栈顶指针 42. top==MaxSize-1
43. top == 0 44. 队尾45. p->link=top 46. 1 47. 一 48. 递归 49. 递归 50.局部变量
51. 释放 52. 递归 53. 表尾 54. ( (d, e, f ) ) 55. 表头结点 56. 重数 57. n-1 58. 2 59. 3 60. 4
61. 85 62. 6 63. 63 64. 3
65. 6 66. 4 67. 2h 68. 2h+1
-1 69. 2 70. 右 71. 2i+1 72. 2i+2 n73. 最小值 74. 最大值 75. O(n) 76.
?pici
i?177. 20.5 78. 3 79. 19
80. 右子树 81. 左子树 82. O(nlog2n) 83. 1 84. 50 85. 先右后左双旋转86. 右单旋转 87. 64 88. O(log2n) 89. 2(n-1) 90. 顶点 91. 4 92. 2 93. n-1 94. 2 95. n-1 96. 30
97. 连通分量 98. 高 99. 邻接矩阵 100. O(n2
) 101. 直接插入 102. 直接选择 103. 交换 104. 二路归并
105. O(n2
)106. O(n) 107. n/2 108. n-1 109. O(log2n) 110. O(nlog2n)
111. 84，79，56，38，40，46 112. O(nlog2n)
113. O(n2
) 114. O(log2n) 115. O(n) 116. 3 117. O(n) 118. O(nlog2n) 119. 关键码
120. 2 121. 3 122. 稀疏 123. O(n)124. 11 125. 500 126. 25 127. 5 128. n/m 129. ?logm(n+1)? 130. 4 131. 5 132. ?m/2?-1 133. ?m/2? 134. m-1 135. m 136. ?m/2?-1
判断题参考解答
1. 错2. 对3. 错4. 对5. 错6. 错7. 对8. 错9. 错10. 对 11. 错12. 对13. 错14. 对15. 对16. 对17. 对18. 错19. 对
20. 对21. 对22. 错23. 对24. 对25. 对26. 错27. 错28. 对29. 错 30. 对31. 错32. 错33. 对34. 错35. 对36. 对37. 错38. 对39. 对 40. 错41. 错42. 对43. 错44. 对45. 对46. 对47. 错48. 错49. 错 50. 对51. 错52. 对53. 对54. 错55. 对56. 错57. 对58. 对59. 错 60. 对61. 对62. 错63. 对64. 错65. 对66. 对67. 对68. 错69. 对 70. 错71. 对72. 错73. 对74. 对75. 对76. 对77. 对78. 错79. 对 80. 对81. 错82. 错83. 错84. 对85. 错86. 错87. 错88. 错89. 对 90. 对91. 错92. 错93. 错94. 对95. 对96. 错97. 对98. 对99. 错 100. 错
30
31