1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 60及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。【说明】某汽车数字仪表系统将完成下述功能： (1)通过模数转换，实现传感器和微处理器的接口。 (2)在发光二极管面板上显示数据。 (3)指示速度 (mph)、行驶里程、油耗 (mpg)等。 (4)指示加速或减速。以下是经分析得到的数据流图，有些地方有待填充，假定顶层数据流图是正确的。图 1一 1是顶层数据流图，图 1 2是第 0层数据流 图，图 1 3是第 1层数据流图，其中 A是加工 1的细化图，
2、 B是加工 2的细化图。图中， sps表示转速 sps的瞬时变化值，若 sps0则汽车加速， sps 【图 1-2】 【图 1-3】1 第 0层数据流图 (图 1-2)中有一条缺失的数据流，请指出该数据流的起点和终点。 加工 1的细化图 (图 1一 3中的 A)中有一条缺失的数据流，请指出该数据流的起点和终点。 2 加工 2的细化图 (图 13中的 B)中有一条错误的数据流，请指出该数据流的起点或终点 (若可以，指出两者 )。 3 小说明是用来描述加工的。小说明的描述方法 有哪些 ?请分别用这些描述方法描述加工 1 2。 4 阅读下列说明和 ER图，回答问题 1至问题 3，将解答填入答题纸的对
3、应栏内。【说明】设有下列关于学生成绩管理系统的 E-R图 (见图 21)。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体间的联系。假定已通过下列 SQL语言建立了基本表： CREATE TABLE STUDENT (SNo CHAR(6) NOT NULL UN工 QUE， SName CHAR(20)， Sex CHAR(1)， DeptCHAR(20)， Age SMALLINT)； CREATE TABLE COURSE (CN0 CHAR(6) NOT NULL UN工QUE， CName CHAR(20)， Hour SMALL工 NT， Credi七 SMALL工
4、NT)；CREATE TABLE SC (SN0 CHAR(6)， CNo CHAR(6)， GRADE SMALL工 NT， PRIMARY KEY (SNo， CNo)；为了答题的方便，图中的实体和属性同时给出了中英文两种名字，回答问题时只须写出英文名即可。【问题】填充下列 SQL程序5 1 5 4中的 (1) (6)，使它们 分别完成以下查询功能：程序 5 1：检索选修所有课程的学生姓名。程序 5 2：给出全体学生人数。程序 5 3：按学号给出每个学生的平均成绩。程序 5 4：按学号给出每个学生选修课程的门数。【程序5 1】 SELECT SName FROM STUDENT wHERE
5、 (1) (SELECT*FROM COURSE WHERE (2)(SELECT* FROMSC WHERE (3) )【程序 5 2】 SELECT (4) FROMSTuDENT 【程序 5 3】 SELEcT (5) FROMSC GR0uP BYSN0 【程序5 4】 SELECT (6) FRoMSC GROup BYSNO 5 阅读以下说明和程序流程图，将应填入 (n)处的字句写在答题纸对应栏内。 【说明】当一元多项式 中有许多系数为零时，可用一个单链表来存储，每个节点存储一个非零项的指数和对应系数。为了便于进行运算，用带头节点的单链表存储，头节点中存储多项式中的非零项数，且各节
6、点按指数递减顺序存储。例如：多项式 8x5一 2x2+7的存储结构为：流程图图 3一 1用于将 pc(Node结构体指针 )节点按指数降序插入到多项式 c(多项式 POLY指针 )中。流程 图中使用的符号说明如下： (1)数据结构定义如下： #define EpSI le一 6 structNode( *多项式中的一项 * d。 uble c; *系数 * int e; *指数* struct Node *next： ； typedef struct *多项式头节点 * Int n； *多项式不为零的项数 * struct N0de *head： POLY;(2)Del(POLY*C， stm
7、ct Node*p)函数，若 p是空指针则删除头节点，否则删除 p节点的后继。 (3)fabs(double c)函数返回实数 c的绝对值。【图 31】6 阅读下列说明和 C程序，将应填入 (n)处的字句写在答题纸对应栏内。 【说明】 借助一个栈结构，可实现二叉树的非递归遍历算法。 InOrderTraverse函数实现中序非递归遍历，遍历过程如下：若不是空树，根节点入栈，进入左子树；若已经是空树，则栈顶元素出栈，访问该元素 (根节点 )，进入该节点的右子树，继续直到遍历完成。函数中使用的预定义符号如下： typedef struct BiTNode int data； struct BiTN
8、ode*lChild， *rChild； BiTNode， *BiTree； typedef struct sNode( *链栈的节点类型 * BiTree elem； struct SN0de *next； SNode； 【函数】 int InorderTraverse(BiTree root) BiTree p； sNode*q， *stop=NuLL； *不带头节点的单链表作为栈的存储结构 * p=root； while(p!=NULL stop !=NULL) if(1) *不是空树 * q= (SNode*)malloc(sizeof q); if(q=NULL)return一 1；
9、 *根节点指针入栈 * (2)； q一 elem=p； stop=q； p= (3)； *进入根的左子树 * )else( q=Stop； (4)； *栈顶元素出栈 * printf(“ d”， q一 elem一 data)； *访问根节点 * p= (5)； *进入根的右子树 * free(q)； *释放原栈项元素 * /if* ) *while* return0； *InOrderTraverse* 从下列的 3道试题 (试题五至试题七 )中任选 1道解答。如果解答的试题数超过 1道，则题号小的 l道解答有效。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答
10、，如果解答的 试题数超过 1道，则仅题号小的 1道题解答有效。 7 阅读下列函数说明和 C代码，将应填入 (n)处的字句写在答题纸对应栏内。 【说明】 所谓货郎担问题，是指给定一个无向图，并己知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度 (作为边的权值 )，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。 函数中使用的预定义符号如下： #defineM100 typedefstruct *x为两端点 p1、 p2之问的距
11、离， p1、 p2所组成边的长度 * floatX； intp1， p2； tdr； typedefstruct( *pl、 p2为和端点相联系的两个端点， n为端点的度 * intn， p1， p2； tr； typedefstruct *给出两点坐标 * floatX， Y； tpd; typedefintt1M； intn=10； 【函数】 floatdistance(tpda， tpdb)； *计算端点 a、 b之间的距离 * voidsortArr(tdraM， intm)； *将已经计算好的距离关系表按距离大小从小到大排序形成排序表， m为边的条数 * intisCircuit(t
12、rrM， inti， intj)； *判断边 (i， j)选入端点关系表 rM后，是否形成回路，若形成同路返回 0* voidselected(trrM， inti， intJ)； *边 (i， j)选入端点关系表 r* voidc。 urse(trrM， t1lM)； *从端点关系表 r中得出回路轨迹表 * voidexchange(tdraM， intm， intb)； *调整表排序表， b表示是否可调，即是否有长度相同的边存在 * voidtravling(tpdpdM， intII， floatdist， t1locusM) *dist ff录总路程 * tdrdrM； *距离关系表
13、* trrM； *端点关系表 * inti， j， k， h， m； *h表示选入端点关系表中的边数 * intb； *标识足否有长度相等的边 * k=0； *计算距离关系表中各边的长度 * for(i=1； i， 1. FROM， WHERE GROUPBYHAVING ORDERBYASC1DESC. 子句顺序为 SELECT、 FROM、 WHERE、 GROUPBY、 HAVING、ORDERBY，但 SELECT和 FROM是必须的， HAVING子句只能与 GROUPBY搭配起来使用。该成绩管理系统的关系模式有： STUDENT(SNo， SName， Sex，Dept， Age)
14、，主键为 SNo， COURSE(CNo， CName， Hour， Credit)，主键为CNo， SC(SNO， CNO， GRADE)，主键为 (Sno， CNo)。程序 5 1是检索选修所有课程的学生姓名，亦即 “不存在没有选修的谋程 ”。空 (1)是引出子查询的，该类连接浏有： IN、 NOTIN、 EXISTS、 NOTEXISTS， EXISTSJI出的子查询一般是SELECT*型，故排除 IN型；再据语意分析应填 NOTEXISTS。空 (2)同理得应填NOTEXISTS。空 (3)是 “真正 ”的查询条件，该查询涉及剑三个表 STUDENT、COURSE、 CS，故应填 ST
15、UDENT SNO=SC SNOANDCOURSE CNO=SCCNO。程序 5 2是给出全体学生人数，涉及集函数的应用。常用的集函数有： COUNT、 SUM、 AVG、 MAX、 MIN。存此用到CoUNT，故空 (4)虑填 COUNT(*)。程序 5 3是按学号给出每个学生的平均成绩，同样是集函数， AVG的应用。要注意的是需要同时给出学号，故空 (5)应填：SNO， AVG(GRADE)。程序 5 4是按学号给出每个学生选修课程的门数，属COUNT的用法，并注意同时给出学号。故空 (6)应填： SNO， COUNT(CNO)。 5 【正确答案】 (1)C一 head： =pC (2)p
16、C一 next： =C一 head (3)tp： =NULL (4)t： NULL (5)t： =NULL 【试题解析】 该流程图是用于将 pC(Node结构体指针 )节点按指数 降序插入到多项式 C(多项式 POLY指针 )中。需要特别注意特殊情况： C为空多项式，即插入第一项时的处理；当 pc的指数比 C中的最大指数还大时的处理：当 DC的指数与 C中某项的指数相同时，进行系数相加，若相加后为 0时的处理。根据结构体POLY的声明，可知 C一 head为 NULL意味着多项式为空，将 pC作为第一项插入，故空 (1)应填 C一 head： =pC。 pC一 eC一 head一 e意味着 p
17、C的指数比 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插入到末尾，此时 t=NULL，因此须正确记录其前驱方可插入 (单链表 )，注意到空 (4)分支 t=NUL
18、L时的处理用 lJtp，易于判断 tp正是用来记录前驱的。亦可由 t一 epC一 e时的处理： tp： =t、 t： =t一 next得到验证。纵观流程， tp没有赋初值，这样，空 (3)处就应该是对其赋初值，故应填 tp： =NULL。再来看空 (5)，此时是 t一 ee，注意 Nc是降序排序 (对指数而言 )的，也就是说 t以前 (不包括 t)的指数均大于 pC，以后 (包括 t)的均小于 pC，这样 pC就应该插在 t以前 (据上述分析，亦即 tp以后 )。而 (5)后的控制流是回到判断 t： NULL，因此，此处应填 t： =NULL。这样，就可将 pC正确的插入 tp之后， t之前，
19、这个工作由空 (4)的分支 t=NULL完成。 6 【正确答案】 (1)P!=NULL (2)q-next=stop (3)p-lChild (4)stop=stop一 next (5)q-elem一 rChild 【试题解析】 本题考察的是二叉树的遍历以及链栈的使用。由注释可知，空 (1)是 “不是空树 ”的条件，应填 P!=NULL。空 (2)是链栈入栈操作， stop是指向链栈栈顶的指针，故空 (2)应填 q一 next=stop。空 (3)进入根的左子树，故应填 P一 lChild。空 (4)是链栈出栈操作， stop是指向链栈栈顶的指针，出栈后，应修改栈顶指 针，故应填 stop=s
20、top一 next。空 (5)是进入右子树，要注意的是，此处是通过链栈节点 q进行访问，不能想当然的认为是 q一 rChild，而应该是 q一 elem一 rChild。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 7 【正确答案】 (1)distance(pdi， pdj) (2)!isCircuit(r， i， j) (3)selected(r， i， j) (4)h=n1 (5)exchange(dr， m， b) 【试题解析】 本题主要是函数调用的问题。空 (1)是计算各边的长度，根据函数的
21、声明及说明，可得应填 distance(pdi,pdj)。由注释可见空 (2)是判断边 (i， j)加入 r后是否形成回路，若形成了回路，不加入，由语句 “dist+=drk x； ”可知此处是将边加入，故此处应该是不形成回路条件。参照 isCircuit函数声明及说明可知，若形成回路返回 0，故空 (2)填！ isCircuit（ r,i， j）。空 (3)是将边 (i， j)加入到r中，参照 selected函数声明及说明可得空 (3)填 selectde(r,i,j)。由注释可见空 (4)是最后一条边条件，变量 h表示的是 “选入端点关系表中的边数 ”，而 n个节点回路 应该包含 n条边
22、，这点也可从后面 h=n输出解看出，故空 (4)填 h=n-1。空 (5)是进行调整，调 mexchangeiN数，正确调用形式为 exchange(dr,m,b)。 8 【正确答案】 (1)virtual (2)DP2： drawline(x1， x2， y1， y2) (3)Drawing (4)_dp-drawLine(x1， y1， x2， y2) (5)Shape(dp) 【试题解析】 由函数 drawLine0结尾的 “=0”易知，空 (1)应填 virtual。 空 (2)是调用 DP2系统的相应方法，可参照 DPI的对应函数的函数体，但要注意参数不完全相同，应填 DP2:dra
23、wline(x1， x2， y1， y2)。一 dpN性是用来存储Drawing对象的，参照 Shape的构造函数可确认这一点，空 (3)应填 Drawing*。Shape类 drawLine方法是通过调用 Drawing对的方法来实现所需要的功能，因此空 (4)应填 dp- drawLine(x1， y1， x2， y2)。空 (5)显然是基类构造函数，应填Shape(dp)。 9 【正确答案】 (1)abstract (2)DP2 drawline(x1， x2， y1， y2) (3)Drawing (4)_dp drawLine(x1， y1， x2， y2) (5)super(dp)
24、 【试题解析】 由类 Drawing的 drawLine()方法是 abstract的知， Drawing要么是接口，要么是抽象类，在此为抽象类，故空 (1)应填 abstract。空 (2)是调用 DP2系统的相应方法，可参加 ,DPI的对应函数的函数体，但 要注意参数不完全相同，应填 DP2.drawine(x1， x2， y1， y2)。一 dpN性是用来存储 Drawing对象的，参照Shape的构造函数可确认这一点，空 (3)应填 Drawing。 Shape类的 drawLine方法是通过调用 Drawing对应的方法来实现所需要的功能，因此空 (4)应填dp.drawine(x1， y1， x2， y2)。空 (5)显然是基类构造函数，应填 super(dp)。
