1、2004年上半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读下列说明和数据流图，回答问题 1至问题 4，将解答填入答题纸的对应栏内。 说明 某基于微处理器的住宅安全系统，使用传感器 (如红外探头、摄像头等 )来检测各种意外情况，如非法进入、火警、水灾等。 房主可以在安装该系统时配置安全监控设备 (如传感器、显示器、报警器等 )，也可以在系统运行时修改配置，通过录像机和电视机监控与系统连接的所有传感器，并通过控制面板上的键盘与系统进行信 息交互。在安装过程中，系统给每个传感器赋予一个编号 (即 id)和类型，并设置
2、房主密码以启动和关闭系统，设置传感器事件发生时应自动拨出电话号码。当系统检测到一个传感器事件时，就激活警报，拨出预置的电话号码，并报告关于位置和检测到事件的性质等信息。 数据流图 4-1 1 数据流图 4-1(住宅安全系统顶层图 )中的 A和 B分别是什么 ? 2 数据流图 4-2(住宅安全系统第 0层 DFD图 )中的数据存储 “配置信息 ”会影响图中的哪些加工 ? 3 将数据流图 4-3(加工 4的细化图 )中的数据流补充完整，并指明加工名称、数 据流的方向 (输入 /输出 )和数据流名称。4 试说明逻辑数据流图 (logical data flow diagram)和物理数据流图 (ph
3、ysical data flow diagram)之间的主要差别。 5 阅读下列说明和算法，回答问题 1和问题 2，将解答填入答题纸的对应栏内。 说明 算法 2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示： 文件 提示信息 (1+2) abc) 缺少对应左括号：第 2行，第 4列 (def)8x) 缺少对应左括号：第 3行，第 10列 (h) ij)(k (1ml) 缺少对应右括号：第 5行，第 4列；第 4行，第 1列 在算法 2-1中， stack为一整数栈。算法中各函数的说明如表 4-1所示。 算法 2-1 将栈
4、stack置空，置 EOF为 False chnextch() ； while(not EOF) kkind(ch) ； if(k=(1) push(2)； push(3)； elself(k=(4) if(not empty() pop()，pop()， else 显示错误信息 (缺少对应左括号或右括号 )； 显示行号 row；显示列号col； endif endif chnextch() ； endwhile if(not empty() 显示错误信息 (缺少对应左括号或右括号 )； while(not empty() rowpop() ； colpop() ； 显示行号 row；显示列号
5、 col cndwhile endif 为了识别更多种类的括号，对算法 2-1加以改进后得到算法2-2。算法 2-2能够识别圆括号，方括号和花括号 (不同类型的括号不能互相匹配 )。改进后，函数 kinnd(char ch)的参数及其对应的返回值如表 4-2所示。 表 4-2 函数的参数及其返回值 算法 2-2 将栈 stack置空，置 EOF为 False chnextch() ； while(not EOF) kkind(ch) ； if(k 0) if( 判断条件 1 ) push(5)； push(6)； push(7)； elseif( 判断条件 2 and 判断条件 3 ) pop
6、()； pop()； pop()； else 显示错误信息 (缺少对应左括号或右括号 )； 显示行号 row；显示列号 col； endif endif chnexteh() ； endwhile if(not empty() 显示错误信息 (缺少对应左括号或右括号 )； while(not empty() pop()； rowpop() ；colpop() ； 显示行号 row；显示列号 col； endwhile endif 5 试将 算法 2-1)和 算法 2-2中 (1) (7)处补充完整。 6 从下面的选项中选择相应的判断逻辑填补 算法 2-2中的 “判断条件 1”至 “判断条件 3
7、”。注意，若 “判断条件 2”的逻辑判断结果为假，就无需对 “判断条 件 3”进行判断。 (a)字符是括号 (b)字符是左括号 (c)字符是右括号 (d)栈空 (e)栈不空 (f)栈顶元素表示的是与当前字符匹配的左括号 (g)栈顶元素表示的是与当前字符匹配的右括号 7 阅读下列说明以及图 4-4和图 4-5，回答问题 1、问题 2和问题 3，将解答填入答题纸的对应栏内。 说明 某电话公司决定开发一个管理所有客户信息的交互式网络系统。系统的功能如下。 1浏览客户信息：任何使用因特网的用户都可以浏览电话公司所有的客户信息 (包括姓名、住址、电话号码等 )。 2登录：电话公司授予每个客户一个账号。拥
8、有授权账号的客户，可以使用系统提供的页面设置个人密码，并使用该账号和密码向系统注册。 3修改个人信息：客户向系统注册后，可以发送电子邮件或者使用系统提供的页面，对个人信息进行修改。 4删除客户信息：只有公司的管理人员才能删除不再接受公司服务的客户的信息。系统采用面向对象方法进行开发，在开发过程中确定的类如表 4-3所示。 表 4-3 开发过程中确定的类7 在需求分析阶段，采用 UML的用例图 (use case diagram)描述系统功能需求，如图 4-4所示。指出图中的 A,B,C和 D分别是哪个用例 ? 8 在 UML中，重复度 (multiplicity)定义了某个类的一个实例可以与另
9、一个类的多个实例相关联。通常把它写成一个表示取值范围的表达式或者一个具体的值。例如，图 4-5中的类 InternetClient和 CustomerList， InternetClient端的 “0.*”表示： 1个 CustomerList的实例可以与 0个或多个 InternetClient的实例相关联；CustomerList端的 “1”表示： 1个 InternetClient 的实例只能与 1个 CustomerList的实例相关。 指出图 4-5中 (1) (4)处的重复度分别为多少 ? 9 类通常不会单独存在，因此当对系统建模时，不仅要识别出类，还必须对类之间的相互关系建模。在
10、面向对象建模中，提供了 4种关系：依赖 (dependency)、概括(generaliza tion)、关联 (association)和聚集 (aggregation)。分别说明这 4种关系的含义，并说明关联和聚集之间的主要区别。 10 程序 START PRUGBC LD GR0， DATA LEA GR1， 0 LEA GR3， 48 LOOP1 CPL GR0， WDT， GR1 JP2 LOOP2 ST GR3， BTASC， GR1 LEA GR1， 1， GR1 LEA GR2， -4， GR1 JN2 LOOP1 (1) LOOP2 LEA GR2， 48 LOOP3 CPL
11、 GR0， WDT， GR1 JMI NEXT (2) LEA GR2， 1， GR2 JMP LOOP3 NEXT (3) LEA GR1， 1， GR1 LEA GR2， -4， GR1 JNZ LOOP2 LAST (4) ；处理个位数 (5) EXIT C48 DC 48 WDT DC 10000 DC 1000 DC 100 DC 10 BTASC DS 5 DATA DC #FA59H END 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 11 函数 int DeleteNode(Bitr
12、ee *r， int e) Bitree p=* r， pp， s， c； while(1)/ * 从树根结点出发查找键值为 e的结点 * / pp p； if(e p data) p p Lchild； else p p Rchild if(! p)return-1； / * 查找失败 * / if(p- Lchild & p- Rchild)/ * 处理情况 * / s=(2)； pp=p； while(3)pp=s； s=s- Rchild； p- dara=s- data； P=s； / * 处理情况 、 * / if(4)c=p- Lchild； else c=p- Rchild i
13、f(p=*r) *r c； else if(5)pp- Lchild=c； else pp- Rchild=c； free(p)； return 0； 12 程序 #include ioStream.h template class T class Array； template class T class ArrayBody friend (1)； T* tpBody； int iRows， iCurrentRow； ArrayBOdy(int iRsz， int iCsz) tpBody=(2)； iRows=iRsz， iColumns=iCsz； iCurrentRow=-1； pub
14、lic： T& operator(int j) bool row_error， column_error； row_error=column_error=false； try if(iCurrentRow 0|iCurrentRowiRows) row_error=； if(j 0| jiColumns column_error=； if(row_error=true | column_error=true) (3)； eatch(char) if(row error=true) cerr “行下标越界 “ iCurrentRow ”； if(column error=true) cerr “
15、列下标越界 “ j ”； cout “n”； return tpBodyiCurrentRow * iColumns+j； ArrayBody()deleretpBody； ； template class T class Array ArrayBody T tBody； public： ArrayBody T & operator(int i) (4)； return tBody； ； void main() Array int a1(10， 20)； Array double a2(3， 5)； int b1； double b2； b1=a1-510； / * 有越界提示：行下标越界 -
16、5 * / b1=a11015； / * 有越界提示：行下标越界 10 * / b1=a114； / * 没有越界提示 * / b2=a226； / * 有越界提示：列下标越界 6 * / b2=a21020； / * 有越界提示：行下标越界 10列下标越界 20 * / b2=a214； / * 没有越界提示 * / 2004年上半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 A：传感器； B：报警器 【试题解析】 本题是一道分层数据流图的题目。解答此类问题最关键的一点就是要细心，把题目看清，不要丢掉任
17、何一个条件。另外解题有一定的技巧，从一些常规的入口作为突破口，会事半功倍。现在就利用分层数据流图的数据流的平衡原则 (即父图和子图 (加工图 )的一致 性 )来解题。 子图是其父图中某一部分内部的细节图 (加工图 )。它们的输入输出数据流应该保持一致。如同看到地上有只蚂蚁有 6条细细的腿，中间是一个小黑点，要看得更清楚一些就拿放大镜看。这时能看到它的头、触角、身体和比较粗的腿，但是看到的一定还是 6条腿，不是 7条，也不是 3条。子图也是如此，在上一级中有几个数据流，它的子图也一定有同样的数据流，而且它们的输送方向是一致的 (也就是说原图有 3条进的数据流， 2条出的数据流，子图同样也是 )。
18、 用这条原则可以轻松地解决问题 3。在 0层图中， “4监控传感器 ”模块有 1条输入数据流 “传感器状态 ”和 3条输出数据流 “电话拨号 ”、 “传感器数据 ”和“告警类型 ”。在加工 4的细化图中，仅看到了输出数据流 “告警类型 ”，所以知道此加工图少了 “传感器状态 ”、 “电话拨号 ”、 “传感器数据 ”这 3 条数据流。加工 4的结构非常清晰，所以只需把这 3条数据流对号入座即可， “电话拨号 ”应是 “4.5拨号 ”的输出数据流； “传感器状态 ”应是作为 “4.4读传感器 ”处理的输入数据流；“传感器数据 ”应该是经 “4.1显示格式 ”处理过的数据流，所以作为 “4.1显示格
19、式 ”的输出数据流。 此题和以往试题有所不同。以往都给 定了完整正确的顶层图。现在顶层图不完整，可以通过题目说明信息以及顶层图来分析顶层图并解答问题。题目中提到了“房主可以在安装该系统时配置安全监控设备 (如传感器，显示器，报警器等 )”在顶层图中这 3个名词都没有出现，但仔细观察，可以看出 “电视机 ”实际上就是 “显示器 ”。因为它接收 TV信号并输出。再看其他的几个实体都和 “传感器 ”“报警器 ”没有关联。又因为 A中输出 “传感器状态 ”到 “住宅安全系统 ”所以 A应填 “传感器 ”。B 接收 “告警类型 ”，所以应填 “报警器 ”。 2 【正确答案】 3.密码处理； 4监控传感器
20、； 5显示信 息和状态 【试题解析】 首先，毫无疑问 “4监控传感器 ”用到了配置信息文件，这点可以在加工 4的细化图中看出。接着，观察。层图， “3密码处理 ”这个处理是用于检验密码的，且它只有 1个输出数据流 “检验 ID信息 ”到 “显示信息和状态 ”，没有反馈回来的数据流，所以 “检验 ID信息 ”是已经验证通过的用户的信息，用户输入密码应是在 “3密码处理 ”这个环节中进行验证的 (因为如果密码验证是在 “5显示信息和状态 ”中进行的，那么从 “5显示信息和状态 ”应有 1条不合法用户的数据流反馈到 “密码处理 ”)。所以 “密码处理 ”一定要用到配置信息 文件中的用户名和密码。同时
21、由于输出到 “5显示信息和状态 ”的数据流是 “检验 ID信息 ”，所以 “5显示信息和状态 ”也用到了配置信息文件。 4 【正确答案】 物理数据流图关注的是系统中的物理实体，以及一些具体的文档、报告和其他输入输出硬拷贝。物理数据流图用作系统构造和实现的技术性蓝图。 逻辑数据流图强调参与者所做的事情，可以帮助设计者决定需要哪些系统资源；为了运行系统用户必须执行的活动；在系统安装之后如何保护和控制这些系统等。 在逻辑数据流图中说明应该具有哪些加工和数据存储，而不关心这些加工和数据存 储是如何实现的；物理数据流图则要说明加工和数据存储是如何实现的。 5 【正确答案】 (1)1 (2)col (3)
22、row (4)2 (5)col (6)row (7)k 【试题解析】 本程序的功能是检查文本文件中的圆括号是否匹配。从提示信息中，可以看出程序不但可以检查出是否有括号匹配错误，而且还知道具体错在哪个括号。由于括号匹配的规则是把最近的左右括号配成一对，所以括号匹配最常用的方法是遇到左括号则入栈，遇到右括号就出栈，出栈的友括号与当前的右括号是匹配的。此算法也不例外。 下面具体分析算法 ： 首先，把栈置空，置 EOF为 False，并从文件中读取第一个字符到 ch。然后进入循环，循环体执行一次处理一个 ch。进入循环，利用 kind函数算出 ch 的类型k，接下来就是一大堆的空了，这个算法本身并不长
23、，但空有这么多，而且比较集中，为解题增加了一定的难度。这里虽然空多，但基本结构却很明显，大致流程如下： 当 k 等于什么的时候把什么入栈，当 k等于什么的时候且栈不为空的时候出栈，如栈为空打印错误信息，如果都不是则读文件下一个字符再次进入循环。 再结合上面提到的算法，可以知道，入栈应是在类型 k为 1(即 ch为左括号时 )，出栈应是在类型 k为 2(即 ch 为右括号时 )。所以 (1)空应填 1， (4)空应填 2。 (2)和 (3)到底是把什么压入栈了呢 ?在 (4)下面出栈时，并没有用到栈的内容。在此有些考生理所当然地认为栈中的内容没有什么用，随便压个 ch 进去了，而且 2个都是写的
24、 ch。其实从逻辑上就可以推翻这种解答，如果是压的同样的数据，又是在同一位置出栈，算法大可只用个 push， pop就可以了。这时继续往后面看，来寻找正确的答案。当看到 “row pop()； col pop()； ”时，所有的疑惑可迎刃而解了，应该把 row和 col压入堆栈 !那么 row 和 col谁先谁后呢 ?由于是先弹出row 后弹出 col，按栈的后进先出的规则，可知先压入栈的是 col，再压入 row。所以 (2)空填写 col， (3)空填写 row。 完成 算法 2-1的分析后，分析 算法 2-2就比较轻松了。 (5)(6)(7)空的答案可直接到后面找到，因为后面有 “pop
25、()； row -pop()； col pop()； ”所以 (5)空应填col， (6)空应填 row。 6 【正确答案】 判断条件 1： (b) 判断条件 2： (e) 判断条件 3： (f) 【试题解析】 因为判断条件 1为真时要人栈，所以判断条件 1应是判断字符是否是左括号，如果是就入栈。所以判断条件 1选 b。 判断条件 2和 3是联系在一起的，当判断条件 2和 3都为真时，要进行出栈操作，因此要判断栈是否为空。由此可以得出判断条件 2和 3中，有一个是用来判断栈是否为空的。 备选答案的一些选项给了一些提示，就是用判断栈顶元素，来确定当前括号是否和栈中压人括号是同一类型的。但前提是左
26、括号类型入了栈，而且要在栈顶，如果 (7)空压入的是 k，就正好吻 合了。所以 (7)空应填 k，判断括号是否匹配的条件也就可以确定了。如果当前 ch 是右括号且当前栈顶的左括号 (只有左括号入了栈 )类型与 ch 匹配，则匹配成功。因为在题目中有提示 “若判断条件 2”的逻辑判断结果为假，就无需对 “判断条件 3”进行判断。所以应把 “栈不空 ”作为判断条件 2，“栈顶元素表示的是与当前字符匹配的左括号 ”作为判断条件 3。即判断条件 2填e，判断条件 3填 f。 7 【正确答案】 A：浏览客户信息； B：修改个人信息； C：登录； D：删除客户信息。 【试题解析】 图 4-4是一个 UML
27、 的用例图。在工程的分析阶 段，例图被用来鉴别和划分系统功能，它们把系统分成动作者 (actor)和用例。 动作者 (actor)表示系统用户能扮演的角色 (role)。这些用户可能是人，可能是其他的计算机、一些硬件或者是其他软件系统。惟一的标准是它们必须要在被划分到用例的系统部分以外。它们必须能刺激系统部分，并接收返回。 用例描述了当某个动作者给系统特定的刺激时系统的活动。这些活动被文本描述。它描述了触发用例的刺激的本质，输入和输出到其他活动者，转换输入到输出的活动。用例文本通常也描述每个活动在特殊的活动线时可能的错误，以及系统应采取的补 救措施。 了解用例图、动作者、用例的基本概念后，题目
28、就迎刃而解了。图中的网络用户、公司客户、管理人员都是动作者。题目说明中提到了系统有 4个功能：浏览客户信息、登录、修改个人信息、删除客户信息。这也就是 4个用例。现在只需把他们对号入座即可。根据题目说明，可以知道任何使用 Internet的网络用户都可以浏览电话公司所有的客户信息，在图中符合这一条件的只有 A，所以 A应填浏览客户信息。因为只有公司的管理人员才能删除不再接受公司服务的客户的信息。所以 D应填删除客户信息。 剩下只有登录和修改个人信息 2个用例了，那么究 竟是 B填登录还是修改呢 ?先介绍包含和扩展的概念。 2个用例之间的关系可以主要概括为 2种情况：一种是用于重用的包含关系，用
29、构造型 include表示；另一种是用于分离出不同的行为，用构造型 extend表示。 (1)包含关系：如果可以从 2个或 2个以上的原始用例中提取公共行为，或者发现能够使用一个构件来实现某一个用例的部分功能时，应该使用包含关系来表示它们。示意图如图 4-6所示。 (2)扩展关系：如果一个用例明显地混合了 2种或 2种以上的不同场景，即根据情况可能发生多种事情。可以断定将这个用例分为一个主用例和 一个或多个辅用例描述可能更加清晰。示意图如图 4-7所示。 因为要先登录才能修改信息，显然 B 应填修改个人信息， C应填登录。 在 UML 中重复度 (multiplicity)又称多重性，多重性表
30、示为一个整数范围 n.m，整数 n 定义所连接的最少对象的数目，而 m则为最多对象数 (当不知道确切的最大数时，最大数用 *号表示 )。最常见的多重性有 0.1， 0.*， 1.1， 1.*。 因为 1个CustomerList的实例可以与 0个或多个 Customer的实例相关联；而 1个 Customer的实例只能与 1个 CustomerList 的实例相关。所以 (1)空应填 1， (2)空应填 0.*。因为 Customer是 CompanyCustomer 的相应的详细信息，所以 (3)空和 (4)空都应该填写 0.1。 用 UMI建立业务模型时，可以把业务人员看作是系统中的角色或
31、者类。在建立抽象模型时，很少有类会单独存在，大多数都将会以某种方式彼此通信，因此还需要描述这些类之间的关系。关系是事物间的连接，在 UML中，有几个很重要的关系。 (1)依赖关系 有 2个元素 A和 B，如果元素 A的变化会引起元素 B 的变化，则称元素 B依赖 (depend ency)于元素 A。 在类中，依赖关系有多种表现形式，例如，一个类向另一个类发消息；一个类是另一个类的成员；一个类是另一个类的某个操作参数等。 (2)概括关系 概括关系(generalization)，也称为泛化关系，描述了一般事物与该事物中的特殊种类之间的关系，也就是父类与子类之间的关系。继承关系是泛化关系的反关系
32、，也就是说子类是从父类中继承的，而父类则是子类的泛化。在 UML 中，对泛化关系有 3个要求： 子类应与父类完全一致，父类所具有的关联、属性和操作，子类都应具有。 子类中除了与父类一致的信息外，还包 括额外的信息。 可以使用子父类实例的地方，也可以使用子类实例。 (3)关联关系 关联 (association)表示 2个类的实例之间存在的某种语义上的联系。例如，一个老师为某个学校工作，一个学校有多间教室。可以认为老师和学校、学校和教室之间存在着关联关系。 关联关系为类之间的通信提供了一种方式，它是所有关系中最通用、语义最弱的。关联关系通常可以再细分成以下几种。 聚集关系：聚集关系 (aggre
33、gation)是关联关系的特例。它表示一种整体和部分的关系。如一个电话机包含一个话筒，一个计算机包含显示器，键盘和 主机等都是聚合关系的例子。 组合关系：如果聚集关系中的表示 “部分 ”的类的存在与表示 “整体 ”的类有着紧密的关系，例如， “公司 ”与“部门 ”之间的关系，那么就应该使用组合关系来表示。 8 【正确答案】 (1)1 (2)0.* (3)0.1 (4)0.1 9 【正确答案】 4种关系的含义如下： 依赖表示类之间的使用关系。 概括表示一般类和特殊类之间的关系。 关联和聚集都表示实例之间的结构关系。 关联和聚集的区别：关联指明一个类的对象与另一个类的对象间的 联系； 2个类之间的
34、关联表示了 2个同等地位类之间的结构关系，这 2个类在概念上是同级别的。聚集是一种特殊的关联，它表示整体与部分的关系。 10 【正确答案】 (1)JMP LAST (2)SUB GR0， WDT， GR1 (3)ST GR2， BTASC， GR1 (4)ADD GR0， C48 (5)ST GR0， BTASC， GR1 【试题解析】 本程序是将 16位无符号二进制数转换为 5位十进制数。 程序的前 3句是对寄存器赋初值， DATA数据 (即要转换的数 )被读取到 GR0，GR1置为 0， GR3置为 48。 第四句是一个逻辑比较语句 (从这个语句可以看出，GR1用作 WDT的偏移地址 )，
35、比较 GR0和 WDT中的数据的大小。 WDT开始的 5个连续空间的数据分别为 “10000， 1000， 100， 10， 5”。因为当前的 GR1为 0，所以 WDT 对应的为 “10000”，当 GR0大于等于 (WDT)时转LOOP2，小于 (WDT)则继续往下执行。其实在这种情况下，最好的分析方法就是把 DATA中的数据自己手动转成十进制，然后把数据代到程序里，跟踪程序的执行，这样能最快的了解程序的执行流程和处理方法，同时也做了验证工作。 因为 #FA59H转成十进制是 64089。所以现在程序转到 LOOP2 执行。 GR2置48，单从这里无法了解 GR2是什么用途。比较 GR0与
36、 (WDT+GR1)的大小， GR0比 10000大，所以执行 (2)，再执行 “LEAGR2， 1， GR2”即把 GR2自加 1(结合题目提到的 “转换结果用 ASCH码表示 ”，可以了解到 GR2的用途，因为 48正好是ASCII码的 “0”，自加就变成 “1”了，所以 GR2是统计 GR0中 (WDT+GR1)的个数并把它转化为 ASCII 码形式 )。 然后再转向 LOOP3 执行，这样又回到了前面比较。在 已知的语句中并没有对GR0， GR1进行变动，所以 (2)中一定是对这 2个寄存器值的改变，不然这段循环就成了死循环了。结合 “LEAGR2， 1， GR2”的功能，可知 (2)
37、应是对 GR0自减一个 (WDT+GR1)，即 SUB GR0， WDT， GR1。 程序分析到这里，可以了解到 NEXT标号后的语句是为下一步的统计做准备，即首先保存上一步已统计的 “10000”的个数，再为统计 “1000”的个数，为寄存器置初始值，程序已有 “LEA GR1， 1， GR1”，它能使 WDT+GR”指向 1000，所以 (3)空要完成的功能是 把 “10000”的个数放到指定的位置，又因为题目中提到 “转换结果用 ASCII码表示，并从高位至低位依次存放在首地址为 BTASC的连续 5个内存单元中 ”，所以 (3)空应填 ST GR2， BTASC， GR1。 接下来执行
38、 “LEAGR2， -4， GR1”GR1中存的是偏移量。当统计万位时， GR1为 0；当统计千位时， GRl为 1，要 (GR1)-4 为 0，即 GR1为 4，应是统计个位数字。所以 (4)和 (5)空是统计个位数字，其实这点在程序注释部分也有提及。 那么如何利用已知数据，且用 2步完成功能呢 ?这里注意到一个 重要寄存器GR0。 GR0中现存的数就是个位数了，因为通过上面的几次循环， GR0中高位都被减掉了，所以现在只需把 GR0加上一个 48，然后再存入 (BTASC+4)内存空间即可。其实把 GR0加 48的方法很多，但是一定要注意一个问题，不能用 LEA GR0， 48， GR0，
39、因为 GR0寄存器是不能用变址寻址的。又因为程序中用到了C48，但一直没有语句用到过，所以用 ADD GR0， C48是最合适的。至此 (5)空毫无疑问填 ST GR0， BTASC， GR1。 最后就剩 (1)了。当万位为 0时，就可以执行 “JPZ LOOP2”后面的一段程序了，“ST GR3， BTASC， GR1”是把 “0”存入 BTASC+GR1位置。接下来的 3条语句都已经很明显了，与程序的倒数第 3， 4， 5条语句完成同样的功能，即判断是否已经处理到个位了，如果是，则直接转到 LAST进行个位处理，所以 (1)空应填 JMP LAST。 二、选答题（共 3道大题，每道大题 1
40、5分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 11 【正确答案】 (1)p & p- data !=e或 p&(*p).data! e (2)p- Lchild或 (*P).Lchild (3)s- Rchild或 (*s).Rchild (4)p- Lchild或 (*p).Lchild (5)p=pp- Lchild或 p=(*PP).Lchild 【试题解析】 本程序的功能是删除二叉查找树的一个结点。二叉查找树又称二叉排序树 (binary sort tree)。一棵二叉查找树或者是一棵空树，应满足以下递归条件： 查找树的左、右子树
41、各是一棵查找树。 若查找树的左子树非空，则其左子树上的各结点值均小于根结点的值。 若查找树的右子树非空，则 其右子树上的各结点值均大于根结点的值。 例如，图 4-8就是一棵二叉查找树。 题目中对怎样删除结点做了比较详细的说明。 第一种情况是删除叶子结点。叶子结点可以直接删除，这点很好理解，因为叶子结点删除后并不会打乱查找树的顺序，也就是说把图 4-8中的 “20”结点删除，剩下的还是一棵查找树。 第二种情况是删除只有 1个子结点的结点，只需把其子结点代替父结点即可，也就是说若要删除图 4-8中的 “56”结点，只需把 “51”移至 “56”位置即可，若 “51”下有子树，子树结构不变。 第三种
42、情况要复杂一点，要用到二叉查找树的一 些性质，就是结点右子树的所有结点都大于根结点，左子树所有结点都小于根结点。所以，当删除有左右子树的结点时，要在左子树找最大的结点来替换被删结点。也就是说若要删除图 4-8中的 “89”结点，首先要把 “56”搬到 “89”的位置，然后用第二种情况规则，把 “51”调整到原来 56的位置。 以下具体分析程序。 第一句是变量的声明以及赋初值， p指向二叉查找树的根。接下来是一个循环，从注释部分可以知道，此循环的功能是查找键值为 e的结点。循环内有判断条件，当 e p data 时，进入左子树查找，否则到右子树中查找。很明显没有 关于找到结点的处理代码，也就是说
43、循环内部只处理了没找到结点的情况，所以循环条件应是当找到键值为 e的结点时退出循环。同时应注意一个隐含的限制条件，就是当 p=NULL时，表示已经查找完毕，也不用进入循环了。所以 (1)空应填 p & p- data !=e。 接下来的 if程序段是处理第 种情况的。由循环中的 “s=sRchild； ”可以看出， s用在要删结点的左子树中查找键值最大的结点。所以 s的初值应是要删除结点的左子结点。所以， (2)空应填 p- Lchild。 结合前面提到的对第 条规则的描述以及二叉查找树的规 则可知，要找的结点 s 应是左子树最右的结点，即右子结点为 NULL 的结点。所以 (3)空应填 S-
44、 Rchild。 接着对 、 处理。这里并没有把 、 处理分开进行，而是合在一起进行处理。这里引入了一个中间变量 c，用 c来存储用于替换 p 的结点。 现在分析怎样的条件可以使这 2种情况合在一起。因为当要删除的结点为叶子结点时， p- Lchild与 p- Rchild 都为 NULL；当要删除的结点有 1个子结点时，如果有左子结点，则 p- Rchild 为NULL；如果有右子结点，则 p- Lchild为 NULL。所以当 p- Lchild不为NULL 时，说明是第二种情况， p结点含左子结点， c=p- Lchild。当 p- Lchild为 NULL 时，说明有 2种可能：第一，
45、 p- Rchild 也为 NULL，则 p是叶子结点；第二， p- Rchild不为 NULL，则 P是有右子结点的结点。但这 2种情况都可以用 c=p- Rchild，因为当 p 是叶子结点的时候用 NULL 代替 p的位置即可，所以 (4)空应填 p- Lchild。在程序中很多地方都用到了变量 pp。 pp一直指向的是p 结点的前一个结点，即 p 的父结点，所以 (5)空的作用是判断 p是其父结点的左子结点还 是右子结点，即 (5)空应填 pp- Lchild=p。 12 【正确答案】 (1)class Array T (2)new TiRsz * iCsz (3)throwe(注意：
46、 throw后可以填写任意的字符常数 ) (4)tBody.iCurrentRow=i (5)tBody(iRsz， iCsz) 【试题解析】 程序中使用了类模板和友元。首先简单地介绍这 2个概念。 模板可以实现逻辑相同、数据类型不同的程序代码的复制，模板机制可以减轻编程和维护的工作量和难度。模板可以分为函数模板和类模 板，类模板的一般定义形式 template类型形参表 class 类名 类声明体 在所有出现类模板的地方不能直接用类名表示，需要加上 类型形参表 )。 友元是一种定义在类外部的普通函数或类，但它需要在类体内进行说明，为了与该类的成员函数加以区别，说明时在前面加关键字 frien
47、d。友元不是成员函数，但是它可以访问类中的私有成员。友元的作用在于提高程序的运行效率，但是它破坏了类的封装性和隐藏性，使得非成员函数可以访问类的私有成员。 友元可以是一个函数，该函数被称为友元函数；友元也可以是一 个类，该类被称为友元类。 本题中， (1)空的前面是友元关键词 friend，但程序中没有独立的函数，所以只能是另一个模板类 Array，所以 (1)空应填 class Array T。 在类模板 ArrayBody的定义中，声明了成员变量 “T tpBody”，且在析构函数中有 “deletetpBody”，因为在 C+中， delete 总是和 new成对出现，所以 (2)空应该
48、使用 new 对 tpBody 进行初始化。通过 return tpBodyiCurrentRow * iColumns+j行，可知该题 中采用一维数组来模拟二维数组的创建。在构造函数有 2个参数，分别为行数和列数，所以 (2)空应填 new TiRsz*iCsz。 (3)空的前后有 try.和 catch.语句序列，这是 C+中典型的异常处理搭配语句。 因为 (3)空前面已做处理，当有行下标越界时，置 row_error=True；当有列下标越界时，置 col_error=True。 (3)空前面的判断是“row_error=True|column_error= True”，即只要有行下标越界或是列下标越界就执行 (3)空 。错误处理语句早已写好，放在 catch 中。 catch 是当正常程序段发生异常时才执行的，并且这里指明了是 catch (char)，所以只要在 (3)空处抛出一个char异常，即可进行错误处理。所以 (3)空应填 throwe，
