2008年下半年软件设计师上午试卷[17]

● 将一个无序序列中的元素依次插入到一棵(60)，并进行中序遍历，可得到一个有序序列。

(60)A. 完全二叉树 B. 最小生成树

C. 二叉排序树 D. 最优二叉树［答案讨论］

● 广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是(61)。

(61)A. 链表 B. 静态数组 C. 动态数组 D. 散列表［答案讨论］

● 某一维数组中依次存放了数据元素12,23,30,38,41,52,54,76,85，在用折半(二分)查找方法(向上取整)查找元素54时，所经历“比较”运算的数据元素依次为(62)。

(62)A. 41, 52, 54B. 41, 76, 54

C. 41, 76, 52, 54D. 41, 30, 76, 54［答案讨论］

● 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

(63)A. O(n2)B. O(e2)C. O(n*e)D. O(n+e)［答案讨论］

● 给定一组长度为n的无序序列，将其存储在一维数组a[0..n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较 a[0]和 a[n-1]，若 a[0]较大，则将二者的值进行交换;再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值;然后依次比较a[2]和a[n-3]、a[3]和 a[n-4]、…，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前 n/2 个元素中查找最小元素，在后n/2个元素查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。

(64)A. 动态规划法 B. 贪心法 C. 分治法 D. 回溯法　［答案讨论］

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]  [12]  [13]  [14]  [15]  [16]  [17]  [18]  [19]  [20]