1、中级软件设计师下午试题-104 及答案解析(总分：165.00，做题时间：90 分钟)一、试题一(总题数：3，分数：45.00)1.【问题 1】假设当前该旅馆各个房间的情况见表 3。序号 i ROOM RANK NBED STATUS1 101 3 4 02 102 3 4 13 201 2 3 04 202 2 4 15 301 1 6 0当输入 M=4，R=0 时，该算法的输出是什么?（分数：15.00）_2.【问题 2】如果等级为 r 的房间每人每天的住宿费为 RATE(r)，RATE 为数组。为使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费 DAYRENT
2、(J)，流程图 1 的 p 所指框中的最后处应增加什么处理?（分数：15.00）_3.【问题 3】如果限制该算法最多输出 K 个可供选择的房间号，则在流程图 1 的。所指的判断框应改成什么处理?流程图 1(如图 2 所示)（分数：15.00）_二、试题二(总题数：3，分数：45.00)4.【问题 1】对文法 G 进行改写，然后对每个非终结符写出不带回溯的递归于程序。（分数：15.00）_5.【问题 2】经改写后的文法是否是 LL(1)的?指出它的预测分析表中(1)(3)处的内容。（分数：15.00）_6.【问题 3】说明输入串(a，a)#是否为 G 的句子。（分数：15.00）_三、试题三(总
3、题数：1，分数：15.00)7.对于教学数据库的三个基本表 S(S#，SNAME，AGE，SEX)，SLLS#，C#，GRADE)，C(C#， CNAME，TEACHER)。现根据查询条件填充下面 SQL 语句空白的部分。1检索 LIU 老师所授课程的课程号和课程名。2检索至少选修 LIU 老师所授课程中一门课程的女学生姓名。3检索 WANG 同学不学的课程的课程名。4检索全部学生都选修的课程的课程号与课程名。5检索选修课程包含 LIU 老师所授课程的学生学号。说明1SELECT (1) FROM C WHERE TEACHER=LIU2. SELECT S. SNAME FROM S,SCW
4、HERE S.S#=SC.S#AND S. SEX=FAND SC.C#= (2) (SELECTC# FROM C WHERE TEACHER = LIU)3. SELECT CNAME FROM CwHEREc# (3) (SELECTSC. C# FROM S,SCWHERE S.S#=SC.S#AND S. SNAME= WANG)4. 由题知，该问题是在表 C 中找课程号和课程名，要求这门课被全部学生所选。SELECT C#,CNAMEFROM CWHERE NOT EXISTS(SELECT *FRoM SWHERE NOT EXISTS(SELECT *FROM SWHERE N
5、OT EXISTS(SELECT *FROM SCWHERE (4) 5. SELECT DISTINCT S#FROM SCWHERE (5) (SELECT C#FROM CWHERE TEACHER = LIU（分数：15.00）_四、试题四(总题数：1，分数：15.00)8.请补充函数 fun()，该函数可以统计一个长度为 n 的字符串在另一个字符串中出现的次数。例如，假定输入的字符串为：asd ascasdfg asd as asd mlosd，子字符串为 asd，则应输出 4。注意：部分源程序给出如下。请勿改动主函数 main 和其他函数中的任何内容，仅在函数 fun()的横线上填
6、人所编写的若干表达式或语句。试题程序：#include stdio. h #include string. h #include conio. h int fun(char * str,char * substr)int n;char *p,*r;(1) ;while( * str)p = str;r = substrwhile( * r)if( (2) )r+;p+;elsebreak;if( (3) )n+;str +;return n;main( )char str81,substr3;int n;clrscr ( );printf(“输入主字符串:);gets(str);printf(
7、输入子字符串:“ );gets( substr );puts(str);puts(substr);n = fun(str,substr);printf(“n=%d/n“,n)（分数：15.00）_五、试题五(总题数：1，分数：15.00)9.预备知识对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合 a，b，c，d 及其权值 2、7、4、5，可构造如图 3 所示的最优二叉树和相应的结构数组Ht(数组元素 Ht0不用)(见表 5)。（分数：15.00）_六、试题六(总题数：1，分数：15.00)10.说明为类 Circle 增加一个构造函数
8、，该函数有一个参数，并在构造时将该参数值赋给成员 radius。将该函数实现为一个非内联函数，并且使用参数列表的方式将类成员赋值。为类 Circle 增加一个成员函数 print()，使得可以输出有关圆的信息，比如下列程序Circle c；c. SetRadius(5)；c. Print()；将输出：The circle has radius of 5!完成友元函数 void CompareR(Circle *c1，Circle *c2)的定义，在屏幕中输出 c1 与 c2 比较 radius大小结果，要求使用 if - else 结构完成。输出结果如下：The circle has radu
9、s of 5 !The circle has radius of 10 !cl c2源程序文件 test7_3, cpp 清单如下:#include iostream, h class Circle public:Circle( ) :radius(5) (1) void SetRadius(int r) radius = r; int GetRadius() return radius; (2) friend void CompareR(Circle * c1,Circle * c2);private:int radius;void CompareR(Circle * c! ,Circle
10、* c2)(3) cout “c1 c2“ endl;elseif ( (c1 - GetRadius( ) = (c2 - GetRadius( )tout “c1=c2 endl;elseif ( (c1 - GetRadius( ) ( c2 - GetRadius( )cout “c1c2“ endl;void main( )Circle c1c1. SetRadius(5)c1. Print( )Circle c2(10);c2. Print( )CompareR(（分数：15.00）_七、试题七(总题数：1，分数：15.00)11.说明下面是一个 Appkt 程序，其功能是从 31
11、00 之间(包括 3 和 100)每隔 0.5 秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。程序运行结果如图 4 所示。import java. awt. *import java. applet. Applet applet code = ex2_7, class width = 800 height = 400 /applet （分数：15.00）_中级软件设计师下午试题-104 答案解析(总分：165.00，做题时间：90 分钟)一、试题一(总题数：3，分数：45.00)1.【问题 1】假设当前该旅馆各个房间的情况见表 3。序号 i ROOM RANK NBED STA
12、TUS1 101 3 4 02 102 3 4 13 201 2 3 04 202 2 4 15 301 1 6 0当输入 M=4，R=0 时，该算法的输出是什么?（分数：15.00）_正确答案：(101，301)解析：解析 当 M=4，R=0 表示客人数为 4，对房间等级没有要求，根据流程图，依次判断各个房间是否满足要求，101 有 4 张床且房间空闲，满足要求；102、202 已被占用，排除，201 床数为 34，排除；301 有 6 张床，且未被占用，满足条件，所以，输出结果为：101，301。2.【问题 2】如果等级为 r 的房间每人每天的住宿费为 RATE(r)，RATE 为数组。为
13、使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费 DAYRENT(J)，流程图 1 的 p 所指框中的最后处应增加什么处理?（分数：15.00）_正确答案：(RATE(RANK (I)*M-DAYRENT(J)解析：解析 房间的费用是根据房间的等级和房间所住客人的数量决定，所以在 框中应加入RATE(RANK(I)*M-DAYRENT(J)。3.【问题 3】如果限制该算法最多输出 K 个可供选择的房间号，则在流程图 1 的。所指的判断框应改成什么处理?流程图 1(如图 2 所示)（分数：15.00）_正确答案：(IN |j=K，其中，J=K 也可写成 JK)解析：解
14、析 若要限制算法最多输出 K 个房间号，也就是说，该程序执行输出结果的条件应为：(1)所有房间都已检查完，且满足条件的房间数小于等于 K。(2)没有检查完但满足条件的房间数已等于 K，所以 框中的条件应该改为 IN|j=K。二、试题二(总题数：3，分数：45.00)4.【问题 1】对文法 G 进行改写，然后对每个非终结符写出不带回溯的递归于程序。（分数：15.00）_正确答案：(改写文法为：(O)S；(1)S；(2)S(T)；(3)TSN；(4)N，SN；(5)N非终结符 FIRST 集 FOLLOW 集S a,( #.,Ta,c N ,. 对左部为 N 的产生式可知：FIRST(SN)=,F
15、IRST()=FOLLOW(N)=)解析：5.【问题 2】经改写后的文法是否是 LL(1)的?指出它的预测分析表中(1)(3)处的内容。（分数：15.00）_正确答案：(文法是 LL(1)的。(1)SN；(2)(T)；(3)解析：6.【问题 3】说明输入串(a，a)#是否为 G 的句子。（分数：15.00）_正确答案：(输入串(a, a)#是文法的句子。)解析：解析 对于文法Sa| (T) TT, S|S由于 SELECT(N, SN)SELECT(N)=,=(作图)，所以文法是 LL(1)的。也可由预测分析表中无多重人口判定文法是 LL(1)的。(3)对输入串(a,a)#的分析过程为：栈 当
16、前输入符 剩余输入符 所用产生式 (STACK) (CUR_CHAR) (INOUT_STRING) (OPERATION)#S ( a,a)#. .#)T( ( a,a)#. S(T)#)T a ,a)#. .#)NS a ,a)#. TSN#)Na a ,a)#. Sa#)N , a)#. .#)NS, , a)#. N,SN#)NS a )#. .#)Na a )#. Sa#)N ) #. .#) ) #. N# #可见输入串(a,a)#是文法的句子。三、试题三(总题数：1，分数：15.00)7.对于教学数据库的三个基本表 S(S#，SNAME，AGE，SEX)，SLLS#，C#，GRA
17、DE)，C(C#， CNAME，TEACHER)。现根据查询条件填充下面 SQL 语句空白的部分。1检索 LIU 老师所授课程的课程号和课程名。2检索至少选修 LIU 老师所授课程中一门课程的女学生姓名。3检索 WANG 同学不学的课程的课程名。4检索全部学生都选修的课程的课程号与课程名。5检索选修课程包含 LIU 老师所授课程的学生学号。说明1SELECT (1) FROM C WHERE TEACHER=LIU2. SELECT S. SNAME FROM S,SCWHERE S.S#=SC.S#AND S. SEX=FAND SC.C#= (2) (SELECTC# FROM C WHE
18、RE TEACHER = LIU)3. SELECT CNAME FROM CwHEREc# (3) (SELECTSC. C# FROM S,SCWHERE S.S#=SC.S#AND S. SNAME= WANG)4. 由题知，该问题是在表 C 中找课程号和课程名，要求这门课被全部学生所选。SELECT C#,CNAMEFROM CWHERE NOT EXISTS(SELECT *FRoM SWHERE NOT EXISTS(SELECT *FROM SWHERE NOT EXISTS(SELECT *FROM SCWHERE (4) 5. SELECT DISTINCT S#FROM S
19、CWHERE (5) (SELECT C#FROM CWHERE TEACHER = LIU（分数：15.00）_正确答案：(1)C#, CNAME (2)SOME (3)ALL (4)SC.S#=S.S# AND SC. C#=C.C#) (5)C#IN)解析：四、试题四(总题数：1，分数：15.00)8.请补充函数 fun()，该函数可以统计一个长度为 n 的字符串在另一个字符串中出现的次数。例如，假定输入的字符串为：asd ascasdfg asd as asd mlosd，子字符串为 asd，则应输出 4。注意：部分源程序给出如下。请勿改动主函数 main 和其他函数中的任何内容，仅在
20、函数 fun()的横线上填人所编写的若干表达式或语句。试题程序：#include stdio. h #include string. h #include conio. h int fun(char * str,char * substr)int n;char *p,*r;(1) ;while( * str)p = str;r = substrwhile( * r)if( (2) )r+;p+;elsebreak;if( (3) )n+;str +;return n;main( )char str81,substr3;int n;clrscr ( );printf(“输入主字符串:);gets
21、(str);printf(输入子字符串:“ );gets( substr );puts(str);puts(substr);n = fun(str,substr);printf(“n=%d/n“,n)（分数：15.00）_正确答案：(1)n=0 (2)*r=*p (3)*r=/0)解析：解析 填空 1：变量 n 用来记录子字符串在字符串中出现的次数，函数中对变量 n 进行了类型声明，但并没有进行初始化，所以此处对 n 初始化为 0。填空 2：进行比较时，如果子字符串的字符与字符串中的字符相同，则将两个字符串的指针都自加 1，继续进行比较，否则跳出循环。填空 3：如果此时指针 r 所指的字符为/
22、0，则说明子字符串在字符串中出现了一次，将记录变量 n 加 1。五、试题五(总题数：1，分数：15.00)9.预备知识对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合 a，b，c，d 及其权值 2、7、4、5，可构造如图 3 所示的最优二叉树和相应的结构数组Ht(数组元素 Ht0不用)(见表 5)。（分数：15.00）_正确答案：(1)codecdlen=/0或 codecdlen=0 (2)Htp.par- ent(3)-cdlen 或等价形式 (4)*buff=0或等价形式(5)buff-或等价形式)解析：解析 (1)根据注释的提示
23、，可知此小段代码的作用是把 code 字符串保存起来，结合下一句，可知应给 code 字符串添加一个结束符0。(2)将指针指向当前结点的父结点。(3)将 code 指针前移一位。(4)如果前缀编码为，0进入左子树。(5)注意下一个语句，Prinf(“%c”，Htpre.ch)；其参数是pre，内层循环中有 pre=p，这样做的目的是当 Htp.lchild 或 Htp. rchild 等于 0 时，不把这层链人结果。六、试题六(总题数：1，分数：15.00)10.说明为类 Circle 增加一个构造函数，该函数有一个参数，并在构造时将该参数值赋给成员 radius。将该函数实现为一个非内联函数
24、，并且使用参数列表的方式将类成员赋值。为类 Circle 增加一个成员函数 print()，使得可以输出有关圆的信息，比如下列程序Circle c；c. SetRadius(5)；c. Print()；将输出：The circle has radius of 5!完成友元函数 void CompareR(Circle *c1，Circle *c2)的定义，在屏幕中输出 c1 与 c2 比较 radius大小结果，要求使用 if - else 结构完成。输出结果如下：The circle has radus of 5 !The circle has radius of 10 !cl c2源程序文
25、件 test7_3, cpp 清单如下:#include iostream, h class Circle public:Circle( ) :radius(5) (1) void SetRadius(int r) radius = r; int GetRadius() return radius; (2) friend void CompareR(Circle * c1,Circle * c2);private:int radius;void CompareR(Circle * c! ,Circle * c2)(3) cout “c1 c2“ endl;elseif ( (c1 - GetR
26、adius( ) = (c2 - GetRadius( )tout “c1=c2 endl;elseif ( (c1 - GetRadius( ) ( c2 - GetRadius( )cout “c1c2“ endl;void main( )Circle c1c1. SetRadius(5)c1. Print( )Circle c2(10);c2. Print( )CompareR(（分数：15.00）_正确答案：(1)Circle(int rad):radius(rad)(2)void Print()cout “The circle has radius of“ radius “!/n“；
27、(3)if(c1-GetRadius()(c2-GetRadius()解析：解析 本题考查成员函数的定义与实现，友元函数，if 分支语句等知识点。友元函数的类体外的定义与一般函数一样，注意(3)中 if- else 的使用，else 总是与其最近的那个 if 配对使用的，书写时最好使用缩进格式，将配对的 if-else 对齐，以免出错。七、试题七(总题数：1，分数：15.00)11.说明下面是一个 Appkt 程序，其功能是从 3100 之间(包括 3 和 100)每隔 0.5 秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。程序运行结果如图 4 所示。import java.
28、awt. *import java. applet. Applet applet code = ex2_7, class width = 800 height = 400 /applet （分数：15.00）_正确答案：(1)String. valueOf(n2_7) (2)n3n100 (3)(n%i) =0(4)i101 或者 i=100 (5)obj2_7. setInt(i)解析：解析 本题主要考查线程的概念和使用，Applet 的执行过程和窗口，for 循环语句以及字符串和int 型的数据转换和面向对象编程的基本思想。解题关键是熟练地将 Applet 的执行和线程的基本思想结合完成一定的综合性的应用；熟练掌握线程的建立、运行以及线程类与封装类之间酌信息传递方式，即通过对象调用封装的方法来进行，如语句 obi2_7. repaint()。本题中，不可以直接填人 n2_7，会导致参数类型不符合的错误，应该用 String 类的 vMueOf()方法对 int 型数据进行转换得到 String 类型数据；注意题目要求，需要包括 3 和 100，因此循环变量的上界应该是 i101 或者 i=100；由于 n2_7 是类ex2_7 的私有成员，因此不可以直接用对象 obi2_7 来调用这个成员变量，需要通过类 ex2_7 的方法setInt()来实现对私有成员变量的修改。
