1、软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编 8及答案与解析 0 (2012年上半年上午试题 54-56)某销售公司数据库的零件关系 P(零件号，零件名称，供应商，供应商所在地，库存量 )，函数依赖集 F=零件号 零件名称， (零件号，供应商 ) 库存量，供应商 供应商所在地 )。零件关系模式 P属于_(54)。 查询各种零件的平均库存量、最多库存量与最少库存量之间差值的 SQL语句如下： SELECT零件号，零件名称， _(55)， FROM P _(56) 1 (54) （ A） 1NF （ B） 2NF （ C） 3NF （ D） 4NF 2 (55) （ A） AVG(库
2、存量 )AS平均库存量， MAX(库存量 )-MIN(库存量 )AS差值 （ B）平均库存量 AS AVG(库存量 )，差值 AS MAX(库存量 )-MIN(库存量 ) （ C） AVG库存量 AS平均库存量， MAX库存量 -MIN库存量 AS差值 （ D）平均库存量 AS AVG库存量，差值 AS MAX库存量 -MIN库存量 3 (56) （ A） ORDER BY供应商 （ B） ORDER BY零件号 （ C） GROUP BY供应商 （ D） GROUP BY零件号 4 (2013年下半年上午试题 57)以下关于线性表存储结构的叙述，正确的是_。 （ A）线性表采用顺序存储结构时
3、，访问表中任意一个指定序号元素的时间复杂度为常量级 （ B）线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级 （ C）线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级 （ D）线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级 5 (2013年下半年上午试题 58)设循环队列 Q的定义中有 front和 size两个域变量，其中 front表示队头元素的指针， size表示队列的长度，如图 8 7所示 (队列长度为3，队头元素为 x、队尾元素为 z)。设队列的存储空间容量为 M，则队尾元素的指针为 _。 （ A） (Q
4、 front+Q size-1) （ B） (Q front+Q size-1+M) M （ C） (Q front-Q size) （ D） (Q front-Q size+M) M 6 (2013年下半年上午试题 59)在一个有向图 G的拓扑序列中，顶点 Vi排列在 Vj之前，说明图 G中 _。 （ A）一定存在弧 Vi， Vj （ B）一定存在弧 Vi， Vj （ C）可能存在 Vi到 Vj的路径，而不可能存在 VVj到 VVi的路径 （ D）可能存在 VVj到 VVi的路径，而不可能存在 VVi到 VVj的路径 7 (2013年下半年上午试题 60)以下关于哈夫曼树的叙述，正确的是 _
5、。 （ A）哈夫曼树一定是满二叉树，其每层节点数都达到最大值 （ B）哈夫曼树一定是平衡二叉树，其每个节点左右子树的高度差为 -1、 0或 1 （ C）哈夫 曼树中左孩子节点的权值小于父节点、右孩子节点的权值大于父节点 （ D）哈夫曼树中叶子节点的权值越小则距离树根越远、叶子节点的权值越大则距离树根越近 8 (2013年下半年上午试题 61)某哈希表 (散列表 )的长度为 n，设散列函数为H(Key)=Key mod p，采用线性探测法解决冲突。以下关于 p值的叙述中，正确的是 _。 （ A） p的值一般为不大于 n且最接近 n的质数 （ B） p的值一般为大于 n的任意整数 （ C） p的值
6、必须为小于 n的合数 （ D） p的值必须等于 n 9 (2013年上半年上午试 题 51)采用顺序表和单链表存储长度为 n的线性序列，根据序号查找元素，其时间复杂度分别为 _。 （ A） O(1)、 O(1) （ B） O(1)、 O(n) （ C） O(n)、 O(1) （ D） O(n)、 O(n) 10 (2013年上半年上午试题 52)设元素序列 a、 b、 c、 d、 e、 f经过初始为空的栈 S后，得到出栈序列 c e d f b a，则栈 S的最小容量为 _。 （ A） 3 （ B） 4 （ C） 5 （ D） 6 11 (2013年上半年上午试题 53)输出受限的双端队列是指
7、元素可以从队列的 两端输入、但只能从队列的一端输出，如图 8 8所示。若有 e1、 e2、 e3、 e4依次进入输出受限的双端队列，则得不到输出序列 _。（ A） e4、 e3、 e2、 e1 （ B） e4、 e2、 e1、 e3 （ C） e4、 e3、 e1、 e2 （ D） e4、 e2、 e3、 e1 12 (2013年上半年上午试题 64)一个高度为 h的满二叉树的节点总数为 2h-1，从根节点开始，自上而下、同层次节点从左至右，对节点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分别为 2和 3，再下一层从左到右的编号为 4、5、 6、 7， 依次类推。那么，在一棵满
8、二叉树中，对于编号为 m和 n的两个节点，若 n=2m+1，则 _节点。 （ A） m是 n的左孩子 （ B） m是 n的右孩子 （ C） n是 m的左孩子 （ D） n是 m的右孩子 13 (2013年上半年上午试题 65)以下关于哈希 (Hash，散列 )查找的叙述中，正确的是 _。 （ A）哈希函数应尽可能复杂些，以消除冲突 （ B）构造哈希函数时应尽量使关键字的所有组成部分都能起作用 （ C）进行哈希查找时，不再需要与查找表中的元素进行比较 （ D）在哈希表中只能添加元素不能删除元 素 14 (2012年下半年上午试题 57)在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的
9、一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法 (朴素的或基本的模式匹配 )中，若主串和模式串的长度分别为 n和 m(且 n远大于 m)，且恰好在主串末尾的 n个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为 _。 （ A） nm （ B） (n-m+1)m （ C） (n-m-1)m （ D） (n-m)n 15 (2012年下半年上午试题 58)若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BKFEACD，则该二叉树为 _。16 (2012年下半年上午试题 59)在 13个元素构成的有
10、序表 M1 13中进行折半查找 (向下取整 )，若找到的元素为 M4，则被比较的元素依次为 _。 （ A） M7、 M3、 M5、 M4 （ B） M7、 M5、 M4 （ C） M7、 M6、 M4 （ D） M7、 M4 17 (2012年下半年上午试题 60)拓扑排序是将有向 图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV网中从顶点 Vi到 Vj有一条路径，则顶点 Vi必然在顶点 Vj之前。对于图 8 9所示的有向图， _是其拓扑序列。（ A） 1234576 （ B） 1235467 （ C） 2135476 （ D） 2134567 18 (2012年下半年上午试题
11、 61)图 8 10所示为一棵 N阶 B一树， N最有可能的值为 _。（ A） 1 （ B） 2 （ C） 3 （ D） 4 19 (2012年上半年上午试题 57)对于一个长度大于 1且不存在重复元素的序 列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列 (栈 )的含义是序列的每个元素都入队列 (栈 )且出队列 (栈 )一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是_。 （ A）出队序列和出栈序列一定相同 （ B）出队序列和出栈序列一定互为逆序 （ C）入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同 （ D）
12、入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序 20 (2012年上半年上午试题 58)在字符串的 KMP模式匹配算法中，需要求解模式串p的 next函数值，其定义如下所示。若模式串 p为 “aaabaaa”，则其 next函数值为_。 （ A） 0123123 （ B） 0123210 （ C） 0123432 （ D） 0123456 21 (2012年上半年上午试题 59)若 n2、 n1、 n0分别表示一个二叉树中度为 2、度为 1和叶子节点的数目 (节点的度定义为节点的子树数目 )，则对于任何一个非空的二叉树， _。 （ A） n2一定大于 n1 （ B） n1一定
13、大于 n0 （ C） n2一定大于 n0 （ D） n0一定大于 n2 22 (2012年上半年上午试题 60)从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是 _。 （ A）有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储 （ B）无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储 （ C）完全图适合采用邻接矩阵存储 （ D）完全图适合采用邻接表存储 22 (2013年下半年上午试题 62、 63)对 n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为 _(62)；若采用快速排序算法，则时 间和空间复杂度分别为 _(63)。 23 (62)
14、（ A） O(n2)和 O(n) （ B） O(n)和 O(n) （ C） O(n2)和 O(1) （ D） 0(n)和 O(1) 24 (63) （ A） O(n2)和 O(n) （ B） 0(nlgn)和 O(n) （ C） O(n2)和 O(1) （ D） O(nlgn)和 O(1) 24 (2013年下半年上午试题 64、 65)在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用 _(64)算法设计策略；若定义问题的 解空间，以深度优先的方式搜索解空间，则采用 _(65)算法设计策略。 25 (64) （ A）分治 （ B）动态规划 （ C）贪心
15、（ D）回溯 26 (65) （ A）动态规划 （ B）贪心 （ C）回溯 （ D）分支限界 26 (2013年上半年上午试题 60、 61)考虑下述背包问题的实例。有 5件物品，背包容量为 100，每件物品的价值和重量如表 9 2所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了_(60)设计策略。考 虑 0 1背包问题 (每件物品或者全部装入背包或者不装入背包 )和部分背包问题 (物品可以部分装入背包 )，求解该实例得到的最大价值分别为 _(61)。27 (60) （ A）分治 （ B）贪心 （ C）动态规划 （ D）回溯 28 (61)
16、 （ A） 605和 630 （ B） 605和 605 （ C） 430和 630 （ D） 630和 430 软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编 8答案与解析 【知识模块】 数据库技术 1 【正确答案】 A 【试题解析】 1NF中，关系模式 P的每一个分量都是不可再分的数据项。 2NF中，关系模式 P属于 1NF，且每个非主属性完全依赖于码。 本题中，关系模式 P的每个分量都不可以再分，满足 1NF的定义。从函数依赖集 F可以看出关系 P的码为 (零件号，供应商 )，零件号决定零件名称，则零件名称不完全依赖于码，不满足 2NF的定义。因此关系模式 P属于 1NF。
17、查询平均库存量需要使用 AVG()函数。计算最大值和最小值则需要使用 MAX()和 MIN()函数。 SELECT语句可以通过 AS子句为属性重新命名，形式为 old-name AS new-name，也就是说，新名字要放在 AS的后面。 ORDER BY子句用于排序， GROPU BY子句用于分组。很显然，本题要按零件进行分组。 【知识模块】 数据库技术 2 【正确答案】 A 【知识模块】 数据库技术 3 【正确答案】 D 【知识模块】 数据库技术 4 【正确答案】 A 【试题解析】 顺序存储结构可以随机存取，时间复杂度最低为常量级，答案选A。 【知识模 块】 数据结构 5 【正确答案】 B
18、 【试题解析】 考虑到循环，要对 M进行求模运算，元素的指针从 9开始到 M-1，所以答案为 B。 【知识模块】 数据结构 6 【正确答案】 C 【试题解析】 根据有向图 G的拓扑序列定义，顶点 Vi排列在 Vj之前，可以得知可能存在 Vi到 Vj的路径，拓扑序列是单向的，所以不可能存在从 Vj到 Vi的路径。所以本题答案选 C。 【知识模块】 数据结构 7 【正确答案】 D 【试题解析】 哈夫曼树即最优二叉树，是一类带权路径长度最短的树。树的带权路径为树中所叶 子节点的带权路径长度之和，记为 WPL= wklk式中， n为带权叶子节点的数目； wk为叶子节点的权值； lk为叶子节点到根的路径
19、长度。则哈夫曼树是指权值为 w1， w2， ， wn的 n个叶子节点的二叉树中带权路径长度最小的二叉树。哈夫曼树与完全二叉树、平衡二叉树之间没有必然的联系。选项 A、 B的说法是错误的。由哈夫曼树的构造算法可知，哈夫曼树中权值最小的两个节点互为兄弟节点，根节点的权值为其左、右子树根节点的权值之和。选项 C错误，选项 D正确。 【知识模块】 数据结构 8 【正确答案】 A 【试题解析】 如果参数 p是合数的话，那么 Key相对于 p的模得到的散列值会有很多是相同的。所以， p一般取质数。如果 p的值大于散列表的长度，散列函数得到的散列地址将和 Kev的范围相同大小，那么散列函数也就没有意义了。所
20、以答案选 A。 【知识模块】 数据结构 9 【正确答案】 B 【试题解析】 顺序表存储位置是相邻且连续的，是可以随机访问的一种数据结构，一个顺序表在使用前必须指定其长度，一旦分配内存，则在使用中不可以动态更改。其优点是访问数据时比较方便，可以随机访问表中的任何一个数据。链表是通过指针来描述元素关系 的一种数据结构，可以是物理地址不连续的物理空间，不能随机访问链表元素，必须从表头开始，一步一步搜索元素。其优点是：对于数组，可以动态地改变数据的长度，分配物理空间。因此二者的查找复杂度就显而易见了。 【知识模块】 数据结构 10 【正确答案】 B 【试题解析】 本题考查栈的用法。根据题中出栈的顺序，
21、当元素 c出栈后，栈中有元素 a、 b，当元素 e出栈之前，栈中有元素 a、 b、 d、 e，此时栈中的元素达到最多。因此栈 S的最小容量为 4。 【知识模块】 数据结构 11 【正确答案】 D 【试 题解析】 本题考查队列的性质。队列为先进先出的线性结构，题中给出的受限的双端队列，两端都可以进，而一端可以出。假设分 a端和 b端， b端可以进出，由 D选项的输出序列，可以看出 e1、 e2、 e3按顺序从 a端进入，而 e4从 b端进入，当 e4从 b端出来之后，无法将后面的 e2出队列，故选项 D有误。 【知识模块】 数据结构 12 【正确答案】 D 【试题解析】 由于该二叉树为满二叉树，
22、且根节点编号从 1开始，由满二叉树的性质可知父节点 m和右孩子之间的关系为 n=2m+1。 【知识模块】 数据结构 13 【正确答案】 B 【试题解析】 哈希表中的元素是由哈希函数确定的。将数据元素的关键字 K作为自变量，通过一定的函数关系 (称为哈希函数 )计算出的值，即为该元素的存储地址。所以在构造哈希函数时应尽量使关键字的所有组成部分起作用。 【知识模块】 数据结构 14 【正确答案】 B 【试题解析】 在最坏情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为 i-m+2。若从主串的第 i个字符开始匹配时成功，则前 i趟不成功的匹配中，
23、每趟都比较了 m次，总共比较了 im次，第 i+l趟的成功匹配也比较了 m次。因此，在本题所述的匹配模式中，字符的比较次数最多为 (n-m+1)m次。 【知识模块】 数据结构 15 【正确答案】 A 【试题解析】 本题考查二叉树的遍历算法。根据中序遍历序列和另一种遍历序列的结果，可以确定该二叉树。后序遍历是按照左子树、右子树、根节点的顺序进行遍历，中序遍历是按照左子树、根节点、右子树的顺序进行遍历。 E为根节点， K为 B的右子树，因此答案为选项 A描述的二叉树。 【知识模块】 数据结构 16 【正确答案】 A 【试题解析】 由于该有序表中共有 13个元素，且元素下标为 1至 13，即low=
24、1， high=13，用折半公式 (low+high) 2，可以计算出首次被比较元素的下标是 7，即 M7。当与 M7比较完毕以后，发现不是要找的数据，所以继续查找。此时， low=1， high=6，用折半公式 (low+high) 2并向下取整，可以计算出被比较元素的下标是 3，即 M3。当与 M3比较完毕以后，发现不是要找的数据，所以继续查找。此时， low=4， high=6，用折半公式 (low+high) 2并向下取整，可以计算出被 比较元素的下标是 5，即 M5。当与 M5比较完毕以后，发现不是要找的数据，所以继续查找，最终找到元素 M4。 【知识模块】 数据结构 17 【正确答
25、案】 C 【试题解析】 对 AOV网进行拓扑排序的方法如下。 (1)在 AOV网中选择一个入度为 0(没有前趋 )的顶点且输出它。 (2)从网中删除该顶点及与该顶点有关的所有边。 (3)重复上述两步，直至网中不存在入度为零的顶点为止。 本题中只有序列 “2135476”是其拓扑序列。 【知识模块】 数据结构 18 【正确答案】 D 【试题解析】 一棵 N阶 B一树为满足以下特性的 N叉树。 (1)树中每个节点至多有 N棵子树。 (2)若根节点不是叶子节点，则至少有两棵子树。 (3)除根之外的所有非终端节点至少有 棵子树。 (4)所有的非终端节点中包含下列数据信息 (n，A0， K1， A1，
26、K2， A2， ， Kn， An)。其中， Ki(j=1， 2， ， n)为关键字 (如 3，47， 53， 63)，且 Ki Ki+1； Ai(i=0， 1， 2， ， n)为指向子树根节点的指针； n为节点中关键字的个数，且 -1nN-1。 (5)所有的叶子节点都出现在 同一层次上，并且不带信息。由图 8 10可知， N最有可能的值为 4。 【知识模块】 数据结构 19 【正确答案】 C 【试题解析】 队列具有先进先出的特点，也就是说最先入队的元素最先出队，所以入队序列和出队序列一定相同。栈则具有先进后出的特点，如果所有元素进栈后再依次出栈，则入栈序列和出栈序列互为逆序，否则不一定。 【知
27、识模块】 数据结构 20 【正确答案】 A 【试题解析】 j=1时， next1=0。 j=2时，不存在 k满足 1 k j，则 next2=1。j=3时， k只能取 2， 等式的左边为 p1，等式的右边为 p2， p1=p2=a， next3=2。j=4时， k可以取 2和 3， k取 2时，左边为 p1，右边为 p3， p1=p3=a； k取 3时，左边为 p1p2，右边为 p2p3， p1p2=p2p3=aa； k取较大值 3，因此 next4=3。 j=5时， k可以取 2、 3、 2， k取 2时，左边为 p1=a，右边为 p4=b，左右两边不等； k取 3时，左边为 p1p2=aa
28、，右边为 p3p4=ab，左右两边不等； k取 4时，左边为p1p2p3=aaa，右边为 p2p3p4=aaba，左右两边不等，因此 next5： 1。至此，可以判断正确答案为 A。 【知识模块】 数据结构 21 【正确答案】 D 【试题解析】 由二叉树的性质可知，度为 0的节点比度为 2的节点数多 1，即n0=n2+1，因此 n0一定大于 n2。 【知识模块】 数据结构 22 【正确答案】 C 【试题解析】 邻接矩阵是用矩阵来指出顶点和顶点之间是否存在着关系。如果图有 n个节点，则需要用 n2个元素来表示顶点间的关系。 邻接表是图的一种链式存储结构。在邻接表中，图中的每一个顶点都需要建立一个
29、单链表，第 i个单链表中的节点表示依附于顶点 vi的边。对 于无向图，若其有 n个顶点、 e条边，则它的邻接表需要 n个头节点和 2e个表节点。对于有向图，若其有 n个顶点、 e条边，则它的邻接表需要 n个头节点和 e个表节点。等 e n(n-1) 2时，采用邻接表表示图比用矩阵节省空间。可见，完全图适合采用邻接矩阵存储。 【知识模块】 数据结构 【知识模块】 算法设计和分析 23 【正确答案】 C 【知识模块】 算法设计和分析 24 【正确答案】 B 【试题解析】 插入排序的基本操作就是将一个数据插入已经排好序的有序数据中，从而得到一个新的、个数加 1的 有序数据，该算法适用于少量数据的排序
30、，时间复杂度为 O(n2)。快速排序是稳定的排序方法，其平均时间复杂度为O(nlgn)。 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 25 【正确答案】 B 【试题解析】 最优子结构和高度重复性是适用动态规划方法求解的主要特征，所以第 (64)题答案选 A。回溯法 (探索与回溯法 )是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足 回溯条件的某个状态的点称为回溯点。回溯法以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 【知识模块】 算法设计和分析
31、 26 【正确答案】 C 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 27 【正确答案】 B 【试题解析】 本题考查贪心算法和背包问题的知识点。 贪心算法 (又称贪婪算法 )是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能 得到整体最优解，但对范围相当广泛的许多问题能产生整体最优解或者是整体最优解的近似解。 考虑 0 1背包问题时，只能放入 1、 2、 3号物品，故总价值为 430；考虑部分背包问题时，可以将物品拆分，故放入 1、 2、 3号物品后还可以将编号 4的物品部分地装入，使得背包容量尽量地满，故总容量为 630。 【知识模块】 算法设计和分析 28 【正确答案】 C 【知识模块】 算法设计和分析
