1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 30及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和有关图表，回答问题 1至问题 3。 【说明】 A公司决定开发一套公共交通自动售票系统，系统要求如下所述。 (1)乘客能按以下 3步操作购票：选定目的地，投入钱币，获得一张票。 (2)并且仅当乘客选定目的地后，系统才接收投钱；每次投入的钱只购买一张票。 (3)只要投入的钱不少于所需的票价，且票库中有所要求的票，则应尽快出票。 (4)如需找钱，则在出票的同时应退还多余的钱。 (5)如果乘客投入的钱不够票价，或者票库中没有所需要的票时，系统将全额退钱，并允许乘
2、客另选目的地，继续购票。 (6)出票前乘客可以单击 “取消 ”按钮取消购票，系统将全额退出该乘客投入的钱，并允许乘客另选目的地，继续购票。 (7)出票结束 (包括退还多余的钱 )后，系统应保存销售记录，并等待乘客购票。 该系统还要求快速响应和操作同步，所以它应是一个实时系统。为此， A公司在该系统的数据流程图中附加了过程控制部分，形成转换图。在该图中，控制流 (事件流 )用虚 线表示，数据流用实线表示。图中的数据流并没有画全，需要考生填补。 对售票全过程进行的控制可以用系统内部各个状态之间的迁移来描述，从而形成状态迁移图。在状态迁移图中，用双线框表示状态，用有向边表示状态的迁移。引起状态迁移的
3、事件以及由该事件引起的动作，在有向边旁用 “ ”形式注明。 该公司还制定了一个过程启动表，用以表明状态迁移图中的 4个动作与转换图中的 4个过程之间的 “启动 ”关系，即说明哪个动作将启动哪个过程。用 1表示启动，用 0表示不启动。启动的过程将根据获得的输入数据产生输出数据，未唐动的过程则不会产生输出数据，该表中没有列出的过程，其执行与否与事件无关。 【问题 1】 转换图中缺少哪 3条数据流 ?请指明每条数据流的名称、起点和终点。 【问题 2】 在状态迁移图中， a、 b、 c分别表示什么事件 ?请用转换图中给出的事件名解答。 【问题 3】 在过程启动表中， d、 e处应填什么 ?请分别用 4
4、位二进制码表示。 1 根据以下关于学校构成的说明回答问题 1至问题 3。 【说明】 学校中有若干系，每个系有若干班级和教研室，每个教研室有若干教员，其中有的教授和副教授各带有若干研究生；每个班有若干学生，每个学生选修若干课程，每门课可由若干学生选修。 【问题 1】 用 E-R图 画出此学校的概念模型，用文字写出各实体和联系的属性。 【问题 2】 将 E-R图转换成关系模型。 【问题 3】 指出各关系模型的候选键。 2 阅读下列说明和有关图表，回答问题。 【说明】 (1)这是一个图书馆支持系统。 (2)图书馆应用系统可以将图书和杂志借给借书者，这些借书者已经在系统中注册了，图书和杂志也已经注册过
5、了。 (3)图书馆负责新书的购买，一本流行图书会多买几本。当旧书和杂志已经过时或破旧不堪时，将它们从图书馆应用系统中删除。 (4)图书馆馆员是图书馆的员工。他们与客户 (借 书者 )打交道，并且是在图书馆软件系统提供的支持下开展工作的。 (5)借书者可以预订图书馆中当前还没有的图书或杂志，这样，当某借书者所预订的图书或杂志归还回来或购进时，应用系统就通知这个预订人。当该借书者借阅了他所预订的图书或杂志后，或者通过一个显式的取消过程取消他的预订后，他的本次预订就被取消了。 (6)图书馆应用系统能够容易地建立、修改和删除系统中的信息，包括书名、借书者、借阅信息和预订信息。 (7)图书馆应用系统能够
6、在所有流行的 Web浏览器平台 (Internet Explorer 5.1以上，Netscape 4.0以上等等 )上运行。 (8)图书馆应用系统应该易于扩展新功能。 【问题】分析这个图书馆系统中涉及的角色和用例，完成用例图。 3 阅读下列 C程序和程序说明，将应填入 (n)处的字句写在对应栏内。 【说明】 本程序在 33方格中填入 1 N(N10)内的某 9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。试求出满足这个要求的所有填法。 33方格中的每个方格按行按列 (先行后列 )序号排列为： 0， 1， 2， 3， 4， 5， 6， 7， 8。 程序采用试探法，即从序号为 0的
7、方格开始， 为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填整数，就要回退到前一方格，调整前一方格的填入整数；直至序号为 8的方格也填入合理的整数后，就找到了一个解，将该解输出。再调整序号为 8的方格所填整数，继续去找下一个解。为了检查当前方格的填入整数的合理性，程序引入二维数组 check Matrix，存放需要进行合理性检查的相邻方格的序号。 # include stdio. h # define N 12 int bN+1; int pos; int a9;/* 用于存储诸方格所填入的整数 */ int AllN
8、um=0;/* 统计有多少种填法 */ int checkMatrix3= -1,0,-1,1,-1, 0,-1,1,3,-1,2,4,-1, 3,-1,4,6,-1,5,7,-1; void write(int a) int i, j; for(i=0; i 3; i+) for(j=0; j 3; j+) printf(“%3d“, a3*i+j); printf(“n“); int isPrime(int m) int i; if(m=2)return 1; if(m=1 m%2=0)return 0; for(i=3; i*i m;) if(m%i=0)return 0; i+=2;
9、return 1; int selectNum(int start) int j; for(j=start; j =N; j+) if(bj)return j; return 0; int check()/*检查填入 pos位置的整数是否合理 */ int i,j; for(i=0; (j=(1) =0; i+) if(!isPrime(apos+aj) (2); (3); extend ()/* 为下一方格找一个尚未使用过的整数 */ a(4)=selectNum(1); bapos=0; void change ()/*为当前方格找下一个尚未使用过的整数 (找不到回溯 )*/ int j;
10、 while(pos =0 if(pos 0)return; bapos=1; apos=j; bj=0; int find () int ok=1; pos=0; apos=1; bapos=0; do if(ok) if(pos=8) write(a); change(); AllNum+;/* 统计有多少种填法 */ else extend(); else change(); ok=check(); while(pos =0); void main() int i; for(i=1; i =N; i+) bi=1; find(); prinrf(“共有 %d种不同填法 !/n“, All
11、Num); 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则 仅题号小的 1道题解答有效。 4 阅读下列 C+程序和程序说明 , 将应填入 (n)处的字句写在答题纸的对应栏内。 【说明】构造最优二叉查找树。 具有 n个结点的有序序列 a1, a2, , an 存在于数组元素 a1、 a2, , an 之中 , a0未被使用。结点 a1, a2, , an -1, an的查找成功的概率 p1, p2, , pn -1, pn存在于数组元素 p1、 p2, , pn 1、 pn之中 , p0未用。另外 , 查找失败的概率 q0, q1,
12、 , qn -1, qn存 在于数组元素 q0、 p1, , qn -1、 qn之中。算法计算的序列 ai+1, ai+2, aj -1, aj的最优二叉查找树 Tij的代价Cij存在于数组元素 cij之中 , Tij的根结点的序号 rij存在于 rij之中 , 它的权值存在于 wij之中。为了便于内存的动态分配 , 统统使用一维数组取代二维数组。 const float MAXNUM=99999. 0; /尽可能大的浮点数 template (1) void OPtimal_Binary_Search_Tree(float p, float q, Type a, int n) float *
13、C, *W; c=(2); w=(3); 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表示根结点的下标或序号 , 范围为 0 n float minimum; for(length=1; length =n; length+) /处理的序列长度由 1到 n for(i=0; i =n-length; i+) /i为二叉查找树 Tij的起始序号
14、 j=i + length; /j为二叉查找树 Tij的终止序号。如：处理序列 a1a2a3时 , /相应的二叉查找树为 T03, i=0, 而 j=3 wi*(n+1)+j=(4); minimum =MAXMUM; for(k=i+1; k =j; k+) /考察以 ai+1、ai+2, , ai 为根的情况 if(5) minimum) minimum=ci*(n+1)+k-1+ck*(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 /构造好的最优二叉查找树的根结点的序号在
15、r0n中 5 阅读下列 Java程序和程序说明 , 将应填入 (n)处的字句写在答题纸的对应栏内。 【说明】数据排序。将给定 的 n个整数分别按照升序和降序进行排列。 class SortInt_1 int i, j, k, temp; void SortInt(int a1, a2)/升序排序 for(i=0; i a1-1; i+) k=i; for(j=i+1 ;j a1 ;j+) if (1) k=j; if(k!=i) temp=a2i;a2i=a2k;a2k=temp; class Sortlnt_2 (2) int i, j, k, temp; void Sortlnt(int
16、a1,a2)/降序排序 for(i=0;i a1-1 ;i+) k=i; for(j=i+1 ;j a1 ;j+) if (3) 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; Sortlnt_1 newlnt1=(4); Newlnt1. SortInt(a. length, a);/调用 SortInt_1类的方法 System. out. println(“升序排列的数据 “);
17、 For(int i=0;i 8;i+) System. out. print(ai+“ “); system. out. println(); SortInt_2 newInt2=new sortint_2(); /创建类 SortInt_2的对象 (5); System. out. println(“降序排列的数据 : “); For(int i=0;i 8;i+) System. out. print(ai+“ “); 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 30答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 【试题解析】 这道考题的题型比较特殊，但仍可
18、以参考常考的数据流程图的解题思路。应全面细致地阅读试题说明、转换图和状态迁移图，体会系统的实际运行场景，以帮助顺利地解题。 问题 1已经明确指出转换图中缺少 3条数据流，而从直观上看， “核查 ”处于核心位置，它还非常显著地同全部 3个文件有关。当然，有些考生不一定有这种直接看出关键点的技能，但是对于具有扎实软件工程理论基础和实际系统设计经验的人员，在经过一定的考试训练后，应该具有这种技能。下面具体分析。 系统的使用者 乘客与系统之间的活动有选择目的地、投钱、出票。首先应该按照这 3个活动去解答第 1个问题。 乘客选择目的地应该经过核查，防止错误和异常，但这一点在转换图中没有画出。 乘客投钱，
19、系统接到钱后应核查，如果正确 (不是假币，规定面值的纸币，面值不低于票价 )，系统将进入后面的出票流程。如果是规定的面值且面值大于票价，同时还要进入退还钱 (找零 )的流程。 在 中，如果系统对钱核查后发现不正确 (假币，不是规定的面值，面值低于票价 )，系统将进入退还钱的流程。 出票时也应该核查，这一点在转换图中已经画出。现在，已经找到了缺少的 3条数据流。 将上述 3条数据流补充到转换图中，在以 “核查 ”为中心的转换图中，每个输入数据流 /输出数据流都经过 “核查 ”的检测。系统设计师们应该具有这样的设计思想：“核查 ”是系统中必须的、核心的、决定系统健壮性的功能。 给出的状态图是一个完
20、整的循环流程，正常过程中，状态 “正在接受投钱 ”后，应该接下去是出票，但事件 a导致 “退 钱 ”事件发生，在说明中已经很明确给出，是乘客按 “取消 ”按钮。 按照问题 1中的分析，知道 “接受投钱 ”后，系统经过 “核查 ”，如果正确，就可以“出票 ”，所以 b是 “核查正确 ”。 出票结束后，该乘客的事务已经完成，系统将进入下一个乘客事务的等待，所以c应该是 “出票结束 ”。 对于问题 3，应该按照已经补充完的转换图和状态迁移图，及过程启动表中的规则进行分析，可以很容易得出解答。 d是 1001， e是 1100。 1 【正确答案】 【问题 1】 用 E-R图表示的概念模型如下所示。 各
21、实体的属性如下所述。 系：系编号，系名。 班级：班级编号，班级名。 教研室：教研室编号，教研室名。 学生：学号，姓名，学历。 课程：课程编号，课程名。 教员：职工号，姓名，职称。 各联系的属性为： 选修课：成绩。 其他联系无属性。【问题 2】 其关系模型为： 系 (系编号，系名，学校 【试题解析】 在画 E-R图时，可以按照对问题的描述一步一步画出每一句话中涉及的实体，再根据给出的实际语义，画出实体之间的联系。例如，每个教研室有若干教员，每个班有若干学生，可以画出教研室和教员、班级和学生之间一对多的联系。再比如，有的教授和副教授每人 各带若干研究生，而一个研究生一般指定一个导师，这是通常的规则
22、，所以可以画出教员和学生之间一对多的关系。 按照上述的分析方法，从题的说明中，可以得到如下实体和联系。 .实体：学校、系、教研室、班级、教员、学生、课程。 .联系：校 系、系 室、系 班、室 教、班 生、指导、选修。 具体说明： .实体 “学校 ”和实体 “系 ”是 “一对多 ”的 “校 系 ”联系。 .实体 “系 ”和实体 “班级 ”是 “一对多 ”的 “系 班 ”联系。 .实体 “系 ”和实体 “教研室 ”是 “一对多 ”的 “系 室 ”联系。 .实体 “班级 ”和实体 “学生 ”是 “一对多 ”的 “班 生 ”联系。 .实体 “教研室 ”和实体 “教员 ”是 “一对多 ”的 “室 教 ”
23、联系。 .实体 “学生 ”和实体 “课程 ”是 “多对多 ”的 “选修 ”联系。 .实体 “教员 ”和实体 “学生 ”是 “一对多 ”的 “指导 ”联系。 2 【正确答案】 参与者 1注册用户 参与者 2图书馆管理员 参与者 3借书者 参与者 4图书馆馆长 用例 1登录 用例 2搜索 用例 3浏览 用例 4管理借书者 用例 5管理书目 用例 6管理标题 用例 7担任借书者的身份 用 例 8预订 用例 9取消预订 用例 10借书 用例 11还书 【试题解析】 由试题给出的用例图可以看到有 4个参与者，并且他们之间是泛化(继承 )的关系，结合案例描述进行分析。 图书馆系统的参与者有图书管理员 (L
24、ibrarian)和借书者 (Borrower)，因为他们二者都是该系统的用户。图书管理员具有添加借书者、标题和书目这些管理能力，而借书者则是来借阅或预订图书和杂志的用户。偶尔，图书馆馆员或另一个图书馆也可能成为借书者。最后，我们有一个图书馆馆长 (Master Librarian)这一 参与者，这个角色具有管理其他图书馆馆员的能力。另外，在该图书馆有某本书籍的副本 (一个书目 )之前，先向该系统添加一个标题，这是可以的，目的是为了让借书者能够进行预订。 图书馆系统中的用例有以下这些： .Login(登录 ) .Search(搜索 ) .Browse(浏览 ) .Make Reservatio
25、n(预订 ) .Remove Reservation(取消预订 ) .Checkout Item(借书 ) .Return Item(还书 ) .Manage Titles(管理标题 ) .Manage Items(管理书目 ) .Manage Borrowers(管理借书者 ) .Manage Librarians(图书管理员 ) .Assume Identity of Borrower(担任借书者的身份 ) 上述列表中需要注意的是 Title(标题 )和 Item(书目 )这两个概念。因为在一个图书馆中，一本流行书通常有多本副本，所以系统必须把标题 (可以是一本书的名称、书的作者 )和同一
26、标题的一个单一物理副本 (这是一个书目 )的概念分开。 从实用角度考 虑，为了限制本题的复杂度，这里不完成某些 “Manage(管理 )”用例(例如 Manage Librarians和 Manage Borrowers)的实现。 3 【正确答案】 (1)checkMatrixposi (2)return 0 (3)return 1 (4)+pos (5)apos+1 【试题解析】 (1)checkMatrixposi 本处填空是在循环检查填入 pos位置的整数是否合理，把与 pos相邻的数都求和判断是否为质数。 (2)return 0 若不是 质数则返回 0，表示不可以。 (3)return
27、 1 若相邻的数都是质数则返回 1，表示可以。 (4)+pos 本处填空是为下一个方格找一个尚未使用过的整数。 (5)apos+1 本处填空是在循环为当前方格找下一个尚未使用过的整数。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 4 【正确答案】 (1) class Type (2) new float(n+1)*(n+1) (3) new float(n+1)*(n+1) (4) wi*(n+1)+j-1+pj+qj (5) ci*(n+1)+k-1+ck*(n+1)+j 【试题解析】 (1) c
28、lass 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) wi*(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。按照一般
29、二维数组的写法是： cij=wij+cim-1+cmj。 5 【正确答案】 (1) a2ja2k (2) extends SortInt_1 (3) a2j a2k (4) new SortInt_1() (5) Newint2.SortInt(a. length, a) 【试题解析】 (1) a2ja2k 选择排序的判断条件， k是最小元素的下标。 (2) extends SortInt_1 类的多态， SortInt2由类 SortInt1派生而来。 (3) a2j a2k 选择排序的判断条件， k是最大元素的下标。 (4) new SortInt_1() 创建类 SortInt1的对象，再调用 SortInt1类的方法进行升序排序。 (5) Newint2.SortInt(a. length, a) 调用 SortInt2类的方法，实现降序排序。 本题采用选择排序的方法，第 1、 3空考查对算法的掌握，两空可互相对照，第2、 4、 5空考查对 Java语言的掌握情况，两空亦可互相对照，难度不大。
