第七章复习题

第七章复习题1．图中有关路径的定义是（A）。

A．由顶点和相邻顶点序偶构成的边所形成的序列

B．由不同顶点所形成的序列

C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B）条边。

A．n-1B．n(n-1)/2C．n(n+1)/2

D．n23．一个n个顶点的连通无向图，其边的个数至少为（A）。

A．n-1B．nC．n+1D．nlogn4．要连通具有n个顶点的有向图，至少需要（B）条边。

A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。A．0B．1C．n-1D．N7．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A．1/2B．2C．1D．48．下列哪一种图的邻接矩阵一定是对称矩阵？（B）A．有向图B．无向图

C．AOV网D．AOE网9.下列说法不正确的是（C）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次

B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图

D．图的深度遍历是一个递归过程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）

A．a,b,e,c,d,fB．a,c,f,e,b,d

C．a,e,b,c,f,dD．a,e,d,f,c,b11．下面哪一方法不能判断出一个有向图是否有环（C）：A．深度优先遍历B.拓扑排序

C.求最短路径D.求关键路径12.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A．G中有弧<Vi，Vj>B．G中有一条从Vi到Vj的路径C．G中没有弧<Vi,Vj>D．G中有一条从Vj到Vi的路径

14．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（A）。

A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V715.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径C．最长回路B．从源点到汇点的最短路径D．最短回路16.下面关于求关键路径的说法不正确的是（C）。

A．求关键路径是以拓扑排序为基础的

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（改为发生）

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

21.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1<=i<=n〉，则e=__di____

22.Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。23.AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。24.有向图G可拓扑排序的判别条件是_图中无环_____。25.在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。26.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。查找的基本概念

列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。查找：

根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。显然，查找算法中涉及到三类参量：①查找对象K（找什么）；②查找范围L（在哪找）；③K在L中的位置（查找的结果）。其中①、②为输入参量，③为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。

平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为：其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH（哈希）查找法。顺序查找法顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。下面给出顺序结构有关数据类型定义：＃defineLIST_SIZE20typedef

struct{

KeyTypekey;

OtherType

otherdata;}RecordType;typedef

struct{

RecordTyper［LIST-SIZE+1］;/*r［0］为工作单元*/

intlength;}RecordList;基于顺序结构的算法如下：int

SeqSearch（RecordListl,KeyTypek）/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/{

l.r［0］.key=k;i=l.length;while(l.r［i］.key!=k)i--;return（i）;}其中l.r［0］称为监视哨，可以起到防止越界的作用。不用监视哨的算法如下：int

SeqSearch（RecordListl,KeyTypek）/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{i=l.length;while(i>=1&&l.r［i］.key!=k)i--;if(i>=1)return（i）

elsereturn(0);}其中，循环条件i>=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：折半查找法折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。图8.1给出了用折半查找法查找12、50的具体过程，其中mid=(low+high)/2，当high<low时，表示不存在这样的子表空间，查找失败。折半查找的算法如下：int

BinSrch

（SqListl,KeyTypek）{low=1;high=l.length;/*置区间初值*/while(low<=high){ mid=(low+high)/2;if(k==l.r［mid］.key)return（mid）;/*找到待查元素*/elseif(k<l.r［mid］.key)high=mid-1;/*未找到，则继续在前半区间进行查找*/elselow=mid+1;/*继续在后半区间进行查找*/}return(0);}折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。6319471025811具有11个元素的有序表进行二分查找时，查找成功时的时间复杂度是什么？？由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为［log2n］+1。这样，折半查找成功时，关键字比较次数最多不超过［log2n］+1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功时，关键字比较次数最多也不超过判定树的深度［log2n］+1。为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为分块查找法分块查找法要求将列表组织成以下索引顺序结构：

·首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。

·构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序