1、中级软件设计师下午试题-33 及答案解析(总分：180.00，做题时间：90 分钟)一、B试题一/B(总题数：3，分数：45.00)1.【问题 1】 转换图中缺少哪三条数据流?请指明每条数据流的名称、起点和终点。（分数：15.00）_2.【问题 2】 在状态迁移图中，a，b，c 分别表示什么事件?请用转换图中给出的事件名解答。（分数：15.00）_3.【问题 3】 在过程启动表中，d，e 处应填什么?请分别用 4 位二进制码表示。（分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)4.说明 下面的流程图(如图 3 所示)用 N - S 盒图形式描述了数组 A 中的元素被划分的
2、过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于 Ai，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i 的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以 4 为基准数的划分过程如下： （分数：15.00）_三、B试题三/B(总题数：4，分数：60.00)5.【问题 1】 请按说明中的要求画出修改后的数据模型。（分数：15.00）_6.【问题 2】 (1)说明中的几个关系仍无法实现甲公司的要求，为什么?
3、 (2)需要在哪个关系中增加什么数据项才能实现这个要求?（分数：15.00）_7.【问题 3】 写出 OrderDetail 中的关键项。（分数：15.00）_8.【问题 4】 以下 SQL 语句用于查询没有订购产品代码为“1K10”的产品的所有客户名。请填补其中的空缺。 SELECT CustomerName FROM CustomerU (1) /U WHEREU (2) /U (SELECT*FROM OrderDetail B, Order C WHERE B. ProductNo=C.ProductNo AND B. ProductNo=1K10 AND C. CustomerNo=
4、A. CustomerNo)（分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)9.说明 下列最短路径算法的具体流程如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。 算法 /*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表 MSTree
5、 返回生成树上各条边。*/ typedef struct VertexType vex1; VertexType vex2; （分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)10.程序 5 说明下列文法可用来描述化学分子式的书写规则(例如，A1 2(CO3)3”Cu(OH)2)：/n/()其中： 是个分子式； 或是一个元素，或是一个带括号的(子)分子式，元素或是一个大写字母(记为)，或是一个大写字母和一个小写字母(记为 ) 或是一个 ，或是在 之后接上一个整数 n，n表示 有 n 个 的元素或(子)分子式。个完整的分子式由若干个 组成。当然一个正确的分子式除符合上述文法规
6、则外，还应满足分子式本身的语义要求。下面的程序输入分子式，按上述文法分析分子式，并计算出该分子式的分子量。例如：元素 H 的原子量是1，元素 O 的原子量是 16。输入分子式 H2O，程序计算出它的分子量为 18 (12+16)。程序中各元素的名及它的原子量从文件 atom.dat 中读入。程序 5#include stdio. h #include string. h #define MAXN 300#define GMLEN 30struct elem char name ; /* 元素名*/double v;/*原子量*/ nTbl MAXN;char cmStr GMLEN, * po
7、s;int c;FILE * fp;double factor( );double atom( ) /* 处理文法符号 */char w 3;int i; double num;while(c = * pos+) =|c =/t); /*略过空白字符*/if(c = /n) return 0.0;if(c=A c= * pos +if(c =aelse pos-;w +i =/0,for(i =0;nTbl i. v 0.0;i +)if(strcmp (w,nTbli. name) =0) return nTbl i. v;printf (“ /n 元素表中没有所输入的无素: /t%s/n,
8、w); retur n - 1.0; elseif (c = =() if(num=U (1) /U) 0.0)return -l.0; /*包括可能为空的情况*/if( * pos + ! = ) printf (“ 分子式中括号不匹配！/n“) ;return - 1.0; return num;printf (“分子式中存在非法字符:/t%c/n“ ,c);return - 1.0;double mAtom( ) /* 处理文法符号 */ double num ;int n = ;if(num=U (2) /U) 0.0)return-l.0;c= *pos+;if(c =O while
9、(c = 0c= *poss +;pos -;return num * n;double factor( ) /*处理文法符号 */ double num =0.0,d;if( hum = mAtom ( ) 0.0) return - 1.0;while( * pos = AU(5) /U; return num;void main( ) char fname =“atom. dst“; /*元素名及其原子量文件*/int i;double num;if(fp=fopon(fname,“r“ ) = NULL) /*以读方式打开正文文件*/prinff(“Can net open%s fil
10、e. /n ,fname) ;return /*程序非正常结束 */i=0;while(i MAXNfclose(fp) ;nTbli. v =-1.0;while(1) /*输入分子式和计算分子量循环，直至输入空行结束*/printf(“ /n 输入分子式! (空行结束) /n“ ) ;gets(cmStr);pos = cmStr;if(cmStr0 = /0) break;if( (num = later( ) ) 0.0)if( * pos! = /0)printf(“分子式不完整! /n“ );else printf(“分子式的分子量为%f/n“,num);（分数：15.00）_六、
11、B试题六/B(总题数：1，分数：15.00)11.说明 定义私有数据成员 code、english 分别用于表示考生的编号、英语成绩，它们都是 int 型的数据。 完成成员函数 void Student:inputinformation()的定义，该函数用于用户输入一个考生对象的信息，输入格式如下： 输入编号： 英语成绩： 计算机成绩： 利用已实现的类 Student 的成员函数，完成函数 void firstname(Student *A，int uum)的定义，该函数根据考生信息 A，输出 num 个考生中总分最高者的编号及其相应的总分，在此不考虑总分相同的情况。 源程序文件 test1.
12、cpp 清单如下： #include iostream. h class Student U(1) /U int computer; int total; public void getinformation( ); void computesum( ); int getcode( ); int gettotalscore( ); Student( ); ; void Student: :getinformation( ) U (2) /U cout “英语成绩:“; cin english; cout “计算机成绩:“; cin computer; void Student: compute
13、sum ( ) total = english + computer; cout “编号“ code “总分:“ total endl; int Student:getcode( ) return code; int Student: gettotalscore ( ) return total; void firstname(Student * A ,int num) U (3) /U tempsum = ( * A0 ). gettotalscore( ); for( int i=1; i num; i+) if ( ( ( * Ai ). gettotalscore( ) ) temps
14、um) tempcode = ( * Ai ). getcode( ); tempsum = ( * Ai ). gettotalscore( ); cout “总分最高者-“ tempcode “:“ tempsum endl; void main( ) Student * A3; int i,n =3 for(i=0;in;i +) Ai = new Student; Ai - getinformation( ) for(i=0;in;i +) Ai - computesum( ) firstname ( A,3 ); （分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)
15、12.说明 面是一个 Applet 程序，其功能是有 2 个按钮，分别为 First 和 Second，以及一个 Label 控件。要求点击 First 时则能在 Label 中显示出 Command：First，而点击 Second 时则能显示出 Command: Second，要求只能使用重载一次 actionPerfonned()方法。 程序运行结果如图 6 所示。 （分数：15.00）_中级软件设计师下午试题-33 答案解析(总分：180.00，做题时间：90 分钟)一、B试题一/B(总题数：3，分数：45.00)1.【问题 1】 转换图中缺少哪三条数据流?请指明每条数据流的名称、起点
16、和终点。（分数：15.00）_正确答案：()解析：数据流名：目的地；起点：“接收目的地”；终点：“核查”。数据流名：投入的钱；起点“接收钱”；终点：“核查”。数据流名：剩余的钱；起点“核查”；终点：“退还钱”。 解析 转换图是在数据流程图中附加了过程控制的部分，该图描述了自动售票系统的基本行为。根据说明中给出的系统需求描述和转换图，可以看出该图没有完整的描述系统的基本行为。由于乘客选择的目的地需要经过系统的验证，确定是否是合法的目的地，因此缺少的数据流起点为“接收目的地”，终点为“核查”。转换图中只给出了将乘客投入的钱全额退还的数据流，没有给出在其他的情况下系统核查和退钱的数据流。因此缺少两条
17、数据流：一条数据流的起点为“接收钱”，终点为“核查”；另一条数据流的起点为“核查”，终点为“退还钱”。2.【问题 2】 在状态迁移图中，a，b，c 分别表示什么事件?请用转换图中给出的事件名解答。（分数：15.00）_正确答案：()解析：a“取消”操作 b核查正确 c出票结束。 解析 结合试题考查状态迁移图，状态“正在接收投钱”之后什么事件能够导致“退钱”，同时还要注意到该事件之后状态转移到“等待选择目的地”。显然，在接受投币之后如果正常发展的话应该是出票，出票的同时退还多余的钱。所以事件 a 是发生在“接收投钱”之后“出票”之前发生的导致退钱的事件，仔细考查试题说明，事件 a 应该是“取消”
18、，因为在试题的说明部分特别提到“出票钱乘客可以按，取消，按钮取消购票，系统将全额退出乘客投入的钱，并且乘客可以另选”“目的地”。按照上面的分析，我们可以看到在“接收投钱”之后，应该是在核查正确的事件发生之后才能够出票，因此事件 b 就是“核查正确”；而出票之后，“接收新的目的地”动作的执行应该是在“出票结束”事件发生之后执行的动作，因此事件 c 就是“出票结束”。3.【问题 3】 在过程启动表中，d，e 处应填什么?请分别用 4 位二进制码表示。（分数：15.00）_正确答案：()解析：d1001 e1000 解析 由于过程启动表与状态迁移图是严格对应的，因此，填充过程启动表就应该从理解状态迁
19、移图人手。结合试题说明、转换图和状态迁移图，我们可以确定，在系统中，动作“退钱”除了启动过程“退钱”外，还需要启动过程“接收目的地”，因为“退钱”之后应该等待乘客继续买票这样就必须启动过程“接收目的地”；而动作“接收新的目的地”启动的过程除了“接收目的地”之外还应该有过程“接收钱”。这样，我们就要在 d 处填写“1001”，在 e 处填写“1000”。二、B试题二/B(总题数：1，分数：15.00)4.说明 下面的流程图(如图 3 所示)用 N - S 盒图形式描述了数组 A 中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元
20、素向高下标端移动。当划分结束时，基准数定位于 Ai，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i 的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以 4 为基准数的划分过程如下： （分数：15.00）_正确答案：()解析：(1)j- (2)i+ (3)Aipivot 或jpivot (4) A，L，k-1 或 A，L，k(5)A，k+1，H 或 A，k，H解析 题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为分治法。其基本思想是：将原问题分解为若干个规模更小，但结构与原问题相似的子问题
21、。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程为：第一步，在待排序的 n 个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成 2 组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这 2 组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的 2 组元素分别进行快速排序，直到所有记录都排到相应的位置为止。在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量 pivot 中，如图中的第步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第步所示，找
22、到一个比基准元素小的元素时为止，将其前移，如图中的第步所示。然后再从前向后扫描，如图中的第步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第步所示。由题目中给出的流程图可知，以第一个元素作为基准数，并将 Alow备份至 pivot，i 用于从前向后扫描的位置指示器，其初值为 low, j 用于从后往前扫描的位置指示器，其初值为 high。当 ij 时退出循环。退出循环时，将 pivot 赋给当前的 Ai(Aipivot)。递归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正
23、常执行，应该遵守下面的规则：1)每当一个递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于 0，如果是这种情形，函数应停止递归。2)每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得“更简单”，即这些参数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达 0。本题中，递归函数 sort(int A，int L, int H)有 3 个参数，分别表示数组 A 及其下界和上界。根据流程图可知，这里的 L 相当于流程图中的 i，这里的 H 相当于流程图中的 j。因为 P()返回基准数所在数组A 中的下标，也就是流程图中最
24、后的“Aipivot”中的 i。根据快速排序算法，在第一趟排序后找出了基准数所在数组 A 中的下标，然后以该基准数为界(基准数在数组中的下标为 k)，把数组 A 分成 2 组，分别是 AL,k-1)和 Ak+1,H)，最后对这 2 组中的元素再使用同样的方法进行快速排序。三、B试题三/B(总题数：4，分数：60.00)5.【问题 1】 请按说明中的要求画出修改后的数据模型。（分数：15.00）_正确答案：()解析：如图 1 所示。 (作图) 解析 订单的情况不能作为订单的属性处理而应该上升为实体，同时由于Order 与 Product 是多对多的关系，所以应该拆分为一个名为 OrderDeta
25、il 的关系模式。其中，Order 和OrderDetail 是一对多的关系， Produce 和 OrderDetail 是一对多的关系。6.【问题 2】 (1)说明中的几个关系仍无法实现甲公司的要求，为什么? (2)需要在哪个关系中增加什么数据项才能实现这个要求?（分数：15.00）_正确答案：()解析：因为只有 product 记录了单价，一旦单价发生改变，用户订单地价格就会发生改变，因此，计算一张订单将采用新的单价，不符合要求。(2)有两种方法：一是在 Order 表中加入一项表示订单地产品总价，二是在 Order 表中加入产品单价，这两种方法都能满足要求。7.【问题 3】 写出 Or
26、derDetail 中的关键项。（分数：15.00）_正确答案：()解析：OrderNo，ProductNo 解析 在客户订商品中，一次订货下一个订单，一个订单可以有多种商品，即对应多个 OrderDetail，也就是说，一个订单、一种商品确定一个 OrderDetail，所以关键字是(OrderNo, produetNo)。8.【问题 4】 以下 SQL 语句用于查询没有订购产品代码为“1K10”的产品的所有客户名。请填补其中的空缺。 SELECT CustomerName FROM CustomerU (1) /U WHEREU (2) /U (SELECT*FROM OrderDetai
27、l B, Order C WHERE B. ProductNo=C.ProductNo AND B. ProductNo=1K10 AND C. CustomerNo=A. CustomerNo)（分数：15.00）_正确答案：()解析：A 或 AS (2)NOT EXIST 解析 在 SQL 语句的最后一行中出现了字符 A，而其他地方没有给出字符A 的含义，所以第一个空只能填 A，表示 Customer 表的简称。子查询的含义是“定购产品代码是1K10产品的所有客户名”，那么根据题意空二应该是：NOT EXIST。四、B试题四/B(总题数：1，分数：15.00)9.说明 下列最短路径算法的具
28、体流程如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。 算法 /*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表 MSTree 返回生成树上各条边。*/ typedef struct VertexType vex1; VertexType vex2; （
29、分数：15.00）_正确答案：()解析：(1)G. vexnum (2)fix_mfset (F, LoeateVex(e. vex2) (3)!= (4)k+。(5)i+ 解析 本题考查的是克鲁斯卡尔(Kruskal)算法。理解该算法的关键在于：由于生成树上不允许有问路，因此并非每一条居当前权值最小的边都可选。例如，如图 2 所示的连通网 G5，在依次选中了(e, f)，(b, c)，(e, d)和(f, s)的 4 条边之后，权值最小边为(s, d)，由于 g 和 d 已经连通，若加上(s, d)这条边将使生成树上产生回路，显然这条边不可取。同理，边(f, d)也不可取，之后则依次取(a,
30、 s)和(a, b)两条边加入到生成树。 那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为 n 个顶点分属 n 棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。五、B试题五/B(总题数：1，分数：15.00)10.程序 5 说明下列文法可用来描述化学分子式的书写规则(例如，A1 2(CO3)3”Cu(OH)2)：/n/()其中： 是个分子式； 或是一个元素，或是一个带括号的(子)分子式，元素或是一个大写字母(记为)，或是一个大写字母和
31、一个小写字母(记为 ) 或是一个 ，或是在 之后接上一个整数 n，n表示 有 n 个 的元素或(子)分子式。个完整的分子式由若干个 组成。当然一个正确的分子式除符合上述文法规则外，还应满足分子式本身的语义要求。下面的程序输入分子式，按上述文法分析分子式，并计算出该分子式的分子量。例如：元素 H 的原子量是1，元素 O 的原子量是 16。输入分子式 H2O，程序计算出它的分子量为 18 (12+16)。程序中各元素的名及它的原子量从文件 atom.dat 中读入。程序 5#include stdio. h #include string. h #define MAXN 300#define GM
32、LEN 30struct elem char name ; /* 元素名*/double v;/*原子量*/ nTbl MAXN;char cmStr GMLEN, * pos;int c;FILE * fp;double factor( );double atom( ) /* 处理文法符号 */char w 3;int i; double num;while(c = * pos+) =|c =/t); /*略过空白字符*/if(c = /n) return 0.0;if(c=A c= * pos +if(c =aelse pos-;w +i =/0,for(i =0;nTbl i. v 0.
33、0;i +)if(strcmp (w,nTbli. name) =0) return nTbl i. v;printf (“ /n 元素表中没有所输入的无素: /t%s/n,w); retur n - 1.0; elseif (c = =() if(num=U (1) /U) 0.0)return -l.0; /*包括可能为空的情况*/if( * pos + ! = ) printf (“ 分子式中括号不匹配！/n“) ;return - 1.0; return num;printf (“分子式中存在非法字符:/t%c/n“ ,c);return - 1.0;double mAtom( ) /
34、* 处理文法符号 */ double num ;int n = ;if(num=U (2) /U) 0.0)return-l.0;c= *pos+;if(c =O while(c = 0c= *poss +;pos -;return num * n;double factor( ) /*处理文法符号 */ double num =0.0,d;if( hum = mAtom ( ) 0.0) return - 1.0;while( * pos = AU(5) /U; return num;void main( ) char fname =“atom. dst“; /*元素名及其原子量文件*/in
35、t i;double num;if(fp=fopon(fname,“r“ ) = NULL) /*以读方式打开正文文件*/prinff(“Can net open%s file. /n ,fname) ;return /*程序非正常结束 */i=0;while(i MAXNfclose(fp) ;nTbli. v =-1.0;while(1) /*输入分子式和计算分子量循环，直至输入空行结束*/printf(“ /n 输入分子式! (空行结束) /n“ ) ;gets(cmStr);pos = cmStr;if(cmStr0 = /0) break;if( (num = later( ) )
36、0.0)if( * pos! = /0)printf(“分子式不完整! /n“ );else printf(“分子式的分子量为%f/n“,num);（分数：15.00）_正确答案：()解析：(1)factor() (2)atom() (3)n*10+c-0 (4)mAtom () (5)num+=d 解析 (1)查找“(”后的子分子式的分子量。(2)得到元素的原子量。(3)计算元素后面的数字。(4)计算文法符号的分子量。(5)将分子式的各个部分的分子量进行累加。atom()查找输入字符串一个元素，并输出它的原子量；遇到括号时，使用递归对括号后的元素进行识别和计算，输出后，检查是否括号匹配；遇到
37、其他字符则直接返回-1；0 表示失败。mAtom()对元素及其后面的数字进行辨识，并调用 atom()计算它们的原子量。Factor()对整个分子式进行辨识并计算其分子量。六、B试题六/B(总题数：1，分数：15.00)11.说明 定义私有数据成员 code、english 分别用于表示考生的编号、英语成绩，它们都是 int 型的数据。 完成成员函数 void Student:inputinformation()的定义，该函数用于用户输入一个考生对象的信息，输入格式如下： 输入编号： 英语成绩： 计算机成绩： 利用已实现的类 Student 的成员函数，完成函数 void firstname(
38、Student *A，int uum)的定义，该函数根据考生信息 A，输出 num 个考生中总分最高者的编号及其相应的总分，在此不考虑总分相同的情况。 源程序文件 test1.cpp 清单如下： #include iostream. h class Student U(1) /U int computer; int total; public void getinformation( ); void computesum( ); int getcode( ); int gettotalscore( ); Student( ); ; void Student: :getinformation(
39、) U (2) /U cout “英语成绩:“; cin english; cout “计算机成绩:“; cin computer; void Student: computesum ( ) total = english + computer; cout “编号“ code “总分:“ total endl; int Student:getcode( ) return code; int Student: gettotalscore ( ) return total; void firstname(Student * A ,int num) U (3) /U tempsum = ( * A0
40、 ). gettotalscore( ); for( int i=1; i num; i+) if ( ( ( * Ai ). gettotalscore( ) ) tempsum) tempcode = ( * Ai ). getcode( ); tempsum = ( * Ai ). gettotalscore( ); cout “总分最高者-“ tempcode “:“ tempsum endl; void main( ) Student * A3; int i,n =3 for(i=0;in;i +) Ai = new Student; Ai - getinformation( ) for(i=0;in;i +) Ai - computesum( ) firstname ( A,3 ); （分数：15.00）_正确答案：()解析：itn code；int engli
