中级软件设计师下午试题-112
(总分：46.00，做题时间：90分钟)
一、试题一(总题数：1，分数：2.00)
1.使用说明中的词语，给出下图中的数据存储D1～D5的名称。



（分数：2.00）
__________________________________________________________________________________________
正确答案：(D1：学生信息文件；D2：课程单元信息文件：D3：课程信息文件；D4：课程成绩文件；
D5：无效成绩文件。
注：D2和D3的答案可以互换。)
解析：
二、试题二(总题数：1，分数：15.00)
[说明]
一个描述学校的部分关系模式的结果描述如下：
1．一个系有若干学生，但一个学生只能在一个系；
2．一个系只有一名主任；
3．一个学生可以选修多门课程，每门课程有若干学生选修；
4．每个学生所学的每门课程都有一个成绩；
5．“学生”和“课程表”及“选课表”的关系示例分别如表1、表2、表3所示。
Student(学生表)的字段按顺序为学号(Sno)、姓名(Sname)、性别(Ssex)、年龄(Sage)、所属院系(Sdept)、系主任(Smaster)；
Course(课程表)的字段按顺序为课程编号(Cno)、课程名(Cname)、先行课程(Cpno)、课程学分 (Ccredit)；
SC(选课表)的字段按顺序为学号(Sno)、课程号(Cno)、成绩(Grade)。
各表的记录如下：
表1 Student
merge函数
Sno
Sname
Ssex
Sage
Sdept
Smaster
95001
李勇
男
20
CS
王平
95002
刘晨
女
19
IS
周言
95003
王明
女
18
MA
展评
95004
张立
男
19
IS
周言

                                      　表2 Course
Cno
Cname
Cpno
Ceredit
1
　数据库
5
4
2
　数学
2
3
　信息系统
1
4
4
　操作系统
6
3
5
　数据结构
7
4
6
　数据处理
2
7
　PASCAL
6
4
                                      　表3 SC
　Sno
　Cno
　Grade
　95001
　1
　92
　95001
　2
　85
　95001
　3
　88
　95002
　2
　90
　95003
　3
　80


（分数：15.00）
(1).[问题1]
试分析该关系模式中的函数依赖，并指出关系模式的候地选码。（分数：5.00）
__________________________________________________________________________________________
正确答案：(在该关系模式中，存在以下函数依赖：
学号→姓名 学号→所在系 所在系→系主任
(学号，课程名)→成绩
系主任传递的依赖学号；
该关系模式的候选码为(学号，课程名)；
姓名、所在系部分依赖候选码。)
解析：[解析]
试题二
本题考查的是基础知识，考生如果掌握对关系模式和SQL语言的相关知识可得出答案。
(2).[问题2]
如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。
SELECT (1)
FROM (2)
WHERE (3) （分数：5.00）
__________________________________________________________________________________________
正确答案：((1)Sname, Ssex
(2)Student
(3)Sdept IN('IS','CS'))
解析：
(3).[问题3]
如下的SQL语句是检索“每个学生及其选修的课程名和成绩”的不完整语句，请在空缺处填入正确的内容。
SELEC (1)
FROM (2)
WHERE (3) （分数：5.00）
__________________________________________________________________________________________
正确答案：((1)Student.Sno,Sname,Course.Cname,SC.Grade
(2)Student,SC,Course
(3)Student.Sno=SC.Sno and SC.Cno=Course.Cno；)
解析：
三、试题三(总题数：1，分数：15.00)
[说明]
背包问题就是有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。
背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。
常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到limitweight，这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为下图。
仔细阅读程序说明和C程序流程图及源码，回答问题1和问题2。
[流程图]



[程序说明]
struct Thing：物品结构
typedef struct Bag：背包结构类型
input ( )：将物品按序号依次存入数组函数
inbag ( )：物品按物价比入包函数
init ( )：初始化函数
sort ( )：对物品按价格重量比排序函数
outbag ( )：取出包中weiht最大的物品函数
print ( )：最佳方案输出函数
[C程序]
#define N 255
struct Thing
double weight;
double value;
double dens;
thing[N];
typedef stmct Bag
Thing thing [N];
double weighttmp;
double sumvalue;
bag,best;
inbag ( )

do
bag.thing[i]=thing[i]
(1)
(2)
i++;
while ( (3) )


init ( )

for (inti=0; i＜N; i++)

input (thing[i].weight, thing [i].value)
thing [i].dens=thing[i].value/thing [i].weight;
;

main ( )

init ( );
sort ( );
inbag ( );
do
best=bag; //把包中物品放入暂存数组
outbag ( ); //取出包中weight最大的物品
(4)
while ( (5) )
print (best)； //输出temp因为是最佳方案


（分数：15.00）
(1).[问题1]
根据程序说明及流程图、部分C源码，充分理解算法思想，填入 (n) 处。（分数：7.50）
__________________________________________________________________________________________
正确答案：(bag.weighttmp=bag.weighttmp+thing[i].weight;
(2)bag.sumvalue=bag.sumvalue+thing[i].value;
(3)bag.weighttmp＜=weightlimit
(4)inbag ( )；
(5)best.sumvalue＜bag.sumvalue)
解析：[解析] 本题考查的是考生对流程图的阅读能力。本题涉及的算法是背包问题。背包问题求解方法很多，考生首先要理解本题中的新方法，然后对照流程图阅读代码。(1)处应该为物品总重量；(2)处应该为物品总价值；(3)处应该为直到达到极限重量limit weight；(4)处应该为继续装物品；(5)处应该为比较当前结果与备份结果。问题2同样是考查有关基本概念的问题。根据软件设计师考试的趋势，本套题设计上有意识地增加了概念考查部分，希望考生能够加强对基本概念的理解与训练。
(2).[问题2]
求解“背包问题”常用的方法有哪几种?各有什么样的特点?（分数：7.50）
__________________________________________________________________________________________
正确答案：(“背包问题”求解方法主要是一些启发式算法，如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解，从中选出最佳解。这种解法实际上是穷举了所有的可能，只是加了一些限制。如果所求的数据很大，这种算法的效率就不是很高，甚至是不可实
现的。贪婪法不用穷举且速度快，但用贪婪法却不一定能到最优解。由于贪婪法所得到的解与最优解存在很大的差距，当要求较高时，就会成为贪婪法致命的且无法挽救的缺陷。)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。