软件水平考试中级软件设计师上午（基础知识）历年真题试卷汇编8
中文选择题
(2012年上半年上午试题54-56)某销售公司数据库的零件关系P(零件号，零件名称，供应商，供应商所在地，库存量)，函数依赖集F={零件号→零件名称，(零件号，供应商)→库存量，供应商→供应商所在地)。零件关系模式P属于_______(54)。
查询各种零件的平均库存量、最多库存量与最少库存量之间差值的SQL语句如下：
SELECT零件号，零件名称，_______(55)，
FROM P
_______(56)
1.(54)(A)
A. 1NF
B. 2NF
C. 3NF
D. 4NF
解析：1NF中，关系模式P的每一个分量都是不可再分的数据项。
2NF中，关系模式P属于1NF，且每个非主属性完全依赖于码。
本题中，关系模式P的每个分量都不可以再分，满足1NF的定义。从函数依赖集F可以看出关系P的码为(零件号，供应商)，零件号决定零件名称，则零件名称不完全依赖于码，不满足2NF的定义。因此关系模式P属于1NF。
查询平均库存量需要使用AVG()函数。计算最大值和最小值则需要使用MAX()和MIN()函数。SELECT语句可以通过AS子句为属性重新命名，形式为old-name AS new-name，也就是说，新名字要放在AS的后面。
ORDER BY子句用于排序，GROPU BY子句用于分组。很显然，本题要按零件进行分组。
2.(55)(A)
A. AVG(库存量)AS平均库存量，MAX(库存量)-MIN(库存量)AS差值
B. 平均库存量AS AVG(库存量)，差值AS MAX(库存量)-MIN(库存量)
C. AVG库存量AS平均库存量，MAX库存量-MIN库存量AS差值
D. 平均库存量AS AVG库存量，差值AS MAX库存量-MIN库存量
解析：
3.(56)(D)
A. ORDER BY供应商
B. ORDER BY零件号
C. GROUP BY供应商
D. GROUP BY零件号
解析：
4.(2013年下半年上午试题57)以下关于线性表存储结构的叙述，正确的是_______。(A)
A. 线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B. 线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C. 线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D. 线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
解析：顺序存储结构可以随机存取，时间复杂度最低为常量级，答案选A。
5.(2013年下半年上午试题58)设循环队列Q的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如图8．7所示(队列长度为3，队头元素为x、队尾元素为z)。设队列的存储空间容量为M，则队尾元素的指针为_______。
(B)
A. (Q．front+Q．size-1)
B. (Q．front+Q．size-1+M)％M
C. (Q．front-Q．size)
D. (Q．front-Q．size+M)％M
解析：考虑到循环，要对M进行求模运算，元素的指针从9开始到M-1，所以答案为B。
6.(2013年下半年上午试题59)在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中_______。(C)
A. 一定存在弧＜Vi，Vj＞
B. 一定存在弧＜Vi，Vj＞
C. 可能存在Vi到Vj的路径，而不可能存在VVj到VVi的路径
D. 可能存在VVj到VVi的路径，而不可能存在VVi到VVj的路径
解析：根据有向图G的拓扑序列定义，顶点Vi排列在Vj之前，可以得知可能存在Vi到Vj的路径，拓扑序列是单向的，所以不可能存在从Vj到Vi的路径。所以本题答案选C。
7.(2013年下半年上午试题60)以下关于哈夫曼树的叙述，正确的是________。(D)
A. 哈夫曼树一定是满二叉树，其每层节点数都达到最大值
B. 哈夫曼树一定是平衡二叉树，其每个节点左右子树的高度差为-1、0或1
C. 哈夫曼树中左孩子节点的权值小于父节点、右孩子节点的权值大于父节点
D. 哈夫曼树中叶子节点的权值越小则距离树根越远、叶子节点的权值越大则距离树根越近
解析：哈夫曼树即最优二叉树，是一类带权路径长度最短的树。树的带权路径为树中所叶子节点的带权路径长度之和，记为WPL=
8.(2013年下半年上午试题61)某哈希表(散列表)的长度为n，设散列函数为H(Key)=Key mod p，采用线性探测法解决冲突。以下关于p值的叙述中，正确的是_______。(A)
A. p的值一般为不大于n且最接近n的质数
B. p的值一般为大于n的任意整数
C. p的值必须为小于n的合数
D. p的值必须等于n
解析：如果参数p是合数的话，那么Key相对于p的模得到的散列值会有很多是相同的。所以，p一般取质数。如果p的值大于散列表的长度，散列函数得到的散列地址将和Kev的范围相同大小，那么散列函数也就没有意义了。所以答案选A。
9.(2013年上半年上午试题51)采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为________。(B)
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的最小容量为_______。(B)
A. 3
B. 4
C. 5
D. 6
解析：本题考查栈的用法。根据题中出栈的顺序，当元素c出栈后，栈中有元素a、b，当元素e出栈之前，栈中有元素a、b、d、e，此时
本文档预览：3600字符，共11164字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
