计算机软考：软件设计师练习试题及答案解析(5)

　　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))。