2004上半年软件设计师考试真题及答案-下午卷.doc

《2004上半年软件设计师考试真题及答案-下午卷.doc》由会员分享，可在线阅读，更多相关《2004上半年软件设计师考试真题及答案-下午卷.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2004上半年软件设计师考试真题及答案-下午卷试题一 阅读下列说明和数据流图，回答问题1至问题4，将解答填入答题纸的对应栏内。 说明 某基于微处理器的住宅安全系统，使用传感器(如红外探头、摄像头等)来检测各种意外情况，如非法进入、火警、水灾等。 房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等)，也可以在系统运行时修改配置，通过录像机和电视机监控与系统连接的所有传感器，并通过控制面板上的键盘与系统进行信息交互。在安装过程中，系统给每个传感器赋予一个编号(即 id)和类型，并设置房主密码以启动和关闭系统，设置传感器事件发生时应自动拨出电话号码。当系统检测到一个传感器事件时，就激

2、活警报，拨出预置的电话号码，并报告关于位置和检测到事件的性质等信息。 数据流图4-1 1、问题1 数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么? 数据流图4-22、问题2 数据流图4-2(住宅安全系统第0层DFD图)中的数据存储“配置信息”会影响图中的哪些加工? 数据流图4-3 3、问题3 将数据流图4-3(加工4的细化图)中的数据流补充完整，并指明加工名称、数据流的方向 (输入/输出)和数据流名称。 4、问题4 试说明逻辑数据流图(logical data flow diagram)和物理数据流图(physical data flow diagram)之间的主要差别。试题二阅读下

3、列说明和算法，回答问题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 将栈stack置空，置EOF为False chnextch()； while(not EOF. kkind(ch)

4、； 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；显示列号col cndwhile endif 为了识别更多种类的括号，对算法2-1加以改进后得到算法2-2。算法2-2能

5、够识别圆括号，方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kinnd(char ch)的参数及其对应的返回值如表4-2所示。 表4-2 函数的参数及其返回值 算法2-2 将栈stack置空，置EOF为False chnextch()； while(not EOF. kkind(ch)； if(k0) if( 判断条件1 ) push( (5) )；push( (6) )；push( (7) )； elseif( 判断条件2 and 判断条件3 ) pop()；pop()；pop()； else 显示错误信息(缺少对应左括号或右括号)； 显示行号row；显示列号col； endif

6、 endif chnexteh()； endwhile if(not empty() 显示错误信息(缺少对应左括号或右括号)； while(not empty() pop()；rowpop()；colpop()； 显示行号row；显示列号col； endwhile endif5、问题1 试将算法2-1)和算法2-2中(1)(7)处补充完整。问题2 从下面的选项中选择相应的判断逻辑填补算法2-2中的“判断条件1”至“判断条件 3”。注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。 (a)字符是括号(b)字符是左括号(c)字符是右括号(d)栈空(e)栈不空 (f)栈顶元素

7、表示的是与当前字符匹配的左括号 (g)栈顶元素表示的是与当前字符匹配的右括号试题三阅读下列说明以及图4-4和图4-5，回答问题1、问题2和问题3，将解答填入答题纸的对应栏内。 说明 某电话公司决定开发一个管理所有客户信息的交互式网络系统。系统的功能如下。 1浏览客户信息：任何使用因特网的用户都可以浏览电话公司所有的客户信息(包括姓名、住址、电话号码等)。 2登录：电话公司授予每个客户一个账号。拥有授权账号的客户，可以使用系统提供的页面设置个人密码，并使用该账号和密码向系统注册。 3修改个人信息：客户向系统注册后，可以发送电子邮件或者使用系统提供的页面，对个人信息进行修改。 4删除客户信息：只有

8、公司的管理人员才能删除不再接受公司服务的客户的信息。系统采用面向对象方法进行开发，在开发过程中确定的类如表4-3所示。 表4-3 开发过程中确定的类 图4-4 图4-5 6、问题1 在需求分析阶段，采用UML的用例图(use case diagram)描述系统功能需求，如图4-4所示。指出图中的A,B,C和D分别是哪个用例?7、问题2 在UML中，重复度(multiplicity)定义了某个类的一个实例可以与另一个类的多个实例相关联。通常把它写成一个表示取值范围的表达式或者一个具体的值。例如，图4-5中的类InternetClient和CustomerList，InternetClient端的

9、“0.*”表示：1个 CustomerList的实例可以与0个或多个InternetClient的实例相关联；CustomerList端的“1”表示：1个InternetClient的实例只能与1个CustomerList的实例相关。 指出图4-5中(1)(4)处的重复度分别为多少?8、问题3 类通常不会单独存在，因此当对系统建模时，不仅要识别出类，还必须对类之间的相互关系建模。在面向对象建模中，提供了4种关系：依赖(dependency)、概括(generaliza tion)、关联(association)和聚集(aggregation)。分别说明这4种关系的含义，并说明关联和聚集之间的主

10、要区别。试题四9、程序4 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 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

11、C48 DC 48 WDT DC 10000 DC 1000 DC 100 DC 10 BTASC DS 5 DATA DC #FA59H END试题五10、函数5 int DeleteNode(Bitree *r，int e) Bitree p=* r，pp，s，c； while( (1) )/ * 从树根结点出发查找键值为e的结点 * / ppp； if(epdata)ppLchild； else ppRchild if(! p)return-1；/ * 查找失败 * / if(p-Lchild & p-Rchild)/ * 处理情况 * / s= (2) ；pp=p； while( (3

12、) )pp=s；s=s-Rchild； p-dara=s-data；P=s； / * 处理情况、 * / if( (4) )c=p-Lchild； else c=p-Rchild if(p=*r) *rc； else if( (5) )pp-Lchild=c； else pp-Rchild=c； free(p)； return 0； 试题六11、程序6 #includeioStream.h templateclass Tclass Array； templateclass Tclass ArrayBody friend (1) ； T* tpBody； int iRows，iCurrentRo

13、w； ArrayBOdy(int iRsz，int iCsz) tpBody= (2) ； iRows=iRsz，iColumns=iCsz；iCurrentRow=-1； public： T& operator(int j) bool row_error，column_error； row_error=column_error=false； try if(iCurrentRow0|iCurrentRowiRows) row_error=； if(j0| jiColumns column_error=； if(row_error=true | column_error=true) (3) ；

14、eatch(char) if(row error=true) cerr“行下标越界“iCurrentRow”； if(column error=true) cerr“列下标越界“j”； cout“n”； return tpBodyiCurrentRow * iColumns+j； ArrayBody()deleretpBody； ； templateclass Tclass Array ArrayBodyT tBody； public： ArrayBodyT & operator(int i) (4) ； return tBody； ； void main() Arrayint a1(10，2

15、0)； Arraydouble a2(3，5)； int b1； double b2； b1=a1-510； / * 有越界提示：行下标越界-5 * / b1=a11015； / * 有越界提示：行下标越界10 * / b1=a114； / * 没有越界提示 * / b2=a226； / * 有越界提示：列下标越界6 * / b2=a21020； / * 有越界提示：行下标越界10列下标越界20 * / b2=a214； / * 没有越界提示 * / 答案:试题一1、A：传感器；B：报警器试题1分析 本题是一道分层数据流图的题目。解答此类问题最关键的一点就是要细心，把题目看清，不要丢掉任何一个

16、条件。另外解题有一定的技巧，从一些常规的入口作为突破口，会事半功倍。现在就利用分层数据流图的数据流的平衡原则(即父图和子图(加工图)的一致性)来解题。 子图是其父图中某一部分内部的细节图(加工图)。它们的输入输出数据流应该保持一致。如同看到地上有只蚂蚁有6条细细的腿，中间是一个小黑点，要看得更清楚一些就拿放大镜看。这时能看到它的头、触角、身体和比较粗的腿，但是看到的一定还是6条腿，不是7条，也不是3条。子图也是如此，在上一级中有几个数据流，它的子图也一定有同样的数据流，而且它们的输送方向是一致的(也就是说原图有3条进的数据流，2条出的数据流，子图同样也是)。 用这条原则可以轻松地解决问题3。在

17、0层图中，“4监控传感器”模块有1条输入数据流“传感器状态”和3条输出数据流“电话拨号”、“传感器数据”和“告警类型”。在加工4的细化图中，仅看到了输出数据流“告警类型”，所以知道此加工图少了“传感器状态”、“电话拨号”、“传感器数据”这3条数据流。加工4的结构非常清晰，所以只需把这 3条数据流对号入座即可，“电话拨号”应是“4.5拨号”的输出数据流；“传感器状态”应是作为“4.4读传感器”处理的输入数据流；“传感器数据”应该是经“4.1显示格式”处理过的数据流，所以作为“4.1显示格式”的输出数据流。 问题1 此题和以往试题有所不同。以往都给定了完整正确的顶层图。现在顶层图不完整，可以通过题

18、目说明信息以及顶层图来分析顶层图并解答问题。题目中提到了“房主可以在安装该系统时配置安全监控设备(如传感器，显示器，报警器等)”在顶层图中这3个名词都没有出现，但仔细观察，可以看出“电视机”实际上就是“显示器”。因为它接收TV信号并输出。再看其他的几个实体都和“传感器”“报警器”没有关联。又因为A中输出“传感器状态”到“住宅安全系统”所以A应填“传感器”。B接收“告警类型”，所以应填“报警器”。2、密码处理；4监控传感器；5显示信息和状态首先，毫无疑问“4监控传感器”用到了配置信息文件，这点可以在加工4的细化图中看出。接着，观察。层图，“3密码处理”这个处理是用于检验密码的，且它只有1个输出数

19、据流“检验ID信息”到“显示信息和状态”，没有反馈回来的数据流，所以“检验ID信息”是已经验证通过的用户的信息，用户输入密码应是在“3密码处理”这个环节中进行验证的(因为如果密码验证是在“5显示信息和状态”中进行的，那么从“5显示信息和状态”应有1条不合法用户的数据流反馈到“密码处理”)。所以“密码处理”一定要用到配置信息文件中的用户名和密码。同时由于输出到“5显示信息和状态”的数据流是“检验ID信息”，所以“5显示信息和状态”也用到了配置信息文件。3、 4、物理数据流图关注的是系统中的物理实体，以及一些具体的文档、报告和其他输入输出硬拷贝。物理数据流图用作系统构造和实现的技术性蓝图。 逻辑数

20、据流图强调参与者所做的事情，可以帮助设计者决定需要哪些系统资源；为了运行系统用户必须执行的活动；在系统安装之后如何保护和控制这些系统等。 在逻辑数据流图中说明应该具有哪些加工和数据存储，而不关心这些加工和数据存储是如何实现的；物理数据流图则要说明加工和数据存储是如何实现的。 试题二5、1 (2)col (3)row (4)2 (5)col (6)row (7)k 判断条件1：(b) 判断条件2：(e) 判断条件3：(f)解析 本程序的功能是检查文本文件中的圆括号是否匹配。从提示信息中，可以看出程序不但可以检查出是否有括号匹配错误，而且还知道具体错在哪个括号。由于括号匹配的规则是把最近的左右括号

21、配成一对，所以括号匹配最常用的方法是遇到左括号则入栈，遇到右括号就出栈，出栈的友括号与当前的右括号是匹配的。此算法也不例外。 下面具体分析算法： 首先，把栈置空，置EOF为False，并从文件中读取第一个字符到ch。然后进入循环，循环体执行一次处理一个ch。进入循环，利用kind函数算出ch的类型k，接下来就是一大堆的空了，这个算法本身并不长，但空有这么多，而且比较集中，为解题增加了一定的难度。这里虽然空多，但基本结构却很明显，大致流程如下： 当k等于什么的时候把什么入栈，当k等于什么的时候且栈不为空的时候出栈，如栈为空打印错误信息，如果都不是则读文件下一个字符再次进入循环。 再结合上面提到的

22、算法，可以知道，入栈应是在类型k为1(即ch为左括号时)，出栈应是在类型k为2(即ch为右括号时)。所以(1)空应填1，(4)空应填2。 (2)和(3)到底是把什么压入栈了呢?在(4)下面出栈时，并没有用到栈的内容。在此有些考生理所当然地认为栈中的内容没有什么用，随便压个ch进去了，而且2个都是写的ch。其实从逻辑上就可以推翻这种解答，如果是压的同样的数据，又是在同一位置出栈，算法大可只用个push，pop就可以了。这时继续往后面看，来寻找正确的答案。当看到“rowpop()；colpop()；”时，所有的疑惑可迎刃而解了，应该把row和col压入堆栈!那么row和col谁先谁后呢?由于是先弹

23、出row后弹出col，按栈的后进先出的规则，可知先压入栈的是col，再压入row。所以(2)空填写col，(3)空填写row。 完成算法2-1的分析后，分析算法2-2就比较轻松了。(5)(6)(7)空的答案可直接到后面找到，因为后面有“pop()；row-pop()；colpop()；”所以(5)空应填col，(6)空应填row。 因为判断条件1为真时要人栈，所以判断条件1应是判断字符是否是左括号，如果是就入栈。所以判断条件1选b。 判断条件2和3是联系在一起的，当判断条件2和3都为真时，要进行出栈操作，因此要判断栈是否为空。由此可以得出判断条件2和3中，有一个是用来判断栈是否为空的。 备选答

24、案的一些选项给了一些提示，就是用判断栈顶元素，来确定当前括号是否和栈中压人括号是同一类型的。但前提是左括号类型入了栈，而且要在栈顶，如果(7)空压入的是k，就正好吻合了。所以(7)空应填k，判断括号是否匹配的条件也就可以确定了。如果当前ch是右括号且当前栈顶的左括号(只有左括号入了栈)类型与ch匹配，则匹配成功。因为在题目中有提示“若判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。所以应把“栈不空”作为判断条件2，“栈顶元素表示的是与当前字符匹配的左括号”作为判断条件3。即判断条件2填e，判断条件3填f。试题三6、A：浏览客户信息；B：修改个人信息；C：登录；D：删除客户信息。

25、解析 图4-4是一个UML的用例图。在工程的分析阶段，例图被用来鉴别和划分系统功能，它们把系统分成动作者(actor)和用例。 动作者(actor)表示系统用户能扮演的角色(role)。这些用户可能是人，可能是其他的计算机、一些硬件或者是其他软件系统。惟一的标准是它们必须要在被划分到用例的系统部分以外。它们必须能刺激系统部分，并接收返回。 用例描述了当某个动作者给系统特定的刺激时系统的活动。这些活动被文本描述。它描述了触发用例的刺激的本质，输入和输出到其他活动者，转换输入到输出的活动。用例文本通常也描述每个活动在特殊的活动线时可能的错误，以及系统应采取的补救措施。 了解用例图、动作者、用例的基

26、本概念后，题目就迎刃而解了。图中的网络用户、公司客户、管理人员都是动作者。题目说明中提到了系统有4个功能：浏览客户信息、登录、修改个人信息、删除客户信息。这也就是4个用例。现在只需把他们对号入座即可。根据题目说明，可以知道任何使用Internet的网络用户都可以浏览电话公司所有的客户信息，在图中符合这一条件的只有A，所以A应填浏览客户信息。因为只有公司的管理人员才能删除不再接受公司服务的客户的信息。所以D应填删除客户信息。 剩下只有登录和修改个人信息2个用例了，那么究竟是B填登录还是修改呢?先介绍包含和扩展的概念。 2个用例之间的关系可以主要概括为2种情况：一种是用于重用的包含关系，用构造型i

27、nclude表示；另一种是用于分离出不同的行为，用构造型extend表示。 (1)包含关系：如果可以从2个或2个以上的原始用例中提取公共行为，或者发现能够使用一个构件来实现某一个用例的部分功能时，应该使用包含关系来表示它们。示意图如图4-6所示。 (2)扩展关系：如果一个用例明显地混合了2种或2种以上的不同场景，即根据情况可能发生多种事情。可以断定将这个用例分为一个主用例和一个或多个辅用例描述可能更加清晰。示意图如图4-7所示。 因为要先登录才能修改信息，显然B应填修改个人信息，C应填登录。 在UML中重复度(multiplicity)又称多重性，多重性表示为一个整数范围n.m，整数n定义所连

28、接的最少对象的数目，而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建立业务模型时，可以把业务人员看作是系统中的角色或者类。在建立抽象模型时，很少有类会单独存在，大多数都将会以某种方式彼此通信，因此还需要描述这些

29、类之间的关系。关系是事物间的连接，在UML中，有几个很重要的关系。 (1)依赖关系 有2个元素A和B，如果元素A的变化会引起元素B的变化，则称元素B依赖(depend ency)于元素A。 在类中，依赖关系有多种表现形式，例如，一个类向另一个类发消息；一个类是另一个类的成员；一个类是另一个类的某个操作参数等。 (2)概括关系 概括关系(generalization)，也称为泛化关系，描述了一般事物与该事物中的特殊种类之间的关系，也就是父类与子类之间的关系。继承关系是泛化关系的反关系，也就是说子类是从父类中继承的，而父类则是子类的泛化。在UML中，对泛化关系有3个要求： 子类应与父类完全一致，父

30、类所具有的关联、属性和操作，子类都应具有。 子类中除了与父类一致的信息外，还包括额外的信息。 可以使用子父类实例的地方，也可以使用子类实例。 (3)关联关系 关联(association)表示2个类的实例之间存在的某种语义上的联系。例如，一个老师为某个学校工作，一个学校有多间教室。可以认为老师和学校、学校和教室之间存在着关联关系。 关联关系为类之间的通信提供了一种方式，它是所有关系中最通用、语义最弱的。关联关系通常可以再细分成以下几种。 聚集关系：聚集关系(aggregation)是关联关系的特例。它表示一种整体和部分的关系。如一个电话机包含一个话筒，一个计算机包含显示器，键盘和主机等都是聚合

31、关系的例子。 组合关系：如果聚集关系中的表示“部分”的类的存在与表示“整体”的类有着紧密的关系，例如，“公司”与“部门”之间的关系，那么就应该使用组合关系来表示。7、1 (2)0.* (3)0.1 (4)0.1 8、4种关系的含义如下： 依赖表示类之间的使用关系。 概括表示一般类和特殊类之间的关系。 关联和聚集都表示实例之间的结构关系。 关联和聚集的区别：关联指明一个类的对象与另一个类的对象间的联系；2个类之间的关联表示了2个同等地位类之间的结构关系，这2个类在概念上是同级别的。聚集是一种特殊的关联，它表示整体与部分的关系。 试题四9、JMP LAST (2)SUB GR0，WDT，GR1 (

32、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的偏移地址)，比较GR0和WDT中的数据的大小。 WDT开始的5个连续空间的数据分别为“10000，1000，100，10，5”。因为当前的 GR1为0，所以WDT对应的为“10000”，当GR0大于等于(WDT)时转LOOP2，小于 (WDT)则继续往下执行。其实在

33、这种情况下，最好的分析方法就是把DATA中的数据自己手动转成十进制，然后把数据代到程序里，跟踪程序的执行，这样能最快的了解程序的执行流程和处理方法，同时也做了验证工作。 因为#FA59H转成十进制是64089。所以现在程序转到LOOP2执行。GR2置48，单从这里无法了解GR2是什么用途。比较GR0与(WDT+GR1)的大小，GR0比10000大，所以执行(2)，再执行“LEAGR2，1，GR2”即把GR2自加1(结合题目提到的“转换结果用ASCH码表示”，可以了解到GR2的用途，因为48正好是ASCII码的“0”，自加就变成“1”了，所以GR2是统计GR0中(WDT+GR1)的个数并把它转化

34、为ASCII码形式)。 然后再转向LOOP3执行，这样又回到了前面比较。在已知的语句中并没有对GR0， GR1进行变动，所以(2)中一定是对这2个寄存器值的改变，不然这段循环就成了死循环了。结合“LEAGR2，1，GR2”的功能，可知(2)应是对GR0自减一个(WDT+GR1)，即 SUB GR0，WDT，GR1。 程序分析到这里，可以了解到NEXT标号后的语句是为下一步的统计做准备，即首先保存上一步已统计的“10000”的个数，再为统计“1000”的个数，为寄存器置初始值，程序已有“LEA GR1，1，GR1”，它能使WDT+GR”指向1000，所以(3)空要完成的功能是把“10000”的个

35、数放到指定的位置，又因为题目中提到“转换结果用ASCII码表示，并从高位至低位依次存放在首地址为BTASC的连续5个内存单元中”，所以(3)空应填ST GR2，BTASC，GR1。 接下来执行“LEAGR2，-4，GR1”GR1中存的是偏移量。当统计万位时，GR1为0；当统计千位时，GRl为1，要(GR1)-4为0，即GR1为4，应是统计个位数字。所以(4)和 (5)空是统计个位数字，其实这点在程序注释部分也有提及。 那么如何利用已知数据，且用2步完成功能呢?这里注意到一个重要寄存器GR0。 GR0中现存的数就是个位数了，因为通过上面的几次循环，GR0中高位都被减掉了，所以现在只需把GR0加上

36、一个48，然后再存入(BTASC+4)内存空间即可。其实把GR0加 48的方法很多，但是一定要注意一个问题，不能用LEA GR0，48，GR0，因为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条语句完成同样的功能，即判断是否已经处理到个位了，如果是，则

37、直接转到LAST进行个位处理，所以(1)空应填JMP LAST。试题五10、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)。一棵二叉查找树或者是一棵空树，应满足以下递归条件： 查找树的左、右子树各是一棵查找树。 若查找树的左子树非空，则其左子树上的各结点值均小于根结点的值。 若查

38、找树的右子树非空，则其右子树上的各结点值均大于根结点的值。 例如，图4-8就是一棵二叉查找树。 题目中对怎样删除结点做了比较详细的说明。 第一种情况是删除叶子结点。叶子结点可以直接删除，这点很好理解，因为叶子结点删除后并不会打乱查找树的顺序，也就是说把图4-8中的“20”结点删除，剩下的还是一棵查找树。 第二种情况是删除只有1个子结点的结点，只需把其子结点代替父结点即可，也就是说若要删除图4-8中的“56”结点，只需把“51”移至“56”位置即可，若“51”下有子树，子树结构不变。 第三种情况要复杂一点，要用到二叉查找树的一些性质，就是结点右子树的所有结点都大于根结点，左子树所有结点都小于根结点。所以，当删除有左右子树的结点时，要在左子树找最大的结点来替换被删结点。也就是说若要删除图4-8中的“89”结点，首先要把“56”搬到“89”的位置，然后用第二种情况规则，把“51”调整到原来56的位置。 以下具体分析程序。 第一句是变量的声明以及赋初值，p指向二叉查找树的根。接下来是一个循环，从注释部分可以知道，此循