第七章图：习题
习题
一、选择题
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条边，所以有2000非零元素，因此该矩阵是稀疏矩阵。
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，29，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，12347568。 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 dist [MAXVE X], 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： } 一、单选题 C01、在一个图中，所有顶点的度数之和等于图的边数的倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A)1/2 B)1 C)2 D)4 B03、有8个结点的无向图最多有条边。 A)14 B)28 C)56 D)112 C04、有8个结点的无向连通图最少有条边。 A)5 B)6 C)7 D)8 C05、有8个结点的有向完全图有条边。 A)14 B)28 C)56 D)112 B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A)O(n) B)O(e) C)O(n+e) D)O(n2) C09、已知图的邻接矩阵，根据算法思想，则从顶点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 B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6 D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3 A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2 A13、图的深度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 D14、图的广度优先遍历类似于二叉树的。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 B15、任何一个无向连通图的最小生成树。 A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在 A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A)n、2e B)n、e C)n、n+e D)2n、2e C17、判断有向图是否存在回路，可以利用___算法。 A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历 A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。 1、特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非 零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所 在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组 表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下 标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的 起始地址与M按列存储时元素（）的起始地址相同。 A、M[2][4] B、M[3][4] C、M[3][5] D、M[4][4] 为第 3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。 一元素，其存储地址为1，每个元素占一个地址空间，则a 85 A. 13 B. 33 C. 18 D. 40 4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线 （i 7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1) 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 第8章图 8.2对于如图8.33所示的无向图，试给出： （1）图中每个顶点的度； （2）该图的邻接矩阵； （3）该图的邻接表； （4）该图的连通分量。 （1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=1；D(V6)=1. 0101000 0101000 1010000 1010000 0101100 0101100 1010100 (2)1010100 邻接矩阵 0011000 0011000 0000001 0000001 0000010 0000010 vV （3）邻接表 (4)连通分量 1： 2： 8.3图8.35所示的是某个无向图的邻接表，试：（1）画出此图； （2）写出从顶点A开始的DFS遍历结果； （3）写出从顶点A开始的BFS遍历结果。 （1）图8.35邻接表对应的无向图如图8.35.1所示 （2） 从顶点A 开始的D F S 遍历，深度优先遍历的基本思想：定的图 G=（V,E ），首先将V 中每一个顶点都标记为未被访问，然后，选取一个源点vV 将v 标记为被访问，再递归地用深度优方法，依v 的所有邻接点 w .若w 未曾访问过w 为新的出发点继续深度优遍历，如果从v 出发 所有路的顶点都已被访问过，则结束。A ，B ，C ，F ，E ，G ，D 从顶点A 开始的B F S 遍历，基本思想：定的图G=（V,E ），从图中某未访 问过的顶点vi 出发： 1）访问顶点vi ； 2）访问vi 的所有未被访问的邻接点w1,w2,?wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直 到图中所有访问过的顶点的邻接点都被访问； A ，B ，C ，D ，F ，E ，G 8.4对如图8.36所示的连通图，分别用P rim 和Kruskal 算法构造其最小生成 树。 解：（1）Prime 算法的基本思路、步骤P167 Prim 算法的基本步骤如下：（1）初始化：U={u0}，TREE={}; （2）如果U=V （G ），则输出最小生成树T ，并结束算法； （3）在所有两栖边中找一条权最小的边（u ，v ）（若候选两栖边中的最小边不止 一条，可任选其中的一条），将边（u ，v ）加入到边集TREE 中，并将顶点v 并入 集合U 中。 （4）由于新顶点的加入，U 的状态发生变化，需要对U 与V-U 之间的两栖边进 行调整。 （5）转步骤（2） 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 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．回答以下问题： I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧 关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B） 第7章 《图》习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点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 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i数据结构第7章-答案
经典数据结构面试题(含答案)
《数据结构》习题汇编07 第七章 图 试题
数据结构第五章习题课课案
数据结构作业系统第七章答案
数据结构模拟卷(含答案)经典习题培训讲学
数据结构习题课第8、7、6章(网上的答案有些有问题的)
数据结构课后习题及解析第二章
数据结构模拟卷(含答案)经典习题
经典数据结构上机题_答案解析
数据结构第七章图
数据结构例题解析(1)
数据结构经典题目c语言代码
数据结构第7章 图习题
数据结构第一章课后习题与答案
数据结构经典例题
数据结构第七章图练习及答案
数据结构第7章习题答案
数据结构典型例题
相关主题
文本预览