1、中级软件设计师下午试题-10 及答案解析(总分：150.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：30.00)阅读以下说明和流程图，回答问题 1和问题 2，将答案写在答卷的对应栏内。（分数：30.00）(1).【问题 1】流程图中的文件 F的记录格式设置为如下形式： 赛车号 姓名 课程代码 其中的、应定义为何种数据?（分数：15.00）_(2).【问题 2】简述处理 2、处理 3和处理 4做何种处理，若有排序处理则需指明排序的键及序(升序或降序)。（分数：15.00）_二、B试题二/B(总题数：1，分数：45.00)阅读以下说明，回答问题 1至问题 3，将答案写在答卷的对
2、应栏内。【说明】下面是某 ERP系统中零件供应模块的 3个关系模式。供应商：S(SNO，SNAME，CITY，STATUS)零件：P(PNO，PNAME，WEIGHT，COLOR，CITY)供应单：SP(SNO，PNO，PTY，SP Date)属性说明：SNO供应商编号，SNAME供应商名称，CITY地址，STATUS供应商状态PNO零件编号，PNAME零件名称，WEIGHT零件重量，COLOR零件颜色， CITY地址，PTY数量，SP Date订单日期问题：用 SQL语句完成以下操作。（分数：45.00）(1).【问题 1】求供应红色零件北京供应商的编号、名称和状态。（分数：15.00）_(
3、2).【问题 2】将所有北京供应商的状态为 2的修改为 1。（分数：15.00）_(3).【问题 3】求零件颜色不是白色和黑色的供应商状态为 1的订单的数量。（分数：15.00）_三、B试题三/B(总题数：1，分数：30.00)阅读以下说明和图，回答问题 1和问题 2，将答案写在答卷的对应栏内。【说明】银行客户需要从 ATM取 100元，他向 ATM的读卡机插卡，读卡机读取卡号，然后 ATM屏幕初始化，ATM 提示输入 PIN(密码)，客户输入 PIN(123456)，ATM 打开他的账户，密码有效，因此 ATM提示选择事务，客户选择取钱，ATM 提示输入金额，客户输入 100元， ATM 验
4、证账户上有足够的钱，就从账上减去 100元，ATM吐出 100元，并退出客户的卡。（分数：30.00）(1).【问题 1】根据上面的描述，完成下述的时序图。（分数：15.00）_(2).【问题 2】比较时序图和协作图，说明区别和联系。（分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)1.【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include stdio. h #include stdlib. h #define MAXN 30 typedef struct int v1,v2; /*一条边依附的两个顶点*/ int weight; /*边上的权值*/ EDGE;
5、 typedef struct int Vnum; /*图中的顶点数目*/ EDGE eMAXN*(MAXN-1)/2; /*图中的边*/ Graph; typedef struct node /*用链表存储同一个连通分量的顶点*/ int v; struct node *next; Alist; void heapadjust(EDGE data, int s, int m) /*将元素序列 datasm调整为小顶堆, 堆顶元素(最小元素)为 datas*/ int j; EDGE t; t=datas; /*备份元素 datas, 为其找到适当位置后再插入*/ for(j=2*s+1; j
6、=m; j=j*2+1)/*沿值较小的子结点向下筛选*/ if(jm if(!(t. weightdataj. weight) break; datas=dataj;s=j; /*用 s记录待插入元素的位置(下标)*/ /*for*/ datas=t; /*将备份元素插入由 s所指出的插入位置*/ /*heapadjust*/ int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/ int k=0; /*记录图中边的数目*/ int n; int v1,v2; int w; printf(“vertex number of the graph:“);
7、 scanf(“%d“, /*输入图中的顶点数目*/ if(n1) return 0; p-Vnum=n; do printf(“edge(vertex1,vertex2,weight):“); scanf(“%d %d %d“, if(v1=0 p-ek. v2=v2; p-ek. weight=w; k+; /*if*/ while(!(U (2) /U); return k; /*返回图中边的数目*/ /*creat_graph*/ int kruskal(Graph G, int enumber, int tree3) /*用 kruskal算法求无向连通图 G的最小生成树, 图中边所
8、得数目为 enumber, */ /*数组 tree3中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/ int i, k, m, c=0; int v1, v2; Alist *p, *q, *aMAXN; for(i=0; iGVnum; +i) /*将每个连通分量中的顶点存放在一个单链表中*/ ai=(Alist*)malloc(sizeof(Alist); if(!ai) printf(“/n mernory allocation error!“); exit(0); /*if*/ ai-v=i; ai-next=NULL; /*for*/ for(i=enumber-1;
9、 i=0; -i)/*按照边上的权值建立小顶堆*/ heapadjust(U (3) /U);k=G. Vnum; /*k用于计算图中的连通分量数目*/ m=enumber-1; i=0; do v1=G. e0. v1; v2=G. e0.v2; p=av1; while(p p=p-next; if(!p) /*当前边的顶点不在一个连通分量中*/ p=q; p-next=aG. e0. v2; p=aG. e0. v1); /*加入边(v1,v2), 将两个连通分量合并为一个*/ while(p)ap-v=U (4) /U; p=p-next; k-; /*连通分量数目减少一个*/ tre
10、ei0=v1; /*记录加入最小生成树的边*/ treei1=v2; treei2=G. e0. weight; c+=G. e0. weight; +i; /*if*/ G. e0=G. em; m-; heapadjust (U (5) /U); while(k1); /*当所有顶点不在同一个连通时, 继续*/ return c; /*返回最小生成树的代价*/ /*kruskal*/ void main(void) int i, enumber; int treeMAXN3; int cost=0; Graph G; enumber=creat_graph( cost=-kruskal(G
11、,enumber,tree); printf(“Minimum-Cost spanning tree(kruskal)：/n“); printf(“edge/t weight/t/n“); for(i=0; iG. Vnum-1; +i) printf(“v %d v %d /t %d/n“, treei0, treei1, treei2); printf(“Cost：%d/n“, cost); （分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)2.【说明】构造最优二叉查找树。具有 n个结点的有序序列 a1, a2, , an存在于数组元素 a1、a2, , an之中, a
12、0未被使用。结点 a1, a2, , an-1, an的查找成功的概率 p1, p2, , pn-1, pn存在于数组元素 p1、p2, , pn1、pn之中, p0未用。另外, 查找失败的概率 q0, q1, , qn-1, qn存在于数组元素 q0、p1, qn-1、qn之中。算法计算的序列 ai+1, ai+2, aj-1, aj的最优二叉查找树 Tij的代价 Cij存在于数组元素 cij之中, T ij的根结点的序号 rij存在于 rij之中, 它的权值存在于 wij之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。const float MAXNUM=99999. 0;
13、/尽可能大的浮点数templateU (1) /Uvoid OPtimal_Binary_Search_Tree(float p, float q, Type a, int n) float *C, *W; c=U (2) /U; w=U (3) /U; int *r; r=new int(n+1)*(n+1); for(i=0; i=n; i+) ci*(n+1)+i=0. 0; / 即：cii=0.0, 用一维数组表示wi*(n+1)+i=qi; / 即：wii=qi, 用一维数组表示int i, j, k, m, length; / m表示根结点的下标或序号, 范围为 0nfloat m
14、inimum; for(length=1; length=n; length+) /处理的序列长度由 1到 nfor(i=0; i=n-length; i+) /i 为二叉查找树 Tij的起始序号j=i + length; /j为二叉查找树 Tij的终止序号。如：处理序列 a1a2a3时, /相应的二叉查找树为 T03, i=0, 而 j=3wi*(n+1)+j=U (4) /U; minimum =MAXMUM;for(k=i+1; k=j; k+) /考察以 ai+1、a i+2, , ai为根的情况if(U (5) /Uminimum) minimum=ci*(n+1)+k-1+ck*(
15、n+1)+j;m=k; ci*(n+1)+j=wi*(n+1)+j+ci*(n+1)+m-1+cm*(n+1)+j; ri*(n+1)+j=m; / rij=m /构造好的最优二叉查找树的根结点的序号在 r0n中（分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)3.【说明】数据排序。将给定的 n个整数分别按照升序和降序进行排列。 class SortInt_1 int i, j, k, temp; void SortInt(int a1, a2)/升序排序 for(i=0; ia1-1; i+) k=i; for(j=i+1 ;ja1 ;j+) if (U (1) /U)
16、k=j; if(k!=i) temp=a2i;a2i=a2k;a2k=temp; class Sortlnt_2U (2) /U int i, j, k, temp; void Sortlnt(int a1,a2)/降序排序 for(i=0;ia1-1 ;i+) k=i; for(j=i+1 ;ja1 ;j+) if (U (3) /U) k=j; if(k!=i) temp=a2i;a2i=a2k;a2k=temp; Class TestOverLoad Public static void main(String args) int a=10,55,100,35,87,90,100,16;
17、 Sortlnt_1 newlnt1=U (4) /U; Newlnt1. SortInt(a. length, a);/调用 SortInt_1类的方法 System. out. println(“升序排列的数据“); For(int i=0;i8;i+) System. out. print(ai+“ “); system. out. println(); SortInt_2 newInt2=new sortint_2(); /创建类 SortInt_2的对象 U (5) /U; System. out. println(“降序排列的数据: “); For(int i=0;i8;i+) S
18、ystem. out. print(ai+“ “); （分数：15.00）_中级软件设计师下午试题-10 答案解析(总分：150.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：30.00)阅读以下说明和流程图，回答问题 1和问题 2，将答案写在答卷的对应栏内。（分数：30.00）(1).【问题 1】流程图中的文件 F的记录格式设置为如下形式： 赛车号 姓名 课程代码 其中的、应定义为何种数据?（分数：15.00）_正确答案：()解析： 成绩 名次。(2).【问题 2】简述处理 2、处理 3和处理 4做何种处理，若有排序处理则需指明排序的键及序(升序或降序)。（分数：15.00
19、）_正确答案：()解析：按课程代码(升序)、成绩(降序) 处理 2：对文件 F排序。 处理 3：决定分赛段名次，计算总成绩，决定总名次，填入文件 F的相应字段。 处理 4：按总成绩(降序)，按课程代码(降序)排列。 试题 1 解析 文件 F是文件 F0经过处理 1产生的文件，这个文件又经过处理 2、处理 3、处理 4的处理和更新，而在处理 5中，只是进行了车手成绩一览表的输出编排，不进行排序和增加名次等处理，文件 F中的数据项必须是由文件 F0产生，还要经过处理产生车手成绩一览表。所以，可以推导出文件 F中是成绩，是名次 通过对给出的车手成绩一览表的观察，可以确定对文件 F的处理中要按课程代码
20、升序，按成绩降序进行排列。 处理 2、处理 3、处理 4要对文件进行一系列处理，最后得到的文件 F在处理 5只是做了输出编排，所以在处理 4已经完成要求的根据分赛段成绩比较而获得的分赛段名次，按总名次降序排序，按课程名排序。所以，可以推导，处理 2对文件 F排序，处理 3决定分赛段名次，计算总成绩，决定总名次，填入文件 F的相应字段。处理 4按总成绩(降序)，按课程代码(降序)排列。二、B试题二/B(总题数：1，分数：45.00)阅读以下说明，回答问题 1至问题 3，将答案写在答卷的对应栏内。【说明】下面是某 ERP系统中零件供应模块的 3个关系模式。供应商：S(SNO，SNAME，CITY，
21、STATUS)零件：P(PNO，PNAME，WEIGHT，COLOR，CITY)供应单：SP(SNO，PNO，PTY，SP Date)属性说明：SNO供应商编号，SNAME供应商名称，CITY地址，STATUS供应商状态PNO零件编号，PNAME零件名称，WEIGHT零件重量，COLOR零件颜色， CITY地址，PTY数量，SP Date订单日期问题：用 SQL语句完成以下操作。（分数：45.00）(1).【问题 1】求供应红色零件北京供应商的编号、名称和状态。（分数：15.00）_正确答案：()解析：SELECT DISTINCT S.SNO, S.SNAME, S.STATUS FROM
22、S, P, SP WHERE S.SNO=SP.SNO AND P.PNO=SP.PNO AND P/PNO=红色(2).【问题 2】将所有北京供应商的状态为 2的修改为 1。（分数：15.00）_正确答案：()解析：UPDATE S SETSTATUS=1 WHERE CITY=北京 AND STATUS=1(3).【问题 3】求零件颜色不是白色和黑色的供应商状态为 1的订单的数量。（分数：15.00）_正确答案：()解析：SELECT COUNT(*) FROM S,P,SP WHERE S.SNO=SP.SNO AND P.PNO=SP.PN0 AND P.COLOR=红色 AND S.
23、STATUS=1 试题 2 解析 这 3个语句比较简单，只是考查考生的 SQL语句基本知识。三、B试题三/B(总题数：1，分数：30.00)阅读以下说明和图，回答问题 1和问题 2，将答案写在答卷的对应栏内。【说明】银行客户需要从 ATM取 100元，他向 ATM的读卡机插卡，读卡机读取卡号，然后 ATM屏幕初始化，ATM 提示输入 PIN(密码)，客户输入 PIN(123456)，ATM 打开他的账户，密码有效，因此 ATM提示选择事务，客户选择取钱，ATM 提示输入金额，客户输入 100元， ATM 验证账户上有足够的钱，就从账上减去 100元，ATM吐出 100元，并退出客户的卡。（分数
24、：30.00）(1).【问题 1】根据上面的描述，完成下述的时序图。（分数：15.00）_正确答案：()解析：1插卡 2读卡号 3提示输入 PIN 4输入 PIN 5验证 PIN 6选择事务(取钱) 7扣钱(100元) 8提供钱(100 元) 9退卡(2).【问题 2】比较时序图和协作图，说明区别和联系。（分数：15.00）_正确答案：()解析：时序图和协作图都可以用来描述系统对象之间的交互。时序图强调一组对象之间调用的时间顺序，协作图强调这组对象之间的关系。 试题 3 解析 时序图用来描述对象间的交互行为。它注重消息的时间顺序，即消息的发送和接收的顺序。 时序图的图形组成成分为：对象、生存线
25、、消息和对象激活期(本题中省略)。 试题中要求的就是完成消息，所以要根据消息的时间顺序，和消息发出与接收的对象。由于已经给出了详细明晰的动作过程描述，未完成的时序图中也标识出对象和部分消息，所以，应该比较容易地完成其它的消息。四、B试题四/B(总题数：1，分数：15.00)1.【说明】用克鲁斯卡尔算法求解给定图的最小生成树。 #include stdio. h #include stdlib. h #define MAXN 30 typedef struct int v1,v2; /*一条边依附的两个顶点*/ int weight; /*边上的权值*/ EDGE; typedef struct
26、 int Vnum; /*图中的顶点数目*/ EDGE eMAXN*(MAXN-1)/2; /*图中的边*/ Graph; typedef struct node /*用链表存储同一个连通分量的顶点*/ int v; struct node *next; Alist; void heapadjust(EDGE data, int s, int m) /*将元素序列 datasm调整为小顶堆, 堆顶元素(最小元素)为 datas*/ int j; EDGE t; t=datas; /*备份元素 datas, 为其找到适当位置后再插入*/ for(j=2*s+1; j=m; j=j*2+1)/*沿
27、值较小的子结点向下筛选*/ if(jm if(!(t. weightdataj. weight) break; datas=dataj;s=j; /*用 s记录待插入元素的位置(下标)*/ /*for*/ datas=t; /*将备份元素插入由 s所指出的插入位置*/ /*heapadjust*/ int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/ int k=0; /*记录图中边的数目*/ int n; int v1,v2; int w; printf(“vertex number of the graph:“); scanf(“%d“, /*
28、输入图中的顶点数目*/ if(n1) return 0; p-Vnum=n; do printf(“edge(vertex1,vertex2,weight):“); scanf(“%d %d %d“, if(v1=0 p-ek. v2=v2; p-ek. weight=w; k+; /*if*/ while(!(U (2) /U); return k; /*返回图中边的数目*/ /*creat_graph*/ int kruskal(Graph G, int enumber, int tree3) /*用 kruskal算法求无向连通图 G的最小生成树, 图中边所得数目为 enumber, *
29、/ /*数组 tree3中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/ int i, k, m, c=0; int v1, v2; Alist *p, *q, *aMAXN; for(i=0; iGVnum; +i) /*将每个连通分量中的顶点存放在一个单链表中*/ ai=(Alist*)malloc(sizeof(Alist); if(!ai) printf(“/n mernory allocation error!“); exit(0); /*if*/ ai-v=i; ai-next=NULL; /*for*/ for(i=enumber-1; i=0; -i)/*按照边上
30、的权值建立小顶堆*/ heapadjust(U (3) /U);k=G. Vnum; /*k用于计算图中的连通分量数目*/ m=enumber-1; i=0; do v1=G. e0. v1; v2=G. e0.v2; p=av1; while(p p=p-next; if(!p) /*当前边的顶点不在一个连通分量中*/ p=q; p-next=aG. e0. v2; p=aG. e0. v1); /*加入边(v1,v2), 将两个连通分量合并为一个*/ while(p)ap-v=U (4) /U; p=p-next; k-; /*连通分量数目减少一个*/ treei0=v1; /*记录加入最
31、小生成树的边*/ treei1=v2; treei2=G. e0. weight; c+=G. e0. weight; +i; /*if*/ G. e0=G. em; m-; heapadjust (U (5) /U); while(k1); /*当所有顶点不在同一个连通时, 继续*/ return c; /*返回最小生成树的代价*/ /*kruskal*/ void main(void) int i, enumber; int treeMAXN3; int cost=0; Graph G; enumber=creat_graph( cost=-kruskal(G,enumber,tree);
32、 printf(“Minimum-Cost spanning tree(kruskal)：/n“); printf(“edge/t weight/t/n“); for(i=0; iG. Vnum-1; +i) printf(“v %d v %d /t %d/n“, treei0, treei1, treei2); printf(“Cost：%d/n“, cost); （分数：15.00）_正确答案：()解析：解析 (1) dataj.weightdataj+1.weight 沿值较小的子结点向下筛选，建堆，堆顶元素最小； (2) v1=-1 /尽可能大的浮点数templateU (1) /Uv
33、oid OPtimal_Binary_Search_Tree(float p, float q, Type a, int n) float *C, *W; c=U (2) /U; w=U (3) /U; int *r; r=new int(n+1)*(n+1); for(i=0; i=n; i+) ci*(n+1)+i=0. 0; / 即：cii=0.0, 用一维数组表示wi*(n+1)+i=qi; / 即：wii=qi, 用一维数组表示int i, j, k, m, length; / m表示根结点的下标或序号, 范围为 0nfloat minimum; for(length=1; leng
34、th=n; length+) /处理的序列长度由 1到 nfor(i=0; i=n-length; i+) /i 为二叉查找树 Tij的起始序号j=i + length; /j为二叉查找树 Tij的终止序号。如：处理序列 a1a2a3时, /相应的二叉查找树为 T03, i=0, 而 j=3wi*(n+1)+j=U (4) /U; minimum =MAXMUM;for(k=i+1; k=j; k+) /考察以 ai+1、a i+2, , ai为根的情况if(U (5) /Uminimum) minimum=ci*(n+1)+k-1+ck*(n+1)+j;m=k; ci*(n+1)+j=wi*
35、(n+1)+j+ci*(n+1)+m-1+cm*(n+1)+j; ri*(n+1)+j=m; / rij=m /构造好的最优二叉查找树的根结点的序号在 r0n中（分数：15.00）_正确答案：()解析：解析 (1) class Type定义最优二叉查找树生成函数模板 Optimal_Binary_Search_Tree。(2) new float(n+1)*(n+1)按数组 a长度 n+1申请动态二维数组 c，存放最优二叉查找树 Tij的代价 Cij。(3) new float(n+1)*(n+1)按数组 a长度 n+1申请动态二维数组 w，存放最优二叉查找树 Tij的权值 Wij。(4) w
36、i*(n+1)+j-1+pj+qj由 Wij-1递推计算 Wij。(5) ci*(n+1)+k-1+ck*(n+1)+j找 Cik+Ckj(k=i+1，j)的最小值的 m=k，求 Cij。按照一般二维数组的写法是： cij=wij+cim-1+cmj。六、B试题六/B(总题数：1，分数：15.00)3.【说明】数据排序。将给定的 n个整数分别按照升序和降序进行排列。 class SortInt_1 int i, j, k, temp; void SortInt(int a1, a2)/升序排序 for(i=0; ia1-1; i+) k=i; for(j=i+1 ;ja1 ;j+) if (U
37、 (1) /U) k=j; if(k!=i) temp=a2i;a2i=a2k;a2k=temp; class Sortlnt_2U (2) /U int i, j, k, temp; void Sortlnt(int a1,a2)/降序排序 for(i=0;ia1-1 ;i+) k=i; for(j=i+1 ;ja1 ;j+) if (U (3) /U) k=j; if(k!=i) temp=a2i;a2i=a2k;a2k=temp; Class TestOverLoad Public static void main(String args) int a=10,55,100,35,87,9
38、0,100,16; Sortlnt_1 newlnt1=U (4) /U; Newlnt1. SortInt(a. length, a);/调用 SortInt_1类的方法 System. out. println(“升序排列的数据“); For(int i=0;i8;i+) System. out. print(ai+“ “); system. out. println(); SortInt_2 newInt2=new sortint_2(); /创建类 SortInt_2的对象 U (5) /U; System. out. println(“降序排列的数据: “); For(int i=0
39、;i8;i+) System. out. print(ai+“ “); （分数：15.00）_正确答案：()解析：解析 (1) a2ja2k 选择排序的判断条件，k 是最小元素的下标。 (2) extends SortInt_1 类的多态，SortInt2 由类 SortInt1派生而来。 (3) a2ja2k 选择排序的判断条件，k 是最大元素的下标。 (4) new SortInt_1() 创建类 SortInt1的对象，再调用 SortInt1类的方法进行升序排序。 (5) Newint2.SortInt(a. length, a) 调用 SortInt2类的方法，实现降序排序。 本题采用选择排序的方法，第 1、3 空考查对算法的掌握，两空可互相对照，第 2、4、 5 空考查对 Java语言的掌握情况，两空亦可互相对照，难度不大。
