A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历
9. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3) 10. 求解最短路径的Floyd算法的时间复杂度为(D )。
A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 11．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
12．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ A ）。
A．存在 B．不存在
13．一个有向无环图的拓扑排序序列（ B ）是唯一的。
A．一定 B．不一定
14. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。
A．G中有弧
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 17．下列关于AOE网的叙述中，不正确的是（ B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 判断题
1. 有e条边的无向图，在邻接表中有e个结点。（ × ） 2. 有向图的邻接矩阵是对称的。（ × ） 3．任何无向图都存在生成树。（ × ）
4. 不同的求最小生成树的方法最后得到的生成树是相同的.（ × ） 5. 有环图也能进行拓扑排序。（ × ）
6. 关键路径是AOE网中从源点到终点的最长路径。（ √ ）
填空题
1．具有10个顶点的无向图，边的总数最多为__45_____。
2. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要___ n ___条弧。 3．n个顶点的连通无向图，其边的条数至少为___n-1____。
4．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_2(n-1)______个非零元素。 5．构造连通网最小生成树的两个典型算法是_普里姆算法、克鲁斯卡尔算法_____。 6. 有一个用于n个顶点连通带权无向图的算法描述如下：
11
（1）．设集合T1与T2，初始均为空； （2）．在连通图上任选一点加入T1； （3）．以下步骤重复n-1次：
a.在i属于T1，j不属于T1的边中选最小权的边； b.该边加入T2。
上述算法完成后，T2中共有__n-1__条边，该算法称_普里姆算法_算法，T2中的边构成图的_最小生成树_。
7．AOV网中,结点表示____活动____,边表示___联系__。AOE网中,结点表示___事件__,边表示__活动__。
8. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为____零_____的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是__ Vk 的入度减1，如为0则入栈____； （3）．若栈空时，输出顶点数小于图的顶点数，说明有___环路____，否则拓扑排序完成。
作业题
1．n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：（1）．图的顶点号从 0开始计； （2）．indegree 是有n个分量的一维数组，放顶点的入度；
（3）．函数 crein 用于算顶点入度； （4）．有三个函数push(data),pop( ),check( )其含义为数据 data进栈，退栈和测试栈是否空（不空返回1，否则0）。
crein( array ,indegree,n)
{ for (i=0;i for(i=0,i for (j=0;j topsort (array,indegree,n) { count= ((4)__ 0______) for (i=0;i { vex=pop( ); printf(vex); count++; for (i=0;i { k=array(6)__ [vex][i];______ if ((7)__ k!=0__) { indegree[i]--; if ((8)__ indegree[i]==0__ ) push(i); } } } if( count } 2．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 234?1 5?1342 124? 31235? 4 524?12 解： 1 2 3 1 2 5 3 4 4 5 3．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。 1621 215 111943 614 63356 18 16 16 解： 2 2 1 1 5 5 11 11 4 3 4 3 6 6 5 6 5 6 18 18 4、对下面的有向图，试利用DIJKSTRA算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。 13 10 v5 10 v6 15 v4 4 10 30 4 v2 2 20 v1 15 v3 14 第十章 选择题 1．下面给出的四种排序法中( D )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆排序 2．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 3．下面的排序算法中，不稳定的是（ CDF ） A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 (A )。 A. 选择 B. 冒泡 C. 快速 D. 插入 5. 在下面的排序方法中，辅助空间为O（n）的是( D ) 。 A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 6. 下列排序算法中，占用辅助空间最多的是：(A ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 7．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40 8．直接插入排序在最好情况下的时间复杂度为（ B ） A． O(logn) B． O(n) C． O(n*logn) D． O(n2) 9．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ． {5,9,17,21,23,25,30} 10．下列四个序列中，哪一个是堆（ C ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 判断 1．内排序要求数据一定要以顺序方式存储。 （ × ） 2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ × ） 3．直接选择排序算法在最好情况下的时间复杂度为O（N）。（× ） 4．在待排数据基本有序的情况下，快速排序效果最好。（ × ） 5．快速排序总比选择排序快。（√） 填空 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较__和记录的_移动_。 2．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_ Q A C S Q D F X R H M Y ____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是__ F H C D M 15 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库期末数据结构复习习题(含答案)(3)在线全文阅读。
相关推荐：