第七章复习题

1、第二十三讲第七章 复习题第二十三讲1图中有关路径的定义是（ A ）。 A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列 C由不同边所形成的序列 D上述定义都不是2设无向图的顶点个数为n，则该图最多有（B）条边。 An-1 Bn(n-1)/2 C n(n+1)/2 Dn2第二十三讲3一个n个顶点的连通无向图，其边的个数至少为（ A ）。 An-1 Bn Cn+1 Dnlogn4要连通具有n个顶点的有向图，至少需要（ B ）条边。 An-l Bn Cn+l D2n第二十三讲5n个结点的完全有向图含有边的数目（D）。An*n n（n） Cn2 Dn*（nl）6一个有n个结点的图，

2、最少有（ B ）个连通分量，最多有（ D ）个连通分量。A0 B1 Cn-1 DN7在一个无向图无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。A1/2 B2 C1 D4第二十三讲8下列哪一种图的邻接矩阵一定是对称矩阵？（ B ）A有向图 B无向图 CAOV网 DAOE网9. 下列说法不正确的是（ C ）。 A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图 D图的深度遍历是一个递归过程第二十三讲10无向图G=(V,E),其中：V=a,b,c

3、,d,e,f, E=(a,b),(a,e), (a,c), (b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（ D） Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b11下面哪一方法不能判断出一个有向图是否有环（C）：A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径第二十三讲12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 AG中有弧 BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 第二十三讲14已知有

4、向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6, V7，E= , , , , , ,G的拓扑序列是（ A ）。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V715. 关键路径是事件结点网络中（ A ）。A从源点到汇点的最长路径 C最长回路 B从源点到汇点的最短路径 D最短回路第二十三讲16. 下面关于求关键路径的说法不正确的是（ C ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最

5、迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（改为发生） D关键活动一定位于关键路径上17下列关于AOE网的叙述中，不正确的是（ B ）。A关键活动不按期完成就会影响整个工程的完成时间B任一个关键活动提前完成，整个工程都将会提前完成C所有的关键活动提前完成，则整个工程将会提前完成D某些关键活动提前完成，会使整个工程提前完成第二十三讲18.G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。 19如果含n个顶点的图形形成一个环，则它有_n_棵生成树。20. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历。

6、 第二十三讲21.设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1=i=1&l.ri.key!=k) i-; if (i=1) return（i） else return (0); 第二十三讲其中，循环条件 i=1 判断查找是否越界。 利用监视哨可省去这个条件，从而提高查找效率。 下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为： niniiniiininnCnCPASL111) 1(21) 1(11第二十三讲

7、折半查找法折半查找法 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。图8.1给出了用折半查找法查找12、50的具体过程， 其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。 第二十三讲6121518222528

8、354658601234567891011low 1mid 6high 116121518222528354658601234567891011low 1mid 3high 56121518222528354658601234567891011low 1mid 1high 26121518222528354658601234567891011low 2mid 2high 2(a) 用折半查找法查找 12的过程6121518222528354658601234567891011low 1mid 6high 116121518222528354658601234567891011low 7mid

9、9high 116121518222528354658601234567891011low 10mid 10high 116121518222528354658601234567891011low 10high 9(b) 用折半查找法查找 50的过程第二十三讲折半查找的算法如下： int BinSrch （SqList l, KeyType k） low=1 ; high=l.length; /*置区间初值*/ while ( low=high) mid=(low+high) / 2; if (k=l.rmid.key) return（mid）; /*找到待查元素*/ else if (kl.

10、rmid. key) high=mid-1; /*未找到，则继续在前半区间进行查找*/ else low=mid+1; /*继续在后半区间进行查找*/ return (0); 第二十三讲 折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录， 左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。 第二十三讲63194

11、71025811具有具有11个元素的有序表进行二分查找时，查找成个元素的有序表进行二分查找时，查找成功时的时间复杂度是什么？功时的时间复杂度是什么？1133)4*44*32*21 (1111niiibsCPASL第二十三讲 由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为log2n+1。这样，折半查找成功时，关键字比较次数最多不超过log2n+1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功时，关键字比较次数最多也不超过判定树的深度log2n+1。为便于讨论，假定表的长度n=2h-1，则相

12、应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等， 则折半查找成功时的平均查找长度为 njjniiibsnnnjnCPASL12111) 1(log121第二十三讲分块查找法分块查找法 分块查找法要求将列表组织成以下索引顺序结构： 首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。 构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。 图8.2所示为一个索引顺序表。其中包括三个块，第一个块的起始地址为0，块内最

13、大关键字为25；第二个块的起始地址为5， 块内最大关键字为58；第三个块的起始地址为10，块内最大关键字为88。 第二十三讲图8.2 分块查找法示意 255888索引表各块内的最大关键字各块的起始地址1814122582832453658608871列表0123456789101112第二十三讲 分块查找的基本过程如下： (1) 首先，将待查关键字K与索引表中的关键字进行比较， 以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。 (2) 进一步用顺序查找法，在相应块内查找关键字为K的元素。 例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为253658，所以36在第二个块中， 进一步在第二个块中顺序查找， 最后在8号单元中找到36。 第二十三讲 分块查找的平均查找长度由两部分构成， 即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度为LW。 ASLbs=LB+LW 假定将长度为n的表分