《2022年云南软件水平考试考试模拟卷（9）.docx》由会员分享，可在线阅读，更多相关《2022年云南软件水平考试考试模拟卷（9）.docx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022年云南软件水平考试考试模拟卷（9）本卷共分为2大题50小题，作答时间为180分钟，总分100分，60分及格。一、单项选择题（共25题，每题2分。每题的备选项中，只有一个最符合题意） 1.为了防止 (54) ，电子商务交易必须具备抗抵赖性。A一个实体假装成另一个实体B参与此交易的一方否认曾经发生过此次交易C他人对数据进行非授权的修改、破坏D信息从被监视的通信过程中泄漏出去。 2.Kerberos是一种对服务请求进行认证的方法，下列 (19) 不是Kerberos的设计目标。A授权B加密C认证D记账 3.白盒测试方法一般适合用于（）测试。A单元B系统C集成D确认4.假设高速缓存Cache工
2、作速度为主存的5倍，且Cache被访问命中的概率为90%，则采用Cache后，能使整个存储系统获得加速比Sp为（）。A3.57B5C4.21D5.175.所谓信息系统集成是指（）。A计算机网络系统的安装调试B计算机应用系统的部署和实施C计算机信息系统的设计、研发、实施和服务D计算机应用系统工程和网络系统工程的总体策划、设计、开发、实施、服务及保障6.（）是国家信息化体系的六大要素。A数据库，国家信息网络，信息技术应用，信息技术教育和培训，信息化人才，信息化政策、法规和标准B信息资源，国家信息网络，信息技术应用，信息技术和产业，信息化人才，信息化政策、法规和标准C地理信息系统，国家信息网络，工业
3、与信息化，软件技术与服务，信息化人才，信息化政策、法规和标准D信息资源，国家信息网络，工业与信息化，信息产业与服务业，信息化人才，信息化政策、法规和标准7.以下关于计算机信息系统集成企业资质的说法正确的是（）。A计算机信息系统集成企业资质共分四个级别，其中第四级为最高级B该资质由授权的认证机构进行评审和批准C目前，计算机信息系统集成企业资质证书有效期为3年D申报二级资质的企业，其具有项目经理资质的人员数目应不少于20名8.信息系统工程监理活动的主要内容被概括为“四控、三管、一协调”，其中“三管”是指（）。A整体管理、范围管理和安全管理B范围管理、进度管理和合同管理C进度管理、合同管理和信息管理
4、D合同管理、信息管理和安全管理9.与客户机/服务器（Client/Server，C/S）架构相比，浏览器朋艮务器（Browser/Server，B/S）架构的最大优点是（）。A具有强大的数据操作和事务处理能力B部署和维护方便、易于扩展C适用于分布式系统，支持多层应用架构D将应用一分为二，允许网络分布操作10.（）的目的是评价项目产品，以确定其对使用意图的适合性，表明产品是否满足规范说明并遵从标准。AIT审计B技术评审C管理评审D走查11.按照规范的文档管理机制，程序流程图必须在（）两个阶段内完成。A需求分析、概要设计B概要设计、详细设计C详细设计、实现阶段D实现阶段、测试阶段12.信息系统的软
5、件需求说明书是需求分析阶段最后的成果之一，（）不是软件需求说明书应包含的内容。A数据描述B功能描述C系统结构描述D性能描述13.在GB/T 14394计算机软件可靠性和可维护性管理标准中，（）不是详细设计评审的内容。A各单元可靠性和可维护性目标B可靠性和可维护性设计C测试文件、软件开发工具D测试原理、要求、文件和工具14.（）不是虚拟局域网VLAN的优点。A有效地共享网络资源B简化网络管理C链路聚合D简化网络结构、保护网络投资、提高网络安全性15.UML 2.0支持13种图，它们可以分成两大类：结构图和行为图。（）说法不正确。A部署图是行为图B顺序图是行为图C用例图是行为图D构件图是结构图16
6、.以太网100Base-TX标准规定的传输介质是（）。A3类UTPB5类UTPC单模光纤D多模光纤17.通过局域网接入因特网，图中箭头所指的两个设备是（）。A二层交换机B路由器C网桥D集线器18.在铺设活动地板的设备间内，应对活动地板进行专门检查，地板板块铺设严密坚固，符合安装要求，每平米水平误差应不大于（）。A1mmB2mmC3mmD4mm19.在（）中，项目经理的权力最小。A强矩阵型组织B平衡矩阵组织C弱矩阵型组织D项目型组织20.矩阵型组织的缺点不包括（）。A管理成本增加B员工缺乏事业上的连续性和保障C多头领导D资源分配与项目优先的问题产生冲突21.定义清晰的项目目标将最有利于（）。A提
7、供一个开放的工作环境B及时解决问题C提供项目数据以利决策D提供定义项目成功与否的标准22.信息系统的安全属性包括（）和不可抵赖性。A保密性、完整性、可用性B符合性、完整性、可用性C保密性、完整性、可靠性D保密性、可用性、可维护性23.（）反映了信息系统集成项目的技术过程和管理过程的正确顺序。A制定业务发展计划、实施项目、项目需求分析B制定业务发展计划、项目需求分析、制定项目管理计划C制定业务发展计划、制定项目管理计划、项目需求分析D制定项目管理计划、项目需求分析、制定业务发展计划24.制定项目计划时，首先应关注的是项目（）。A范围说明书B工作分解结构C风险管理计划D质量计划25.德尔菲法区别于
8、其他专家预测法的明显特点是（）。A引入了权重参数B多次有控制的反馈C专家之间互相取长补短D至少经过4轮预测二、多项选择题（共25题，每题2分。每题的备选项中，有多个符合题意） 1.试题四（15 分，每空3 分） 阅读以下说明和C 语言函数，将应填入 （n） 处的字句写在答题纸的对应栏内。说明 假设一个剧场有N*N 个座位，顾客买票时可以提出任意有效的座号请求。下面用二维数组aNN模拟剧场中的座位，aij等于0 表示第i 排第j 列(0i,jN-1)的票尚未售出。函数int Find(int aN,int R,int *row,int *col)的功能是：在部分票已售出的情况下，找出剧场中的R*
9、R 个空座位，要求这些座位的排列形成一个正方形。若找到满足要求的一个座位排列，则函数返回1，并算出该正方形左上角的行、列号；若未找到，返回0。 例如，一个77 个座位的剧场如下图(a)所示，已售出部分座位的剧场如下图(b)所示，图中阴影部分表示已售出的座位，从图(b)中找出的33 正方形空座位如图(c)中斜线区所示。函数int Find(int aN,int R,int *row,int *col) int i,j,k,c,t; int FOUND = 0; for(i=0; !FOUND & i = R) /*找到第i 排连续的R 个空座位*/ for(c = 0; c n ) m = m
10、- n; else n = n - m; (2) ;函数2.2 说明 函数long fun2(char *str)的功能是：自左至右顺序取出非空字符串str 中的数字字符形成一个十进制整数(最多8 位)。 例如，若字符串str 的值为“f3g8d5.ji2e3p12fkp”，则函数返回值为3852312。函数2.2long fun2(char *str) int i = 0; long k = 0; char *p = str; while ( *p != 0 & (3) ) if ( *p = 0 & *p (11) 加密会话密钥，接收方使用 (12) 解密会话密钥。为保证电子邮件信息的完整
11、性和不可抵赖性，发送方需要使用一定的算法获取邮件信息摘要，并使用 (13) 加密摘要信息，接收方使用 (14) 解密摘要信息，验证发送方身份。 (11)(14)的各选答案如下； A发送方的公钥 B发送方的私钥 C接收方的公钥 D接收方的私钥 4. 1该商务网站选择SET支付模型，请根据SET支付模型的工作流程，将图6-5中 (7)(9)实体补充完整。 图6-5 2SET支付模型中，利用 (10) 技术可以保证商家不能看到客户的支付信息。 A单向加密 B双重数字签名 C数字证书 D数字摘要 5. 贸易活动中，相应的格式单证需经过一系列转换，图6-6是格式单证转换示意图，请填写(1)(3)处相应转
12、换软件的名称。 图6-6 6. 1标准化是实现EDI互通及互联的前提和基础。目前，在EDI标准上， (8) 已被国际标准化组织(ISO)接收为国际标准。 2EDI报文的要素是： (9) 、 (10) 、 (11) 。 7. 请根据EDI的工作流程，填写图6-7中(4)(7)的单证名称或单证流向单位名称。 图6-7 8. 已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A5，10， 20，15，25，30，集合B5，15，35，25，如图(a)所示，运算完成后的结果如图(b)所示。 链表结点的结构
13、类型定义如下： typedef struct Node ElemType elem； struct Node *next； NodeType； void Difference(NodeType *LA，NodeType *LB) NodeType *pa， *pb， *pre， *q； preNULL； (1) ； while (pa) pbLB； while( (2) ) pbpb-next； if( (3) ) if(!pre) *LA (4) ； else (5) pa-next； q pa； papa-next； free(q)； else (6) ； papa-next； 9. 已知
14、某类库开发商提供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示。其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。 当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如上图中的类MyApplication和类MyDocument，并分别实现Application和 Document类中的某些方法。 已知Applicat
15、ion类中的openDocument方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示： 1首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回； 2创建文档对象； 3通过文档对象打开文档； 4通过文档对象读取文档信息； 5将文档对象加入到Application的文档对象集合中。 #includeiostream #includevector using namespace std； class Document public： void save()/*存储文档数据，此处代码省略*/) void open(string doc
16、Name) /*打开文档，此处代码省略*/) void close() /*关闭文档，此处代码省略*/) virtual void read(string docName) 0； ； class Appplication private： vector (1) docs； /*文档对象集合*/ public： bool canOpenDocument(string docName) /*判断是否可以打开指定文档，返回真值时表示可以打开， 返回假值表示不可打开，此处代码省略*/ void addDocument(Document * aDocument) /*将文档对象添加到文档对象集合中*/
17、docs.push_back( (2) )； virtual Document * doCreateDocument()0；/*创建一个文档对象*/ void openDocument(string docName)/*打开文档*/ if ( (3) ) cout“文档无法打开!”endl； return； (4) adoc (5) ； (6) ； (7) ； (8) ； ； 10. 已知某类库开发商捉供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示，其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。A
18、pplication类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。 当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如上图中的类MyApplication和类MyDocument，并分别实现Application和 Document类中的某些方法。 已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示： 1首先检查文档是否能够被打开，若不能打开，则给出出错信息并返
19、回； 2创建文档对象； 3通过文档对象打开文档； 4通过文档对象读取文档信息； 5将文档对象加入到Application的文档对象集合中。 abstract class Document public void save()/*存储文档数据，此处代码省略*/ ) public void open(String docName) /*打开文档，此处代码省略*/) public void close() /*关闭文档，此处代码省略*/) public abstract void read(String docName)； ； abstract class Appplication private
20、Vector (1) docs； /*文档对象集合*/ public boolean canOpenDocument(String docName) /*判断是否可以打开指定文档，返回真值时表示可以打开，返回假值表示不可打开，此处代码省略*/ public void addDocument(Document aDocument) /*将文档对象添加到文档对象集合中*/ docsadd( (2) )； public abstract Document doCreateDocument()；/*创建一个文档对象*/ public void openDocument(String docName)/
21、*打开文档*/ if ( (3) ) Systemoutprintln(“文档无法打开!”)； return； (4) adoc (5) ； (6) ； (7) ； (8) ； ； 11.试题一论基于DSSA的软件架构设计与应用 软件架构设计的一个重要课题是如何解决软件重用问题。特定领域软件架构（DomainSpecificSoftwareArchitecture，DSSA）是一种有效实现特定领域软件重用的手段。按照Tracz的说法，DSSA就是一个特定的问题领域中由领域模型、参考需求、参考架构等组成的开发基础架构，其目标就是支持一个特定领域中多个应用的生成。 DSSA的基本活动包括领域分析、
22、领域设计和领域实现。领域分析的主要目的是获得领域模型，领域模型描述领域中系统之间共同的需求，即领域需求；领域设计的主要目标是获得DSSA，DSSA描述领域模型中表示需求的解决方案；领域实现的主要目标是依据领域模型和DSSA开发和组织可重用信息。 请围绕“基于DSSA的软件架构设计与应用”论题，依次从以下三个方面进行论述。 1概要叙述你参与管理和开发的软件项目以及你在其中所承担的主要工作。 2就你所熟悉的领域，请给出针对该特定领域，在基于DSSA的软件设计开发中所涉及的领域模型、参考需求和参考架构以及相应的支持环境或设施。 3具体阐述你参与管理和开发的项目中使用DSSA的情况，包括领域分析、领域
23、设计和领域实现等活动是如何具体实施的，最终实际效果如何。 12.试题二论信息系统建模方法 系统模型在软件开发中扮演着重要的角色。可为已有的系统创建模型，以便更好地理解这些系统；也可以针对待开发的系统创建模型，作为记录业务需求或技术设计的方法。模型是建立信息系统的基础。恰当地运用信息系统建模方法，是成功地进行软件开发的一个关键环节。 请围绕“论信息系统建模方法”论题，依次从以下三个方面进行论述。 1概要叙述你参与管理和开发的信息系统项目以及你在其中所承担的主要工作。 2论述常见的信息系统建模方法的主要内容（包括每种建模方法的核心思想以及所创建的模型）。 3具体阐述你参与管理和开发的项目中选择使用
24、的信息系统建模方法以及选择该方法的原因，给出具体的实施过程和实施效果。 13.试题三论基于REST服务的Web应用系统设计 REST（REpresentationalStateTransfer）是指从几种基于网络的架构风格衍生出来的一种混合架构风格，它是目前互联网的核心架构风格。基于REST服务（RESTfulService）的Web应用系统设计任务主要包括：识别并设计REST风格的服务，采用面向服务的思想进行REST服务集成。采用这种方法设计的Web应用系统能够结合REST风格和面向服务思想的优点，近年来受到了广泛的关注。 请围绕“基于REST服务的Web应用系统设计”论题，依次从以下三个方
25、面进行论述。 1概要叙述你参与实施的Web应用系统开发项目以及你所承担的主要工作。 2简要叙述与传统的Web服务相比，采用REST服务构建的Web应用具有哪些优势和不足。 3阐述你在设计基于REST服务的Web应用系统时遇到了哪些问题，如何解决。 14.试题四论软件可靠性设计与应用 目前在企业中，以软件为核心的产品得到了广泛的应用。随着系统中软件部分比例的不断增加，使得系统对软件的依赖性越来越强，对软件的可靠性要求也越来越高。软件可靠性与其它质量属性一样，是衡量软件架构的重要指标。 软件工程中已有很多比较成熟的设计技术，如结构化设计、模块化设计、自顶向下设计等，这些技术为保障软件的整体质量发挥
26、了重要作用。在此基础上，为了进一步提高软件的可靠性，通常会采用一些特殊的设计技术，即软件可靠性设计技术。 在软件可靠性工程体系中，包含有可靠性模型与预测、可靠性设计和可靠性测试方法等。实践证明，保障软件可靠性最有效、最经济、最重要的手段是在软件设计阶段采取措施进行可靠性控制。 请围绕“软件可靠性设计与应用”论题，依次从以下三个方面进行论述。 1概要叙述你参与实施的软件开发项目以及你所承担的主要工作。 2简要叙述影响软件可靠性的因素有哪些。 3阐述常用的软件可靠性设计技术以及你如何应用到实际项目中，效果如何。 15.试题一 论软件的静态演化和动态演化及其应用 软件演化（Software Evol
27、ution）是指软件在其生命周期内的更新行为和过程。演化是一系列贯穿软件生命周期始终的活动，系统需求改变、功能实现增强、新功能加入、软件架构改变、软件缺陷修复、运行环境改变均要求软件系统能够快速适应变化，具有较强的演化能力。软件静态演化（Static Evolution）和动态演化（Dynamic Evolution）是目前软件演化的两种重要类型。 请围绕“软件的静态演化和动态演化及其应用”论题，依次从以下三个方面进行论述。 1.概要叙述你参与管理和开发的软件项目以及你在其中所担任的主要工作。 2.请分别对软件静态演化和动态演化的特点进行论述，说明两种软件演化类型各自的优缺点及其应用场合，并举
28、例说明各自的常见演化技术手段。 3.具体阐述你参与管理和开发的项目中所进行的软件演化活动的特点、演化的类型，以及所采取的对应演化技术手段，说明具体实施过程以及实际应用的效果。 16.试题二 论数据挖掘技术的应用 随着信息技术的高速发展，各组织机构积累的数据量急剧增长。如何从海量的数据中提取有用的知识成为当务之急。数据挖掘(Data Mining）就是为顺应这种需要应运而生发展起来的数据处理技术，是知识发现的关键步骤。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 请围绕“论数据挖掘技术的应用”论题，
29、依次对以下三个方面进行论述。 1.概要叙述你参与分析和开发的软件项目以及你所担任的主要工作。 2.数据挖掘的主要任务是什么？具体论述你在项目中使用数据挖掘技术所解决的问题。 3.数据挖掘的方法主要有哪些？分析并讨论你所选择的数据挖掘方法，简述其具体实现过程和实际应用效果。 17.试题三 论大规模分布式系统缓存设计策略 大规模分布式系统通常需要利用缓存技术减轻服务器负载、降低网络拥塞、增强系统可扩展性。缓存技术的基本思想是将客户最近经常访问的内容在缓存服务器中存放一个副本，当该内容下次被访问时，不必建立新的数据请求，而是直接由缓存提供。良好的缓存设计，是一个大规模分布式系统能够正常、高效运行的必
30、要前提。在进行大规模分布式系统开发时，必须从一开始就针对应用需求和场景对系统的缓存机制进行全面考虑，设计一个可伸缩的系统缓存架构。 请围绕“大规模分布式系统缓存设计策略”论题，依次从以下三个方面进行论述。 1.概要叙述你参与实施的大规模分布式系统开发项目以及你所担任的主要工作。 2.从不同的用途和应用场景考虑，请详细阐述至少两种常见的缓存工作模式，并说明每种工作模式的适应场景。 3.阐述你在设计大规模分布式系统的缓存机制时遇到了哪些问题，如何解决。 18.试题四 论软件可靠性评价 软件可靠性评价是指选用和建立合适的可靠性数学模型，运用统计技术和其他手段，对软件可靠性测试和系统运行期间的软件失效
31、数据（也可能包含软件生命周期内其他可靠性数据）进行处理，并评估和预测软件可靠性的过程。 软件可靠性评价是软件可靠性活动的重要组成部分，既可在软件开发过程实施，也可针对最终软件系统实施。软件可靠性评价的难点在于软件可靠性模型的选择和软件可靠性数据的收集与处理。 请围绕“软件可靠性评价”论题，依次从以下三个方面进行论述。 1.简要概述你参与实施的软件开发项目以及你承担的主要工作。 2.说明你在项目实施过程中所选择的软件可靠性模型，并论述在软件可靠性模型选择时应该考虑的主要因素。 3.收集软件可靠性数据时经常遇到的问题有哪些？简述你收集软件可靠性数据时所遇到的具体问题及解决的方法。 19.试题七 （
32、共 15 分 ）阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG 和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG 和GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图7-1所示。 采用该设计模式的原因在于：系统解析BMP、GIF与JPEG文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码
33、则仅与操作系统相关。class Matrix /各种格式的文件最终都被转化为像素矩阵/此处代码省略;abstract class ImageImppublic abstract void doPaint(Matrix m); /显示像素矩阵m;class WinImp extends ImageImppublic void doPaint(Matrix m) /*调用windows系统的绘制函数绘制像素矩阵*/ ;class LinuxImp extends ImageImppublic void doPaint(Matrix m)/*调用Linux系统的绘制函数绘制像素矩阵*/;abstra
34、ct class Image public void setImp(ImageImp imp)（1） = imp; public abstract void parseFile(String fileName);protected （2） imp;class BMP extends Imagepublic void parseFile(String fileName)/此处解析BMP文件并获得一个像素矩阵对象m（3） ;/ 显示像素矩阵m;class GIF extends Image/此处代码省略;class JPEG extends Image/此处代码省略;public class ja
35、vaMainpublic static void main(String args)/在windows操作系统上查看demo.bmp图像文件Image image1 = （4） ;ImageImp imageImp1 = （5） ;（6） ;image1.parseFile(demo.bmp);现假设该系统需要支持 10 种格式的图像文件和 5 种操作系统，不考虑类 Matrix 和类javaMain，若采用桥接设计模式则至少需要设计（7）个类。 20.试题六（共15分）阅读下列说明和C+代码，将应填入 （n） 处的字句写在答题纸的对应栏内。现欲实现一个图像浏览系统，要求该系统能够显示BMP、
36、JPEG 和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG 和GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如下图所示。 采用该设计模式的原因在于：系统解析BMP、GIF与JPEG文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。class Matrix /各种格式的文件最终都被转化为像素矩阵/此处代码省略;class ImageImppublic:vir
37、tual void doPaint(Matrix m) = 0; /显示像素矩阵m;class WinImp : public ImageImppublic:void doPaint(Matrix m) /*调用windows系统的绘制函数绘制像素矩阵*/ ;class LinuxImp : public ImageImppublic:void doPaint(Matrix m) /*调用Linux系统的绘制函数绘制像素矩阵*/ ;class Image public:void setImp(ImageImp *imp) （1） = imp;virtual void parseFile(str
38、ing fileName) = 0;protected:（2） *imp;class BMP : public Imagepublic:void parseFile(string fileName)/此处解析BMP 文件并获得一个像素矩阵对象m（3） ;/ 显示像素矩阵m;class GIF : public Image/此处代码省略;class JPEG : public Image/此处代码省略;void main()/在windows操作系统上查看demo.bmp图像文件Image *image1 = （4） ;ImageImp *imageImp1 = （5） ;（6） ;image1
39、-parseFile(demo.bmp);现假设该系统需要支持10种格式的图像文件和5种操作系统，不考虑类Matrix，若采用桥接设计模式则至少需要设计（7）个类。 21.试题五（共 15 分）阅读下列说明和C 函数代码，将应填入 （n） 处的字句写在答题纸的对应栏内。对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BtNodeElemType data; /*结点的数据域，ElemType的具体定义省
40、略*/struct BtNode *lchild,*rchild; /*结点的左、右孩子指针域*/BtNode, *BTree;在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表（简称链栈），其结点类型定义如下：typedef struct StNode /*链栈的结点类型*/BTree elem; /*栈中的元素是指向二叉链表结点的指针*/struct StNode *link;StNode;假设从栈顶到栈底的元素为 en、en-1、e1，则不含头结点的链栈示意图如图5-1所示。 int InOrder(BTree root) /* 实现二叉树的非递
41、归中序遍历 */ BTree ptr; /* ptr用于指向二叉树中的结点 */ StNode *q; /* q暂存链栈中新创建或待删除的结点指针*/ StNode *stacktop = NULL; /* 初始化空栈的栈顶指针stacktop */ ptr = root; /* ptr指向二叉树的根结点 */ while ( （1） | stacktop != NULL) while (ptr != NULL) q = (StNode *)malloc(sizeof(StNode); if (q = NULL) return -1; q-elem = ptr; （2） ; stacktop
42、= q; /*stacktop指向新的栈顶*/ ptr = （3） ; /*进入左子树*/ q = stacktop; （4） ; /*栈顶元素出栈*/ visit(q); /*visit是访问结点的函数，其具体定义省略*/ ptr = （5） ; /*进入右子树*/ free(q); /*释放原栈顶元素的结点空间*/ return 0; /*InOrder*/ 22.试题一阅读下列说明、流程图和算法，将应填入 (n) 处的字句写在答题纸的对应栏内。流程图说明下面的流程图用N-S 盒图形式描述了数组A 中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Ai，并且数组中下标小于i 的元素的值均小于基准数，下标大于i 的元素的值均大于基准数。设数组A 的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4 为基准数的划分过程如下：流程图算法说明将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A,int low,int hig