第七章图：习题
习题
一、选择题
1．设完全无向图的顶点个数为n，则该图有( )条边。
A. n-l
B. n(n-l)/2
C.n(n+l)/2
D. n(n-l)
2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。
A.3
B.2
C.1
D.1/2
3．有向图的一个顶点的度为该顶点的( )。
A.入度
B. 出度
C.入度与出度之和
D.(入度+出度)/2
4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。
A.强连通图
B.连通图
C.非连通图
D.非强连通图
5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。
A.上三角矩阵
B.稀疏矩阵
C.对角矩阵
D.对称矩阵
6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵
A.第i列元素之和
B.第i行元素之和减去第i列元素之和
C.第i行元素之和
D.第i行元素之和加上第i列元素之和
7．对于具有e条边的无向图，它的邻接表中有( )个边结点。
A.e-l
B.e
C.2(e-l)
D. 2e
8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。
A. O(n2)
B. O(n*e)
C. O(n*logn)
D.O(e)
9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( )
A.n
B.n+l
C.n-l
D.n+e
10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。
A.最小
B.任何
C.广度优先
D.深度优先
二、填空题
1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。
2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。
3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。
4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。
5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。
6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。
7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。
8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个___ _来存放入度为零的顶点。
三、简答题
l．回答以下问题：
(1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？
(2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多少非零元素？是否为稀疏矩阵？
2．题图7-1为一有向图，按要求回答问题：
(1)写出各顶点的入度、出度和度。
(2)给出该图的邻接矩阵。
(3)给出该图的邻接表。
(4)给出该图的十字链表。
3．题图7-2为一无向图，请按要求回答问题：
(1)画出该图的邻接表。
(2)画出该图的邻接多重表。
(3)分别写出从顶点1出发按深度优先搜索遍历算法得到的顶点序列和按广度优先搜索
遍历算法得到的顶点序列。
4．题图7-3为一带权无向图，请按要求回答问题。
(1)画出该图的邻接矩阵，并按普里姆算法求其最小生成树。
(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。
5．题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra算法求从顶点1到其他各项点的最短路径，要求给出整个计算过程。
6．题图7-5为一个带权有向图
(1)给出该图的邻接矩阵。
(2)请用弗洛伊德算法求出各顶点对之间的最短路径长度，要求写出其相应的矩阵序列。
7．对于有向无环图，
(1)叙述求拓扑有序序列的步骤。
(2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。
8．题图7-7是一个AOE网，试求：
(1)每项活动的最早开始时间和最迟开始时间。
(2)完成整个工程至少需要多少天。
(3)哪些是关键活动。
(4)是否存在某些活动，当提高其速度后能使整个工期缩短。
四、算法设计题
1．编写一个算法，判断图G中是否存在从顶点v i到v j的长度为k的简单路径。
2．以邻接表作为图的存储结构，编写实现连通图G的深度优先搜索遍历（从顶点v 出发）的非递归函数。
3．给定n个村庄之间的交通图。若村庄i与村庄j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值Wij表示这条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院。试编写一个算法，求出该医院应建在哪个村庄，才能使距离医院最远的村庄到医院的路程最短。
4．编写一个函数，计算给定的有向图的邻接矩阵的每对顶点之间的最短路径。
第七章图
第7章图
一、选择题（参考答案）：
1．B 2．B 3．C 4．B 5．D
6. C 7．D 8．A,D 9．D 10.A
二、填空题（参考答案）
1．n(n-l)/2, n(n-l)。2．第i行。
3. 2e, e0 4．邻接表，逆邻接表。
5．权值递增，顶点连通。 6．O(e)，O(e)。
7．n，n-l。8．栈。
三、简答题
1．回答以下问题：
(1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？
(2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多少非零元素？是否为稀疏矩阵？
【解答】(l)有n个顶点的无向连通图最多有n(n-l)/2条边（构成一个无向完全图的情况）;最少有n-l条边（n个顶点是连通的）。
(2)这样的矩阵共有lOOO*1000=1000000个矩阵元素，因为有1000条边，所以有2 000非零元素，因此该矩阵是稀疏矩阵。
2．题图7-1为一有向图，按要求回答问题：
题图7-1
(1)写出各顶点的入度、出度和度。
(2)给出该图的邻接矩阵。
(3)给出该图的邻接表。
(4)给出该图的十字链表。
【解答】(l)各顶点入度、出度和度如下表所示。
(2)邻接矩阵如下所示。
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
(3)邻接表如下所示。
(4)十字接表如下所示。
3．题图7-2为一无向图，请按要求回答问题：
(1)画出该图的邻接表。
(2)画出该图的邻接多重表。
(3)分别写出从顶点l出发按深度优先搜索遍历算法得到的顶点序列和按广度优先搜索
遍历算法得到的顶点序列。
题图7-2
【解答】(1)邻接表如下所示。
(2)多重邻接表如下所示。
(3)从顶点1出发，深度优先搜索遍历序列为：123456;广度优先搜索遍历序列为：123 564。
4．题图7-3为一带权无向图，请按要求回答问题：
(1)画出该图的邻接矩阵，并按普里姆算法求其最小生成树。
(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。
【解答】(1)按普里姆算法其最小生成树如下所示。
(2)按克鲁斯卡尔算法其最小生成树如下所示。
5．题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra
算法求从顶点l到其他各顶点的最短路径，要求给出整个计算过
程。
【解答】(1)初值：s[]={1），dist[]={0，20，15，∞，
∞，∞}（顶点1到其他各项点的权值），path[]={1，1，
1，
-l，-1，-1）(顶点l到其他各项点有弧存在时为1，否则
为-1)。
(2)在V-S中找最近（dist[]最小）的顶点3，加入S中，即s[]={l，3），并重新计算顶点l到达顶点2，4，5和6的距离，修改相应的dist值：
dist[2]=min{dist[2], dist[3]+cost[3][2]}=min{20, 15+4}=19;
dist[6l=min{dist[6], dist[3]+cost[3][6]}==Inin{∞，15+10}=25;
则有dist[]={0，19，15，∞，∞，25}，path[]={l，3，1，-l，-l，3}。
(3)在V-S中找出最近的顶点4，加入S中，即s[]={1，3，2}，并重新计算顶点1到达顶点4，5和6的距离，修改相应的dist值：
dist[5]-min{dist[5], dist[2]+ cost[2][5])-min{∞，19+10}=29,
则有dist[]={0,19,15, ∞，29,25），path[]={l,3,l，-1,2,3}.
(4)在V-S中找出最近的顶点6，加入S中，即s[]．{1，3，2，6），并重新计算顶点l到达顶点4和5的距离，修改相应的dist值：
dist[4]=min{dist[4], dist[6]+cost[6][4])=min{∞..,25+4}=29,
则有dist[]={0, 19, 15, 29, 29, 25}, path[]={l,3,1,6,2,3}。
(5)在V-S中找出最近的顶点4，加入S中，即s[]：{l，3，2，6，4}，并重新计算顶点l到达顶点5的距离，此时不需要修改dist值，则有dist[]={0，19，15，29，2 9，25），path[]={l，3， l，6，2， 3}。
(6)在V-S中找出最近的顶点5，加入S中，即s口={l，3，2，6，4，5}。此时S 中包含了图的所有顶点，算法结束。最终dist[]={0，19，15，29，29，25），path[]= {1，3，l，6，2， 3}。
由此得到：
从顶点1到顶点2的最短路径长度为：19 最短路径为：2<-3<-1
从顶点l到顶点3的最短路径长度为：15 最短路径为：3<-1
从顶点l到顶点4的最短路径长度为：29 最短路径为：4<-6<-3<-1
从顶点l到顶点5的最短路径长度为：29 最短路径为：5<-2<-3<-l
从顶点l到顶点6的最短路径长度为：25 最短路径为：6<-3<-1
6．题图7-5为一个带权有向图，
(1)给出该图的邻接矩阵。
(2)请用弗洛伊德算法求出各顶点对之间的最短路径长度，要求写出其相应的矩阵序列。
【解答】(1)邻接矩阵如下：
0 10 ∞∞
15 0 6 ∞
3 ∞0 4
∞8 2 0
(2)采用弗洛伊德算法求最短路径的过程如下：
7．对于有向无环图，
(1)叙述求拓扑有序序列的步骤。
(2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。
【解答】(1)参见7.6节的介绍。
(2)它的4个不同的拓扑有序序列是：12345678，12354678，12347856，1234756 8。
8．题图7-7是一个AOE网，试求：
(l)每项活动的最早开始时间和最迟开始时间。
(2)完成整个工程至少需要多少天（设弧上权值为天数）。
(3)哪些是关键活动。
(4)是否存在某些活动，当提高其速度后能使整个工期缩短。
【解答】(1)所有活动的最早开始时间e(i)、最迟开始时间l(i)以及d(i)=1(i)一e(i)，如下所示。
(2)完成此工程最少需要23天。
(3)从以上计算得出关键活动为：a2，a4，a6，a8，a9，aio，a12，a13和a14。
(4)存在a2，a4，al4活动，当其提高速度后能使整个工程缩短工期。
四、算法设计题
1．编写一个算法，判断图G中是否存在从顶点vi到vj的长度为k的简单路径。
【解答】采用深度优先遍历算法来判断图G中是否存在从顶点vi到vj的长度为k 的简单路径。其中，变量n用于记录经过的顶点数，当n=k+l时，表示路径长度为k;suc 记录是否成功地找到了所求路径。算法如下所示。
#define Max<一个大于顶点数的常量>
int visited [Max]， //全局变量
int exist (ALGraph *g,int vi; int Vj, intk)
{
int i，suc;
for（i=O;i
visited [i] =0;
suc=0; n=0;
dfs (g, vi, Vj, suc,k);
return suc;
}
void dfs (ALGraph *g,int V,int Vj, int &suc, int k)
{
ArcNode *p;
Visited [v] =l;
n++;
if (n==k+l＆＆v==vj)suc=l; //找到了满足题意的路径
if(n p=g->adj list[v] ->firstarc; while(p!=NULL&& suc==0){ if (visited[p->adj vex] ==0){ dfs (g, p->adjvex, Vj, suc,k)j n--; } p=p->nextarc; } } } 2．以邻接表作为图的存储结构，编写实现连通图G的深度优先搜索遍历（从顶点v出发）的非递归函数。 【算法基本思想】第一步，首先访问图G的指定起始顶点v;第二步，从v出发，访问一个与V邻接且未被访问的顶点p，再从顶点p出发，访问与p邻接且未被访问的顶点q，如此重复，直到找不到未访问过的邻接顶点为止;第三步，退回到尚有未被访问过的邻接点的顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。为此，用一个栈保存被访问过的结点，以便回溯查找已被访问结点的未被访问过的邻接点。具体函数如下： #define MAXVEX 100 //定义顶点数的最大值 Void dfs (Adj List g，int v，int n) //n表示顶点数 { Struct ArcNode *stack[MAXVEX],*p; int visited [MAXVEX], top=0,i; for (i-0，i printf(¨%d\n¨，v); p=g[v]．firstarc; while (top>0||p) { while (p) if (visited[p->adj vex] ==0) p=p->nextarc //查找下一邻接点 else { printf(¨%d\n¨, p->adjvex); visited [p->adjvex] =l; top++; //将访问过的结点入栈 stack[top] =p; p=g [p->adj veX].firstarc; } if (top>0) { p=stack [top]; top--; //退钱，回溯查找已被访问结点的未被访问过的邻接点 p=p->nextarc; } } } 3．给定n个村庄之间的交通图。若村庄i与村庄j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值Wij表示这条道路的长度。现打算在这n个村庄中选择一个村庄建一所医院。试编写一个算法，求出该医院应建在哪个村庄，才能使距离医院最远的村庄到医院的路程最短。 将n个村庄的交通图用邻接矩阵A表示。 【算法思路】先应用弗洛伊德算法计算每对顶点之间的最短路径;然后找出从每一个顶 点到其他各顶点的最短路径中最长的路径;最后在这n条最长路径中找出最短的一条。算法如 下： #define n<村庄个数> int maxminpath (float A[n] [n]) { int i,j,k; float s.min=10000; //最短路径长度min置初值10000 for(k=O;k for(i=O;i for(j=0;j if (A[i][k]+A[k][j] A[i][j]=A[i][k]+A[k][j]; k=-l; f。r(i=O; i s=0; f。r(j=0;j if(A[i][j]>s) s=A[i][j]; if (s k=i; min=s; } } return k： } 4．编写一个函数计算给定的有向图的邻接矩阵的每对顶点之间的最短路径。本题实质上就是狄杰斯特拉算法。 【算法思想】假设原点为v： (l)置集合s的初态为空。 (2)把顶点v放入集合s中。 (3)确定从v开始的n-l条路径。 (4)选择最短距离的顶点u。 (5)把顶点u加入集合s中。 (6)更改距离。 【解答】具体实现如下： #define MAXVEX 100 //定义顶点数的最大值 void Shortestpath (int v,int cost [MAXVEX] [MAXVEX], int d ist [MAXVEX], int) //最终的dist[j](1≤j≤n)为从顶点v到项点j之间的最短路径长度 f int s[mAXVEXl,i.u,nux,w; for（i=O;i≤n-l; i++） //置集合s的初态为空 ‘ s[i]=O; dist[i] =cost[v][i]; s [v]=1; //把顶点v放入集合s dist [v] =O; num=0; while (num { U=Choose(s，dist,n); s[u]=l; num++; //把顶点u放入s for (w=0;w if ( !s[w]) if (dist[u]+cost [u] [w] dist [w] =dist[u]+cost[u] [w]; } } 其中函数choose0的功能是返回满足条件dist[u]=minimum(dist[w])，且s[w]=0的顶点u。定义如下： int choose (int s[],int dist[],int n) { int min, i=O,u; while (s[i] ==1) i++, min=dist [i]; u=i; while (i {if(s[i]==1)i++; else if (min>dist[i] {u=i; min=dist [i] } i++; } return U： } 数据结构习题和答案及解析 数据结构是计算机科学中非常重要的一个领域，它关注数据的存储、组织和管理方式。在学习数据结构的过程中，遇到习题是必不可少的，通过解答这些习题可以更好地理解和掌握数据结构的概念和应用。以 下是一些常见的数据结构习题及其答案和解析，希望可以帮助读者更 好地学习和理解数据结构。 习题一：栈的应用 题目描述：设计一个栈，使其具有获取栈中最小元素的操作。 解答及解析：可以通过两个栈来实现，一个栈用于存储数据，另一 个栈用于存储当前最小元素。在入栈时，如果新的元素比当前最小元 素小，则将新元素同时入栈到数据栈和最小栈；在出栈时，如果当前 出栈元素与最小栈的栈顶元素相同，则同时出栈。这样，最小栈的栈 顶元素始终为当前栈的最小元素。 习题二：队列的应用 题目描述：设计一个队列，使其具有获取队列中最大元素的操作。 解答及解析：可以通过两个队列来实现，一个队列用于存储数据， 另一个队列用于存储当前最大元素。在入队时，如果新的元素比当前 最大元素大，则将新元素同时入队到数据队列和最大队列；在出队时，如果当前出队元素与最大队列的队首元素相同，则同时出队。这样， 最大队列的队首元素始终为当前队列的最大元素。 习题三：链表的操作 题目描述：给定一个链表，删除链表中倒数第n个节点，并返回链表的头节点。 解答及解析：使用双指针法来解决该问题。首先让一个指针从链表的头节点向前移动n+1步，然后再让另一个指针从链表的头节点开始移动。这样两个指针之间的间隔为n，当第一个指针到达链表末尾时，第二个指针指向的节点就是倒数第n个节点的前一个节点。接着，将第二个指针指向的节点的next指针指向下下个节点，完成删除操作。 习题四：树的遍历 题目描述：给定一个二叉树，按照中序遍历的顺序返回其节点值的集合。 解答及解析：采用递归的方式进行中序遍历，先遍历左子树，然后访问根节点，最后遍历右子树。对于任意一个节点，递归遍历其左子树，将节点值添加到集合中。然后访问该节点，并将节点值添加到集合中。最后递归遍历右子树，将节点值添加到集合中。最终得到的集合即为中序遍历的结果。 习题五：图的搜索 题目描述：给定一个有向图，判断是否存在从起点到终点的路径。 解答及解析：可以使用深度优先搜索算法（DFS）来解决该问题。从起点开始进行深度优先搜索，如果找到终点，则存在从起点到终点的路径；如果遍历完所有节点都没有找到终点，则不存在路径。在搜 数据结构图练习题 数据结构图练习题 在计算机科学领域中，数据结构是一种用来组织和存储数据的方式。而图是一 种常见的数据结构，它由一组节点和连接这些节点的边组成。图可以用来表示 各种各样的关系，比如社交网络中的用户关系、城市之间的道路网络等等。在 本文中，我们将探讨一些与图相关的练习题，帮助读者更好地理解和应用图的 概念。 1. 最短路径问题 最短路径问题是图论中的经典问题之一。给定一个带权重的有向图，我们需要 找到从一个起始节点到目标节点的最短路径。这里的权重可以表示为距离、时 间或者其他度量。解决这个问题的算法有很多，其中最著名的是Dijkstra算法 和Bellman-Ford算法。读者可以尝试使用这些算法来解决一些具体的实例，比 如计算两个城市之间的最短路径。 2. 拓扑排序 拓扑排序是对有向无环图(Directed Acyclic Graph，简称DAG)进行排序的一种算法。在一个DAG中，节点之间存在一种偏序关系，即某些节点必须在其他节点之前进行处理。拓扑排序可以帮助我们确定这种偏序关系，从而找到一种合理 的处理顺序。比如，在编译器中，拓扑排序可以用来确定源代码中各个函数的 调用顺序。读者可以尝试编写一个拓扑排序算法，并应用到一些具体的场景中。 3. 最小生成树 最小生成树是一个无向连通图中一棵权值最小的生成树。在一个连通图中，最 小生成树可以帮助我们找到一种最优的连接方式，以满足一些约束条件。最常 用的算法是Prim算法和Kruskal算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个城市之间建设光纤网络，以最小的成本实现全覆盖。4. 图的遍历 图的遍历是指按照某种方式访问图中的所有节点。常见的遍历算法有深度优先 搜索(DFS)和广度优先搜索(BFS)。DFS通过递归地访问每个节点的邻居节点，直 到所有节点都被访问完。BFS则通过队列来实现，先访问起始节点的邻居节点，然后依次访问它们的邻居节点，直到所有节点都被访问完。读者可以尝试实现 这两种遍历算法，并观察它们的不同特点。 5. 最大流问题 最大流问题是图论中的一个经典问题，它可以用来解决一些网络流的优化问题。在一个有向图中，每条边都有一个容量，表示通过这条边的最大流量。最大流 问题的目标是找到从源节点到汇节点的最大流量。常用的解决方法是Ford-Fulkerson算法和Edmonds-Karp算法。读者可以尝试使用这些算法来解决一些 具体的实例，比如在一个供水网络中确定最大供水量。 通过以上的练习题，读者可以更好地理解和应用图的概念。图作为一种重要的 数据结构，广泛应用于计算机科学领域的各个方面。掌握图的基本概念和算法，对于解决实际问题和提高编程能力都有很大的帮助。希望读者能够通过练习和 实践，深入理解图的特性，并能够灵活运用它们解决各种问题。 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 第七章图 一、名词解释 1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历 7.图的最小生成树 一、填空题 1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但 习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 数据结构练习题(含答案)数据结构练习题(含答案) 一、单项选择题 1. 在数组中插入和删除元素最慢的时间复杂度是： A. O(1) B. O(log n) C. O(n) D. O(n^2) 答案：C 2. 在链表中插入和删除元素最慢的时间复杂度是： A. O(1) B. O(log n) C. O(n) D. O(n^2) 答案：A 3. 下列哪种数据结构采用了“先进先出”的存储方式： A. 栈 B. 队列 D. 二叉树 答案：B 4. 下列哪种数据结构采用了“先进后出”的存储方式： A. 栈 B. 队列 C. 哈希表 D. 二叉树 答案：A 5. 以下哪种排序算法的时间复杂度最好： A. 冒泡排序 B. 插入排序 C. 快速排序 D. 选择排序 答案：C 二、填空题 1. 假设有一个长度为10的数组arr，要访问第7个元素，应该使用arr[]表示。 2. 栈的特点是后进先出，所以从栈中取出第一个元素需要调用的操作是。 答案：pop 3. 结点的度可以理解为： 答案：与该结点相连的边的数目 4. 图中的结点称为： 答案：顶点 5. 在二叉树中，度为 2 的结点称为。 答案：内部结点 三、编程题 1. 使用Python编写代码，实现冒泡排序算法，并对以下数组进行排序：[5, 2, 9, 1, 3, 6, 8, 7, 4] 答案： ```python def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] arr = [5, 2, 9, 1, 3, 6, 8, 7, 4] bubble_sort(arr) print(arr) ``` 2. 使用Java编写代码，实现队列的基本操作：入队（enqueue）、出队（dequeue）、查看队首元素（peek）。 答案： ```java import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { Queue 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 第7章图 一、单选题 01、在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2 B．1 C．2 D．4 02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A．1/2 B．1 C．2 D．4 03、有8个结点的无向图最多有条边。 A．14 B．28 C．56 D．112 04、有8个结点的无向连通图最少有条边。 A．5 B．6 C．7 D．8 05、有8个结点的有向完全图有条边。 A．14 B．28 C．56 D．112 06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A．O(n) B．O(e) C．O(n+e) D．O(n2) 09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2 10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6 C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 6 11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历15、任何一个无向连通图的最小生成树。 A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在 ( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A．n、2e B．n、e C．n、n+e D．2n、2e 17、判断有向图是否存在回路，可以利用算法。 A．关键路径 B．最短路径的Dijkstra C．拓扑排序D．广度优先遍历 18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 19、求最短路径的Dijkstra算法的时间复杂度是___。A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。 A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。 A．第i行非∞的元素之和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 22、一个有n个顶点的无向图最多有条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 A．n B．(n-1)2 C．n-1 D．n2 24、对某个无向图的邻接矩阵来说，。 A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数 25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。 A．abecdf B．acfebd C．aebcfd D．aedfcb 26、已知图的表示如上题，若从顶点a出发按广度搜索法进 数据结构习题 第七章图 一、选择题 1、一个有n个顶点的无向图最多有（ C ）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有4个顶点的无向完全图有（ A ）条边。 A、6 B、12 C、16 D、20 3、具有6个顶点的无向图至少有（ A ）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 4、设连通图G的顶点数为n，则G的生成树的边数为（ A ）。 A、n-1 B、n C、2n D、2n-1 5、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ D ）和（ B ） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 6、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ B ）和（ D ）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 7、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ C ）和（ B ）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2 8、已知一个图如下，在该图的最小生成树中各边上权值之和为（ C ），在该图的最小生成树中，从v1到v6的路径为（ G ）。 A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 9、正确的AOE网必须是（ C ） A、完全图 B、哈密尔顿图 C、无环图 D、强连通图 10、已知一个图如下，则由该图得到的一种拓扑序列为（ A ）。 A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 11、下面结论中正确的是（ B ） A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 数据结构习题及解答 第1章 概述 【例1-1】分析以下程序段的时间复杂度。 for(i=0;i log) 得：T（n）=O(n2 【例1-4】有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n<=1) return(1);① else return(n*fact(n-1));② } 解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。 由此可得fact（n）的时间复杂度为O(n)。 习题1 一、单项选择题 1.数据结构是指（1. A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（3. D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4. B）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（5. C、），算法分析的两个主要方面是（A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（6. C、），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7. B）。 第七章 图 一、选择题 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】 3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A ．0 B ．1 C ．n-1 D ．n 【北京邮电大学 2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2分）】 A ．1/2 B ．2 C ．1 D ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学1999一、14】 A ．5 B ．6 C ．8 D ．9 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A ．邻接矩阵 B ．逆邻接表 C ．邻接多重表 D ．十字链表 E ．邻接表 【北京工业大学 2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接阵矩???? ? ???? ?=01 0101 010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右 子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A ．不确定 B ．2n C ．2n+1 D ．2n-1 7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ） A ．?logn ?+1 B ．logn+1 C ．?logn ? D ．logn-1 9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1= 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数 据的基本单位；___________是数据的最小单位。通常被计 算机加工处理的数据不是孤立无关的，而是彼此之间存在 着某种联系，将这种数据间的联系称为________。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成 的二元组：DS=（D，R）。 3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>， <01，03>，<01，04>，<02，05>，<02，06>，<03，07>， <03，08>，<03，09>}。则此数据结构属于_____________ 结构。 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时， 则表示为__________；成正比关系时，则表示为 ___________；成对数关系时，则表示为___________；成 平方关系时，则表示为__________。 5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为 _____________；数据结构的存储结构主要包括 ____________和____________两种类型。 6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后 继结点，其余每个结点有且仅有_______个后继结点。 7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后 继结点，其余结点可以有_________个后继结点。 8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 一、单选题 1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。 A.7 B.8 C.6 D.5 正确答案：A 2、设图G=(V,VR)，其中: V={A,B,C,D,G}， VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。 A. B. C. D. 正确答案：C 3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。 A.n-1 B.n+2 C.n D.n+1 正确答案：C 4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。 A.1 B.2 C.3 D.1/2 正确答案：B 5、一个无向连通图的生成树是该连通图的_____。 A.极小连通子图 B.强连通子图 C.连通子图 D.极大连通子图 正确答案：A 6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。 A.n(n+1)/2 B.（n-1）2 C. n2 D. （n+1）2 正确答案：C 7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。 A.O(n2) B.O(n+e） C.O(n*e） 正确答案：D 8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。 A.O(n） B.O(n*e） C.O(n+e） D.O(n2) 正确答案：C 9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。 A.G'是G的连通分量 B.G'是G的一个无环子图 C.G'是G的极小连通子图且V=V' D.G'是G的子图 正确答案：A 10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。 A.7 B.6 C.5 D.8 正确答案：B 11、 n个顶点的有向图为强连通图时，至少含有________。 A.n条弧 B.n(n-1)/2条弧 C.n(n-1)条弧 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 D．2 ．4 C2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 D．4 C．2 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 D ．n(n-1)/2 C．n-1 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) D．n(n-l)/2 C．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) D．C．n(n-l)/2 n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。nnB．×．An (n-l) ×(n-l)．D n-1 C． ．无向图的邻接矩阵是一个______。7 ．零矩阵B ．对称矩阵A．C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e D．2e C．2n 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e DC．2n ．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边 D．不是入边也不是出边C．入边和出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边 D ．不是人边也不是出边C．入边和出边数据结构习题和答案及解析
数据结构 图 练习题
数据结构 第六章 图 练习题及答案详细解析(精华版)
数据结构 图的习题
数据结构第7章 图习题
数据结构图习题
数据结构练习题(含答案)
数据结构练习题(含答案)
数据结构习题与答案--图
数据结构 图 作业及部分答案
数据结构各章习题及答案!
数据结构图练习题(附答案)
数据结构第6章 树习题+答案
数据结构习题(含答案)
数据结构(图)习题与答案
数据结构图习题分解
相关主题
文本预览