1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 68及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 某公司的主要业务是出租图书和唱碟。由于业务需求，该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决定采用面向对象的分析和设计方法开发此系统。图 14-3所示为某类图书或唱碟被借阅时应记录的信息，图 14-4描述了系统定义的两个类Book和 CD，分别表示图书和唱碟的信息。1 经过进一步分析，设计人员决定定义一个类 Items_on_loan，以表示类 Book和CD的共有属性和方法。请采用图 14-4中属
2、性和方法的名称给出类 Items_on_loan应该具有的属性和方法 (注意，不同名称的属性和方法表示不同的含义，如 CD中的 composer与 Book中的 author无任何关系 )。 2 为了记录每种图书或唱碟租借的历史记录，引入类 CirculationHistory，类中存储的信息是图 14-3中所表示的内容。请采用 UML表示法将下列 4个类之间的关系表示出来。 3 现需了解十大最畅销 (借出次数最多 )图书或唱碟。为此，引入 TenPopulate类以存储所有十大畅销图书或 CD的名称及其被借出的次数。如图 14-5所示的顺序图描述了某类图书或唱碟被借出后成为十大畅销图书或唱碟
3、时对象间的消息交互。系统在一次运行过程中，应有 (1)个 TenPopulate实例对象最合适，一个 TenPopulate类实例对象最多需要和 (2)个 Items on loan实例对象交互。3 阅读下列说明和图，回答问题 1问题 3，将解答填入答题纸的对应栏内。 【说明】 某城市的各国家公园周边建造了许多供游客租用的小木屋和营地，为此该城市设置了一个中心售票处和若干 个区域售票处。游客若想租用小木屋或营地，必须前往中心售票处进行预定并用现金支付全额费用。所有的预定操作全部由售票处的工作人员手工完成。现欲开发一信息系统，实现小木屋和营地的预定及管理功能，以取代手工操作。该系统的主要功能描述
4、如下： (1)管理预定申请。游客可以前往任何一个售票处提出预定申请。系统对来自各个售票处的预定申请进行统一管理。 (2)预定。预定操作包含登记游客预定信息、计算租赁费用、付费等步骤。 (3)支付管理。游客付费时可以选择现金和信用卡付款两种方式。使用信用卡支付可以享受3的折扣，现金支付没 有折扣。 (4)游客取消预定。预定成功之后，游客可以在任何时间取消预定，但需支付赔偿金，剩余部分则退还给游客。赔偿金的计算规则是，在预定入住时间之前的 48小时内取消，支付租赁费用 10的赔偿金；在预定入住时间之后取消，则支付租赁费用 50的赔偿金。 (5)自动取消预定。如果遇到恶劣天气 (如暴雨、山洪等 )，
5、系统会自动取消所有的预定，发布取消预定消息，全额退款。 (6)信息查询。售票处工作人员查询小木屋和营地的预定情况和使用情况，以判断是否能够批准游客的预定申请。 现采用面向对象方法开发上述系统，得到如表 14-1所示的用例列表和表 14-2所示的类列表。对应的用例图和类图分别如图 14-8和图 14-9所示。4 根据说明中的描述与表 14-1，给出图 14-8中 UC1 UC6处所对应的用例名称。 5 根据说明中的描述与表 14-2，给出图 14-9中 C1 C7处所对应的类名。 6 对于某些需求量非常大的小木屋或营地，说明中功能 4的赔偿金计算规则，不足以弥补取消预定所带来的损失。如果要根据预
6、定的时段以及所预定场地的需求量，设计不同层次的赔偿金计算规则，请用文字说明需要对图 14-9进行怎样的修改 ? 7 一般的树结 构常采用孩子 -兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图 15-1(a)所示的树的孩子 -兄弟表示如图 15-1(b)所示。 函数 LevelTraverse()的功能是对给定树进行层序遍历。例如，当对图 15-1(a)中的树进行层序遍历时，结点的访问次序为 DBAEFPC。对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表 15-1所示。 Bool、 Status类型定
7、义如下： typedef enumFALSE=0， TRUE=1Bool； typedef enumOVERFLOW=-2， UNDERFLOW=-1， ERROR=0， OK=1Status；树的二叉链表结点定义如下： typedef struct Nodechar data； struct Node *firstchiid，*nextbrother； Node， *TreeNode；【函数代码】 Status LevelTraverse(TreeNode root) *层序遍历树，树采用孩子一兄弟表示法， root是树根结点的指针 * Queue temQ； TreeNode ptr， b
8、rotherptr； if(!root)return ERROR；InitQueue(&tempQ)； (1)； brotherptr= root-nextbrother ；while( brotherptr ) EnQueue( &tempQ， brotherptr )； (2)； *end-while*while(3) (4)； printf(” c t”， ptr-data)； if(5)continue； (6)； brotherptr=ptr-firstchild-nextbrother； while( brotherptr ) EnQueue( &tempQ， brotherptr
9、 )； (7)； *end-while* *end-while* return OK； *LevelTraverse* 8 函数 int Toplogical(LinkedWDigraph G)的功能是对图 G中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G表示一个具有 n个顶点的 AOE网，图中顶点从1 n依次编号，图 G的存储结构采用邻接表表示，其数据类型定义如下： typedef struct Gnode *邻接表的表结点类型 * int adjvex； *邻接顶点编号 * int weight； *弧上的权值 * struct Gnode*nextarc； *指示下一个弧的结点
10、* Gnode； typedef struct Adj list *邻接表的头结点类型 * char vdata； *顶点的数据信息 * struct Gnode*Firstadj； *指向邻接表的第一个表结点 * Adjulist； typedef struct LinkedwDigraph *图的类型 * int n， e； *图中顶点个数和边数 * struct Adjlist*head； *指向图中第一个顶点的邻接表的头结点 * LinkedWDigraph；例如，某 AOE网如图 15-2所示，其邻接表存储结构如图15-3所示。 【函数代码】 int Toplogical(Linke
11、dWDigraph G)Gnode *p； int j， w， top=0； int *Stack， *ve，*indegree； ve=(int*)malloc(G n+1)*sizeof(int)；indegree=(int*)malloc(G n+1)*si zeof(int)； *存储网中各项点的入度 *Stack=(int*)malloc(G n+1)*sizeof(int)； *存储入度为 0的顶点的编号 *if(!ve !indegree !Stack) exit(0)； for(j=1； jnextarc； *while* *for*for(j=1； j0) w=(2)； pr
12、intf(” c”， G headw vdata)； P=G headw Firstadj； while(P) (3)； if(!indegreep-adjvex) Stack+top=P-adjvex； if(4) vep-adjvex=vew+p-weight； P=P-nextarc； *while* *while* return(5)； *Toplogical* 8 快速排序是一种典型的分治算法。采用快速排序对数组 Ap r排序的三个步骤如下： 分解：选择一个枢轴 n-1) *得到问题解 * bestW=cw； bestC=cp； for(j=0； j 13 现欲实现一个图像浏览系统，
13、要求该系统能够显示 BMP、 JPEG和 GIF三种格式的文件，并且能够在 Windows和 Linux两种操作系统上运行。系统首先将BMP、 JPEG和 GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接 (Bridge)设计模式进行设计所得类图如图 16-1所示。 采用该设计模式的原因在于：系统解析 BMP、 GIF与 PEG文件的代码仅与文件格式相关，而 在屏幕上显示像素矩阵的代码则仅与操作系统相关。 【 C+代码】 class Matrix 各种格式的文件最终都被转化为像素
14、矩阵 此处代码省略 ； class ImageImp public： virtual void doPaint(MatriX m)=0； 显示像素矩阵 m ； class WinImp： public ImageImp public： void doPaint(Matrix m) *调用 Windows系统的绘制函数绘制像素矩阵 * ， class LinuxImp： public ImageImp public： void doPaint(Matrix m)f *调用 Linux系统的绘制函数绘制像素矩阵 * ； class Image public： void setImp(ImageIm
15、p *imp)(1) =imp； virtual void parseFile(string fileName)=0； protected： (2)*imp； ； class BMP： public Image public： void parseFile(string fileName) 此处解析 BMP文件并获得一个像素矩阵对象 m (3)；显示像素矩阵 m ； class GIF： public Image 此处代码省略 ；class JPEG： public Image 此处代码省略 ； void main() 在 windows操作系统上查看 demo bmp图像文件 Image*i
16、magel= (4)； ImageImp*imageImpl= (5)； (6)； imagel-parseFile(”demo bmp”)； 现假设该系 统需要支持 10种格式的图像文件和 5种操作系统，不考虑类 Matrix，若采用桥接设计模式则至少需要设计 (7)个类。 14 某咖啡店当卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如表 16-1所示。现采用装饰器 (Decorator)模式来实现计算费用的功能，得到如图 16-4所示的类图。【 C+代码】include includeUSing namespace
17、 std； const int ESPRESSO_PRICE=25； const int DRAKROAST_PRICE=20； const int MOCHA_PRICE=10； const int WHIP_PRICE=8； class Beverage 饮料 (1)： String deScription； public： (2)()return description； (3)； ； class condimentDecorator ： public Beverage 配料 protected： (4)； ； class Espresso： public Beverage 蒸馏咖啡 p
18、ublic： Espresso ( ) description=”Espresso”； int cost( )return ESPRESSO PRICE； ；class DarkRoast： public Beverage 深度烘焙咖啡 public：DarkRoast( ) description= “DardRoast”； int cost()return DRAKROAST PRICE； ； class Mocha ： public condimentDecorator 摩卡 public：Mocha(Beverage*beverage) this-beverage=beverage；
19、string getDescription( )return beverage-getDescription( )+“， Mocha”； int COSt( ) return MOCHA PRICE+beVerage-cost( )； ； class Whip ： public condimentDecorator 奶泡public： Whip(Beverage*beuerage) this-beverage=beverage； string getDescription( ) return beverage-getDescription( )+“， Whip”； int cost( ) re
20、turn WHIP PRICE+beverage-cost( )； ； int meln() Beverage*beverage=new DarkRoast( )；beverage=new Mocha(5)； beverage=new Whip(6)； coutgetDescription ( )cost( ) endl； return 0； 编译运行上述程序，其输出结果为： DarkRoast， Mocha， Whip ￥ 38 15 某大型商场内安装了多个简易的纸巾售卖机，自动出售 2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态图如图 16-6所示。采用状态 (State)模式来
21、实现该纸巾售卖机，得到如图 16-7所示的类图。其中，类 State为抽象类，定义了投币、退币、出纸巾等方法接口。类 SoldState、 SoldOutState、 NoQuarterState和HasQuarterState分别对应图 16-6中纸巾售卖机的 4种状态：售出纸巾、纸巾售完、没有投币、有 2元钱。【 Java代码】 import j ava util *； interface State public void insertQuarter()； 投币 public void ejectQuarter()； 退币 public void turnCrank()； 按下 “出纸巾
22、 ”按钮 public void dispense()； 出纸巾 class TissueMachine (1)soldOutState，noQuarterState， hasQuarterstate， soldState， state； state=soldOutState； int count=0； 纸巾数 public TissueMachine(int numbers) *实现代码省略 * publ ic State getHasQuarterState() return hasQuarterState； public State getNoQuarterState() return
23、noQuarterState； public State getSoldState() return soldState； public State getSoldOutState() return soldOutState； public int getCount() return count； 其余代码省略 class NoQuarterState implements State TissueMachine tissueMachine； public void insertQuarter() tissueMachine setState(2)； 构造方法以及其余代码省略 class Ha
24、sQuarterState implements State TiSsueMachine tissueMachine； public void ejectQuarter() tissueMachine setState(3)； 构造方法以及其余代码省略 class SoldState implements State TissueMachine tissueMachine； public void dispense()if(tiSsueMachine getCount()0) tissueMachine setState(4)； else tissueMachine setState(5)；
25、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 68答案与解析 一、必答题（共 4道大题，每道大题 15分） 【知识模块】 UML建模 1 【正确答案】 属性： title， 方法： Reference Title。 【试题解析】 问题 1要求考生写出类 Items on loan的属性和方法，由于题目已经说明此类的属性和方法是 Book类和 CD类的公共属性和方法；又因为 Book类和 CD类中，不同名的属性、方法表示的含义不同，所以公共属性和方法就是同名属性和方法，因此 Items_on_loan的属性有 title，方法有 Reference title。 【知识模块】 UM
26、L建模 2 【正确答案】 。 【试题解析】 问题 2引入了 CirculationHistory类，此类用 于记录每种图书或光盘的租借记录。现要求 CirculationHistory类、 Book类、 CD类及 Items_on_loan类之间的关系，根据【问题 1】可以知道， Items_on_loan是类 Book和 CD的公共部分，用面向对象的术语来说，类 Items_on_loan是类 Book和 CD的父类，所以它们之间存在继承关系。 再看 CirculationHistory类和其他类的关系，CirculationHistory类只需要记录图书或唱碟的名称及借阅记录，而不需要其他
27、详细资料，这样， CirculationHistory不必和 Book与 CD产生关系，只需要与Items_on_loan产生关系即可。由于 CirculationHistory中除记录图书或唱片名称以外，还需要记录借出时间、归还时间及用户名，这些数据无法从 Items_on_loan中获取。一个 CirculationHistory只包含一个。 Items_on_loan，存在 1： 1的关系，这说明 Items_on_loan其实只是 CirculationHistory的组成部分，但Items_on_loan可脱离 CirculationtJistory而独立存在，也 就是说，一本图书或
28、一张 CD可以没有记录其借阅历史的 CirculationHistory，但有记录其基本信息的Items_on_loan，所以它们之间又存在聚集关系 (而不是那种部分随整体销毁而销毁的组合关系 )。综上所述， 4个类的关系如图 14-14所示。聚合关联中涉及重复度，当没有指定重复度时，默认重复度为 1，那么，图 14-14中两个类 CirculationHistory、Items_on_loan所在端的重复度都为 1。 【知识模块】 UML建模 3 【正确答案】 (1) 1。 (2)图书和唱碟种类数。 【试题解析】 本题主要涉及类的设计、类之间的关系和顺序图。 在面向对象的程序设计当中，类的设
29、计是非常重要的，类设计的合理性直接影响到整个系统的性能。 题目中说 “引入 TemPopulate类以存储所有十大畅销图书或 CD的名称及其被借出的次数 ”，可见 TemPopulate类的功能是存储所有十大畅销图书或 CD的名称及其被借出的次数。既然如此，系统在一次运行中只需要 1个 TenPopulate实例对象就可以了，因为它存储所有十大畅销图书或 CD的名称及其被借出的次 数。每当有图书或唱碟被借出时，都需要和 TenPopulate类的对象发生交互，因此，当所有图书或 CD都被借阅时， TenPopulate类实例对象需要跟所有这些 Items_on _loan实例对象交互更新借出次
30、数以评出十大最畅销图书或 CD，一个TenPopulate类实例对象最多需要和 “图书和唱碟种类总数 ”个 Items_on_loan实例对象交互。 【知识模块】 UML建模 【知识模块】 UML建模 4 【正确答案】 UC1 CheckAvailability UC2： MakeReservation UC3： GetDiscount UC4： MangeCashPayment UC5： ManageCrCardPayment UC6： CalcuateRefund 【试题解析】 本题要补充完整用例图，这是考试中常考的知识点。在题目的描述中，其实已经给出了本题中相关的用例，只需要通过阅读题目
31、的描述，理解清楚这些用例之间的关系，然后结合用例图就可以完成这个问题。 在用例图中，只有一个参与者，就是售票处工作人员，通过题目的描述，不难知道，他应该与自动取消预订、游客取消预定、管理预定申请和信息查询 这些用例有直接关系，因此可以知道用例 UC2是信息查询用例 (CheckAvailability)。从用例图中可以看出， UC1与信息查询和管理预定申请都是一种包含关系，说明用例UC1是信息查询和管理预定申请这两个用例必须都经历的一种行为，因此可以知道此用例是预订 (MakeReservation)。 UC3是支付管理的包含用例，根据题目的描述不难知道，在每次付款时，都要首先计算付款折扣，因
32、此支付管理用例肯定包含了计算付款折扣这个用例， UC3就是计算付款折扣 (GetDiscount)。支付方式有现金支付和信 用卡支付两种方式，这两种方式与支付管理是一种泛化关系，因此可以 UC4和 UC5分别是现金支付(MangeCashPayment)和信用卡支付 (ManageCrCardPayment)，当然，它们的位置可以互换。 另外，从用例图不难看出， UC6是游客取消预定和系统自动取消预定用例所包含的用例，而这两个用例都必须包含的部分是计算机赔偿金，因此 UC6是计算取消预定的赔偿金 (CalcuateRefund)。 【知识模块】 UML建模 5 【正确答案】 C1 Nation
33、alPark C2： Rate C3： Ticketing officer C4： Payment C5： Discount C6： CasbPayment C7： CreditCardPayment 【试题解析】 本题要补充完整类图，也是考试中常考的知识点。题目中给出了相关的类，要根据题目的描述并结合类图来完成。 C1与类预定申请内容是一种组合关系，而其内容其实就是供游客租用的小木屋和营地以及它们的价格等信息，再结合类图可知， C1应该是国家公园。而从类图可以看出， C2聚合而成预定申请内容类，那么根据前面的分析，不难知道 C2是租凭费用 类。 从类图不难看出， C6和 C7是继承与 C4，
34、而从题目的分析中，只有付款、现金支付、信用卡支付存在这种继承关系，因此可以确定 C4是付款，而 C6和 C7分别对应现金支付和信用卡支付其位置可以互换。这样就剩下 C3和 C5没有确定，而没有确定的类还有售票处和付款折扣。其中， C3与预定申请有关，根据题目描述，预定申请是要提交给售票处的，因此可以确定 C3就是售票处，而付款的时候有个付款折扣信息， C5就是付款折扣。 【知识模块】 UML建模 6 【正确答案】 增加一个新的类，该类与类 Reservationltem之间有关联关系。 【试题解析】 本题考查用例图和类图。涉及用例之间的关系、类之间的关系等问题。 问题 3主要是要设计赔偿金计算
35、规则，要实现这个功能，可以添加一个类来实现，这类要与类 Reservationltem之间有关联关系，也可以在原来的类中实现，如果是这样，就应该是类 Rate中实现，因为这个类实现的是租凭费用，且这个类与Reservationltem之间是一种聚合的关联关系。 【知识模块】 UML建模 7 【正确答案】 (1)EnQueue(&tempQ， root)。 (2)brotherptr： brotherptr-nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(&tempQ， &ptr)。 (5)!ptr-firstchild。 (6)EnQueue(&temp
36、Q， ptr-firstchild)。 (7)brotherptr=brotherptr-nextbrother。 【试题解析】 解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的：首先将树根结点入队，然后将其所有兄弟结点入队 (当然，由于是根结点，故无 兄弟结点 )；完成这一操作以后，便开始出队、打印；在打印完了之后，需要进行一个判断，判断当前结点有无孩子结点，若有孩子结点，则将孩子结点入队，同时将孩子结点的所有兄弟结点入队；完了以后继续进行出队操作；出队后再次判断当前结点是否有孩子结点，并重复上述过程，直至所有结点输出。 这一描述可能过于理论，难以理解，接下来以本题为例来说明
37、此过程。首先将树根结点 D入队，并同时检查是否有兄弟结点，对于兄弟结点应一并入队。这里的 D没有兄弟结点，所以队列此时应是： D 接下来执行出队操作。 D出队，出队以 后检查 D是否有子结点，经检查， D有子结点 B，所以将 B入队，同时将 B的兄弟结点： A和 E按顺序入队。得到队列： B A E 接下来再执行出队操作。 B出队，同时检查 B是否有子结点， B无子结点，所以继续执行出队操作。 A出队，同时检查 A是否有子结点， A有子结点 F，所以将 F入队，同时将 F的兄弟结点 P入队。得到队列： E F P 接下来再次执行出队操作。 E出队， E有子结点 C，所以 C入队。得： F P
38、C 接下来再次执行出队操作 。 F出队， F无子结点，继续出队操作， P出队，仍无子结点，最后 C出队，整个过程结束。 通过对算法的详细分析，现在便可轻松得到答案。 (1)应是对根结点 root执行入队操作，即 EnQueue(&tempQ， root)。 (2)在一个循环当中，循环变量是brotherptr，此变量无语句对其进行更新，所以 (2)必定是更新 brotherptr。结合前面的算法分析可知 (2)应填： brotherptr=brotherptr-nextbrother。 (3)、 (4)加上后面的语句 “printf(“ c t”， ptr-data)； ”是控制数据的输出，这
39、些数据应是从队列中得到，所以此处必有出队操作，同时在出队之前应判断队列是否为空，所以(3)、 (4)填： !IsEmpty(tempQ)和 DeQueue(&tempQ， &ptr)。 (5)实际上是问 “在什么情况下，要持续进行出队操作 ?”，前面的算法分析中已指出：若出队结点无子结点，则继续进行出队操作，所以 (5)填 !ptr-firstchild。 (6)和 (7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队，所以 (6)填：EnQueue(&tempQ， ptr-firstchild)。 (7)和 (2)相同，填 brotherptr=brotherptr-nextbro
40、ther。 【知识模块】 数据结构与算法应用 8 【正确答案】 (1)indegreep-adjvex+。 (2)Stacktop-。 (3)indegreep-adjvex-。 (4)(Vew+p-weight)vep-adjvex。 (5)Vew。 【试题解析】 此 C语言程序题考点为拓扑排序和关键路径。在解题之前，先了解几个概念。 (1)AVO网络。 一 个大工程中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为
41、用顶点表示活动网络，简称 AOV网络，图 15-4所示是一个 AOV网络。(2)拓扑排序。 对 AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得如在 AOV网络中存在一条弧 (i， j)，则活动 i排在活动 j之前。对图 15-4中的顶点进行拓扑排序，可以得到多个不同的拓扑 序列，如 02143567， 01243657， 02143657， 01243567。 (3)AOE网络。 利用AOV网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶
42、点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为 AOE网络。图 15-5所示为一个具有 8个活动的某个工程的 AOE网络。图中，有 6个顶点，分别表示事件 V1 V6， 其中 V1是工程的开始状态，V4是工程的结束状态。边上的权表示完成该活动所需的时间。(4)关键路径。 在 AOE网络中某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图 15-5的 AOE网络的关键路径为 V1V2V6V4，关键路径长度为80。 了解了上面的这些
43、概念以后，解题就非常容易了。 从程序中的注释可知下段程序的作用是求网中各顶点的入度。 for( j = 1； jnextarc； 从已知的代 码结合邻接表来看，首先 p指向了邻接表弟 1个结点 V1的 Firstadj域，然后用 while循环遍历了 V1的 Firstadj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有： indegree=(int*)malloc( (G n+1)*sizeof(int) )； *存储网中各顶点的入度 * 所以第 (1)空应填 indegreep-adjvex+。 接下来看
44、第 (2)空，第 (2)空是给 w赋值，接下来是打印第 w号结点的数据， 这也就意味着 w号结点是拓扑排序选出来的结点，所以 w必是一个入度为 0的结点。然而在此之前已经有程序把所有的入度为 0的结点保存在 Stack数组中了，而且 Stack数组是模拟的一个栈，其控制指针只有 top，所以我们应该从 Stack中取出栈顶元素赋值给 w。所以第 (2)空填 Stacktop-。注意这里不能用 “Stack-top”，因为前面有入栈语句“Stack+top j； ”。 接下来看下面的程序段。 while(p) (3)； if( !indegreep-adjvex ) stack+top ： p-
45、adjvex； if (4) Vep-adjvex =Vew+p-weight； p=p-nextarc； 此段程序的作用是：把选出结点所关联的边去掉，即原来 V1有到 V3的边 a1=30和到 V2的边 a2=10，当 V1结点选出以后， a1， a2也要随之消失。这时 V3和 V2的入度要更新，也就是把 V3和 V2的入度分别减 1。所以第 (3)空应填 indegreep-adjvex-。第 (4)空看起来比较棘手，因为前面没有说明 ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序 有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定 if
46、 (4) vep-adjve=Vew+p-weight；的功能是计算关键路径长度。 ve的初值最开始都是 0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点 vx， vevx中存的都是最长路径即可。也就是说，首先选出的是 V1，从 V1 V2只有一条路径，所以 vev2=a2=10，从 V1 V3只有一条路径，所以vev3=a1=30。然后选出 V2结点， V2选出以后，因为 V2 V6有 a5=50，所以现在到 V6的最长路径为 vev6=vev2+a5=60。经过若干步后，当程序选中 V3结点时，会产生到 V6的另外一条路径 V1-V3-V6，这条路径的长度为 50，
47、这条路径比现存的路径长度 vev6短，所以单纯的更新语句 “vep-adjvex=vew+p-weight”不能正确保存最长路径，为了保证 ve中保存的路径最长，应该有判断 (Vew+p-weigh()Vep-adjvex。所以第 (4)空应该填 “(vew+p-weight)vep-adjvex”。 第 (5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢 ?这一点可以从关键路径的定义着手： “称从开始顶点到结束顶点的最长路径为关键路径 ”，所以最后一个选出结点的 ve存放的便是关键路径。所以第 (5)空应填 vew。 【知识模块】 数据结构与算法应
48、用 【知识模块】 数据结构与算法应用 9 【正确答案】 (1)Ai+1或 Ar。 (2)Ar或 Ai+1。 (3)i+1。 【知识模块】 数据结构与算法应用 10 【正确答案】 (4)O(nlgn)或 O(nlog2n)。 (5)O(nlgn)或 O(nlog2n)。 (6)O(n2)。 (7)最坏。 【知识模块】 数据结构与算法应用 11 【正确答案】 (8)Ai。 (9)Ar。 (10)否。 【试题解析】 该题主要考查考生对分治算法的快速排序的理解，对伪代码、快速排序的复杂度的掌握，做题的关键是要读懂题干，理解题干中对算法的描述。 问题 1考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题，分解成一些规模较小的相同问题，各个击破。其快速排序算法的核心处理是进 行划分，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组。一个子数据组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分，从
