1、中级软件设计师下午试题-91 及答案解析(总分：-4.98，做题时间：90 分钟)一、试题一(总题数：1，分数：-1.00)【说明】某直达列车车票预售系统接受顾客的订票、取票和售票处工作人员的查询业务。1顾客为了提前订票，可向系统提供个人信息及其预订购的车次及日期，系统根据个人信息是否齐全以及车次是否正确来判断订票单是否合格。对于合格的订票单系统，如果相应的车次有剩余票，则记录顾客个人信息以及订票信息，并向顾客提供取票单。2到了可以取票的时间，顾客向系统提供取票单，在检查单据合格的情况下，系统向顾客提供火车票。3售票处的工作人员可以利用系统查询各车次车票的售票情况。该直达列车车票预售系统的分层
2、数据流图中部分数据流和文件的组成如下：文件：火车时刻表=车次+开车时间+到站时间+起始站+终点站+上铺票价+下铺票价订票信息表=车次+车票日期+旅客身份证号+座位号+是否领票旅客信息表=旅客身份证号+姓名+性别+联系电话座位表=车次+座位号数据流：订票单=旅客姓名+性别+身份证号+联系电话+车次十车票日期车票=车次+起始站生终点站+开车日期+开车时间+座位号+票价假定顶层图是正确的，“火车时刻表”和“座位表”文件已由其他系统生成。【数据流图】（分数：-0.99）_二、试题二(总题数：1，分数：-1.00)【算法说明】下面是一段插入排序的程序，将 Rk+1插入到 R1.k的适当位置。R0=Rk+
3、1；j=k；while(RjR0)Rj+1=Rj；j- -；Rj+1=R0；【流程图】（分数：-1.00）_三、试题三(总题数：1，分数：-1.00)对文法 GS：Sa|(T)；TT，S|S：回答问题 1问题 3。【表】表 4-2 预测分析表a ( ) , #S a (u)(2)(/u)T (u)(1)(/u) SN SNN (u)(3)(/u) ,SN1. 【问题 1】对文法 G 进行改写，然后对每个非终结符写出不带回溯的递归子程序。（分数：-0.99）_四、试题四(总题数：1，分数：-1.00)阅读下列程序和控制流图，将应填入 (n) 的字句写在答题纸的对应栏内。【程序】下面是一段求最大值
4、的程序，其中 datalist 是数据表，n 是 datalist 的长度+int GetMax (int n, int datalist) int k=0;for (int j=1;jn;j+)if (datalistj datalistk)k=j;retum k;【控制流图】（分数：-1.00）_五、试题五(总题数：1，分数：-1.00)1.阅读下列程序说明和 C 程序，将应填入 (n) 处的字句写在答卷纸的对应栏内。【程序说明】该程序定义了两个子函数 strsort 和 strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序，并删去相同字符。在主函数里，先输入两
5、个字符串 s1 和 s2，然后调用 strsort 函数对它们分别排序，然后调用 strmerge 函数将 s1 和 s2 合并，将合并后的字符串赋给字符串 s3，最后输出字符串 s3。【程序】#include stdio.hvoid strmerge(char *a,char *b,char *c) /将字符串 a,b 合并到字符串 cchar t,*w;W=c;while( (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)
6、 ) /开始，可直接赋值*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 !=/0)if(*b!=*w)*(+w)=*b;b+;elseb+;(7) void strsort(char *s) /将字符串 s 中的字符排序int i,j,n;char t,*w;w=s;f
7、or(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 );prinff(“/nPlease input the second string:“);scanf(“%s“,s2);strsort(s1); /将字符串 s1 排序strson(s2); /
8、将字符串 s2 排序prinff(“%s/n,s1);printfC % sW,s2);s30=/O; /字符串 s3 的第一个字符先置/0结束标志(10) ; /将 s1 和 s2 合并，按照字母顺序排列,prinff(“%s“,s3);（分数：-1.00）_中级软件设计师下午试题-91 答案解析(总分：-4.98，做题时间：90 分钟)一、试题一(总题数：1，分数：-1.00)【说明】某直达列车车票预售系统接受顾客的订票、取票和售票处工作人员的查询业务。1顾客为了提前订票，可向系统提供个人信息及其预订购的车次及日期，系统根据个人信息是否齐全以及车次是否正确来判断订票单是否合格。对于合格的订
9、票单系统，如果相应的车次有剩余票，则记录顾客个人信息以及订票信息，并向顾客提供取票单。2到了可以取票的时间，顾客向系统提供取票单，在检查单据合格的情况下，系统向顾客提供火车票。3售票处的工作人员可以利用系统查询各车次车票的售票情况。该直达列车车票预售系统的分层数据流图中部分数据流和文件的组成如下：文件：火车时刻表=车次+开车时间+到站时间+起始站+终点站+上铺票价+下铺票价订票信息表=车次+车票日期+旅客身份证号+座位号+是否领票旅客信息表=旅客身份证号+姓名+性别+联系电话座位表=车次+座位号数据流：订票单=旅客姓名+性别+身份证号+联系电话+车次十车票日期车票=车次+起始站生终点站+开车日
10、期+开车时间+座位号+票价假定顶层图是正确的，“火车时刻表”和“座位表”文件已由其他系统生成。【数据流图】（分数：-0.99）_正确答案：(0 层图中文件“座位表”是局部数据文件，不必画出。)解析：分析“不必画出”是指在数据流图中，只画流程图中各加工之间的公共数据文件，隐藏某加工的局部数据文件，这个规则只是为了使整个数据流图的层次结构更科学、更清晰，不过画出“不必画出的数据文件”对数据流图不会造成理解错误。在 0 层图中有文件“火车时刻表”、“订票信息表”、“旅客信息表”和“座位表”，其中“座位表”是加工 1“顾客订票”的局部数据文件，所以不必画出。_正确答案：(数据流图 4-1 中从加工“1
11、.1 检查订票单”到文件“列车时刻表”的数据流。(2)数据流图 4-1 中从文件“旅客信息表”到加工“1.3 填写取票单”的数据流。(3)数据流图 4-2 中从加工“2.1 枪查取票单”到文件“旅客信息表”的数据流。)解析：分析本题是找出错误的数据流。解决这种问题的关键是父图与子图的平衡，即子图的输入输出数据流与父图相应的加工的输入输出数据必须一致。从 0 层图中可以看到对于加工 1“顾客订票”，有到文件“旅客信息表”的输出流，从文件“列车时刻表”得到的输入流，以及与文件“订票信息表”的输入输出流。而加工 l 子图中只有从加工 1.1 到文件“列车时刻表”的数据流，与父图不一致，因此是错误的，
12、应该为从文件“列车时刻表”到加工 1.1 的数据流。同理，从文件“旅客信息表”到加工 1.3 的数据流也与父图不一致，应该改为从加工 1.3 到文件“旅客信息表”的数据流。0 层图中加工 2“顾客取票”中存在从文件“旅客信息表”到加工 2 的数据流，而加工 2 子图中从加上2.1 到文件“旅客信息表”的数据流是与 0 层图相悖的，因此也是错误的。应该改成从文件“旅客信息表”到加工 2.1“检查信息表”的数据流。_正确答案：(不可以。从 0 层图中可以看出，加工 3“查询处理”仅有从文件“订票信息表”的输入流，而从说明中的文件组成可以看出，订票信息表仅记录了旅客订票和取票的信息，不能知道总的座位
13、数，因此加工 3 能查询已订购和已售出的车票情况，而不能查询出剩余票的情况。)解析：分析每个加工的功能要从提供给该加工的文件的信息量决定。从 0 层图中可以看出，加工 3“查询处理”仅有从文件“订票信息表”的输入流，而从说明中的文件组成可以看出，订票信息表仅记录了旅客订票和取票的信息，不能知道总的座位数，因此加上 3 能查询己订购和已售出的车票情况，而不能查询出剩余票的情况。要向查询出剩余票的情况，需要利用文件“座位表”来了解车次座位的总的情况，再利用文件“订票信息表”的已订和已售车票信息共同得出剩余票信息。二、试题二(总题数：1，分数：-1.00)【算法说明】下面是一段插入排序的程序，将 R
14、k+1插入到 R1.k的适当位置。R0=Rk+1；j=k；while(RjR0)Rj+1=Rj；j- -；Rj+1=R0；【流程图】（分数：-1.00）_正确答案：(F(2)Rj+1=R0(3)T)解析：分析本题考查用路径覆盖方法为算法设计足够的测试用例，属于基本概念的送分题。这类题拿分的关键是考生平时对于理论的理解和临场的细心。_正确答案：(5)(6)(7)(8) 1(9) 3)解析：三、试题三(总题数：1，分数：-1.00)对文法 GS：Sa|(T)；TT，S|S：回答问题 1问题 3。【表】表 4-2 预测分析表a ( ) , #S a (u)(2)(/u)T (u)(1)(/u) SN
15、 SNN (u)(3)(/u) ,SN1. 【问题 1】对文法 G 进行改写，然后对每个非终结符写出不带回溯的递归子程序。（分数：-0.99）_正确答案：(改写文法为：(0)Sd(1)S(2)S(T)(3)TSN(4)N,SN(5)N非终结符 FIRST 集 FOLLOW 集S a，( #,T a，( N , 对左部为 N 的产生式可知：FIRST(，SN)；，FIRST()：FOLLOW(N)=)解析：分析对于文法Sd|(T) TT,S|S由于 SELECT(N，SN)SELECT(N)=，=*，所以文法是。LL(1)的。也可由预测分析表中无多重入口判定文法是 LL(1)的。(3)对输入串(
16、a,a)#的分析过程为：栈 当前输入符 剩余输入符 所用产生式(STACK) (CUR CHAR) (1NOUT 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)#是文法的句子。_正确答案：(文法是 LL(1)的。(1)SN(2)(T)(3)C)解析：_正确答案：(输入串(a，a)#是文法的句
17、子。)解析：四、试题四(总题数：1，分数：-1.00)阅读下列程序和控制流图，将应填入 (n) 的字句写在答题纸的对应栏内。【程序】下面是一段求最大值的程序，其中 datalist 是数据表，n 是 datalist 的长度+int GetMax (int n, int datalist) int k=0;for (int j=1;jn;j+)if (datalistj datalistk)k=j;retum k;【控制流图】（分数：-1.00）_正确答案：(jn(2)return k；(3)datalistjdatalistk(4)k=j；(5)j+；)解析：分析本题考查对软件测试概念和过程
18、的理解，结合具体实例运用各种测试技术，学会测试用例设计、软件测试与程序调试的方法。软件测试是为了发现错误而执行程序的过程，其目的在于以最少的时间和人力系统地找出软件中潜在的各种错误和缺陷。根据 2004 新大纲和最近两次软件设计师考试的真题，不难发现各类系统分析理论的实例化考核比例逐渐升温，只要读者平时对这部分知识的实例多分析、多思考，这部分分数其实不难拿到。_正确答案：(McCabe 环路复杂性为 3。)解析：_正确答案：(测试路径：Path1：Path2：.Path3：.)解析：_正确答案：(测试用例：Path1：取 n=1，datalist0=1，预期结果：k=0Path2：取 n=2，
19、datalist0=1，datalist1=0，预期结果：k=OPath3：取 n=2，datalist0=0，datalist1=1，预期结果：k=1)解析：五、试题五(总题数：1，分数：-1.00)1.阅读下列程序说明和 C 程序，将应填入 (n) 处的字句写在答卷纸的对应栏内。【程序说明】该程序定义了两个子函数 strsort 和 strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序，并删去相同字符。在主函数里，先输入两个字符串 s1 和 s2，然后调用 strsort 函数对它们分别排序，然后调用 strmerge 函数将 s1 和 s2 合并，将合并后的字
20、符串赋给字符串 s3，最后输出字符串 s3。【程序】#include stdio.hvoid strmerge(char *a,char *b,char *c) /将字符串 a,b 合并到字符串 cchar t,*w;W=c;while( (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(*
21、a!=/O) /如果字符串 a 还没有结束，则将 a 的剩余部分赋给 cwhile(*a!=/0)if(*a!=*w)*(+w)=*a;a+;else(6) if(*b!=“,/0) /如果字符串 b 还没有结束，则将 b 的剩余部分赋给 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 进行排序，按字母先后顺序for
22、O=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 );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结
23、束标志(10) ; /将 s1 和 s2 合并，按照字母顺序排列,prinff(“%s“,s3);（分数：-1.00）_正确答案：(*a!=/0/)&(*b!=/0)(2)a+(3)b+(4)*w=/0(5)*(+w)=t(6)a+(7)*(+w)=/0(8)sisj(9)sj=t(10)strmerge(s1,s2,s3)解析：分析根据题意，对字符串的处理分为三步：第一步是从键盘上输入两个字符串：第二步是将两个字符串分别排序；第三步是将字符串合并；第四步是显示处理结果。第一步和第四步容易实现，关键是第二步和第三步的处理，下面分别加以说明。字符串排序是指将一个字符串中各个字符按照 ASCII
24、码值的大小排序。例如，字符串“Beijing”由小到大的排序结果应该是：”Bejiign“。排序算法很多，第二个例子，我们就要介绍快速排序算法。在这里使用简单的冒泡排序算法：即将字符串中的每一个字符一个个进行比较，找出最小的字符，然后再在剩下的字符中找最小的字符。例如，字符“Beijing”的排序过程如下：第一次将字符“Beijing”中的每一个字符：B、e、i、j、i、n、g进行比较，找到最小的字符B。第二次在剩下的字符e、i、j、n、g中，找到最小的字符e。第三次在剩下的字符i、j、i、n、g中，找到最小的字符j。第三步是合并字符串，合并后的字符串仍然由小到大排序。由于待合并的两个字符串已
25、经排好序。假定两个排好序的字符串分别为 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结尾的。
