对有向图进行拓扑排序的方法是：
（1）初始时拓扑序列为空；
（2）任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；
（3）重复（2），直到不存在入度为0的顶点为止（若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序）。
函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：
#define MAXVNUM 50/*最大顶点数*/
typedef struct ArcNode{/*表结点类型*/
int adjvex;/*邻接顶点编号*/
struct ArcNode*nextarc;/*指示下一个邻接顶点*/
}ArcNode;
typedef struct AdjList{/*头结点类型*/
char vdata;/*顶点的数据信息*/
ArcNode*firstarc;/*指向邻接表的第一个表结点*/
}AdjList;
typedef struct LinkedDigraph{/*图的类型*/
int n;/*图中顶点个数*/
AdjList Vhead[MAXVNUM];/*所有顶点的头结点数组*/
}LinkedDigraph;
例如，某有向图G如图4-1所示，其邻接表如图4-2所示。
图4-1有向图G
函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：
【C代码】
int*TopSort(LinkedDigraph G){
ArcNode*p;/*临时指针，指示表结点*/
Queue Q;/*临时队列，保存入度为0的顶点编号*/
int k=0;/*临时变量，用作数组元素的下标*/
int j=0，w=0;/*临时变量，用作顶点编号*/
int*topOrder，*inDegree;
topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int));/*存储图G中各顶点的入度*/
if(!inDegree||!topOrder)return NULL;
（1）;/*构造一个空队列*/
for(j=1;j＜=G.n;j++){/*初始化*/
topOrder[j]=0;inDegree[j]=0;
}
for(j=1;j＜=G.n;j++)/*求图G中各顶点的入度*/
for(p=G.Vhead[j].firstarc;p;p=p->nextarc)
inDegree[p->adjvex]+=1;
for(j=1;j＜=G.n;j++)/*将图G中入度为0的顶点保存在队列中*/
if(0==inDegree[j])EnQueue(&Q，j);
while(!IsEmpty(Q)){
（2）;/*队头顶点出队列并用w保存该顶点的编号*/
topOrder[k++]=w;
/*将顶点w的所有邻接顶点的入度减1（模拟删除顶点w及从该顶点出发的弧的操作）*/
for(p=G.Vhead[w].firstarc;p;p=p->nextarc){
（3）-=1;
if(0==（4）)EnQueue(&Q，p->adjvex);
}/*for*/
free(inDegree);
if(（5）)
return NULL;
return topOrder;
}/*TopSort*/
【问题1】（9分）
根据以上说明和C代码，填充C代码中的空（1）～（5）。
【问题2】（2分）
对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。
【问题3】（4分）
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是（6）。
若有向图采用邻接矩阵表示（例如，图4-1所示有向图的邻接矩阵如图4-3所示），且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是（7）。
正确答案及解析
正确答案
解析
【问题1】（9分）
（1）InitQueue(&Q)（1分）注：函数名与参数必须完全正确才可得分
（2）DeQueue(&Q，&w)（2分）注：函数名与参数必须完全正确才可得分
（3）inDegree[p->adjvex]及其等价形式（2分）
（4）inDegree[p->adjvex]及其等价形式（2分）
（5）k＜G.n或k!=G.n（2分）
【问题2】（2分）
队列方式：v1 v2 v5 v4 v3 v7 v6（或1 2 5 4 3 7 6）（1分）
栈方式：v1 v2 v5 v4 v7 v3 v6（或1 2 5 4 7 3 6）（1分）
【问题3】（4分）
（6）O(n+e)（2分）
（7）O（n2）（2分）
本题考查数据结构和算法中的拓扑排序算法。
【问题１】
拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在顶点Vj之前。
对AOE网进行拓扑排序的方法如下：
①在AOE网中选择一个入度为零（没有前驱）的顶点且输出它：
②从网中删除该顶点及其与该顶点有关的所有边；
③重复上述两步，直至网中不存在入度为零的顶点为止。
在拓扑排序过程中，需要将入度为0的顶点临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然，空（1）处应填入InitQueue（&Q）。
进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组inDegree[]中，从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点操作转化为令队头所代表的顶点出队。
根据注释，空（2）处应填入DeQueue(&Q，&w)，实现队头元素出队列的处理。
题中图采用邻接表存储结构，当指针p指向Vi邻接表中的结点时，p->adjvex表示vi的一个邻接顶点，删除vi至顶点p->adjvex的弧的操作实现为顶点p->adjvex的入度减1，因此，空（3）处应填入inDegree[p->adjvex]，当顶点p->adjvex的入度为0时，需要将其加入队列，因此空(4）处也应填入inDegree[p->adjvex]。
空（5）处判断是否所有顶点都加入了拓扑序列，算法中变量k用于对加入序列的顶点计数，因此，空（5）处应填入“k＜G.n”或“k!=G.n"。
【问题2】
使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式更下：
（1）开始时仅顶点V1的入度为0，因此顶点V1入队：
（2）队头顶点V1出队，并进入拓扑序列，然后删除从顶点V1出发的弧后，仅使顶点v2的入度为0，因此顶点v2入队：
（3）队头顶点v2出队，并进入拓扑序列，然后删除从顶点v2出发的弧后，仅使顶点v5的入度为0，因止顶点v5入队；
（4）队头顶点v5出队，并进入拓扑序列，然后删除从顶点v5出发的弧后，仅使顶点v4的入度为0，因此顶点v4入队；
（5）队头顶点v4出队，并进入拓扑序列，然后删除从顶点v4出发的弧后，仅使顶点v3和v7的入度为0，因此顶点v3和v7依次入队；
（6）队头顶点v3出队，并进入拓扑序列，然后删除从顶点v3出发的弧后，没有产生新的入度为0的顶点；
（7）队头顶点v7出队，并进入拓扑序列，然后删除从顶点v7出发的弧后，使顶点v6的入度为0，因此顶点v6入队；
（8）队头顶点v6出队，并进入拓扑序列，然后删除从顶点v6出发的弧后，没有产生新的入度为0的顶点，队列已空，因此结束拓扑排序过程，得到的拓扑序列为v1 v2 v5 v4 v3 v7 v6。
使用栈保存入度为0的顶点时，前4步都是一样的，因为每次仅有一个元素进栈，因此出栈序列与入栈序列一致。到第5步时，v3和v7依次入栈后，出栈时的次序为v7和v3，因此得到的拓扑序列为v1 v2 v5 v4 v7 v3 v6。
【问题3】
以邻接表为存储结构时，计算各顶点入度的时间复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，（图中无环情况下）每个顶点进出队列各1次，入度减l的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。
以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为O（n），建立零入度顶点队列的时间复杂度为O（n）。在拓扑排序过程中，（图中无环情况下）每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍（时间复杂度为O(n))，所以总的时间复杂度为O(n2）。
包含此试题的试卷
你可能感兴趣的试题
（ ）a method of obtaining early feedback on requirements by providing aworking model of the expected product before actually building it.
-
- A.Prototypes
- B.Object oriented
- C.Structure
- D.Iterative methoD
- 查看答案
【说明】
某公司现有网络拓扑结构如图1-1所示。该网络中使用交换机SW1为三层交换机，SW2和SW3均为二层智能交换机。
【问题4】（4分）
为了对用户上网行为进行监管，需要在SW1与R1之间部署（9）。
（9）备选答案：
A.FW（防火墙） B.IDS（入侵检测系统） C.堡垒机 D.上网行为管理
随着公司各部门成员增加，某些时候部分员工获取到IP地址和真实DHCP分出来IP不一致，为了避免这种情况可以在交换机上开启（10）功能。
（10）备选答案：
A．dhcp snooping B. broadcast-suppression C. loopback-detect
- 查看答案
阅读下列说明，回答问题1至问题5，将解答填入答题纸对应栏内。 【说明】 攻克要塞教育中心在部署计算机网络时采用了一款硬件防火墙，该防火墙带有三个以太网络接口，其网络拓扑如图3-1所示。
【问题1】（8分）
防火墙包过滤规则默认策略为拒绝，表3-1给出防火墙包过滤规则配置。若要求内部所有主机能使用IE浏览器访问外部IP地址202.117.118.23Web服务器，为表中（1）~（4）空缺处选择正确答案，填写在答题纸相应位置。（1）备选答案：A．允许 B．拒绝（2）备选答案：A．192.168.1.0/24 B．211.156.169.6/30 C．202.117.118.23/24（3）备选答案：A．TCP B．UDP C．ICMP（4）备选答案：A．E3E2 B．E1E3 C．E1E2
【问题2】（6分）
内部网络经由防火墙采用NAT方式与外部网络通信，表3-2中（5）~（7）空缺处选择正确答案，填写在答题纸相应位置。（5） 备选答案：A．192.168.1.0/24 B．anyC．202.117.118.23/24（6）备选答案： A．E1 B．E2 C．E3（7）备选答案： A．192.168.1.1 B．210.156.169.6C．211.156.169.6
【问题3】（2分）
图3-1中 （8）适合设置为DMZ区。（8）备选答案：A．区域A B．区域B C．区域C【问题4】（4分）防火墙上配置信息如图3-2所示。要求启动HTTP代理服务，通过HTTP缓存提高浏览速度，代理服务端口为3128，要使主机PC1使用HTTP代理服务，其中“地址”栏中内容应填写为 （9） ，“端口”栏中内容应填写为 （10） 。
【问题5】（4分）
NAT和HTTP代理分别工作在 （11） 和 （12） 。（11）备选答案：A．网络层 B．应用层 C．服务层（12）备选答案：A．网络层 B．应用层 C．服务层
- 查看答案
阅读以下说明，回答问题1至问题4，将解答填入答题纸对应解答栏内。
【说明】
某企业采用PIX防火墙保护公司网络安全，网络结构如图4-1所示。
【问题1】（4分）
防火墙一般把网络区域划分为内部区域（trust区域）、外部区域（untrust区域）以及(1)，其中在这个网络区域内可以放置一些公开服务器，下列(2)服务器不适合放在该区域。
空(2)备选答案：
A．Web
B．FTP
C．邮件
D．办公自动化(OA)
【问题2】（2分）
衡量防火墙性能主要参数有并发连接数、用户数限制、吞吐量等，其中最重要参数是(3)，它反映出防火墙对多个连接访问控制能力和连接状态跟踪能力，这个参数大小直接影响到防火墙所能支持最大信息点数。
空(3)备选答案：
A．并发连接数
B．用户数限制
C．吞吐量
D．安全过滤带宽
【问题3】（4分）
设置防火墙接口名称，并指定安全级别，安全级别取值范围为0～100，数字越大安全级别越高。要求设置：ethemet0命名为外部接口outside，安全级别是0；ethernet1命名为内部接口inside，安全级别是100；ethernet2命名为中间接口dmz，安全级别为50。
请完成下面命令。
…
PLX#config terminal
PLX (config)#nameif ethemet0 (4) security0
PLX (config)#nameif ethernet1 inside (5)
PLX (config)#nameif ethemet2 (6) (7)
…
【问题4】（5分）
编写表4-1中规则，设置防火墙安全规则，允许外网主机133.20.10.10访问内网数据库服务器10.66.1.101，同时允许内网和外网访问DMZ区WWW服务器10.65.1.101。
- 查看答案
阅读以下说明，回答问题一，并将解答填入答题纸对应解答栏中。 某公司用ASP 实现了用户满意度调查网页，系统几个主要文件及作用如表1所示， 网页效果如图1 所示。
用户调查数据库表info表结构如表2所示：
问题1：完成下列代码填空
备选答案：A.用户满意度调查 B. rs C. username
D. ＜/frameset> E. dbpathF.Conn G.exec H. top.html I.info J. login.asp K.searchtext L. rs.EOF M. MoveNext N.wt1 O. rowcount
- 查看答案