1、中级软件设计师下午试题-112 及答案解析(总分：46.00，做题时间：90 分钟)一、试题一(总题数：1，分数：2.00)1.使用说明中的词语，给出下图中的数据存储 D1D5 的名称。（分数：2.00）_二、试题二(总题数：1，分数：15.00)说明一个描述学校的部分关系模式的结果描述如下：1一个系有若干学生，但一个学生只能在一个系；2一个系只有一名主任；3一个学生可以选修多门课程，每门课程有若干学生选修；4每个学生所学的每门课程都有一个成绩；5“学生”和“课程表”及“选课表”的关系示例分别如表 1、表 2、表 3 所示。Student(学生表)的字段按顺序为学号(Sno)、姓名(Sname
2、)、性别(Ssex)、年龄(Sage)、所属院系(Sdept)、系主任(Smaster)；Course(课程表)的字段按顺序为课程编号(Cno)、课程名(Cname)、先行课程(Cpno)、课程学分 (Ccredit)；SC(选课表)的字段按顺序为学号(Sno)、课程号(Cno)、成绩(Grade)。各表的记录如下：表 1 StudentSno Sname Ssex Sage Sdept Smaster95001 李勇 男 20 CS 王平95002 刘晨 女 19 IS 周言95003 王明 女 18 MA 展评95004 张立 男 19 IS 周言表 2 Course Cno Cname
3、Cpno Ceredit1 数据库 5 42 数学 23 信息系统 1 44 操作系统 6 35 数据结构 7 46 数据处理 27 PASCAL 6 4表 3 SC Sno Cno Grade95001 1 9295001 2 8595001 3 8895002 2 9095003 3 80（分数：15.00）(1).问题 1试分析该关系模式中的函数依赖，并指出关系模式的候地选码。（分数：5.00）_(2).问题 2如下的 SQL 语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT (1) FROM (2) WHERE (
4、3) （分数：5.00）_(3).问题 3如下的 SQL 语句是检索“每个学生及其选修的课程名和成绩”的不完整语句，请在空缺处填入正确的内容。SELEC (1) FROM (2) WHERE (3) （分数：5.00）_三、试题三(总题数：1，分数：15.00)说明背包问题就是有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。背包问题是一个典型的 NP 完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。常用
5、的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到 limitweight，这时的物品就是 limit weight 的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为下图。仔细阅读程序说明和 C 程序流程图及源码，回答问题 1 和问题 2。流程图（分数：15.00）(1).问题 1根据程序说明及流程图、部分 C 源码，充分理解算法思想，填
6、入 (n) 处。（分数：7.50）_(2).问题 2求解“背包问题”常用的方法有哪几种?各有什么样的特点?（分数：7.50）_四、试题四(总题数：1，分数：15.00)2.【说明】设某城市有 n 个车站，并有 m 条公交线路连接这些车站，设这些公交车都是单向的，这 n 个车站被顺序编号为 0 至 n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站 0 出发乘公交车至站 n-1 的最少换车次数。程序利用输入信息构建一张有向图 G(用邻接矩阵 g 表示)，有向图的顶点是车站，若有某条公交线路经 i站到达 j 站，就在顶点 i 到顶点 j 之间设置一条权为 1 的
7、有向边i,j。如果这样，从站点 x 至站点 y的最少上车次数便对应图 G 中从点 x 到点 y 的最短路径长度。而程序要求的换车次数就是上车次数减 1。#include stdio.h#define M 20#define N 50int aN+1； /*用于存放一条线路上的各站编号*/int gNN； /*严存储对应的邻接矩阵*/int distN； /*严存储站 0 到各站的最短路径*/int m, n；void buildG()int i, j, k, sc, ddprintf(“输入公交线路数，公交站数/n”)；scanf(“%d%d“，W=c;while( (1) )/找到字符串 a
8、,b 当前字符中较小的字符if(*a*b)t=-*a,(2) else if(*a*b)t=*b;(3) else /字符串 a,b 当前字符相等t=-*a;a-H-;b-H-;if( (4) ) /开始，可直接赋值*w=t;else if(t!=*w)/如果 a,b 中较小的当前字符与 c 中当前字符不相等，才赋值(5) if(*a!=/O) /如果字符串 a 还没有结束，则将 a 的剩余部分赋给 cwhile(*a!=/0)if(*a!=*w)*(+w)=*a;a+;else(6) if(*b!=“,/0) /如果字符串 b 还没有结束，则将 b 的剩余部分赋给 cwhile(*b !=/
9、0)if(*b!=*w)*(+w)=*b;b+;elseb+;(7) void strsort(char *s) /将字符串 s 中的字符排序int i,j,n;char t,*w;w=s;for(n=O;*w!=/O;n+) /得到字符串长度 nw+;for(i=O;in-1;i+) /对字符串 s 进行排序，按字母先后顺序forO=i+ 1 ;jn;j+)if( (8) t=si;si=sj;(9) void mainOchar s1 100,s2100,s3100;prinff(“/nlPlease input the first string:“);scanfC(“% s“,s1 );
10、prinff(“/nPlease input the second string:“);scanf(“%s“,s2);strsort(s1); /将字符串 s1 排序strson(s2); /将字符串 s2 排序prinff(“%s/n,s1);printfC % sW,s2);s30=/O; /字符串 s3 的第一个字符先置/0结束标志(10) ; /将 s1 和 s2 合并，按照字母顺序排列,prinff(“%s“,s3);（分数：-1.00）_中级软件设计师下午试题-112 答案解析(总分：46.00，做题时间：90 分钟)一、试题一(总题数：1，分数：2.00)1.使用说明中的词语，给
11、出下图中的数据存储 D1D5 的名称。（分数：2.00）_正确答案：(D1：学生信息文件；D2：课程单元信息文件：D3：课程信息文件；D4：课程成绩文件；D5：无效成绩文件。注：D2 和 D3 的答案可以互换。)解析：二、试题二(总题数：1，分数：15.00)说明一个描述学校的部分关系模式的结果描述如下：1一个系有若干学生，但一个学生只能在一个系；2一个系只有一名主任；3一个学生可以选修多门课程，每门课程有若干学生选修；4每个学生所学的每门课程都有一个成绩；5“学生”和“课程表”及“选课表”的关系示例分别如表 1、表 2、表 3 所示。Student(学生表)的字段按顺序为学号(Sno)、姓名
12、(Sname)、性别(Ssex)、年龄(Sage)、所属院系(Sdept)、系主任(Smaster)；Course(课程表)的字段按顺序为课程编号(Cno)、课程名(Cname)、先行课程(Cpno)、课程学分 (Ccredit)；SC(选课表)的字段按顺序为学号(Sno)、课程号(Cno)、成绩(Grade)。各表的记录如下：表 1 StudentSno Sname Ssex Sage Sdept Smaster95001 李勇 男 20 CS 王平95002 刘晨 女 19 IS 周言95003 王明 女 18 MA 展评95004 张立 男 19 IS 周言表 2 Course Cno
13、Cname Cpno Ceredit1 数据库 5 42 数学 23 信息系统 1 44 操作系统 6 35 数据结构 7 46 数据处理 27 PASCAL 6 4表 3 SC Sno Cno Grade95001 1 9295001 2 8595001 3 8895002 2 9095003 3 80（分数：15.00）(1).问题 1试分析该关系模式中的函数依赖，并指出关系模式的候地选码。（分数：5.00）_正确答案：(在该关系模式中，存在以下函数依赖：学号姓名 学号所在系 所在系系主任(学号，课程名)成绩系主任传递的依赖学号；该关系模式的候选码为(学号，课程名)；姓名、所在系部分依赖候
14、选码。)解析：解析 试题二本题考查的是基础知识，考生如果掌握对关系模式和 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)
15、 （分数：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 完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装
16、载问题等均可建模为背包问题。常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到 limitweight，这时的物品就是 limit weight 的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为下图。仔细阅读程序说明和 C 程序流程图及源码，回答问题 1 和问题 2。流程图（分数：15.00）(1).问题 1根据程序说明及流程图、部分
17、 C 源码，充分理解算法思想，填入 (n) 处。（分数：7.50）_正确答案：(bag.weighttmp=bag.weighttmp+thingi.weight;(2)bag.sumvalue=bag.sumvalue+thingi.value;(3)bag.weighttmp=weightlimit(4)inbag ( )；(5)best.sumvaluebag.sumvalue)解析：解析 本题考查的是考生对流程图的阅读能力。本题涉及的算法是背包问题。背包问题求解方法很多，考生首先要理解本题中的新方法，然后对照流程图阅读代码。(1)处应该为物品总重量；(2)处应该为物品总价值；(3)处应
18、该为直到达到极限重量 limit weight；(4)处应该为继续装物品；(5)处应该为比较当前结果与备份结果。问题 2 同样是考查有关基本概念的问题。根据软件设计师考试的趋势，本套题设计上有意识地增加了概念考查部分，希望考生能够加强对基本概念的理解与训练。(2).问题 2求解“背包问题”常用的方法有哪几种?各有什么样的特点?（分数：7.50）_正确答案：(“背包问题”求解方法主要是一些启发式算法，如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解，从中选出最佳解。这种解法实际上是穷举了所有的可能，只是加了一些限制。如果所求的数据很大，这种算法的效率就不是很高，甚至是不可实现的。贪婪
19、法不用穷举且速度快，但用贪婪法却不一定能找到最优解。由于贪婪法所得到的解与最优解存在很大的差距，当要求较高时，就会成为贪婪法致命的且无法挽救的缺陷。)解析：四、试题四(总题数：1，分数：15.00)2.【说明】设某城市有 n 个车站，并有 m 条公交线路连接这些车站，设这些公交车都是单向的，这 n 个车站被顺序编号为 0 至 n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站 0 出发乘公交车至站 n-1 的最少换车次数。程序利用输入信息构建一张有向图 G(用邻接矩阵 g 表示)，有向图的顶点是车站，若有某条公交线路经 i站到达 j 站，就在顶点 i 到顶点
20、 j 之间设置一条权为 1 的有向边i,j。如果这样，从站点 x 至站点 y的最少上车次数便对应图 G 中从点 x 到点 y 的最短路径长度。而程序要求的换车次数就是上车次数减 1。#include stdio.h#define M 20#define N 50int aN+1； /*用于存放一条线路上的各站编号*/int gNN； /*严存储对应的邻接矩阵*/int distN； /*严存储站 0 到各站的最短路径*/int m, n；void buildG()int i, j, k, sc, ddprintf(“输入公交线路数，公交站数/n”)；scanf(“%d%d“，W=c;while
21、( (1) )/找到字符串 a,b 当前字符中较小的字符if(*a*b)t=-*a,(2) else if(*a*b)t=*b;(3) else /字符串 a,b 当前字符相等t=-*a;a-H-;b-H-;if( (4) ) /开始，可直接赋值*w=t;else if(t!=*w)/如果 a,b 中较小的当前字符与 c 中当前字符不相等，才赋值(5) if(*a!=/O) /如果字符串 a 还没有结束，则将 a 的剩余部分赋给 cwhile(*a!=/0)if(*a!=*w)*(+w)=*a;a+;else(6) if(*b!=“,/0) /如果字符串 b 还没有结束，则将 b 的剩余部分赋
22、给 cwhile(*b !=/0)if(*b!=*w)*(+w)=*b;b+;elseb+;(7) void strsort(char *s) /将字符串 s 中的字符排序int i,j,n;char t,*w;w=s;for(n=O;*w!=/O;n+) /得到字符串长度 nw+;for(i=O;in-1;i+) /对字符串 s 进行排序，按字母先后顺序forO=i+ 1 ;jn;j+)if( (8) t=si;si=sj;(9) void mainOchar s1 100,s2100,s3100;prinff(“/nlPlease input the first string:“);sca
23、nfC(“% s“,s1 );prinff(“/nPlease input the second string:“);scanf(“%s“,s2);strsort(s1); /将字符串 s1 排序strson(s2); /将字符串 s2 排序prinff(“%s/n,s1);printfC % sW,s2);s30=/O; /字符串 s3 的第一个字符先置/0结束标志(10) ; /将 s1 和 s2 合并，按照字母顺序排列,prinff(“%s“,s3);（分数：-1.00）_正确答案：(1)(*a!=/0/)&(*b!=/0)(2)a+(3)b+(4)*w=/0(5)*(+w)=t(6)a
24、+(7)*(+w)=/0(8)sisj(9)sj=t(10)strmerge(s1,s2,s3)解析：分析根据题意，对字符串的处理分为三步：第一步是从键盘上输入两个字符串：第二步是将两个字符串分别排序；第三步是将字符串合并；第四步是显示处理结果。第一步和第四步容易实现，关键是第二步和第三步的处理，下面分别加以说明。字符串排序是指将一个字符串中各个字符按照 ASCII 码值的大小排序。例如，字符串“Beijing”由小到大的排序结果应该是：”Bejiign“。排序算法很多，第二个例子，我们就要介绍快速排序算法。在这里使用简单的冒泡排序算法：即将字符串中的每一个字符一个个进行比较，找出最小的字符，
25、然后再在剩下的字符中找最小的字符。例如，字符“Beijing”的排序过程如下：第一次将字符“Beijing”中的每一个字符：B、e、i、j、i、n、g进行比较，找到最小的字符B。第二次在剩下的字符e、i、j、n、g中，找到最小的字符e。第三次在剩下的字符i、j、i、n、g中，找到最小的字符j。第三步是合并字符串，合并后的字符串仍然由小到大排序。由于待合并的两个字符串已经排好序。假定两个排好序的字符串分别为 A 和 B，合并后的字符串为巴要使待合并后的字符串仍然由小到大排序，可采取下述步骤：1从前往后取 A 中的字符，并按从前往后的顺序与 B 中的字符比较，若 A 中的字符较小，则将该字符存入 C，并移到 A 的下一个字符，继续与 B 中的字符比较。2若 A 中的字符较大，则将 B 中的字符存入 C，并移到 B 的下一个字符，继续与 A 中的字符比较。3若 A 与 B 中的字符相等，则将 A 或 B 中的字符存入 C 并将 A 和 B 均移到下一个字符。4若 A 或 B 字符串到达末尾，则将 B 或 A 的剩余部分加到字符串 C 中。需要注意的是：A、B 和 C 三个字符串均可以用字符数组来表示，C 数组的长度不能小于 A、B 两数组的长度之和。另外，判别字符串是否结尾的方法是：从 A 或 B 中取出的字符是否为/0，所有字符串都是以/0结尾的。
