[计算机类试卷]软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编13及答案与解析.doc

1、软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编 13及答案与解析 1 无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图 G中的顶点数为 n，边数为 e，则所有顶点的度数之和为 (59)。 （ A） ne （ B） n+e （ C） 2n （ D） 2e 2 设一个包含 N个顶点、 E条边的简单无向图采用邻接矩阵存储结构 (矩阵元素Aij等于 I 0分别表示顶点 i与顶点 i之间有无边 )，则该矩阵中的非零元素数据为 (60)。 （ A） N （ B） E （ C） 2E （ D） N+E 3 (59)是图 88的合法拓扑序列。 （ A） 654321 （ B） 12

2、3456 （ C） 563421 （ D） 564213 4 以下关于哈希 (Hash，散列 )查找的叙述中，正确的是 (65)。 （ A）哈希函数应尽可能复杂些，以消除冲突 （ B）构造哈希函数时应尽量使关键字的所有组成部分都能起作用 （ C）进行哈希查找时，不再需要与查找表中的元素进行比较 （ D）在哈希表中只能添加元素不能删除元素 5 某哈希表 (散列表 )的长度为 n，设散列函数为 H(Key)=Keymodp，采用线性探测法解决冲突。以下关于 p值的叙述中，正确的是 (61)。 （ A） p的值一般为不大于 n且最接近 n的质数 （ B） p的值一般为大于 n的任意整数 （ C） p

3、的值必须为小于 n的合数 （ D） p的值必须等于 n 6 在 13个元素构成的有序表 M1 13中进行折半查找 (向下取整 )，若找到的元素为 M4，则被比较的元素依次为 (59)。 （ A） M7、 M3、 M5、 M4 （ B） M7、 M5、 M4 （ C） M7、 M6、 M4 （ D） M7、 M4 7 图 89所示为一棵 N阶 B一树， N最有可能的值 为 (61)。（ A） 1 （ B） 2 （ C） 3 （ D） 4 8 对 n个元素的有序表 A1.n进行顺序查找，其成功查找的平均查找长度 (即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值 )为 (58)

4、。 （ A） n （ B） (n+1) 2 （ C） log2n （ D） n2 9 对于关键字序列 (26， 25， 72， 38， 8， 18， 59)，采用散列函数H(Key)=Keymod13构造散列表 (哈希表 )。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元 )，则关键字 59所在散列 表中的地址为 (61)。 （ A） 6 （ B） 7 （ C） 8 （ D） 9 10 某一维数组中依次存放了数据元素 15,23,38,47,55,62,88,95， 102， 123，采用折半 (二分 )法查找元素 95时，依次与 (60)进行了比较。 （ A） 62,88,95

5、（ B） 62,95 （ C） 55,88,95 （ D） 55,95 11 对 n个元素的有序表 A1 n进行二分 (折半 )查找 (除 2取商时向下取整 )，查找元素 Ai(1in)时，最多于 A中的 (57)个元素进行比较。 （ A） n （ B） log2n一 1 （ C） n 2 （ D） log2n+1 12 对于哈希表，如果将装填因子 定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时， (62)。 （ A） 的值随冲突次数的增加而递减 （ B） 越大发生冲突的可能性就越大 （ C） 等于 1时不会再发生冲突 （ D） 低于 0 5时不会发生冲突 13 递增序列 A(a

6、1， a2， ， an)和 B(b1， b2， ， bn)的元素互不相同，若需将它们合并为一个长度为 2n的递增序列，则当最终的排列结果为 (61)时，归并过程中元素的比较次数最多。 （ A） a1， a2， ， an,b1， b2， ， bn （ B） b1， b2， ， bn,a1， a2， ， an （ C） a1， b1， a2， b2， ， ai， bi， ， an,bn （ D） a1， a2， ， ai/2,b1， b2， ， bi/2， ai/2+1， ai/2+2， a n,bi/2+1， bi/2+2， ， bn 14 用插入排序和归并排序算法对数组 进行从大到小排序，则分

7、别需要进行 (65)次数组元素之间的比较。 （ A） 12， 14 （ B） 10， 14 （ C） 12， 16 （ D） 10， 16 15 对以下四个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是 (61)。 （ A） 89， 27， 35， 78， 41， 15 （ B） 27， 35， 41， 16， 89， 70 （ C） 15， 27， 46， 40， 64， 85 （ D） 90， 80， 45， 38， 30， 25 16 以下关于渐近符号的表示中，不正确的是 (62)。 （ A） n2=O(n2) （ B） n2=O(n2) （ C） n2=O(n) （ D

8、） n2=O(n3) 17 现要对 n个实数 (仅包含正实数和负实数 )组成的数组 A进行重新排列，使得 其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为 (65)。 i=0； 1=n一 1 whlle10do j=j一 1； ifi0的比较次数共为 n+2， i=i+1和 j=j一 1执行的次数最多为 n+2次， if语句中的 ij的比较和和交换 Ai1和 【知识模块】 算法与数据结构 18 【正确答案】 C 【试题解析】 Dijkstra用来解决从顶点 V0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径：对于图 G=(

9、V， E)，将图中的顶点分成两组 S和 T， S为已求出的最短路径的终点集合 (开始为 V0)， T为尚未求出最 短路径的终点集合 (开始为 V一 V0)的全部节点 )。算法将按最短路径长度的递增顺序逐个将 T的顶点加入到 S中，直到所有顶点都被加入到顶点集 S为止。本质上说，该算法是一种基于贪心策略的算法。贪心算法根据当前已有的信息作出选择， 【知识模块】 算法与数据结构 19 【正确答案】 A 【试题解析】 分治算法的基本思想是：将一个难以直接解决的大问题分解成一些规模较小的小问题以便各个击破，分而治之。分支算法的每一层都有 3个步骤：分解、求解和合并。本题的查找算法，不断划分数组，缩小查

10、找范围，可见该算法是基于 分支策略的算法。 【知识模块】 算法与数据结构 20 【正确答案】 D 【试题解析】 8皇后问题等价于要求在一个 8x8格的棋盘上放置 8个皇后，使得任意两个皇后不能放在同一行或同一列或同意斜线上。求解过程从空棋盘开始，设在第 1行至第 m行都已经正确放置了 m个皇后的基础上，再在第 m+1行上找合适的位置放置第 m+1个皇后，直至第 8行也找到合适的位置放置第 8个皇后。 在任一行上都有 8种选择，开始时，位置在第 1列，以后改变时，顺序选择第 2列、第 3列、 、第 8列 .当第 8列也不是一个合适的位置时，就要回溯， 去改变前一行的位置。分治法将复杂的大问题分解

11、成规模小的问题以各个击破。归并排序等算法用到的是分治法实 【知识模块】 算法与数据结构 21 【正确答案】 A 【试题解析】 分治算法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。分治算法产生的子问题往往是原问题的较小模式。一般来说，分支算法分为三个步骤：将原问题分解成一系列子问题；递归求解各个子问题；将子问题的解合并成原问题的解。 【知识模块】 算法与数据结构 22 【正确答案】 A 【试 题解析】 a=6， b=5， f(n)=n， logba=1 113，存在 =0 113，使得f(n)=D(nlogba-)，因此 T(n)=(nlogba)

12、=(nlog56)。 【知识模块】 算法与数据结构 23 【正确答案】 A 【试题解析】 对于算法 A，设 a=7， b=2， f(n)=n2，则 logba 2，因此存在常数，使得 f(n)=D(nlogba-)，因此 T(n)=(nlogba)=(nlog27)。如果要使 B渐进地快于算法 A，则有 nlog27 nlog4a，得 log27 log4a，求得 a 49因此 a的最大整数位 48。 【知识模块】 算法与数据结构 24 【正确答案】 C 【试题解析】 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，最优的计算次序是使得矩阵连乘中乘法次数最少的次序。选项 A

13、,乘法的次数为 20355+20435+20254=6700选项 B，乘法的次数为20355+35254+202535=24500选项 C，乘法的次数为5435+2045+20254=3100选项 D，乘法的次数为35254+52535+20255=10375可见，选项 C中的计算次序为最优的计算次序。 【知识模块】 算法与数据结构 25 【正确答案】 B 【试题解析】 贪心法在解决问题的策略上仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。也就是说，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获

14、得全局最优解，但通常能得到较好的近似最优解。 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 26 【正确答案】 D 【知识模块】 算法与数据结构 27 【正确答案】 A 【试题解析】 插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n2)，是稳定的排序方法，快速排序的平均时间复杂度为 O(nlogn)。 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 28 【正确答案】 A 【知识模块】 算法与数据结构 29 【正确答案】 B 【试 题解析】 直接插入排序算法的

15、基本思想是将待排序数组分为两个部分：已排好序部分和未排序部分。其主要步骤为：开始时，第一个元素在已排好序部分中，其余部分在未排序部分。然后依次从未排序部分中取出第一个元素，从后向前与排好序部分的元素进行比较并将其插入到已排好序部分的正确位置，直到所有元素排好序。当序列基本有序时，直接插入排序过程中元素比较的次数较少；当序列为逆序时，元素的比较次数最多。使用直接插入排序算法，数组 1， 1，2,4,7,5需要比较 6次，依次为 1与 1比较、 2与 1比较、 4与 2比较、 7与 4比较、 5与 7比较 、 5与 4 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 30 【正确答案】

16、 B 【知识模块】 算法与数据结构 31 【正确答案】 C 【试题解析】 本题考查贪心算法和背包问题的知识点。贪心算法 (又称贪婪算法 )是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。采用 0 1背包考虑 该问题时，只能放入 1、 2、3号物品，故总价值为 430，采用部分背包可以将物品拆分，故放入 1、 2、 3号物品后还可以将编号 4的物品部分的装入，使得背包容量尽量的满，故总容量为630。 【知识

17、模块】 算法与数据结构 【知识模块】 算法与数据结构 32 【正确答案】 A 【知识模块】 算法与数据结构 33 【正确答案】 B 【试题解析】 分治算法的基本思想是将一个规模为 N的问题分解为 K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分支算 法的时间复杂度为 O(nlgn)。 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 34 【正确答案】 B 【知识模块】 算法与数据结构 35 【正确答案】 C 【试题解析】 最优子结构和高度重复性是适用动态规划方法求解的主要特征；而回溯法 (探索与回溯法 )是一种选优搜索法，按选优条件

18、向前搜索，以达到目标。但当探索到某。步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点 ”。以深度优先方 式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 36 【正确答案】 B 【知识模块】 算法与数据结构 37 【正确答案】 C 【试题解析】 贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择，即不是从整体最优考虑，它所作出的选择只是力求局部最优。本题给出的霍夫曼编码操作过程基于典型的贪心策略。采用固定长度编码，需要 3位二进制数字来表

19、示 6个字符，即 a=000， b=001， c=010， d=011， e=100， f=101。这种方法需要300000位来对整个源文件编码。采用霍夫曼编码，频繁出现的字符采用短编码，出现频率较低的字符采用长编码，这种编码方式需要(32*1+26*3+18*3+12*3+4*4+8*4)*1000 【知识模块】 算法与数据结构 【知识模块】 算法与数据结构 38 【正确答案】 C 【知识模块】 算法与数据结构 39 【正确答案】 A 【试题解析】 贪心算法不考虑整体情况，以当前情况为基础作出最优选择。很明显，题目中用到的是贪心算法。分值算法是将规模为 n的问题分解 为 k个子问题，这些子问题相互独立，且与原问题相同，然后将子问题的解合并得到原问题的解。动态规划算法与分值算法类似，但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间。 在选择路径时，首先选择离中央仓库最近的运输目的地 1，需要将所有 n个目的地到中央仓库的距离进行比较，选择最近的作为目的地 1，相当于从 n个数中选择一个最小数，此时比较了 【知识模块】 算法与数据结构