1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 58及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和数据流图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。【说明】下面给出的是某房产管理系统的一套分层数据流图。其功能描述如下： (1)系统随时根据住房送来的入住单更新住户基本信息文件； (2)每月初系统根据物业管理委员会提供的月附加费 (例如清洁费、保安费、大楼管理费等 )表和房租调整表，计算每家住户的月租费 (包括月附加费 )，向住户发出交费通知单。住户交费时，系统输入交费凭证 ，核对后输出收据给住户； (3)系统定期向物业管理委员会提供住房分配
2、表和交费情况表； (4)住户因分户或换房，在更新住户基本信息文件的同时，系统应立即对这些住户做月租费计算，以了结分户或换房前的房租。以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图 11是顶层数据流图，图 1一 2是第 0层数据流图，图 13是第1层数据流图，其中 A是加工 1的细化图， B是加工 2的细化图。假定题中提供的顶层图是正确的，请回答下列问题。【图 1一 1】【图 12】【图 13】1 指出图 1一 2中的哪些文件可不必画出。 2 指出在哪些图中遗漏了哪些数据流。回答时请用如下形式之一： 1)图中遗漏了 加工 (或文件 )流向 加工 (或文件
3、 )的 数据流； 2)图中加工 遗漏了输入 (或输出 )数据流 。 3 指出图 1一 3的 B中加工 2 3能检查出哪些不合格交费凭证。 3 阅读下列说明和 ER图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。【说明】建立一个供应商零件数据库，数据库要满足如下要求： (1)供应商代码不能为空，且是值唯一的，供应商的名也是唯一的。 (2)零件号不能为空，且值是唯一的，零件号不能为空。 (3)一个供应商可以供应多个零件，而一个零件可以由多个供应商供应。图 21是该系统的 ER图。【图 21】4 根据 ER图中给出的词汇，按照 “有关模式名 (属性，属性， )” 的格式，将此ER图转换为 3
4、个关系模式，指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。 5 创建 S表时， SNo使用 CHAR(5)并且唯一， SName使用 CHAR(30)， Status使用CHAR(8)， City使用 CHAR(20)。请在下列用于创建表 S的 SQL语句空缺处填入正确的 内容。 CREATE TABLE S(SN()CHAR(5)， SName CHAR(30)， Status CHAR(8)， City CHAR(20)， (1)； 6 假定 SP表存储供应情况，如下的 SQL语句是用于查询 “产地为 Beijing、零件号为 P101的零件的所供应的总数 (包括所有
5、供应商 )”的不完整语句，请在空缺处填入正确的内容。 SELECT SUM(Qty) FROM Sp WHERE pN0=“P101” (1)PNo(2) (SELECT PNo FROM(3) wHERE city=“Beij ing”) (4)PNc); 7 阅读以下说明和程序流程图，将应填入 (n)处的字句写在答题纸对应栏内。 【说明】 假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数 m表示为： m=ak10k-2+ak一 110k-3+a310+a2 其中a1保存该长整数的位数， a0保存该长整数的符号： 0表示正数、 1表示负数。注：数组下标从
6、0开始。流程图 (图 3一 1)用于计算长整数的加 (减 )法。运算时先决定符号，再进行绝对值运算。对于绝对值相减情况，总是绝对值较大的减去绝对值较小的，以避免出现不够减情况。注，此处不考虑溢出情况，即数组足够大。这样在程序中引进两个指针 pA和 pB，分别指向绝对值较大者和较小者。而对绝对值相加情况，让 pA指向 LA， pB指向 LB，不区分绝对值大小。 pApB可用通式pA+tlag*pB来计算， flag为 +1时即对应 pA+pB， flag为一 1时即对应 pApB。需特别注意的是，对丁相减，不够减时要进行借位，而当最高位借位 后正好为 0时，结果的总位数应减 1；对于加法，有最高
7、进位时，结果的总位数应加 1。流程图中涉及的函数说明如下： (1)cmp(int*LA， int*LB)函数，用于比较长整数 LA与 LB的绝对值大小，若 LA绝对值大于 LB绝对值则返回正值， LA绝对值小于 LB绝对值返回负值，相等则返回 0。 (2)max(int A， int B)函数，用于返回整数 A与 B中较大数。另外，对流程图中的写法进行约定： (1)“=”表示赋值， 如 “flag：=LA0+LB0”表示将 “LA0+LB0”的结果赋给 flag，相当于 C中 的赋值语句： “flag=LA0+LB0； ”； (2)“： ”表示比较运算，如 “flag： 1”表示 flag与
8、l比较。 8 阅读下列函数说明和 C代码，将应填入 (n)处的字句写在答题纸对应栏内。【说明】 Huffman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。构造最优二叉树的 Huffman算法如下： 根据给定的 n各权值 w1， w2， ， wn构成 n棵二叉树的集合 F=T1， T2， ， Tn，其中每棵树 Ti中只有一个带权为 wi的根节点，其左右子树均空。 在 F中选取两棵根节点的权值 较小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左右子树根节点的权值之和。 从 F中删除这两棵树，同时将新得到的二叉树加入到 F中。重复 ，直到 F中只剩一
9、棵树为止。函数中使用的预定义符号如下： #detineINTMAX 10000#define ENCODINGLENGTH 1000typedef enum(rlone， 1eft一 child， right一 child) which； *标记是左孩子还是右孩子 * typedef char Elemtype； typedef struct TNode Huffman树节点 Elemtype letter； int weight； 权值 int parent； 父节点 Which Sigh； char*code; 节点对应编码 )HTNode，*HuffmanTree； int n； cha
10、r coding50;储存代码【函数】 void Select(HuffmanTree HT， int end， int*s1， int*s2) *在 0 END之问，找出最小和次小的两个节点序号，返回 s1、 s2* int i;int mini=INT_MAX;int min2=INT_MAX； for(i=0； iHTi weight)*S2： i；min2=HTi weight： void HuffmanTreecrea七 (HuffmanTreeint m=2*n一 1； int S1， S2； for(i=n;i 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选
11、 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 9 阅读下列函数说明和 C代码，将应填入 (n)处的字句写在答题纸对应栏内。【说明】若要在 N个城市之间建立通信网络，只需要 N1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在 8个城市间建立通信网络，其问拓扑结构如图 51所示，边表示城市间通信线路，边上标示的是建立该线路的代价。【图 5一 1】无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵足对称的且对角线上元素均为 0，故压缩存储，只存储上三角元素 (不包括对角线 )。现用 Prim算法生成网络的最小生成树。由网络 G=(V
12、， E)构造最小生成树 T=(U,TE)的 Prim算 法的基本思想是：首先从集合 V中任取一顶点放入集合 U中，然后把所有一个顶点在集合 U里、另一个顶点在集合 VU里的边中，找出权值最小的边 (u， v)，将边加入 TE，并将顶点 v加入集合 U，重复上述操作直到 U=V为止。函数中使用的预定义符号如下： define MAX 32768 *无穷大权，表示顶点问不连通 * #define MAXVEx 3 0 *图中顶点数目的最大值 * typedef struct int startVex， stopVex； *边的起点和终点 * float weight； *边的 权 * Edge；
13、typedef struct char vexs MAXVExj *顶点信息 * float arcsMAXVEx*(MAXVEx一 1) 2； *邻接矩阵信息，压缩存储 * int n； *图的顶点个数 * )Graph； 【函数】 void primMST(Graph*pGraph， Edge mst) int i， j,k,min,vx,vy： float weight，minWeight； Edge edge； for(i=0； in一 1； i+) msti StartVex=0； msti StopVex=i+1； msti weight=pGraph一 arcsi； for(i=
14、0 ; in*vyvy*(vy+1) 2+VXvy一 1； )e1Se k=pGraph一 n*vxvx*(VX+1) 2+vyvx一 1； weight= (5)； if(weight 10 阅读以下说明和 C+代码，将应填入 (n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一个 Shape类 (接口 )，有方法显示 display()。需要新增图形 Circle，又已知有类 XXCircle实现了所需要实现的功能：显示 displaylt()。为 了继承自 Shape以提供统一接口，又不希望从头开发代码，希望使用 XXCir
15、cle。这样将 XXCircle作为 Circle的一个属性，即 Circle的对象包含一个 XXCircle对象。当一个 Circle对象被实例化时，它必须实例化一个相应的 XXCircle对象；当 Circle对象收到的做任何事的请求都将转发给这个 XXCircle对象。通过这种称 Adapter模式， Circle对象就可以通过 “让XXCircle做实际工作 ”来表现自己的行为了。图 6-1显示了各个类间的关系。以下是 C+语言实现，能够正确编译通过 。【图 6一 1】【 C+代码】 ClasS Shapepublic： (1) void display()=0； ； class Li
16、ne： publ ic Shape(省略具体实现 ； class Square： public Shape省略具体实现 ； ClasS XXCircle(public： void displayIt()(省略具体实现 省略其余方法和属性 ；Class Circle： publ iC Shape(private： XXCircle*pxc;public： Circle()； void display()； ； Circle： Circle()(pxc=(2)； VOid Circle： display()pxc一 (3)； Class Factorypublic： (4)getShapeInst
17、ance(int type)生成特定类实例switch(type)(case 1： return new Square； case 2： return new Line； case 3： returrl flew C1rcle； default： return NULL； ； void main(int argc， charargv)i f(argc!=2)toutdisplay()； delete s； rettlrn； 11 阅读以下函数说明和 JaVa代码，将应填入 (n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线 Line、矩形 Square，抽象出一+Sh
18、ape类 (接口 )，有方法显示 display()。需要新增图形 Circle，又已知有类XXCircle实现了所需要实现的功能：显示 displayIt()。为了继承自 Shape以提供统一接口，又不希望从头开发代码，希望使用 xxCircle。这样将 XxCircle作为 Circle的一个属性，即 Circle的对象包含一个 xxCircle对象。当一个 Circle对象被实例化时，它必须实例化一个相应的 XXCnle对象；当 Circle对象收到的做任何事的请求都将转发给这个 xXCircle对象。通过这种称为 Adapter模式， Circle对象就可以通过 “让 xxcircle
19、做实际工作 ”，来表现自己的行为了。图 7 1显示了各个类间的关系。以下是 JAVA语言实现，能够正确编译通过。【图 7一 1】Java代码】 Shape Java文件 public interface Shape public(1)void display()； xXCircle Java文件 public class XXCircle public void displayIt() 省略具体实现 Circle Java文件 public class Circle (2) Shape private XXCircle pcx=(3)； public void display()( pcx d
20、isplayIt(); Factory Java文件 pubic class Factory publ ic (4) getShapeInstance(int type) switch(type) case 1： return new Line(); 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=
21、new Factory(); Shape s； S=factory (5)； if(S=null) System out printin(”Error get the instance!”)； return； S display(); return； 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 58答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 “房租文件 ”和 “交费文件 ” 【试题解析】 分层数据流图中，只涉及单个加工的文件不必画出，可在子图中再画。依此标准，图 1一 2中文件 “房租文件 ”和 “交费文件 ”不必画出。 2 【正确答案】 加工
22、1子图中，遗漏了从住户基本信息文件到加工 1 1(入住单校验 )的数据流。 加工 1子图中，加工 1 6(制作住房分配报告 )遗漏了输出数据流：住房分配表。 加工 2子图中，加工 2 1(计算月租费 )遗漏了输入数据流：月附加费表。 加工 2子图中，加工 2 4(制作收据 )遗漏了输出数据流：收据。 【试题解析】 分层数据流图时刻牢记父图与子图平衡原则。对这种数据流缺失题目，认真对照父图与子图就可得出答案。另外，还要注意与文件的交互，包括错误数据流大多也是出在此。 3 【正确答案】 交费凭证中有 非法字符； 交费文件中不存在与之对应的交费凭证。 4 【正确答案】 S(Sno， Sname， S
23、tatus， City)，主键为 SNo。 P(PNo， PName， Color， Weight， City)，主键为 PNo。 SP(SNo， PNo， Status， Qty)，主键为 (SNo， PNo)。 【试题解析】 ER模型向关系模型的转换应遵循如下原则： 每个实体类型转换成一个关系模式。 一个 1： 1的联系 (一对一联系 )可转换为一个关系模式，或与任意一段的关系模式合并。 一个 1： n的联系 (一对多联系 )可转换为一个 关系模式，或与 n端的关系模式合并。 一个 n： m的联系 (多对多联系 )可转换为一个关系模式，两端关系的码及其联系的属性为该关系的属性，而关系的码为
24、两端实体的码的组合。 三个或三个以上多对多的联系可转换为一个关系模式，诸关系的码及联系的属性为关系的属性，而关系的码为各实体的码的组合。具有相同码的关系可以合并。根据题述易于判断供应商的主键为供应商编号 sNo，零件的主键为零件编号PNo。 5 【正确答案】 (1)PRIMARYKEYSNo 【试题解析】 创建表时往往需要声明主键、外键、非空、唯一等完整性约束 条件，表 S中， sNo是主键，声明主键有两种实现手法： PRIMARYKEY(sNO)，或者 NOTNuLL、 UNIQUE，不同的是 NOTNULL是列级约束，必须在列名之后声明，而 PRIMARYKEY是表级约束。创建表的完整 S
25、QL语句如下：CREATETABLE(列级完整性约束条件 ， 列级完整性约束条件 .， )列级完整性约束条件有： NULL(空 )、 UNIQUE(取值唯一 )。 PRIMARYKEY(属性或属性组 )申明主码，FOREIGNKEY(属性或属性组 )申明外码。故空 (1)应填 PRIMARYKEYSNo。 6 【正确答案】 (1)AND(2)IN(3)P(4)GROUPBY 【试题解析】 查询 “产地为 Beijing、零件号为 P101的零件的所供应的总数 (包括所有供应商 )”是一个集函数查询，具体是求和 suM，往往搭配 GR0uPBY；查询条件有两个：产地是 Beijing、零件号足
26、P101；这样涉及到的表有： SP、 P。空 (1)是连接两个查询条件的，在此两个条件是 “并 R ”关系，故空 (1)应填 AND，空 (4)应填 GROUPBY。空 (2)引出的是一个子查询，可选的有： IN NOTIN、 EXISFS NOTEXISTS，首先排除： EXISTS NOTEXISTS，根据语义，子查询是 “产地为 Beijfing的零件号 ”，故空 (2)应填 IN。 包含产地和零件号属性的表自然是零件表 P，故空 (3)应填 P。 7 【正确答案】 (1)flag： =1 (2)carry： =0 (3)carry： 0 (4)LCi+1： 0 (5)LCi+2： 0
27、【试题解析】 对这种题目，首先阅读说明，从功能上了解程序的结构，把握整体框架，冉仔细 对照阅读流程图，且勿先阅读流程图。仔细阅读完说明，就知道整体框架了：先决定符号，冉进行绝对值的加减，其中加减是用， flag来标识的。对于加法，要注意进位，特别是最高进位；对于减法，要注意借位，亦即负进位，在此不用考虑不够减情况，但仍要特别注意最高借位，当最高位正好为 O时，要把高位所有的 0去掉。空 (1)很容易就得到答案，应为 flag： =1。空 (2)以下就开始绝对值的加减了。此时 PA、 PB已正确赋值。在计算过程中，进位是需要特别注意的，从下面的流程可知， carry表示的就是进位，需进行初始化，
28、故空 (2)应填carry； =0。空 (3)以下是 i=N的情况，即对于计算结束，进行后期处理，此时就要考虑最高进位的问题。可得空 (3)应填 carry： 0，即判断最高进位是否为 0(对减法为负进位 )。空 (4)是删除高位的，故应填 LCi+1： 0。空 (5)处是具体进行加减法运算的。空 (5)处的条件主要是针对减法的，当不够减时需要借位，故空 (5)应填LCi+2： 0。 8 【正确答案】 (1)HTi parent=0 (2)*s1！ =i (3)HT， i1， &s1， &s2 (4)HTs1 weight+HTIs2 weight (5)HTj code 【试题解析】 根据算
29、法说明的 可知是根据根节点权值选择，即只考察根节点，而根节点对应 parent等于 0，故空 (1)应填 HTi parent=0。此答案可由空 (2)处的 i涤件容易得出。至于空 (2)，此处是找次小的，自然需要排除最小的， S1记录了最小树的下标，故填 *s1!=i。仔细参照 Select数的定义，容易得出空 (3)答案。应填 “HT， il， &sl， &s2”，要注意的是后两个参数需要传递地址，因形参是指针。根据算法说明的 ， “置新构造二叉树的根节点的 权值为其左右子树根节点的权值之和 ”，而此处 HTi的左右子树的根节点分别为 HTs1和 NHTs2，所以空(4)应填 HTs1 w
30、eight+HTs2 weight。由注释 “字母匹配则用代码取代 ”可知，此处是将对应代码加到 coding中，而节点的 code字段存储了节点对应编码，故空(5)应填 HTj code。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 9 【正确答案】 (1)pGraph一 111 (2)mstj weight (3)resti StopVex (4)vyarcsk 【试题解析】 由注释 “n一 1条边 ”可得， (1)处应为 pGraph一 n1。空 (2)有关程序段是选出权值最小的边， minW
31、eight表示的是最小权值，因此空 (2)应填mstj weight。 “vx为刚加入最小生成树的顶点下标 ”，因此空 (3)应填msti StopVex。邻接矩阵是压缩存储的，只存储上三角阵，因此下标需要进行转换。比较 if及 else块，可发现两算式 区别在于 vx、 vy互换，由邻接矩阵的对称性可得空 (4)处应填 vyarcsk。 10 【正确答案】 (1)virtual (2)new XXCircle (3)displayIt() (4)Shape*： (5)getShapeInstance(type) 【试题解析】 由 “=0”可轻易判知 display()函数是一个纯虚函数，因此
32、空 (1)应填virtual。由题设， Circle实例化时，须先实例化一个 XXCircle对象，而 pxciE好也是 XXCircle对象指针，故空 (2)应填 new XXCircle。 Circle在此充当适配器的角色，它所做的就是将消息转发给 XXCircle实例， display()是 “显示 ”消息，故调用XXCircle的相应方法，故空 (3)应填 displayIt()。方法 getShapeInstance(1int type)的返回值有 new Line、 new Square以及 new circle，参照类的层次结构，可得空 (4)应填 Shape*。注意是指针。 F
33、actory类仅定义了一个方法 getShapeInstance，而此处语义正是取得一个形状进行显示，故空 (5)应填 getShapeInstance(type)。 11 【正确答案】 (1)abstract (2)implements (3)new XXCircle() (4)Shape (5)getShape!nstance(type) 【试题解析】 Shape是接口，其中的方法都是抽象方法，故空 (1)应填 abstract。Shape是接口，故空 (2)应填 i lplements，表示实现某个接口。初始化一个XXCircle实例，空 (3)应填 new xXCircle()。方法 getShapeInstance(int type)的返回值有 new Line()、 new Square()以及 new Circle()，参照类的层次结构，可得空 (4)应填 Shape。 Factory类仅定义了一个方法 getShapeInstance，而此处语义正是取得一个形状进行显示，故空 (5)应填 getShapeInstance(type)。
