【计算机类职业资格】软件设计师-数据结构及算法设计(一)及答案解析.doc

《【计算机类职业资格】软件设计师-数据结构及算法设计(一)及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】软件设计师-数据结构及算法设计(一)及答案解析.doc（16页珍藏版）》请在麦多课文档分享上搜索。

1、软件设计师-数据结构及算法设计(一)及答案解析(总分：180.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明 5-1】B 树是一种多叉平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树：树中每个节点至多有 m 棵子树；若根节点不是叶子节点，则它至少有两棵子树；除根之外的所有非叶子节点至少有m/2棵子树；所有的非叶子节点中包含下列数据信息(n，A 0，K 1，A 1，K 2，A 2，K n，A n)，其中：Ki(i=1，2，n)为关键字，且 KiK i+1(i=1，2，n-1)，A i(i=0，1，n)为指向子树根节点的指针，且指针

2、 Ai-1所指子树中所有节点的关键字均小于 Ki，A i+1所指子树中所有节点的关键字均大于 Ki，n为节点中关键字的数目；所有的叶子节点都出现在同一层次上，并且不带信息(可以看成是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。例如，一棵 4 阶 B 树如图 5-1 所示(节点中关键字的数目省略)。B 树的阶 M、bool 类型、关键字类型及 B 树节点的定义如下：#define M 4 /*B 树的阶*/typedef enumFALSE=0,TRUE=1bool;typedef int ElemKeyType;typedef struct BTreeNodein

3、t numkeys; /*节点中关键字的数目*/struct BTreeNode *parent; /*指向父节点的指针，树根的父节点指针为空*/struct BTreeNode *AM; /*指向子树节点的指针数组*/ElemKeyType KM; /*存储关键字的数组，K0闲置不用*/BTreeNode；函数 SearchBtree(BTreeNode* root，ElemKeyType akey，BTreeNode *ptr)的功能是：在给定的一棵 M阶 B 树中查找关键字 akey 所在节点，若找到则返回 TRUE，否则返回 FALSE。其中， root 是指向该 M 阶B 树根节点的

4、指针，参数 ptr 返回 akey 所在节点的指针，若 akey 不在该 B 树中，则 ptr 返回查找失败时空指针所在节点的指针。例如，在如图 5-1 所示的 4 阶 B 树中查找关键字 25 时，ptr 返回指向节点 e 的指针。注：在节点中查找关键字 akey 时采用二分法。【函数 5-1】bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode *ptr)int lw,hi,mid;BTreeNode *p=root;*pb=NULL;while(p)lw=1;hi=U (1) /U;while(lw=hi)mid=(l

5、w+hi)/2;if(p-Kmid=akey)*Ptr=p;return TRUE;else if(U (2) /U)hi=mid-1;elselw=mid+1;*ptr=p;p=U (3) /U;return FALSE;【说明 5-2】在 M 阶 B 树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高

6、度增 1。例如，在如图 5-1 所示的 B 树中插入关键字 25 时，需将其插入节点 e 中，由于 e 中已经有 3 个关键字，因此将关键字 24 插入节点 e 的父节点 b，并以 24 为分界线将节点 e 分裂为 e1 和 e2 两个节点，结果如图5-2 所示。（分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.【说明】 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放 m 个记录，当桶中已有 m 个同义词(散列函数值相同)的记录时，存放第 m+1 个同义词会发生“溢出”。此时需要将第 m+1 个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前 m 个

7、同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。 例如：设散列函数为 Hash(Key)=Key mod 7，记录的关键字序列为 15，14，21，87，96， 293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图 5-3 所示。 （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)3.【说明】 函数 int Toplogcal(LinkedWDigraph G)的功能是对图 G 中的顶点进行拓扑

8、排序，并返回关键路径的长度。其中图 G 表示一个具有 n 个顶点的 AOE 网，图中顶点从 1n 依次编号，图 G 的存储结构采用邻接表表示，其数据类型定义如下： typedef struct Gnode /*邻接表的表节点类型*/ int adjvex; /*邻接顶点编号*/ int weieht; /*弧上的权值*/ stract Gnode *nextarc; /*指示下一个弧的节点*/ Gnode; typedef struct Adjlist /*邻接表的头节点类型*/ char vdata; /*顶点的数据信息*/ struct Gnode *Firstadj; /*指向邻接表的第

9、一个表节点*/ Adjlist; typedef struct LinkedWDigraph /*图的类型*/ int n,e; /*图中顶点个数和边数*/ struct Adjlist *head; /*指向图中第一个顶点的邻接表的头节点*/ LinkedWDigraph; 例如，某 AOE 网如图 5-4 所示，其邻接表存储结构如图 5-5 所示。 （分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)4.【说明】 函数 DeleteNode(Bitree*r，inte)的功能是：在树根节点指针为 r 的二叉查找(排序)树上删除键值为 e 的节点，若删除成功，则函数返回 0

10、，否则函数返回-1。二叉查找树节点的类型定义为： typedef struct Tnode int data;/*节点的键值*/ struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/ *Bitree; 在二叉查找树上删除一个节点时，要考虑 3 种情况。 若待删除的节点 p 是叶子节点，则直接删除该节点。 若待删除的节点 p 只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。 若待删除的节点 p 有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点 s 的值代替节点 p 的值，然后删除节点 s，节点 s 必属于上述、情

11、况之一。 【函数 5-5】 int DeleteNode(Bitree *r,int e) Bitree p=*r,pp,s,c; while(U (1) /U/*从树根节点出发查找键值为 e 的节点*/ pp=p; if(ep-data)p=p-Lchild; else p=p-Rehild; if(!p)retrn -1;/*查找失败*/ if(p-Lchild pp=p; while(U (3) /U)pp=s;s=s-Rchild; p-data=s-data;p=s; /* 处理情况、*/ if(U (4) /U)c=p-Lchild; else c=p-Rchild; if(p=

12、*r)*r=c; else if(U (5) /U)pp-Lchild=c; else pp-Rchild=c; free(p); return 0; （分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)5.【预备知识】 对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合a，b，c，d及其权值 2、7、4、5，可构造如图 5-6 所示的最优二叉树和相应的结构数组 Ht(数组元素 Ht0不用)。 （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)6.【说明】 设 M 叉树采用列表法表示，即每棵子树对应一

13、个列表，列表的结构为：子树根节点的值部分(设为一个字符)和用“()”，括起来的各子树的列表(如有子树的话)，各子列表间用“，”分隔。例如下面的三叉树可用列表 a(b(c，d)，e，f(g，h，i)表示。 （分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)7.【说明】 设某城市有 n 个车站，并有 m 条公交线路连接这些车站，设这些公交车都是单向的，这 n 个车站被顺序编号为 0 至 n-1。输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站 0 出发乘公交车至站 n-1 的最少换车次数。 程序利用输入信息构建一张有向图 G(用邻接矩阵 g 表示)，有向图

14、的顶点是车站，若有某条公交线路经 i 站能到达 j 站，就在顶点 i 到顶点 j 之间设置一条权为 1 的有向边i,j。如是这样，从站点 x 至站点 y 的最少上车次数便对应图 G 中从点 x 至点 y 的最短路径长度。而程序要求的换车次数就是上车次数减 1。 【函数 5-9】 #include stdio.h #define M 20 #define N 50 int aN+1; /*用于存放一条线路上的各站编号*/ iht gNN; /*存储对应的邻接矩阵*/ int distN; /*存储站 0 到各站的最短路径*/ int m,n; void buildG() int i,j,k,sc

15、,dd; printf (“输入公交线路数，公交站数/n“); scanf(“%d%d“, for(i=0; in; i+) /*邻接矩阵清 0*/ for(j = 0; j n; j+)gij = 0; for(i=0; im; i+) printf(“沿第%d 条公交车线路前进方向的各站编号(O=编号=%d,-1 结束):/n“, i+1, n-1); sc=0;/* 当前线路站计数器 */ while(1) scanf(“%d“, if(dd=-1)break; if(dd=0 asc=-1; for(k=1;ak=0; k+) /* 处理第 i+1 条公交线路 */ for(j=0;

16、jk; j+) gU (2) /U=1; int minLen() int j, k; for(j=0;jn;j+)distj=g0j; dist0=1; do for(k=-1,j=0;jn;j+) /* 找下一个最少上车次数的站*/ if(distj0 if (k0 | k=n-1) break; distk=-distk; /* 设置 k 站已求得上车次数的标记 */ for(j=1;jn;j+) /* 调整经过 k 站能到达的其余各站的上车次数 */ if (U (3) /U while(1); j=distn-1; return U(5) /U; void main() int t；

17、 buildG(); if(t=minLen()0)printf(“无解!/n“);else pdnff(“从 0 号站到%d 站需换车%d 次/n”，n-1，t)； （分数：15.00）_八、B试题八/B(总题数：1，分数：15.00)8.【说明】 假设需要将 N 个任务分配给 N 个工人同时去完成，每个人都能承担这 N 个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配 1 个不同的任务。程序中，N 个任务从 0 开始依次编号，N 个工人也从。开始依次编号，主要的变量说明如下。 cij：将任务 i 分配给工人 j 的费用。 taski：值为 0

18、 表示任务 i 未分配，值为 j 表示任务 i 分配给工人j。 workerk：值为 0 表示工人 k 未分配任务，值为 1 表示工人 k 已分配任务。 mincost：最小总费用。 【C 程序】 #includestdio.h #define N 8 /*N 表示任务数和工人数*/ int cNN; unsigned int mincost=65535; /*设置的初始值，大于可能的费用*/ int taskN, tempN, workerN; void plan(int k, unsigned int cost) int i; if(U (1) /U for(i=0; iN; i+)tem

19、pi=taski; else for(i=0; iN;i+)/*分配任务 k*/ if(workeri=0 taskk=U (3) /U; plan(U (4) /U,cost+cki); U(5) /U; taskk=0; /*if*/ /*Plan*/ void main() int i,j; for(i=0; iN; i+) /*设置每个任务由不同工人承担时的费用及全局数组的初值*/ workeri=0; taski=0; tempi=0; for(j=0; jN; j+) scanf(%d“, plan(0,0);/*从任务 0 开始分配*/ printf(“/n 最小差用=%d/n“

20、, mincost); for(i=0;iN;i+) printf(“Task%d is assigned to Worker%d/n“,i,tempi); /*main*/（分数：15.00）_九、B试题九/B(总题数：2，分数：15.00)9.【问题 1】 请将【算法 5-1】和【算法 5-2】中(1)至(7)处补充完整。（分数：7.00）_10.【问题 2】 请从下面的选项中选择相应的判断逻辑填补【算法 5-2】中的“判断条件 1”至“判断条件 3”。注意，若“判断条件 2”的逻辑判断结果为假，就无须对“判断条件 3”进行判断。 (a) 字符是括号 (b) 字符是左括号 (c) 字符是右

21、括号 (d) 栈空 (e) 栈不空 (f) 栈顶元素表示的是与当前字符匹配的左括号 (g) 栈顶元素表示的是与当前字符匹配的右括号（分数：8.00）_十、B试题十/B(总题数：1，分数：15.00)11.【说明】 “背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为 w1，w2，wn。希望从 N 件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于 S。 如下程序均能求得“背包问题”的一组解，其中程序 1 是“背包问题”的递归解法，而程序 2 是“背包问题”的非递归解法。 【程序 1】 #includestdio.h #d

22、efine N 7 #define S 15 int wN+1=0,1,4,3,4,5,2,7; int knap(int s, int n) if(s=0) return 1; if(s0 | (s0 if(U (1) /U)/*考虑物品 n 被选择的情况*/ printf(“%4d“,wn); return 1; return U(2) /U;/*考虑不选择物品 n 的情况*/ main() if(knap(S,N)printf(“OK!/n“); else printf(“N0!/n“); 【程序 2】 #includestdio.h #define N 7 #define S 15 t

23、ypedef struct int s; int n; int job; KNAPTP; int wN+1=0,1,4,3,4,5,2,7; int knap(int s, int n); main() if(knap(S,N) printf(“0K!/n“); else printf(“N0!/n“); int knap(int s, int n) KNAPTP stack100,x; int top, k, rep; x.s=s;x.n=n; x.job=0; top=1; stacktop=x; k=0; while(U (3) /U) x=stacktop; rep=1; while(

24、!k /*已求得一组解*/ else if(x.s0 | x.n=0) rep=0; else x.s=U (4) /U; x.job=1; U (5) /U=x; /*while*/ if(!k) rep=1; while(top=1 if(x.job=1) x.s +=wx.n+1; x.job=2; stack+top=x; U(6) /U; /*if*/ /*while*/ /*if*/ /*while*/ if(k) /*输出一组解*/ while(top=1) x=stacktop-; if(x.job=1)printf(“%4d/t“,wx.n+1); return k; （分数

25、：15.00）_十一、B试题十一/B(总题数：1，分数：15.00)12.【程序说明】 著名的四色定理指出任何平面区域图均可用 4 种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过 4 种颜色的着色方案。程序中用 14 表示 4 种颜色。要着色的 N 个区域用 0N-1 编号，区域相邻关系用 adj矩阵表示，矩阵的 i 行 j 列的元素为 1，表示区域i 与区域 j 相邻：矩阵的 i 行 j 列的元素为 0，表示区域 i 与区域 j 不相邻。数组 color用来存储着色结果，colori的值为区域 i 所着颜色。 【程序】 #includestdio.h #defi

26、ne N 10 void output(int color)/*输出一种着色方案*/ int i; for(i=0; iN; i+) printf(“%4d“, colori); pfintf(“/n“); int back(int *ip,int color)/*回溯*/ int c=4; while(c=4) if(*ip=0)return 0; -(*ip); c= U(1) /U; color*ip=-1; return c; /*检查区域 i,对 c 种颜色的可用性*/ int colorOK(int i, int c, int adjN, int color) int j; for

27、(j=0; ji; j+) if(U (2) /U)return 0; return 1; /*为区域 i 选一种可着的颜色*/ int select(int i,int c,int adjN, int color) int k; for(k = c; k=4; k+) if(U (3) /U)return k; return 0; int coloring(int adjN)/*寻找各种着色方案*/ int colorN, i, c, cnt; for(i=0; iN; i+)cotori=-1; i=c=0;cnt=0; while(1) if(c=U (4) /U=0) c=back(

28、if(c=0)return cnt; else U (5) /U; i+; if(i=N) output(color); +cnt; c=back( else c = 0; void main() int adjNN= 0,1,0,1,1,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,0, 0,1,0,1,0,1,1,0,1,1, 1,1,1,0,1,1,0,0,1,1, 1,0,0,1,0,1,0,0,0,0, 1,1,1,1,1,0,1,0,0,1, 1,1,1,0,0,1,0,0,1,0, 1,1,0,0,0,0,0,0,1,1, 1,1,1,1,0,0,1,1,0,1, 1

29、,0,1,1,0,1,0,1,1,0 ; printf(“共有%d 组解./n“,coloring(adj); （分数：15.00）_十二、B试题十二/B(总题数：1，分数：15.00)13.【程序说明】 下列文法可用来描述化学分子式的书写规则(例如，A12(C03)、Cu(OH)2)： | |n | 其中， 是一个分子式； 或是一个元素，或是一个带括号的(子)分子式，元素或是一个大写字母(记为 )，或是一个大写字母和一个小写字母(记为 )； 或是一个 ，或是在 之后接上一个整数 n，n 表示 有 n 个 的元素或(子)分子式。一个完整的分子式由若干个 组成。 当然一个正确的分子式除符合上述文

30、法规则外，还应满足分子式本身的语义要求。下面的程序输入分子式，按上述文法分析分子式，并计算出该分子式的分子量。例如，元素 H 的原子量是1，元素 O 的原子量是 16。输入分子式 H2O，程序计算出它的分子量为重 18(12+16)。程序中各元素的名及它的原子量从文件 atom.dat 中读入。 【程序】 #include stdio.h #include string.h #define MAXN 300 #define CMLEN 30 struct elem char name3;/*元素名*/ double v; /*原子量*/ nTblMAXN; char cmStrCMLEN, *

31、pos; int c; FILE *fp; double factor(); double atom() /*处理文法符号 */ char w3; int i; double num; while(c = *pos+)=“| c=/t); /* 略过空白字符 */ if(c=/n) return 0.0; if(c=A c=*pos+; if(c=a else pos-; w+i=/0; for(i=0; nTbli.v0.0; i+) if(strcmp(w, nTbli.name)=0) return nTbli.v; printf(“/n 元素表中没有所输入的元素: /t%s/n“,w)

32、; return -1.0; else if(c=() if(num =U (1) /U0.0)return -1.0; /* 包括可能为空的情况 */ if(*pos+ !=) printf(“ 分子式中括号不匹配!/n“); return -1.0; return num; printf(“分子式中存在非法字符: /t%c/n“,c); return -1.0; double mAtom() /* 处理文法符号 */ double num; int n=1; if(num = U(2) /U)0.0) return -1.0; c = *pos+; if(c=0 while(c=0 c=*

33、pos+; pos-; return num *n; double factor() /* 处理文法符号 */ double num=0.0, d; if(num=mAtom()0.0) return -1.0; while(*pos=A return num; void main() char fname=“atom.dat“; /*元素名及其原子量文件*/ int i; double num; if(fp=fopen(fname, “r“)=NULL)/* 以读方式打开正文文件*/ printf(“Can not open %s file./n“, fname); return;/* 程序

34、非正常结束 */ i=0; while(iMAXN fclose(fp); nTbli.v=-1.0; while(I) /* 输入分子式和计算分子量循环，直至输入空行结束*/ printf (“/n 输入分子式!(空行结束)/n“); gets(cmStr); pos=cmStr; if(cmStr0=/0)break; if(num=factor()0.0) if (*pos != /0)printf(“分子式不完整!/n“); else printf(“ 分子式的分子量为 %f/n“, num); （分数：15.00）_软件设计师-数据结构及算法设计(一)答案解析(总分：180.00，做

35、题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明 5-1】B 树是一种多叉平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树：树中每个节点至多有 m 棵子树；若根节点不是叶子节点，则它至少有两棵子树；除根之外的所有非叶子节点至少有m/2棵子树；所有的非叶子节点中包含下列数据信息(n，A 0，K 1，A 1，K 2，A 2，K n，A n)，其中：Ki(i=1，2，n)为关键字，且 KiK i+1(i=1，2，n-1)，A i(i=0，1，n)为指向子树根节点的指针，且指针 Ai-1所指子树中所有节点的关键字均小于 Ki，A i+1所指子树中

36、所有节点的关键字均大于 Ki，n为节点中关键字的数目；所有的叶子节点都出现在同一层次上，并且不带信息(可以看成是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。例如，一棵 4 阶 B 树如图 5-1 所示(节点中关键字的数目省略)。B 树的阶 M、bool 类型、关键字类型及 B 树节点的定义如下：#define M 4 /*B 树的阶*/typedef enumFALSE=0,TRUE=1bool;typedef int ElemKeyType;typedef struct BTreeNodeint numkeys; /*节点中关键字的数目*/struct BTre

37、eNode *parent; /*指向父节点的指针，树根的父节点指针为空*/struct BTreeNode *AM; /*指向子树节点的指针数组*/ElemKeyType KM; /*存储关键字的数组，K0闲置不用*/BTreeNode；函数 SearchBtree(BTreeNode* root，ElemKeyType akey，BTreeNode *ptr)的功能是：在给定的一棵 M阶 B 树中查找关键字 akey 所在节点，若找到则返回 TRUE，否则返回 FALSE。其中， root 是指向该 M 阶B 树根节点的指针，参数 ptr 返回 akey 所在节点的指针，若 akey 不在

38、该 B 树中，则 ptr 返回查找失败时空指针所在节点的指针。例如，在如图 5-1 所示的 4 阶 B 树中查找关键字 25 时，ptr 返回指向节点 e 的指针。注：在节点中查找关键字 akey 时采用二分法。【函数 5-1】bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode *ptr)int lw,hi,mid;BTreeNode *p=root;*pb=NULL;while(p)lw=1;hi=U (1) /U;while(lw=hi)mid=(lw+hi)/2;if(p-Kmid=akey)*Ptr=p;retur

39、n TRUE;else if(U (2) /U)hi=mid-1;elselw=mid+1;*ptr=p;p=U (3) /U;return FALSE;【说明 5-2】在 M 阶 B 树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增 1。例如，在如图 5-1 所示的 B 树中插入关键字 25 时，

40、需将其插入节点 e 中，由于 e 中已经有 3 个关键字，因此将关键字 24 插入节点 e 的父节点 b，并以 24 为分界线将节点 e 分裂为 e1 和 e2 两个节点，结果如图5-2 所示。（分数：15.00）_正确答案：()解析：(1) p-numkeys(2) akeyp-Kmid(3) p-Ahi(4) root，akey， /*邻接顶点编号*/ int weieht; /*弧上的权值*/ stract Gnode *nextarc; /*指示下一个弧的节点*/ Gnode; typedef struct Adjlist /*邻接表的头节点类型*/ char vdata; /*顶点的

41、数据信息*/ struct Gnode *Firstadj; /*指向邻接表的第一个表节点*/ Adjlist; typedef struct LinkedWDigraph /*图的类型*/ int n,e; /*图中顶点个数和边数*/ struct Adjlist *head; /*指向图中第一个顶点的邻接表的头节点*/ LinkedWDigraph; 例如，某 AOE 网如图 5-4 所示，其邻接表存储结构如图 5-5 所示。 （分数：15.00）_正确答案：()解析：(1) indegreep-adjvex+，及其等价形式 (2) Stacktop-，及其等价形式 (3) indegre

42、ep-adjvex-，及其等价形式 (4) vew+p-weightvep-adjvex，及其等价形式 (5) yew)，及其等价形式 分析 本题考查 AOE 网络及其拓扑排序和关键路径，做题前需要先弄清楚图 G 的存储结构。 根据注释，空(1)所在 for 循环用来统计 AOE 网中各顶点的入度。根据入度的定义及题中 AOE网的存储结构，当 p 不为 NULL 时，应将 p-adjvex 对应的顶点的入度加 1。又数组 indegree 正是用来存储各顶点入度的，从紧接着的用来求入度为 0 的顶点的 for 循环可看出， indegree 数组有效下标是从1 到 G.n，而顶点的编号正好也是从 1 开始，故空(1)应填 indegreep-adjvex+。 各顶点入度统计