1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 48及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和图，回答问题 1至问题 3，将解答填入对应栏内。 说明 某汽车数字仪表系统将完成下述功能： (1)通过模一数转换，实现传感器和微处理器的接口。 (2)在发光二极管面板上显示数据。 (3)指示速度 (mph)、行驶里程、油耗 (mpg)等。 (4)指示加速或减速。 以下是经分析得到的数据流图，有些地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图 1-2是第 0层 数据流图，图1-3是第 1层数据流图，其中 A是加工 1的细化图， B是加
2、工 2的细化图。图中， sps表示转速 sps的瞬时变化值，若 sps 0则汽车加速， sps 0则减速， sps=0则匀速。假定题中提供的顶层图是正确的，请回答下列问题。 图 1-1 图 1-2 图 1-3 1 第 0层数据流图 (图 1-2)中有一条缺失的数据流，请指出该数据流的起点和终点。 加工 1的细化图 (图 1-3中的 A)中有一条缺失的数据流，请指出该数据流的起点和终点。 2 加工 2的细化图 (图 1-3中的 B)中有一条 错误的数据流，请指出该数据流的起点或终点 (若可以，指出两者 )。 3 小说明是用来描述加工的。小说明的描述方法有哪些 ?请分别用这些描述方法描述加工 1.
3、2。 3 阅读下列说明和 E-R图，回答问题 1至问题 3，将解答填入对应栏内。 说明 设有下列关于学生成绩管理系统的 E-R图 (见图 2-1)。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体间的联系。假定已通过下列 SQL语言建立了基本表： CREATE TABLE STUDENT(SNo CHAR(6)NOT NULL UNIQUE， SName CHAR(20)， Sex CHAR(1)， Dept CHAR(20)， Age SMALLINT)； CREATE TABLE COURSE(CNo CHAR(6)NOT NULL UNIQUE， CName CHAR(20
4、)， Hour SMALLINT， Credit SMALLINT)； CREATE TABLE SC (SNo CHAR(6)， CNo CHAR(6)， GRADE SMALLINT， PRIMARY KEY (SNo， CNo)； 为了答题的方便，图中的实体和属性同时给 出了中英文两种名字，回答问题时只须写出英文名即可。 填充下列 SQL程序 5.1 5.4中的 (1) (6)，使它们分别完成以下查询功能： 程序 5.1：检索选修所有课程的学生姓名。 程序 5.2：给出全体学生人数。 程序 5.3：按学号给出每个学生的平均成绩。 程序 5.4：按学号给出每个学生选修课程的门数。 程序 5
5、.1 SELECT SName FROM STUDENT WHERE (1) (SELECT FROM COURSE WHERE (2) (SELECT * FROM SC WHERE (3) ) 程序 5.2 SELECT (4) FROM STUDENT 程序 5.3 SELECT (5) FROM SC GROUP BY SNO 程序 5.4 SELECT (6) FROM SC GROUP BY SNO 4 (1) 5 (2) 6 (3) 7 (4) 8 (5) 9 (6) 9 阅读以下说明和程序流程图，将应填入 (n)处的字句写在对应栏内。 说明 当一元多项式 中有许多系数为零时，可
6、用一个单链表来存储，每个节点存储一个非零项的指受和对应系数。 为了便于进行运算 ，用带头节点的单链表存储，头节点中存储多项式中的非零项数，且各节点按指数递减顺序存储。例如：多项式8x5-2x2+7的存储结构为： 流程图图 3-1用于将 pC(Node结构体指针 )节点按指数降序插入到多项式 C(多项式POLY指针 )中。 流程图中使用的符号说明如下： (1)数据结构定义如下： #define EPSI 1e-6 struct Node /*多项式中的一项 */ double c； /*系数 */ int e； /*指数 */ Struct Node *next； ； typedef struc
7、t /*多项式头节点 */ int n； /*多项式不为零的项数 */ struct Node *head； POLY； (2)Del(POLY *C， struct Node *p)函数，若 p是空指针则删除头节点，否则删除 p节点的后继。 (3)fabs(double c)函数返回实数C的绝对值。 图 3-1 10 (1) 11 (2) 12 (3) 13 (4) 14 (5) 14 阅读下列说明和 C程序，将应填入 (n)处的字句写在对应栏中。 说明 借助一个栈结 构，可实现二叉树的非递归遍历算法。 InOrderTraverse数实现中序非递归遍历，遍历 过程如下： 若不是空树，根节点
8、入栈，进入左子树；若已经是空树，则栈顶元素出栈，访问该元素 (根节点 )，进入该节点的右子树，继续直到遍历完成。 函数中使用的预定义符号如下： typedef struct BiTNode int data； struct BiTNode *iChiid， *rChiid； BiTNode， *BiTree； typedef struct SNode/*链栈的节点类型 */ BiTree elem； struct SNode *next； SNode； 函数 int InOrderTraverse(BiTree root) BiTree P； SNode *q， *stop=NULL； /*不
9、带头节点的单链表作为栈的存储结构 */ P=root； while(p !=NULL | stop !=NULL) if( (1) ) /*不是空树 */ q=(SNode*)malloc(sizeof q)； if(q=NULL)return-1； /*根节点指针入栈 */ (2)； q- elem=P； stop=q； P=(3)； /*进入根的左子树 */ else q=stop； (4)； /*栈顶元素出栈 */ printf(“%d|， q- elem- data)； /*防问根节点 */ P=(5)； /*进入 根的右子树 */ free(q)； /*释放原栈顶元素 */ /*if
10、*/ /*while*/ return 0； /*InOrderTraverse*/ 15 (1) 16 (2) 17 (3) 18 (4) 19 (5) 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 19 阅读下列函数说明和 C代码，将应填入 (n)处的字句写上。 说明 若要在 N个城市之间建立通信网络，只需要 N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在 8个城市间建立通信网络，其问拓扑结构如图 5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代
11、价。 图 5-1 无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素 (不包括对角线 )。 现用 Prim算法生成网络的最小生成树。由网络 G=(V， E)构造最小生成树 T=(U， TE)的 Prim算法的基本思想是：首先从集合 V中任取一顶点放 入集合 U中，然后把所有一个顶点在集合 U里、另一个顶点在集合 V-U里的边中，找出权值最小的边 (u， v)，将边加入 TE，并将顶点 v加入集合 U，重复上述操作直到 U=V为止。 函数中使用的预定义符号如下： #define MAX 32768 /*无穷大权，表示顶点间不连通
12、*/ #define MAXVEX 30 /*图中顶点数目的最大值 */ typedef struct int startVex， stopVex; /*边的起点和终点*/ float weight; /*边的权 */ Edge; typedef struct char vexsMAXVEX; /*顶点信息 */ float arcsMAXVEX*(MAXVEX-1)/2; /*邻接矩阵信息，压缩存储 */ int n; /*图的顶点个数 */ Graph; 函数 void PrimMST(Graph*pGraph, Edge mst) int i,j,k,min,vx,vy; float w
13、eight， minWeight; Edge edge; for(i=0; i pGraph- n-1；i+) msti.StartVex=0; msti.StopVex=i+1; msti.weight=pGraph- arcsi; for(i=0； i (1)； i+)/*共 n-1条边 */ minWeight=(float)MAX; min=i; /*从所有边(vx， vy)中选出最短的边 */ for(j=i; j pGraph- n-1; j+) if(mstj.weightminWeight) minWeight=(2); min=j； /*mstminl是最短的边 (vx， v
14、y)，将mstmin加入最小生成树 */ edge=mstmin； mstmin=msti; msti=edge; vx=(3);/*vx为刚加入最小生成树的顶点下标 */ /*调整 msti+1到 mstn-1*/ for(j=i+1； j pGraph- n-1； j+) vy=mstj.StopVex; if( (4) )/*计算 (vx， vy)对应的边在压缩矩阵中的下标 */ k=pGraph- n*vy-vy*(vy+1)/2+vx-vy-1； else k=pGraph- n*vx-vx*(vx+1)/2+vy-vx-1; weight(5)； if(weightmstj.wei
15、ght) mstj.weight=weight; mstj.StartVex=vx; 20 (1) 21 (2) 22 (3) 23 (4) 24 (5) 24 阅读以下说明和 C+代码，将应填入 (n)处的字句写上。 说明 现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一个 Shape类 (接口 )，有方法显不 display()。 需要新增图形 Circle，又已知有类 XXCircle实现了所需要实现的功能：显示 displayIt()。为了继承自 shape以提供统一接口，又不希望从头开发代码，希望使用 XXCircle。这样将 XXcircle作为 Circ
16、le的一个属性，即 Circle的对象包含一个 XXCircle对象。当一个 Circle对象被实例化时，它必须实例化一个相应的 XXCircle对象： Circle对象收到的做任何事的请求都将转发给这个 XXCircle对象。通过这种称为 Adapter模式， Circle对象就可以通过 “让 XXCircle做实际 工作 ”来表现自己的行为了。图 6-1显示了各个类间的关系。以下是 C+语言实现，能够正确编译通过。 图 6-1 C+代码 class Shape public： (1) void display()=0; ; class Line： public Shape/省略具体实现 ;
17、 class Square： public Shape/省略具体实现 ; class XXCircle public： void displayIt() /省略具体实现 /省略其余方法和属性 ; class Circle： public Shape private： XXCircle *pxc; public： Circle(); void display(); ; Circle：Circle() pxc=(2); void Circle： display() pxc- (3); class Factory public： (4) getshapeInstance(int type)/生成特定
18、类实例 switch(type) case 1： return new Square; case 2： return new Line; case 3 ： return new Circle; default： return NULL; ; void main(int argc， char*argv) if(argc !=2) cout “error parameters!“ endl; return; int type=atoi(argv1); Factory factory； Shape*s=factory. (5); if(s=NULL) cout “Error get the inst
19、ance!“ endl; return; s- display(); delete s； return； 25 (1) 26 (2) 27 (3) 28 (4) 29 (5) 29 阅读以下函数说明和 Java代码，将应填入 (n)处的字句写上。 说明 现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一个 Shape类 (接口 )，有方法显示 display()。 需要新增图形 Circle，又已知有类 XXCircle实现了所需要实现的功能：显示 displayIt()。为了继承自 shape以提供统一接口，又不希望从头开发代码，希望使用 XXCircle。这样将 X
20、XCircle作为 Circle的一个属性，即 Circle的对象包含一个 XXCircle对象。当一个 Circle对 象被实例化时，它必须实例化一个相应的 XXCircle对象；当 Circle对象收到的做任何事的请求都将转发给这个XXCircle对象。通过这种称为 Adapter模式， Circle对象就可以通过 “让 XXCircle做实际工作 ”来表现自己的行为了。图 7-1显示了各个类间的关系。以下是 JAVA语言实现，能够正确编译通过。 图 7-1 Java代码 /Shape.java文件 public interface Shape public (1) void displa
21、y(); /XXCircle.jave文件 public class XXCircle public void displayIt() /省略具体实现 /Circle.java文件 public class Circle (2) Shape private XXCircle pcx=(3); public void display() pcx.displayIt()； /Factory.java文件 public class Factory public (4) getShapeInstance(int type) switch(type) case 1： return new Line()；
22、 case 2： return new Square()； case 3： return new Circle()； default： return null； /Main.java文件 public class Main public static void main(Stringargs) int type=1； Factory factory=new Factory()； Shape s; s=factory. (5)； if(s=null) System.out.println(“Error get the instance!“); return； s.display(); retur
23、n； 30 (1) 31 (2) 32 (3) 33 (4) 34 (5) 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 48答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 图 1-2中，缺失的数据流：速度 mph，起点：加工 1速度处理，终点： 仪表板图 1-3A中，缺失的数据流：加速 /减速，起点：加工 1.2确定加速 /减速，终点：仪表板 【试题解析】 分层数据流图应时刻牢记父图与子图平衡原则。对这种数据流缺失题目，认真对照父图与子图就可答案。另外，还要注意与文件的交互，包括错误数据流大多也是出在此。 将第 0层数据流图 (图 1-2)与项层数据
24、流图 (图 1-1)仔细对照，可以发现缺失了输出数据流 “速度 ”，其起点为加工 1速度处理，终点为仪表板。数据流 “速度 mph”虽然从加工 1输出到了加工 2，但这内部数据流。 同理，加工 1的细化图 (图 1-3A)缺失了数据流 “加速 /减速 ”，其起点是加工 1.2确定加速 /减速，终仪表板。 2 【正确答案】 图 1-3B中，错误的数据流：速度 mph，起点：加工 2.2计算油耗 【试题解析】 仔细对照加工 2(图 1-2)和加工 2的细化图 (图 1-3B)，可以发现对于加工 2.2数据流 “速度 mph”作出数据，而该数据流应该是输入数据。 3 【正确答案】 小说明并不描述具体
25、的加工过程，常用的有自然语言、结构化自然语言、判定表和判定树。 自然语言描述：若 sps 0则汽车加速， sps 0则减速， sps=0则匀速。 结构 化自然语言描述： IF sps 0 THEN加速 ELSE IF sps 0 THEN减速 ELSE匀速 判定表描述：4 【正确答案】 NOT EXISTS 5 【正确答案】 NOT EXISTS 6 【正确答案】 STUDENT.SN0=SC.SN0 AND COURSE.CNO=SC.CNO 7 【正确答案】 COUNT(*) 8 【正确答案】 SNO， AVG(GRADE) 9 【正确答案】 SNO， COUNT(CNO) 【试题解析】
26、本题主要是考察 SQL。 SQL中数 据查询是最常用的，其完整形式如下： SELECT ALL | DISTINCT目标列表达式 ，目标列表达式 FROM 表名或视图名 ，表名或视图名 WHERE 条件表达式 GROUP BY列名 1 HAVING条件表达式 ORDER BY列名 2 ASC | DESC 子句顺序为 SELECT、 FROM、 WHERE、 GROUP BY、 HAVING、 ORDER BY，但 SELECT和 FROM是必须的， HAVING子句只能与 GROUP BY搭配起来使用。 该成绩管理系统的关系模式有： STUDENT(SNo， SName， Sex， Dept
27、， Age)，主键为 SNo， COURSE(CNo， CName， Hour， Credit)，主键为 CNo， SC(SNO，CNO， GRADE)，主键为 (Sno， CNo)。 程序 5.1是检索选修所有课程的学生姓名，亦即 “不存在没有选修的课程 ”。空 (1)是引出子查询的，该类连接词有： IN、 NOT IN、 EXISTS、 NOT EXISTS，EXISTS引出的子查询一般是 SELECT*型，故排除 IN型；再据语意分析应填NOT EXISTS。空 (2)同理得应填 NOT EXISTS。空 (3)是 “真正 ”的查询条件，该查询涉及到三个表 STUDENT、 COURSE
28、、 CS，故应填 STUDENT.SNO=SC.SNO ANDCOURSE.CNO=SC.CNO。 程序 5.2是给出全体学生人数，涉及集函数的应用。常用的集函数有：COUNT、 SUM、 AVG、 MAX、 MIN。在此用到 COUNT，故空 (4)应填COUNT(*)。 程序 5.3是按学号给出每个学生的平均成绩，同样是集函数， AVG的 应用。要注意的是需要同时给出学号，故空 (5)应填： SNO， AVG(GRADE)。 程序 5.4是按学号给出每个学生选修课程的门数，属 COUNT的用法，并注意同时给出学号。故空 (6)应填： SNO， COUNT(CNO)。 10 【正确答案】 C
29、- head： =Pc 11 【正确答案】 pC- next： =C- head 12 【正确答案】 tp： =NULL 13 【正确答案】 t： NULL 14 【正确答案】 t： =NULL 【试题解析】 该流程图是用于将 pC(Node结构体指 针 )节点按指数降序插入到多项式 C(多项式 POLY指针 )中。需要特别注意特殊情况： C为空多项式，即插入第一项时的处理；当 pC的指数比 C中的最大指数还大时的处理；当 pC的指数与 C中某项的指数相同时，进行系数相加，若相加后为 0时的处理。 根据结构体 POLY的声明，可知 C- head为 NULL意味着多项式为空，将 pC作为第一项
30、插入，故空 (1)应填 C- head： =pC。 pC- e C- head- e意味着 pC的指数比 C中的最大指数还大，此时应将将pC作为第一项插入，处理方式同上，故空 (2)应填 pC- next： =C- head。 先分析空 (4)，控制流可以从两条路到达空 (4)处，一是 t=NULL(到了多项式 C的末尾 )，亦即 pC的指数比 C中最小的还小，此时须将 pC插入到末尾；一是 t- e=： pC- e(找到同指数项，进行合并 )，显然 t!=NULL，此时不必在作任何操作。因此可通过判断 t是否为 NULL区分这两种情况，故空 (4)处应填 t： NULL。 要将 pC插入到末
31、尾，此时 t=NULL，因此须正确记录其前驱方可插入 (单链表 )，注意到空 (4)分支 t=NULL时的处理用到 tp，易于判断 tp正是用来记录前驱的。亦可 at- e pC- e时的处理： tp： =t、 t： =t- next得到验证。纵观流程，tp没有赋初值，这样，空 (3)处就应该是对其赋初值，故应填 tp： =NULL。 再来看空 (5)，此时是 t- e pC- e，注意到 C是降序排序 (对指数而言 )的，也就是说 t以前 (不包括 t)的指数均大于 pC，以后 (包括 t)的均小于 pC，这样 pC就应该插在 t以前 (据上述分析，亦即 tp以后 )。而 (5)后的控制流是
32、回到判断 t：NULL，因此，此处应填 t： =NULL。这样，就可将 pC正确的插入 tp之后， t之前，这个工作由空 (4)的分支 t=NULL完成。 15 【正确答案】 P!=NULL 16 【正确答案】 q- next=stop 17 【正确答案】 p- lChild 18 【正确答案】 stop=stop- next 19 【正确答案】 q- elem- rChild 【试题解析】 本题考察的是二叉树的遍历以及链栈的使用。 由注释可知，空 (1)是 “不是空树 ”的条件，应填 P!=NULL。 空 (2)是链栈入栈操作， stop是指向链栈栈顶的指针，故空 (2)应填 q-next=
33、stop。 空 (3)进入根的左子树，故应填 P- lChild。 空 (4)是链栈出栈操作， stop是指向链栈栈顶的指针，出栈后，应修改栈顶指针，故应填 stop=stop- next。 空 (5)是进入右子树，要注意的是，此处是通过链栈节点 q进行访问，不能想当然的认为是 q- rChild，而应该是 q- elem- rChild。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 20 【正确答 案】 pGraph- n-1 21 【正确答案】 mstj.weight 22 【正确答案】 mst
34、i.StopVex 23 【正确答案】 vy vx 24 【正确答案】 pGraph- arcsk 【试题解析】 由注释 “n-1条边 ”可得， (1)处应为 pGraph- n-1。 空 (2)有关程序段是选出权值最小的边， minWeight 表示的是最小权值，因此空 (2)应填 mstj.weight。 “vx为刚加入最小生成树的顶点下标 ”，因此空 (3)应填 msti.StopVex。 邻接矩阵是压缩存储的，只存储上三角阵，因此下标需要进行转换。比较 if及else块，可发现两算式区别在于 vx、 vy互换，由邻接矩阵的对称性可得空 (4)处应填 vy vx。 空 (5)相关程序段是
35、进行调整，应填 pGraph- arcsk。 25 【正确答案】 virtual 26 【正确答案】 new XXCircle 27 【正确答案】 displayIt() 28 【正确答案】 Shape* 29 【正确答案】 getShapeInstance(type) 【试题解析】 由 “=0”可轻易判知 display()函数是一个纯虚函数，因此空 (1)应填virtual。 由题设， Circle实例化时，须先实例化一个 XXCircle对象，而 pxc正好也是XXCircle对象指针，故空 (2)应填 new XXCircle。 Circle在此充当适配器的角色，它所做的就是将消息转发
36、给 XXCircle实例，display()是 “显示 ”消息，故调用 XXCircle的相应方法，故空 (3)应填 displayIt()。 方法 getShapelnstance(int type)的返回值有 new Line、 new Square以及 new Circle，参照类的层次结构，可得空 (4)应填 Shape*。注意是指针。 Factory类仅定义了一个方法 getShapeInstance，而此处语义正是取得一个形状进行显示，故空 (5)应填 getShapeInstance(type)。 30 【正确答案】 abstract 31 【正确答案】 implements 3
37、2 【正确答案】 new XXCircle() 33 【正确答案】 Shape 34 【正确答案】 getShapeInstance(type) 【试题解析】 Shape是接口，其中的方法都是抽象方法，故空 (1)应填 abstract。 shape是接口，故空 (2)应填 implements，表示实现某个接口。 初始化一个 XXCircle实例，空 (3)应填 new XXCircle()。 方法 getShapeInstance(int type)的返回值有 new Line()、 new Square()以及 new Circle()，参照类的层次结构，可得空 (4)应填 Shape。 Factory类仅定义了一个方法 getShapelnstance，而此处语义正是取得一个形状进行显示，故空 (5)应填 getShapelnstance(type)。
