81. 利用逐点插入建立序列(52,43,73,88,76,18,38,61,45,39)对应的二叉排序树之后，查找元素61要进行 (86) 次元素间的比较。
(86) A.3
B.4
C.6
D.8
参考答案：(86)A。
解析：利用逐点插入建立二叉排序树是从空树开始，通过查找将每个节点作为一个叶子插入。建立序列(50,72,43,85,75,20,35,45,65,30)的二叉排序树如图8所示。
根据图8所示的二叉排序树可知，查找元素61要进行3次元素间的比较。
82. 为了在状态空间树中 (87) ，可以利用LC-检索(Least Cost Search)快速找到一个答案节点。
(87) A.进行遍历
B.找出最优的答案节点
C.找出任一个答案节点
D.找出所有的答案节点
参考答案：(87)B。
解析：在状态空间树中，定义 为节点的成本函数，g(X)为从节点向X到达一个答案节点所需做的附加工作的估计函数，h(X)为从根节点到节点X的成本，则用成本估计函数 选择下一个E-节点的检索策略总是选取 值最小的活节点作为下一个E-节点，因此这种检索策略称为最小成本检索，简称LC-检索(Least Cost Search)。
在状态空间树中找出最优的答案节点，就可以利用LC-检索快速找到一个答案节点。根据定义在进行LC-检索时，为避免算法过分偏向于做纵深检查，应该在成本估计函数 中考虑根节点到当前节点的成本(距离)。
83. 图9中不存在 (88) 。
图9
(88) A.欧拉路径
B.欧拉回路
C.欧密尔顿路径
D.哈密尔顿回路
参考答案：(88)B。
解析：通过连通图G中每条边一次且仅一次，遍历图中所有节点的回路称为欧拉回路。
通过连通图G中每条边一次且仅一次，遍历图中所有节点的开路称为欧拉开路(欧拉路径)。
若G是连通图，则存在欧拉回路的充要条件是所有节点的度数均为偶数度;存在欧拉开路的充要条件是当且仅当G中有且只有两个节点的度数为奇数度。
由于图3-6中有两个节点的度数是奇数度，因此图3-6中只存在欧拉路径，但不符合欧拉回路的充要条件，即不存在欧拉回路。
通过连通图G中每个节点一次且仅一次的回路称为欧密尔顿回路。
通过连通图G中每个节点一次且仅一次的开路称为欧密尔顿开路(哈密尔顿路径)。
84. 在最好和最坏情况下的时间复杂度均为O(nlogn)，但不稳定的排序算法是 (89) 。
(89) A.堆排序
B.快速排序
C.归并排序
D.基数排序
参考答案：(89)A。
解析：堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定。
快速排序最好和最坏情况下的时间复杂度分别为O(n2)和O(nlogn)且不稳定。
归并排序是在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法。
基数排序在最好和最坏情况下的时间复杂度均为O(d(n+rd))。
相关推荐：计算机软考软件设计师考试重点难点：死锁
计算机软考：软件设计师练习试题及答案解析(1)
计算机软考：软件设计师练习试题及答案解析(2) 读书人IT频道reader8.com/exam/jisuanji/
