1、中级软件设计师下午试题-79 及答案解析(总分:105.00,做题时间:90 分钟)一、B试题一/B(总题数:1,分数:15.00)阅读下列说明和图,回答问题 1 至问题 3,将解答填入对应栏内。 说明 某汽车数字仪表系统将完成下述功能: (1)通过模一数转换,实现传感器和微处理器的接口。 (2)在发光二极管面板上显示数据。 (3)指示速度(mph)、行驶里程、油耗(mpg)等。 (4)指示加速或减速。 以下是经分析得到的数据流图,有些地方有待填充,假定顶层数据流图是正确的。图 1-1 是顶层数据流图,图 1-2 是第 0 层数据流图,图 1-3 是第 1 层数据流图,其中 A 是加工 1 的
2、细化图,B 是加工 2 的细化图。图中,sps 表示转速 sps 的瞬时变化值,若sps0 则汽车加速,sps0 则减速,sps=0 则匀速。假定题中提供的顶层图是正确的,请回答下列问题。图 1-1 图 1-2 图 1-3 (分数:15.00)(1).第 0 层数据流图(图 1-2)中有一条缺失的数据流,请指出该数据流的起点和终点。 加工 1 的细化图(图 1-3 中的 A)中有一条缺失的数据流,请指出该数据流的起点和终点。 (分数:5.00)_(2).加工 2 的细化图(图 1-3 中的 B)中有一条错误的数据流,请指出该数据流的起点或终点(若可以,指出两者)。 (分数:5.00)_(3).
3、小说明是用来描述加工的。小说明的描述方法有哪些?请分别用这些描述方法描述加工 1.2。 (分数:5.00)_二、B试题二/B(总题数:1,分数:15.00)阅读下列说明和 E-R 图,回答问题 1 至问题 3,将解答填入对应栏内。 说明 设有下列关于学生成绩管理系统的 E-R 图(见图 2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列 SQL 语言建立了基本表:(分数:15.00)(1).(分数:2.50)填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、B试题三/B(总题数:1,分数:15.00)阅读以下说明和程序流程图
4、,将应填入U (n) /U处的字句写在对应栏内。 说明 当一元多项式中有许多系数为零时,可用一个单链表来存储,每个节点存储一个非零项的指受和对应系数。为了便于进行运算,用带头节点的单链表存储,头节点中存储多项式中的非零项数,且各节点按指数递减顺序存储。例如:多项式 8x5-2x2+7 的存储结构为: 流程图图 3-1 用于将 pC(Node 结构体指针)节点按指数降序插入到多项式 C(多项式 POLY 指针)中。 流程图中使用的符号说明如下: (1)数据结构定义如下: #define EPSI 1e-6 struct Node /*多项式中的一项*/ double c; /*系数*/ int
5、e; /*指数*/ Struct Node *next; typedef struct /*多项式头节点*/ int n; /*多项式不为零的项数*/ struct Node *head; POLY; (2)Del(POLY *C,struct Node *p)函数,若 p 是空指针则删除头节点,否则删除 p 节点的后继。 (3)fabs(double c)函数返回实数 C 的绝对值。 图 3-1 (分数:15.00)(1).(分数:3.00)填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、B试题四/B(总题数:1,分数:15.00)阅读下列说明和 C 程序,将应填入U (n) /
6、U处的字句写在对应栏中。 说明 借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse 数实现中序非递归遍历,遍历过程如下: 若不是空树,根节点入栈,进入左子树;若已经是空树,则栈顶元素出栈,访问该元素(根节点),进入该节点的右子树,继续直到遍历完成。 函数中使用的预定义符号如下: typedef struct BiTNode int data; struct BiTNode *iChiid,*rChiid; BiTNode,*BiTree; typedef struct SNode/*链栈的节点类型*/ BiTree elem; struct SNode *next;
7、SNode; 函数 int InOrderTraverse(BiTree root) BiTree P; SNode *q,*stop=NULL;/*不带头节点的单链表作为栈的存储结构*/ P=root; while(p !=NULL | stop !=NULL) if(U (1) /U) /*不是空树*/ q=(SNode*)malloc(sizeof q); if(q=NULL)return-1; /*根节点指针入栈*/ U (2) /U; q-elem=P; stop=q; P=U (3) /U; /*进入根的左子树*/ else q=stop; U (4) /U; /*栈顶元素出栈*/
8、 printf(“%d|,q-elem-data); /*防问根节点*/ P=U (5) /U; /*进入根的右子树*/ free(q); /*释放原栈顶元素*/ /*if*/ /*while*/ return 0; /*InOrderTraverse*/ (分数:15.00)(1).(分数:3.00)填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、B试题五/B(总题数:1,分数:15.00)阅读下列函数说明和 C+代码,将应填入U (n) /U处的字句写在对应栏内。 说明 在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(包括不用的功能)都要全面
9、初始化的话,会导致应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。 以下示例展示了 Proxy(代理)模式,PrinterProxy 类执行一些比较“轻”的方法,需要真正执行“重”的方法时才初始化 Print 类。图 5-1 显示了各个类间的关系。 图 5-1 C+代码 class Printable public: virtual void setPrinterName(string name)=0; virtual string getprinterName()=0; virtual void print(string name)=0; ; cl
10、ass Printer:public Printable private: string name; public: Printer(string name) cout“正在产生 Printer 的对象实例“endl; thisname=name; void setPrinterName(string name) this-name=name; string getPrinterName() return name; void print(string msg) cout“=“name“=“endl; coutmsgendl; ; class printerproxy :publicU (1)
11、 /U private: String name; Printer *real; public: PrinterProxy(string name) U (2) /U=NULL; this-name=name; void setPrinterName(string name) if(U (3) /U)real-setPrinterName(name); this-name=name; string getPrinterName() return name; void print(string msg) U (4) /U; real-print(msg); void realize() if(r
12、eal=NULL)real=U (5) /U; ;(分数:15.00)(1).(分数:3.00)填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、B试题六/B(总题数:1,分数:15.00)阅读以下说明和 Java 代码,将应填入U (n) /U处的字句写在对应栏内。 说明 在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(连不用的功能)都要全面初始化的话,会连带影响到应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。 以下示例展示了 Proxy(代理)模式,PrinterProxy 类执行一些比较“轻”的方
13、法设置名称和取得名称,需要真正执行“重”的方法真正打印时才初始 Print 类。图 6-1 显示了各个类间的关系。 图 6-1 Java 代码 /Printable.Java publiCU (1) /UPrintable public abstract void setPrinterName(String name); public abstract String getprinterName(); public abstract void print(String string); /Printer.Java public class Printer implements Printabl
14、e private String name; public Printer() System.out.println(“正在产生 Printer 的对象实例“); public Printer(String name) this.name=name; heavyJob(“正在产生 Printer 的对象实例(“+name+“)“); public void setPrinterName(String name) this.name=name; public String getPrinterName() return name; public void print(String string)
15、 System.out.println(“=“ +name+“ =“); System.out.println(string); /PrinterProxy.Java public class PrinterProxyU (2) /UPrintable private String name; private Printer real; public PrinterProxy() public PrinterProxy(String name) this.name=name; public gynchronized void setPrinterName(String name) if(U (
16、3) /U) real.setPrinterName(name); this.name=name; public String getprinterName() return name; public void print(String string) U (4) /U; real.print(string); private synchronized void realize()/产生真正的 Printer 对象 if(real=null) real=U (5) /U; (分数:15.00)(1).(分数:3.00)填空项 1:_填空项 1:_填空项 1:_填空项 1:_七、B试题七/B(总
17、题数:1,分数:15.00)阅读以下说明和 C 代码,将应填入U (n) /U处的字句写在对应栏内。 说明 下面程序用来将打乱的单词还原为原来的次序,比如将 rty 还原为 try。单词的原来次序存储于wordlist.txt 文件中,原则上可用穷举法(rty 对应的穷举为:rty、ryt、try、tyr、ytr、yrt),但考虑到破译速度,采用如下方法。 注意到单词列表中不存在组成字符完全相同的单词(如 Hack12 与 Hack21 包含完全相同的字符),因此将单词中的字符进行重组再进行比较,例如,try 单词重组为 rty(按 ASC码顺序),这样不管打乱的单词是什么顺序,只要是由 r、
18、t、y 三个字母组成的均破译为 try,大大提高破译速度。程序中借助二叉排序树以进一步提高查找效率,二叉排序树左子树(如果有)上的节点对应的值均小于根节点的值,右子树(如果有)上的节点对应的值均大于根节点的值。 函数中使用的符号定义如下: #define NumberofWords 1275/单词总数 #define MaxLength 10/最长单词所含字符数 char WordListNumberofWordsMaxLength;/存储单词列表 int cmp(Node *q,Node *p);/q 与 p 比较。p 小,返回负值;P 大返回正值:相等,返回 0 typedef struc
19、t Node(/二叉树节点 char *eleLetters;/重组后的字符串 int index;/对应单词表中的下标 struct Node *lChiId,*rChiid;/左右子节点 Node; C 代码 void reCompose(Node *p,char *temp) /重纰,亦即将 temp 字符串中的字符升序排序,存储于 p 节点中 /采用直接插入排序法 char c; strcpy(p-eleLetters,temp);/ int len=strlen(temp); int i,j,k; for(i=0;ilen1;i+) k=i; for(j=i+1;jlan;j+) i
20、f(p-eleLettersjP-eleLettersk)k=J; if(U (1) /U) C=P-eleLettersi; P-eleLettersi=P-eleLettersk; P-eleLettersk=c; /if /for ; int find(Node &root,char *temp) /在二叉排序树 root 中查找与 temp 匹配的单词。 /若匹配返回相应单词在 WordList 中下标;若查找失败,返回-1 Node *P,*q; int flag; P=U (2) /U;/临时存储 reCompose(p,temp);/将 temp 重组 q=&root; whil
21、e(flag=U (3) /U)q !=NULL) if(flag0)/搜索左子树 q=q-lChiid; else(/搜索右子树 q=q-rChild; /while if(flag=0)/找到匹配的,保存下标 returnU (4) /U; if(U (5) /U)/查找失败 printf(“cant unscramble the following word:%s“,temp); return -1; ;(分数:15.00)(1).(分数:3.00)填空项 1:_填空项 1:_填空项 1:_填空项 1:_中级软件设计师下午试题-79 答案解析(总分:105.00,做题时间:90 分钟)一
22、、B试题一/B(总题数:1,分数:15.00)阅读下列说明和图,回答问题 1 至问题 3,将解答填入对应栏内。 说明 某汽车数字仪表系统将完成下述功能: (1)通过模一数转换,实现传感器和微处理器的接口。 (2)在发光二极管面板上显示数据。 (3)指示速度(mph)、行驶里程、油耗(mpg)等。 (4)指示加速或减速。 以下是经分析得到的数据流图,有些地方有待填充,假定顶层数据流图是正确的。图 1-1 是顶层数据流图,图 1-2 是第 0 层数据流图,图 1-3 是第 1 层数据流图,其中 A 是加工 1 的细化图,B 是加工 2 的细化图。图中,sps 表示转速 sps 的瞬时变化值,若sp
23、s0 则汽车加速,sps0 则减速,sps=0 则匀速。假定题中提供的顶层图是正确的,请回答下列问题。图 1-1 图 1-2 图 1-3 (分数:15.00)(1).第 0 层数据流图(图 1-2)中有一条缺失的数据流,请指出该数据流的起点和终点。 加工 1 的细化图(图 1-3 中的 A)中有一条缺失的数据流,请指出该数据流的起点和终点。 (分数:5.00)_正确答案:()解析:图 1-2 中,缺失的数据流:速度 mph,起点:加工 1 速度处理,终点:仪表板图 1-3A 中,缺失的数据流:加速/减速,起点:加工 1.2 确定加速/减速,终点:仪表板 分层数据流图应时刻牢记父图与子图平衡原则
24、。对这种数据流缺失题目,认真对照父图与子图就可答案。另外,还要注意与文件的交互,包括错误数据流大多也是出在此。 将第 0 层数据流图(图 1-2)与项层数据流图(图 1-1)仔细对照,可以发现缺失了输出数据流“速度”,其起点为加工 1 速度处理,终点为仪表板。数据流“速度 mph”虽然从加工1 输出到了加工 2,但这内部数据流。 同理,加工 1 的细化图(图 1-3A)缺失了数据流“加速/减速”,其起点是加工 1.2 确定加速/减速,终仪表板。(2).加工 2 的细化图(图 1-3 中的 B)中有一条错误的数据流,请指出该数据流的起点或终点(若可以,指出两者)。 (分数:5.00)_正确答案:
25、()解析:图 1-3B 中,错误的数据流:速度 mph,起点:加工 2.2 计算油耗 仔细对照加工 2(图 1-2)和加工2 的细化图(图 1-3B),可以发现对于加工 2.2 数据流“速度 mph”作出数据,而该数据流应该是输入数据。(3).小说明是用来描述加工的。小说明的描述方法有哪些?请分别用这些描述方法描述加工 1.2。 (分数:5.00)_正确答案:()解析:小说明并不描述具体的加工过程,常用的有自然语言、结构化自然语言、判定表和判定树。 自然语言描述:若sps0 则汽车加速,sps0 则减速,sps=0 则匀速。 结构化自然语言描述:IF sps0 THEN 加速 ELSE IF
26、sps0 THEN 减速 ELSE 匀速 判定表描述:二、B试题二/B(总题数:1,分数:15.00)阅读下列说明和 E-R 图,回答问题 1 至问题 3,将解答填入对应栏内。 说明 设有下列关于学生成绩管理系统的 E-R 图(见图 2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列 SQL 语言建立了基本表:(分数:15.00)(1).(分数:2.50)解析:填空项 1:_ (正确答案:NOT EXISTS)解析:填空项 1:_ (正确答案:STUDENT.SN0=SC.SN0 AND COURSE.CNO=SC.CNO)解析:填空项 1:_ (
27、正确答案:COUNT(*))解析:填空项 1:_ (正确答案:SNO,AVG(GRADE))解析:填空项 1:_ (正确答案:SNO,COUNT(CNO))解析:本题主要是考察 SQL。SQL 中数据查询是最常用的,其完整形式如下: SELECT ALL | DISTINCT目标列表达式,目标列表达式 FROM 表名或视图名,表名或视图名 WHERE 条件表达式 GROUP BY列名 1HAVING条件表达式 ORDER BY列名 2ASC | DESC 子句顺序为 SELECT、FROM、WHERE、GROUP BY、HAVING、ORDER BY,但 SELECT 和 FROM 是必须的,
28、HAVING 子句只能与 GROUP BY 搭配起来使用。 该成绩管理系统的关系模式有:STUDENT(SNo,SName,Sex,Dept,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)同理得应
29、填 NOT EXISTS。空(3)是“真正”的查询条件,该查询涉及到三个表 STUDENT、COURSE、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 的用法,并
30、注意同时给出学号。故空(6)应填:SNO,COUNT(CNO)。三、B试题三/B(总题数:1,分数:15.00)阅读以下说明和程序流程图,将应填入U (n) /U处的字句写在对应栏内。 说明 当一元多项式中有许多系数为零时,可用一个单链表来存储,每个节点存储一个非零项的指受和对应系数。为了便于进行运算,用带头节点的单链表存储,头节点中存储多项式中的非零项数,且各节点按指数递减顺序存储。例如:多项式 8x5-2x2+7 的存储结构为: 流程图图 3-1 用于将 pC(Node 结构体指针)节点按指数降序插入到多项式 C(多项式 POLY 指针)中。 流程图中使用的符号说明如下: (1)数据结构定
31、义如下: #define EPSI 1e-6 struct Node /*多项式中的一项*/ double c; /*系数*/ int e; /*指数*/ Struct Node *next; typedef struct /*多项式头节点*/ int n; /*多项式不为零的项数*/ struct Node *head; POLY; (2)Del(POLY *C,struct Node *p)函数,若 p 是空指针则删除头节点,否则删除 p 节点的后继。 (3)fabs(double c)函数返回实数 C 的绝对值。 图 3-1 (分数:15.00)(1).(分数:3.00)解析:填空项 1
32、:_ (正确答案:pC-next:=C-head)解析:填空项 1:_ (正确答案:tp:=NULL)解析:填空项 1:_ (正确答案:t:NULL)解析:填空项 1:_ (正确答案:t:=NULL)解析:该流程图是用于将 pC(Node 结构体指针)节点按指数降序插入到多项式 C(多项式 POLY 指针)中。需要特别注意特殊情况:C 为空多项式,即插入第一项时的处理;当 pC 的指数比 C 中的最大指数还大时的处理;当 pC 的指数与 C 中某项的指数相同时,进行系数相加,若相加后为 0 时的处理。 根据结构体POLY 的声明,可知 C-head 为 NULL 意味着多项式为空,将 pC 作
33、为第一项插入,故空(1)应填 C-head:=pC。 pC-eC-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 插入到末尾,此时
34、t=NULL,因此须正确记录其前驱方可插入(单链表),注意到空(4)分支 t=NULL 时的处理用到 tp,易于判断 tp 正是用来记录前驱的。亦可 at-epC-e 时的处理:tp:=t、t:=t-next 得到验证。纵观流程,tp 没有赋初值,这样,空(3)处就应该是对其赋初值,故应填 tp:=NULL。 再来看空(5),此时是t-epC-e,注意到 C 是降序排序(对指数而言)的,也就是说 t 以前(不包括 t)的指数均大于 pC,以后(包括 t)的均小于 pC,这样 pC 就应该插在 t 以前(据上述分析,亦即 tp 以后)。而(5)后的控制流是回到判断 t:NULL,因此,此处应填
35、t:=NULL。这样,就可将 pC 正确的插入 tp 之后,t 之前,这个工作由空(4)的分支 t=NULL 完成。四、B试题四/B(总题数:1,分数:15.00)阅读下列说明和 C 程序,将应填入U (n) /U处的字句写在对应栏中。 说明 借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse 数实现中序非递归遍历,遍历过程如下: 若不是空树,根节点入栈,进入左子树;若已经是空树,则栈顶元素出栈,访问该元素(根节点),进入该节点的右子树,继续直到遍历完成。 函数中使用的预定义符号如下: typedef struct BiTNode int data; struct B
36、iTNode *iChiid,*rChiid; BiTNode,*BiTree; typedef struct SNode/*链栈的节点类型*/ BiTree elem; struct SNode *next; SNode; 函数 int InOrderTraverse(BiTree root) BiTree P; SNode *q,*stop=NULL;/*不带头节点的单链表作为栈的存储结构*/ P=root; while(p !=NULL | stop !=NULL) if(U (1) /U) /*不是空树*/ q=(SNode*)malloc(sizeof q); if(q=NULL)r
37、eturn-1; /*根节点指针入栈*/ U (2) /U; q-elem=P; stop=q; P=U (3) /U; /*进入根的左子树*/ else q=stop; U (4) /U; /*栈顶元素出栈*/ printf(“%d|,q-elem-data); /*防问根节点*/ P=U (5) /U; /*进入根的右子树*/ free(q); /*释放原栈顶元素*/ /*if*/ /*while*/ return 0; /*InOrderTraverse*/ (分数:15.00)(1).(分数:3.00)解析:填空项 1:_ (正确答案:q-next=stop)解析:填空项 1:_ (正
38、确答案:p-lChild)解析:填空项 1:_ (正确答案:stop=stop-next)解析:填空项 1:_ (正确答案:q-elem-rChild)解析:本题考察的是二叉树的遍历以及链栈的使用。 由注释可知,空(1)是“不是空树”的条件,应填P!=NULL。 空(2)是链栈入栈操作,stop 是指向链栈栈顶的指针,故空(2)应填 q-next=stop。 空(3)进入根的左子树,故应填 P-lChild。 空(4)是链栈出栈操作,stop 是指向链栈栈顶的指针,出栈后,应修改栈顶指针,故应填 stop=stop-next。 空(5)是进入右子树,要注意的是,此处是通过链栈节点 q进行访问,
39、不能想当然的认为是 q-rChild,而应该是 q-elem-rChild。五、B试题五/B(总题数:1,分数:15.00)阅读下列函数说明和 C+代码,将应填入U (n) /U处的字句写在对应栏内。 说明 在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(包括不用的功能)都要全面初始化的话,会导致应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。 以下示例展示了 Proxy(代理)模式,PrinterProxy 类执行一些比较“轻”的方法,需要真正执行“重”的方法时才初始化 Print 类。图 5-1 显示了各个类间
40、的关系。 图 5-1 C+代码 class Printable public: virtual void setPrinterName(string name)=0; virtual string getprinterName()=0; virtual void print(string name)=0; ; class Printer:public Printable private: string name; public: Printer(string name) cout“正在产生 Printer 的对象实例“endl; thisname=name; void setPrinterNa
41、me(string name) this-name=name; string getPrinterName() return name; void print(string msg) cout“=“name“=“endl; coutmsgendl; ; class printerproxy :publicU (1) /U private: String name; Printer *real; public: PrinterProxy(string name) U (2) /U=NULL; this-name=name; void setPrinterName(string name) if(
42、U (3) /U)real-setPrinterName(name); this-name=name; string getPrinterName() return name; void print(string msg) U (4) /U; real-print(msg); void realize() if(real=NULL)real=U (5) /U; ;(分数:15.00)(1).(分数:3.00)解析:填空项 1:_ (正确答案:real)解析:填空项 1:_ (正确答案:real!=NULL)解析:填空项 1:_ (正确答案:realize())解析:填空项 1:_ (正确答案:new Printer(name))解析:由类图可知 PrinterProxy 类是 Printable 的子类,因此应声明为继承自 Printable,故空(1)应填Printable。 real 是一个 Printer 对象指针,应该进行初始化,初始化工作是在构造函数中完成的,若不进行初始化的话,realize()方法将不可预期,故空(2)应填 real。 real 是一个指针,调用之前当然得先判断 real 是否为空指针,只有不是空指针才能进行调用,否则将出现不可预期的结果,因此空(3)应填real!=NULL。 在执