第七章复习题

第七章复习题,1,1图中有关路径的定义是（A）。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由不同边所形成的序列D上述定义都不是2设无向图的顶点个数为n，则该图最多有（B）条边。An-1Bn(n-1)/2Cn(n+1)/2Dn2,2,3一个n个顶点的连通无向图，其边的个数至少为（A）。An-1BnCn+1Dnlogn4要连通具有n个顶点的有向图，至少需要（B）条边。An-lBnCn+lD2n,3,5n个结点的完全有向图含有边的数目（D）。An*nn（n）Cn2Dn*（nl）6一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。A0B1Cn-1DN7在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A1/2B2C1D4,4,8下列哪一种图的邻接矩阵一定是对称矩阵？（B）A有向图B无向图CAOV网DAOE网9.下列说法不正确的是（C）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次B遍历的基本算法有两种：深度遍历和广度遍历C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程,5,10无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（D）Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b11下面哪一方法不能判断出一个有向图是否有环（C）：A深度优先遍历B.拓扑排序C.求最短路径D.求关键路径,6,12.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。AG中有弧BG中有一条从Vi到Vj的路径CG中没有弧DG中有一条从Vj到Vi的路径,7,14已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（A）。AV1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7DV1,V2,V5,V3,V4,V6,V715.关键路径是事件结点网络中（A）。A从源点到汇点的最长路径C最长回路B从源点到汇点的最短路径D最短回路,8,16.下面关于求关键路径的说法不正确的是（C）。A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（改为发生）D关键活动一定位于关键路径上17下列关于AOE网的叙述中，不正确的是（B）。A关键活动不按期完成就会影响整个工程的完成时间B任一个关键活动提前完成，整个工程都将会提前完成C所有的关键活动提前完成，则整个工程将会提前完成D某些关键活动提前完成，会使整个工程提前完成,9,18.G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。19如果含n个顶点的图形形成一个环，则它有_n_棵生成树。20.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历。,10,21.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：,22,折半查找法,折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。图8.1给出了用折半查找法查找12、50的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。,23,24,折半查找的算法如下：,intBinSrch（SqListl,KeyTypek）low=1;high=l.length;/*置区间初值*/while(low=high)mid=(low+high)/2;if(k=l.rmid.key)return（mid）;/*找到待查元素*/elseif(kl.rmid.key)high=mid-1;/*未找到，则继续在前半区间进行查找*/elselow=mid+1;/*继续在后半区间进行查找*/return(0);,25,折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。,26,具有11个元素的有序表进行二分查找时，查找成功时的时间复杂度是什么？,？,27,由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为log2n+1。这样，折半查找成功时，关键字比较次数最多不超过log2n+1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功时，关键字比较次数最多也不超过判定树的深度log2n+1。为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为,28,分块查找法,分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。图8.2所示为一个索引顺序表。其中包括三个块，第一个块的起始地址为0，块内最大关键字为25；第二个块的起始地址为5，块内最大关键字为58；第三个块的起始地址为10，块内最大关键字为88。,29,图8.2分块查找法示意,30,分块查找的基本过程如下：(1)首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。(2)进一步用顺序查找法，在相应块内查找关键字为K的元素。例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为253658，所以36在第二个块中，进一步在第二个块中顺序查找，最后在8号单元中找到36。,31,分块查找的平均查找长度由两部分构成，即查找索引表时的平均查找长度为LB，以及在相应块内进