33. 在用floyd 算法求解各顶点的最短路径时，每个表示两点间路径的pathk-1[i,j]一定是pathk [i,j]的子集(k=1,2,3,…,n)。（    ）【合肥工业大学 2000 二、6 （1分）】
34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（  ）【南京航空航天大学1995五、8（1分）】
35．拓扑排序算法仅能适用于有向无环图。（    ）【南京航空航天大学 1997 一、7 （1分）】 
36. 无环有向图才能进行拓扑排序。（    ）【青岛大学 2002 一、7 （1分）2001 一、8 （1分）】
37. 有环图也能进行拓扑排序。（    ）【青岛大学 2000 四、6 （1分）】
38．拓扑排序的有向图中，最多存在一条环路。（    ）【大连海事大学 2001 一、6（1分）】
39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（    ）【上海交通大学1998 一、13】
40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（    ）【合肥工业大学 2001 二、6（1分）】
41．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（    ）
【中科院软件所 1997 一、5 （1分）】
42．aov网的含义是以边表示活动的网。（    ）【南京航空航天大学 1995 五、7 （1分）】
43．对一个aov网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995五、9(1分）】
44. 关键路径是aoe网中从源点到终点的最长路径。（    ）【青岛大学 2000 四、10（1分）】
45. aoe网一定是有向无环图。（    ）【青岛大学 2001 一、9 （1分）】
46. 在表示某工程的aoe网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（    ）
【长沙铁道学院 1997 一、2  (1分)】
47．在aoe图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（    ）
【大连海事大学 2001 一、15 （1分）】
48．在aoe图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（    ）
    【大连海事大学 2001 一、16 （1分）】
49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学1998 一、14】 
三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图g的强连通分量是指______。【北京科技大学 1997 一、7】
3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】
4．具有10个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1分）】
5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学1998 一、6（1分）】
6. 设无向图 g 有n 个顶点和e 条边，每个顶点vi 的度为di（1<=i<=n〉，则e=______
【福州大学 1998 二、2  (2分)】
7．g是一个非连通无向图，共有28条边，则该图至少有______个顶点。
【西安电子科技大 2001软件一、8 （2分）】
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
【合肥工业大学 2000 三、8 （2分）】
9．在有n个顶点的有向图中，每个顶点的度最大可达______。【武汉大学 2000 一、3】
10．设g为具有n个顶点的无向连通图，则g中至少有______条边。
【长沙铁道学院 1997 二、2 (2分)】
11．n个顶点的连通无向图，其边的条数至少为______。【哈尔滨工业大学 2000 二、2（1分）】
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
【西安电子科技大学  2001软件  一、2 （2分）】
13．n个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1分）】
14．构造n个结点的强连通图，至少有______条弧。【北京轻工业学院 2000  一、4（2分）】   
15．有n个顶点的有向图，至少需要量______条弧
才能保证是连通的。【西南交通大学 2000 一、3】 
38．设g是含有n顶点（设顶点编号为1,2,…,n）的有向无环图。将g用如下定义的邻接表存储：
   type   arcptr=↑arcnode;
          arcnode=record{邻接表中的结点}
adjvex:1..n;  nextarc:arcptr; end;
          vexnode=record{邻接表的表头结点}
vexnum: 1..n;  firstarc:arcptr;  mpl:integer  end;
   hnodes=array[1..n] of  vexnode;
请编写一个非递归算法求g的每个顶点出发的最长路径的长度（每条弧的长度均为1）并存入mpl域中。 要求：首先写出算法思想，然后写算法过程。【山东科技大学 2001 六 （20分）】
39．图g有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生g的最小生成树的算法。
【东南大学 1994 四（18分）】
40．设g是一个用邻接表表示的连通无向图。对于g中某个顶点v，若从g中删去顶点v及与顶点v相关联的边后，g变成由两个或两个以上非空连通分量所组成的图，则称v是原来图g的一个关节顶点。如下图中，只有顶点4和顶点6是关节顶点，而其它顶点都不是关节顶点。试叙述寻找图g的所有关节顶点的算法，并用算法语言（pascal或c）编写一个实现你所给出的算法的程序。【复旦大学 1996 八 （20分）】

41．对于一个使用邻接表存储的有向图g，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。
（1）．给出完成上述功能的图的邻接表定义（结构）：（4分）
（2）．定义在算法中使用的全局辅助数组。（4分）
（3）．写出在遍历图的同时进行拓扑排序的算法：（10分）
【东北大学 1999 五 (18分)】 【清华大学 1997 一（18分）】
42．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。
（1）．试用一种数据结构表示地图上各国相邻的关系，（６分）。
（2）．描述涂色过程的算法。（不要求证明）（１２分）。
【浙江大学 2002 八 （18分）】

上一页234下一页