2003年高级程序员试题

2003年度系统设计师(高级程序员)上午试题•系统中模块的__(l)__不仅意味着作用于系统的小变动将导致行为上的小变化，也意味着规格说明的小变动将影响到一小部分模块。(1)A.可分解性B.保护性C.可理解性D.连续性•下面关于面向对象方法中消息的叙述，不正确的是 (2)__。(2)A.键盘、鼠标、通信端口、网络等设备一有变化，就会产生消息操作系统不断向应用程序发送消息，但应用程序不能向操作系统发送消息应用程序之间可以相互发送消息发送与接收消息的通信机制与传统的子程序调用机制不同•面向对象技术中，对象是类的实例。对象有三种成份： (3) 、属性和方法(或操作)。A.标识 B.规则 C.封装 D.消息•关键路径是指AOE(ActivityOnEdge)网中 (4) 。A.最长的回路 B.最短的回路C.从源点到汇点(结束顶点)的最长路径 D.从源点到汇点(结束顶点)的最短路径•以下序列中不符合堆定义的是 (5) 。(5)A.(102，87，100，79，82，62，84，42，22，12，68)(102，100，87，84，82，79，68，62，42，22，12)(12，22，42，62，68，79，82，84，87，100，102)(102，87，42，79，82，62，68，100，84，12，22)•一个具有767个结点的完全二叉树，其叶子结点个数为__(6)__。A.383 B.384 C.385 D.386•若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有—(7)—棵树。A.k B.n C.n-k D.n+k•若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有__(8)_个顶点。TOC\o"1-5"\h\zA.11 B.10 C.9 D.8•将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较__(9)__次A.I B.n-1 C.n D.2n•已知AOE网中顶点V］〜v7分别表示7个事件，弧a］〜a10分别表示10个活动，弧上的数值表示每个活动花费的时间，如下图所示。那么，该网的关键路径的长度为__(10)__，活动a6的松驰时间(活动的最迟开始时间-活动的最早开始时间)为A.7 B.9 C.10 D.11\o"CurrentDocument"A.3 B.2 C.1 D.0•已知文法G[S]:S-AO|BI,A-S1|1,B-SO|O；该文法属于乔姆斯基定义的__(12)__文法，它不能产生串_(13)(12)A.0型B.1型C.2型D.3型(13)A.0011B.1010C.1001D.0101•语言L={ambn|m>0，n>1}的正规表达式是_(14)_。(14)A.a*bb* B.aa*bb* C.aa*b* D.a*b*•一个文法G=(N,T,P,S),其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号，令集合V=NUT,那么G所描述的语言是__(15)_的集合。(15)A.由S推导出的所有符号串 B.由S推导出的所有终结符号串C.V中所有符号组成的符号串 D.V的闭包中的所有符号串•程序设计语言引入''类”的概念是为了解决数据保护问题。C++语言将类的成员封装在类体之中，使之具有一定的存取规则，这些规则规定了存取类的成员的权利，其中，对于用private说明的成员，它_(16)_。(16)A.既能被该类的成员函数访问，又能被外界直接访问只能被该类的成员函数访问，外界不能直接访问不能被该类的成员函数访问，只能被外界直接访问既不能被该类的成员函数访问，也不能被外界直接访问•在数据库逻辑结构的设计中，将E-R模型转换为关系模型应遵循相关原则。对于三个不同实体集和它们之间的多对多联系m:n:p,最少可转换为__(17)__个关系模式。A.2 B.3 C.4 D.5•给定关系模式R(U,F),U={A,B,C,D,E},F={B—A,D—A,A—E,AC—B},其属性AD的闭包为_(18)_，其候选关键字为__(19)__。A.ADE B.ABD C.ABCD D.ACDA.ABD B.ADE C.ACD D.CD•若有关系模式R(A,B,C)和S(C,D,E),对于如下的关系代数表达式：E=nA,D(°B<'2003'AR.C=S.Cae='80'(RxS))E=nA,D(aR.C=S.C(aB<'2003'(R)XaE='80'(S)))S))B.耳三S))B.耳三J但Ei*E2D.与轩4但丘2三JB.E2D.E第3页共17页E=nA,D(aB<'2003'AE='80'(R正确的结论是__(20)__，表达式__(21)__的查询效率最高A.E1=E2=E3=E4C.E1三E2但E3主E4A.E1 C.E3•在UNIX操作系统中，当用户执行如下命令1ink("/user/include/myfile.sh"，"/usr/userwang/youfile.sh")则文件名"/usr/userwang/youfile.sh"存放在__(22)__。(22)A.user目录文件中 B.include目录文件中C.userwang目录文件中 D.youfile.sh的文件内容中•假设在系统中—个文件有两个名字，它与—个文件保存有两个副本的区别是__(23)__。(23)A.前者比后者所占用的存储空间更大前者需要两个目录项，后者只需要一个目录项前者存取文件的速度快，后者存取文件的速度慢前者改变与某个名字相联系的文件时，另一个名字相连的文件也改变；后者的另一个副本不改变•在某超市里有一个收银员，且同时最多允许有n个顾客购物，我们可以将顾客和收银员看成是两类不同的进程，且工作流程如下图所示。为了利用PV操作正确地协调这两类进程之间的工作，设置了三个信号量S1、S2和Sn，且初值分别为0、0和n。这样图中的a应填写_(24)_，图中的bl、b2应分别填写_(25)_，图中的cl、c2应分别填写—(26)__。(24)A.P(S1)B.P(S2)C.P(Sn)D.P(Sn)、P(S1)(25)A.P(Sn)、V(S2)B.P(Sn)、V(S1)C.P(S2)、V(S1)D.V(S1)、P(S2)(26)A.P(S1)、V(S2)B.P(Sn)、V(S1)C.P(S2)、V(S1)D.V(S1)、P(S2)•软件开发的螺旋模型综合了瀑布模型和演化模型的优点，还增加了__(27)__。采用螺旋模型时，软件开发沿着螺线自内向外旋转，每转一圈都要对__(28)__进行识别和分析，并采取相应的对策。螺旋线第一圈的开始点可能是一个__(29)__。从第二圈开始，一个新产品开发项目开始了，新产品的演化沿着螺旋线进行若干次迭代，一直运转到软件生命期结束。A.版本管理 B.可行性分析 C.风险分析 D.系统集成A.系统 B.计划 C.风险 D.工程A•原型项目 B.概念项目 C.改进项目 风险项目•关于程序模块优化的启发式规则有若干条，以下规则中不符合优化原则的是__(30)__。如果一个模块调用下层模块时传递一个数据结构，则这种耦合属于__(31)__。A•通过模块的合并和分解，降低模块的耦合度，提高模块的内聚性提高上层模块的扇出，减少模块调用的层次将模块的作用范围限制在模块的控制范围之内降低模块之间接口的复杂性，避免''病态连接"A.简单耦合 B.直接耦合 C.标记耦合 D.控制耦合•软件设计包括四个既独立又相互联系的活动，分别为__(32)__、__(33)__、数据设计和过程设计。A•用户手册设计 B.语言设计 C.体系结构设计 D.文档设计A.文档设计 B.程序设计 C.实用性设计 D.接口设计•标准化是一门综合性学科，其工作内容极为广泛，可渗透到各个领域。标准化工作的特征包括横向综合性、政策性和__(34)(34)A•统一性 B.灵活性 C.先进性 D.安全性•美国卡内基一梅隆大学SEI提出的CMM模型将软件过程的成熟度分为5个等级，以下选项中，属于可管理级的特征是_(36)_。A.工作无序，项目进行过程中经常放弃当初的计划建立了项目级的管理制度建立了企业级的管理制度软件过程中活动的生产率和质量是可度量的•某学院张老师在某大学进修时，获取了该大学李教授编制的考试试卷，之后将该套试卷收入其编写的《典型试卷分析》，并将该(典型试卷分析》出版，则张老师__(37)__。A•不侵权，因为试卷不属于著作权法的适用对象不侵权，因为试卷经首次考试后便进入了公有领域侵权，因为试卷是著作权法的保护对象是否侵权，应根据甲乙双方协商情况而定•甲将其一篇短文(心灵的呼唤》投递给杂志社。未经甲的许可，杂志社便委托乙对甲的短文进行修改，然后杂志社将署名为乙和甲的短文发表在其刊物上，则__(38)__。A.杂志社侵犯了甲的著作权，乙未侵权 B.杂志社未侵犯甲的著作权，乙侵了权C.杂志社和乙均侵犯了甲的著作权 D.杂志社和乙均未侵犯甲的著作权•自标准实施之日起，至标准复审重新确认、修订或废止的时间，称为标准的有效期，我国在国家标准管理办法中规定，国家标准的有效期一般为__(39)__年。A.2 B.5 C.7 D.10•__(40)__是指在经济、技术、科学及管理等社会实践中，对重复性事物和概念通过制订、发布和实施标准达到统一，以获得最佳秩序和最大社会效益。A.标准化 B.标准 C.规范 D.规程•甲通过计算机网络给乙发消息，表示甲己同意与乙签订合同，不久后甲不承认发过该消息。为了防止这种情况的出现，应该在计算机网络中采取__(41)__技术。A.数据压缩 B.数据加密 C.数据备份 D.数字签名•就目前计算设备的计算能力而言，数据加密标准DES不能抵抗对密钥的穷举搜索攻击，其原因是_(42)_。A.DES的算法是公开的 B.DES的密钥较短DES除了其中S盒是非线性变换外，其余变换均为线性变换DES的算法简单•为了保证网络的安全，常常使用防火墙技术。防火墙是__(43)__。A•为控制网络访问而配置的硬件设备 B.为防止病毒攻击而编制的软件指建立在内外网络边界上的过滤封锁机制为了避免发生火灾专门为网络机房建造的隔离墙•MPEG-I编码器输出视频的数据率大约为__(44)__。PAL制式下其图像亮度信号的分辨率为__(45)__，帧速为__(46)__。(44)A.128Kb/sB.320Kb/sC.1.5Mb/sD.15Mb/s(45)A.352x288B.576x352C.720x576D.1024x720(46)A.16帧/秒B.25帧/秒C.30帧/秒D.50帧/秒

•超文本是一种信息管理技术，其组织形式以__(47)__作为基本单位。D.环球网(Web)A.文本(Text) B.节点(Node) C.链(Link)D.环球网(Web)•单指令流多数据流计算机由__(48)__。A•单一控制器、单一运算器和单一存储器组成单一控制器、多个执行部件和多个存储器模块组成多个控制部件同时执行不同的指令，对同一数据进行处理多个控制部件、多个执行部件和多个存储器模块组成•使Cache命中率最高的替换算法是__(49)(49)A.先进先出算法FIFO•使Cache命中率最高的替换算法是__(49)(49)A.先进先出算法FIFOC.先进后出算法FILO•__(50)__不是RISC的特点。(50)A•__(50)__不是RISC的特点。(50)A.指令的操作种类比较少C.寻址方式比较少B.指令长度固定且指令格式较少D.访问内存需要的机器周期比较少•某计算机有14条指令，其使用频度分别如下表所示；I10.15I20.15I30.14I40.13I50.12I60.11I70.04I80.04I90.03I100.031110.02I120.02I130.01I140.01这14条指令的指令操作码用等长码方式编码，其编码的码长至少为__(51)__位。若只用两种码长的扩展操作码编码，其平均码长至少为__(52)__位。A.3 B.4 C.5 D.6A.2.8 B.3.4 C.3.8 D.4.2•硬磁盘存储器的道存储密度是指__(53)__，而不同磁道上的位密度是__(54)__。A•沿同磁道每毫米记录的二进制位数 B.同一柱面上的磁道数一个磁道圆周上所记录的二进制位数沿磁盘半径方向上单位长度(毫米或英时)上的磁道数A•靠近圆心的密度大 B.靠近外边沿的密度大C.靠近圆心的密度小 D.靠近半径中间的密度小•中央处理器CPU中的控制器是由些基本的硬件部件构成的。(55)A.时序部件和微操作形成部件C.外设接口部件__(55)__不是构成控制器的部件。B.程序计数器D.指令寄存器和指令译码器•下图表示客／''通过网络访问远端服务器的一种实现方式，请指出在服务器端的设备1是__(56)__，没备2是__(57)__。使用电话线路连接远程网络的一种链路层协议是__(58)__。(56)A•默认网关B.主交换机C.Modem池D.集线器(57)A.Web服务器B.FTP服务器C.Mail服务器D.RAS服务器(58)A.TCPB.PPPC.UDPD.ARP•Browser/Serer结构是把__(59)__技术和数据库技术结合起来的一种应用模式，这种应用模式把所有应用功能和数据库集中放在__(60)__，实现了开发环境与应用环境的分离，便于管理和系统维护。该模式最大的优点之—是__(61)__。(59)A．FTP B．TCP/IP C．Web D．HTTPA.客户端 B. C. D.A.客户端不用安装专用软件 B.服务器端不用安装专用软件C.运算效率高 D.传输速率快•设集合N={0,1,2,…},f为从N到N的函数，且f(f(+11) 0<x<90f(x)=x-10 x>90经计算f(90)=81,f(89)=81,f(49)=__(62)__。((62)A.39 B.49 C.81 D.92•集合A={d.b.c}上的二元关系R为：R={<a,a>,<c,c>,<a,b>)}，则二元关系R是__(63)—。A•自反的 B.反自反的 C.对称的 D.传递的•对n个元素进行快速排序时，最坏情况下的时间复杂度为_(64)_。A.O(1og2n) B.O(n) C.O(nlog2n) D.0(n2)•任何一个基于“比较”的内部排序的算法,若对6今元素进行排序,则在最坏情况下所需的比较次数至少为__(65)__。第7页共17页(65)A．10(65)A．10B．1lC．21D．36•SOCKSisagenericproxyprotocolforICP/I-Pbasednetworking,applications.SOCKSincludestwo__(66)__,theSOCKSserverandtheSOCKSclient.TheSOCKSserverisimplementedattheapplicationlayer.TheSOCKSclientisimplementedbetweenapplicationsandthe__(67)__layer.Whenanapplicationclientneedstoconnecttoanapplicationserver,theclientconnectstoaSOCKSproxyserver.Theproxyserverconnectstotheapplicationserverinsteadof.theclient,and__(68)__databetweentheclientandtheapplicationserver.Fortheapplicationserver,theproxyserveristhe__(69)__.SOCKSisalsooneofthepopular__(70)__tonetworkfirewalls.Becauseofitssimplicityandflexibility,SOCKShasbeenusedasgenericapplicationproxyinvirtualprivatenetwork(VPN),andforextranetapplications.(66)A．elementsB．componentsC．servicesD．ctients(67)A．transportB．transmissionC．networkD．datalink(68)A．relaysB．replacesC．replaysD．repeals(69)A．workstationB．userC．customerD．client(70)A．methodsB．alternativesC．choicesD．replacements•AWebbrowserissimplyaterminalemulator,designedtodisplaytextonascreen.ThetwoessentialdifferencesbetweenanordinaryterminalemulatorandaWebbrowserarethatthebrowserknowshowtodealwith__(71)__,andthatithasamechanismfor__(72)__graphicalfiles.Displaytext,displaygraphics,and__(73)__hyperlinks--there's99percentofthe__(74)__value.That'snottosaythatthemanufacturersdidn'tgoall-outtoattachahyperactiveefflorescenceofuselesscapabilitiesontotheirbrowsers.Rememberwhenmediachannelsinthebrowserwereabigdeal,insteadoftheclutteryoucan'twaittodeletefromyourfavoritesofbookmarksmenu?Rememberwhenclient-sideJavaappletsweresupposedtobecomethepreferred__(75)__forapplicationdevelopment?Rememberframesandalltheirnastysideeffects?(71)A．superlinksB．linksC．hyperlinksD．connections(72)A．displayingB．illustratingC．drawingD．writing(73)A．directB．navigateC．indicateD．go-on(74)A．Webbrowser'sB．terminal'sC．emulator'sD．network's(75)A．planeB．plantC．plateD．platform2003高级程序员考试下午试题试题一阅读下列算法说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。［算法说明］某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0（空闲）或丨（占用）。客房是以房间（不是床位）为单位出租的。本算法根据几个散客的要求预订一间空房。程序的输入为：人数M,房间等级要求R（R=0表示任意等级都可以）。程序的输出为；所有可供选择的房间号。流程图1描述了该算法。［问题1］假设当前该旅馆各个房间的情况如下表：序号iROOMRANKNBEDSTATUS11013402102341320123042022415301160当输入M=4,R=0时,该算法的输出是什么?［问题2］如果等级为r的房间每人每天的住宿费为RATE（r）,RATE为数组。为使该算法在输出每个候选的房间号RM（J）后，再输出这批散客每天所需的总住宿费DAYRENT（J）,流程图1的B所指框中的最后处应增加什么处理？［问题3］如果限制该算法最多输出K个可供选择的房间号，则在流程图1的a所指的判断框应改成什么处理？试题二阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。［说明］甲公司的经营销售业务目前是手工处理的，随着业务量的增长，准备采用关系数据库对销售信息进行管理。经销业务的手工处理主要涉及三种表：订单、客户表和产品表。订 单客户代码：订单号：

客户名： 订货日期为了用计算机管理销售信息，甲公司提出应达到以下要求：产品的单价发生变化时，应及时修改产品表中的单价数据。客户购货计价采用订货时的单价。订货后，即使单价发生变化，计算用的单价也不变。在设计数据库时，经销部的王先生建立了以下数据模型：其中，方框表示实体，单向箭头表示1对多的联系，双向箭头表示多对多的联系。由于上述模型对建立关系数据库是不合适的，因此王先生又修改了数据模型，并设计了如下几个关系(带下划线的数据项是关键项最后一个关系中没有指出关键项)：Customer(CustomerNo,CustomerName,Address,Phone)Product(ProductNo,ProductName,UnitPrice)Order(OrderNo,CustomerNo,Date)OrderDetail(OrderNo,ProductNo,Quantity)［问题1］请按［说明］中的要求画出修改后的数据模型。［问题2］(1)［说明］中的几个关系仍无法实现甲公司的要求,为什么?(2)需要在哪个关系中增加什么数据项才能实现这个要求?［问题3］写出Orde「Detail中的关键项。［问题4］以下SQL语句用于查询没有订购产品代码为“1K10”的产品的所有客户名。请填补其中的空缺。SELECTCustomerNameFROMCustomer___(1) WHERE___(2)___(SELECT*FROMOrderDetailB，OrderCWHEREB．ProductNo=C.ProductNoANDB．ProductNo='1KIO'ANDC．CustomerNo=A.CustomerNo)试题三阅读下列说明和有关的图，回答问题1至问题4，将解答填入答题纸的对应栏内。［说明］某制造企业的物料出入库管理的工作流程分别叙述如下：1．出库工作流程领料人提交领料单(每一种物料有一张领料单)；仓库保管员根据领料计划单检验该领料单是否有效；⑨若经检验没有相应的领料计划，则通知领料人该领料单无效；若领料单有效，仓库保管员根据领料单上的物料代码核对是否有足够的库存；若没有足够的库存，仓库保管员向领料人发缺货单；若有足够的库存，仓库保管员在领料单上签字，并登记出库单，修改物料主文件中的现有库存数；相应的物料出库，物料清单交领料人。2．入库工作流程采购员提交入库申请单(每一种物料有一张入库申请单)；仓库保管员根据采购计划单验收入库申请单；⑧若验收发现没有相应的采购计划，则仓库保管员向采购员发无效申请单：若验收合格，则仓库保管员向检验员申请物料检验；检验员根据检验结果填写物料检验单。如果物料或供货方不合格，则向采购员发出退货单；如果检验合格，则仓库保管员登记入库单，修改物料主文件中的现有库存数，相应的物料入库。为便于及时了解库存情况、核查出入库情况，该企业决定将上述人工流程由计算机来实现。在设计该系统时，采用了两种方法：结构化方法和面向对象方法。图3.1给出了物料出入库系统的数据流图，图中的数据流并没有画全，需要考生填补。图3.2给出了采用面向对象方法所认定出的类。［问题1］图3.1中缺少了那些数据流?请指明每条数据流的名称、起点和终点。［问题2］给出“领料单”和“入库申请单”这两个类至少应具有的属性。［问题3］为建立功能完善的库存管理系统，除了查询、统计、报表输出功能外，还应具有哪些对提高企业效益至关重要的功能?［问题4］用面向对象方法设计的类中，有一些类的对象是需要持久存储的，这样的类一般需要映射到关系数据库模式中。请指出图3.2中哪些类需要做这样的映射。

试题四在COMET型计算机上可以使用试卷上所附的CASL汇编语言，阅读程序说明和CASL程序，把应填入___(n)___处的字句写在答卷的对应栏内。［程序4说明］本程序统计出考试成绩在80分以上(含80分)、60分到79分、低于60分的学生人数，并将统计结果存放在以CHJG为首地址的连续三个内存单元中。学生的成绩数据连续存放在以XSCH为首地址的内存空间中，以数据-1作为结束标志。［程序4］START BEGINXSCH DC 90；此处的数据未完全列出DC-1

CHJBDC80DC60CHJGDC0DC0DC0ONEBEGINNEXTDC1___(1)___LDGR2，XSCH，GR1LEAGR0，0，GR2JMIEXITLEAGR2，0CPAGRO，CHJBJPZGOON (2) (3) JPZGOONLEAGR2，1，GR2GOON___(4) ___(5) STGRO，CHJG，GR2LEAGR1，1，GR1JMPNEXTEXITEXITEND试题五阅读以下预备知识、函数说明和C代码，将应填入__（n）__处的字句写在答题纸的对应栏内。［预备知识］①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合＜a,b,c,d｝及其权值2、7、4、5,可构造如下所示的最优二叉树和相应的结构数组Ht（数组元素Ht［O］不用）。结构数组Ht的类型定义如下：#defineMAXLEAFNUM20structnode{charch；intweight；intparent；/*扫当前结点表示的字符，对于非叶子结点，此域不用*//*当前结点的权值*//*当前结点的父结点的下标，为0时表示无父结点*/intlchild，rchild；/*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/）Ht［2*MAXLEAFNUM］；②用'0'或'1'标识最优二叉树中分支的规则是：从一个结点进入其左（右）孩子结点，就用'0'（'1'）标识该分支（示例见上图）。若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由‘0''1'组成的一个序列，称此序列为该叶子结点的前缀编码。例如上图所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。［函数5.1说明］函数voidLeafCode(introot,intn)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。在构造过程中，将Ht[p].weight域用作被遍历结点的遍历状态标志。[函数5.1]char**HC；voidLeafCode(introot，intn){/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/inti，p=root，cdlen=0;charcode[20];Hc=(char**)malloc((n+1)*sizeof(char*))；/*申请字符指针数组*/for(i=1；i<=p；++i)Ht[i].weight=0；/*遍历最优二叉树时用作被遍历结点的状态标志*/while(p){/*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/if(Ht[p].weight==0){ ／*向左*／Ht[p].weight=1;if(Ht[p].lchild!=0){p=Ht[p].lchild；code[cdlen++]='0';}elseif(Ht[p].rchild==0){/*若是叶子结点，则保存其前缀编码*/Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));___(1)___;strcpy(Hc[p]，code)；}}elseif(Ht[p].weight==1){ ／*向右*／Ht[p].weight=2;if(Ht[p].rchild!=0){p=Ht[p].rchild；code[cdlen++]='1';}}else{/*Ht[p].weight==2，回退*/Ht[p].weight=0；p=__(2)__;___(3)___;／*退回父结点*／}}／*while结束*／}[函数5.2说明]函数voidDecode(char*buff，introot)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。[函数5．2]voidDecode(char*buff，introot){intpre=root，p;while(*buff!='\0'){p=root;while(p!=0){/*存在下标为p的结点*/pre=p；if(__(4)___)p=Ht[p].lchild； /*进入左子树*/elsep=Ht[p].rchild： ／*进入右子树*／buff++; ／*指向前缀编码序列的下一个字符*／}___(5)___;printf("％c"，Ht[pre].ch);}试题六阅读以下说明和C++代码，将应填入—(n)—处的字句写在答题纸的对应栏内。[说明]本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数；a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度；kay为二维数组,存储最短路径，kay[i][j]=k表示顶点i到达顶点j的最短路径必须经过顶点k.类中的主要成员函数有：Input():输入有向网的顶点数、各条弧及权值，建立带权邻接矩阵a。若顶点i到顶点j有弧，则a[i][j]取弧上的权值，否则a[i][j]的值取NoEdge。AllPairs()：用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。OutShortestPath(inti，intj)：计算顶点i到顶点j的最短路径。outputPath(inti，intj)：输出顶点i到顶点j的最短路径上的顶点。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2…,Cn,其中C0是已知的带权邻接矩阵a，Ck(i，j)(0Wi,j<n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0Wk<n,有Ck(i，j)=C0(i,j)=a[i][j]。递推地产生C1,C2,…,Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。[C++代码]#include<iostream.h>#defineNoEdge10000//当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示voidMake2DArray(int**&x，introws，intcols);classAdjacencyWDigraph{private：intn；//有向网中的顶点数目int**a；