数据结构第七章测试(长春理工大学精品课)

第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索算法写出从C开始的深度优先搜索序列。

1
2
3
4
5
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J 之间有可能通过道路连接，则Wij表示这条路的长度。

要求每个镇都通公路且所修公路总里程最短，那么应选择哪些线路来修。

(1).画出该图。

(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量
的实际含义。

(3).图示你所定义的数据结构。

(4).标识出你选择的线路。

【解答】 （1）
（2）
#define MAX 6 typedef struct {
char vexs[MAX]; // 顶点信息 int arcs[MAX][MAX]; // 边的信息
int vexnum, arcnum; // 顶点数，边数 } MGraph; （3）略
（4）{(1,3), (3,4), (2,4), (4,5), (5,6)}
3．图G 如下所示。

(1).给出该图的所有强连通分量。

(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。

5
4
6
1
3
2
4
15 10
2
15
20
30
4
10
10
【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4。

数据结构第7章-答案(总12页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

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 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点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 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。

数据结构综合测试（⼀）（长春理⼯⼤学精品课）数据结构测试（长春理⼯⼤学精品课）综合测试⼀⼀、选择1.数据结构中,与所使⽤的计算机⽆关的是数据的（）结构。

查看答案A 顺序B 物理C 逻辑D 物理和存储正确答案为C解释：与计算机⽆关的结构是逻辑结构，是⽤户对数据的组织形式，存储时的物理结构才与计算机有关。

收起2.在长度为n的顺序表中插⼊⼀个元素时,等概率情况下的平均移动元素的次数是（）查看答案A （n-1）/2B n/2C n*(n-1)/2D (n+1)/2正确答案为B解释：在往长度为n的线性表中插⼊元素时，位置可以是1,2,3.......n+1，因此移动元素个数为[n+(n-1)+......+0]/ (n+1)=n/2收起3.对于⼀个头指针为H的带头结点的单链表，判定该表为空表的条件是（）。

查看答案A H==NULLB H!=NULLC H→next ==HD H→next==NULL解释：A答案是不带头结点的单链表H为空的判定条件B答案是不带头结点的单链表H不为空的判定条件C答案是带头结点的循环单链表H为空的判定条件收起4.在⼀个顺序表中，若表的第⼀个元素的存储地址是210，每⼀个元素的长度为3，则第5个元素的存储地址是（）。

查看答案A 219B 222C 225D 228正确答案为B解释：第5个元素之前有4个元素，因此地址为210+（4*3）=222收起5.栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下⾯序列（）是可能的出栈序列。

查看答案A edcbafB bcefadC cbedafD adfebc正确答案为C解释：堆栈的特点是后进先出，⽽且最多⼊栈4个元素收起6.循环队列⽤数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（）。

查看答案A rear-front+1B rear-front-1解释：若rear>=front 则元素个数为rear-front 若rear7.已知⼀棵⼆叉树的有35个叶⼦结点，则该⼆叉树⾄少有（）个结点。

第七章图一、选择题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．n2【清华大学 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．2n5．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．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。

【中山大学1999一、14】A．5 B．6 C．8 D．99．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序 B．拓扑有序 C．无序的【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表【北京工业大学 2001 一、3 (2分)】11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。

第七章一、填空题1、n(n-l)/22、极大连通子图3、深度优先广度优先4、普里姆方法克鲁斯卡尔方法二、选择题1、B 2、C 3、C 4、A 5、B三、应用题1、「0 1 1 L10 0 1.10 0 1.L I I 1 0；四、算法设计题1、#include "stdio.h"include "stdlib.h"typedef struct node 〃邻接表结点结构定义{int adj vex; struct node *next;} Anode;(ypedef struct〃顶点数组元素结点结构定义char vertex;Anode *link;} Vnode;typedef struct{Vnode adjlistflOOl;int vexnuni,arcnuni;} Adjgraph;Adj graph creat(){Anode *p;int i,s,d;Adjgraph ag;printfC请输入顶点和边的数量：，scanf("%d,%d",&ag.vexnum,&ag.arcnum); getcharO;//吸收回车符for(i=0;i<ag.vexnum;i++)〃输入顶点信息{printfC*请输入点的值：，scanf("%c",&ag.adjlist[i]. vertex); getchar();ag.adjlist[i].link=NULL;}for(i=0;i<ag.arcnuni;i++){printfC*请输入边的序号：，scanf("％d,%d”,&s,&d);//前插法p=(Anodc *)malloc(sizcof(Anode)); p->adjvex=d;p->next=ag.adjlist[s].link;ag.adjlist[s].link=p;p=(Anode *)malloc(sizeof(Anode)); p->adjvex=s;p->next=ag.adjlisl[d].link; ag.adjlist[d].link=p;}return ag;}int count(Adjgraph ag){Anode *p;int sum=0,n,i;for(i=0;ivag.vexnum;i++){n=0;p=ag.adjlist[i].link; whilc(p!=NULL) {n++; p=p->next;}if(n= =2)sum++;}return sum;Imain()(Adjgraph ag;int sum;ag=crcat();sum=count(ag);printf("%d",suni);I2、#include "stdio.h"#include "stdlib.h"int visitcd[ 10];typedef struct{char vexsflO];int edges[10][10];int n,e;〃分别代表图的顶点数和边数}MGraph;//结构体类型void CreateMGraph(MGraph *G){int i,j,k;scanf("%d,%d".&G->n,&G->e); 〃输入顶点数和边数getchar();for(i=0;ivG->n;i++)G->vexs[i]=getchar(); // 输入顶点信息for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->cdgesLiJUJ=O; 〃邻接短阵初始化printfC*请输入一对顶点的序号:\n"); for(k=0;kvG->e;k++)scanf(”％d,%d”,&i,&j); 〃输入边的-对顶点序号G->edges[i]Ij]=l；G->edges[j][i]=l;void dfs(MGraph *Gint i)(intj;prinlf(”％c”,G->vexs[i]);visited|i]=l;for(j=0;j<G->n;j++)i f(G->edges[i][j]==l &&visited[j]==O) dfs(Gj)；Ivoid dfstraverse(MGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=O;〃初始化都未曾访问过for(i=0;i<G->n;i++)if(visitedfi]==O)// 未曾访问过dfs(Gi)；}main(){MGraph *G,ag;G=&ag;CreaieMGraph(G);dfstraverse(G);。

数据结构第七章的习题答案数据结构第七章的习题答案数据结构是计算机科学中非常重要的一门学科，它研究如何组织和管理数据以便高效地访问和操作。

第七章是数据结构课程中的一个关键章节，它涵盖了树和二叉树这两个重要的数据结构。

本文将为读者提供第七章习题的详细解答，帮助读者更好地理解和掌握这些概念。

1. 问题：给定一个二叉树，如何判断它是否是二叉搜索树？解答：要判断一个二叉树是否是二叉搜索树，我们可以使用中序遍历的方法。

中序遍历会按照从小到大的顺序访问二叉树中的节点。

所以，如果一个二叉树是二叉搜索树，那么它的中序遍历结果应该是一个有序的序列。

具体实现时，我们可以使用递归或者迭代的方式进行中序遍历，并将遍历的结果保存在一个数组中。

然后，我们检查这个数组是否是有序的即可判断二叉树是否是二叉搜索树。

2. 问题：给定一个二叉树，如何找到它的最大深度？解答：要找到一个二叉树的最大深度，我们可以使用递归的方式。

对于每个节点，它的最大深度等于其左子树和右子树中的最大深度加1。

递归的终止条件是节点为空，此时深度为0。

具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的最大深度。

在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的最大深度，然后取两者中的较大值加1作为当前节点的最大深度。

3. 问题：给定一个二叉树，如何判断它是否是平衡二叉树？解答：要判断一个二叉树是否是平衡二叉树，我们可以使用递归的方式。

对于每个节点，我们分别计算其左子树和右子树的高度差，如果高度差大于1，则该二叉树不是平衡二叉树。

具体实现时，我们可以定义一个递归函数，该函数接收一个节点作为参数，并返回以该节点为根节点的子树的高度。

在递归函数中，我们先判断节点是否为空，如果为空则返回0；否则，我们分别计算左子树和右子树的高度，然后取两者中的较大值加1作为当前节点的高度。

最后，我们判断左子树和右子树的高度差是否大于1，如果大于1，则该二叉树不是平衡二叉树。

1第七章 数据结构作业第七章 图选择题1．设无向图的顶点个数为n ，则该图最多有（，则该图最多有（ ）条边。

）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 22．一个n 个顶点的连通无向图，其边的个数至少为（个顶点的连通无向图，其边的个数至少为（ ）。

）。

A ．n-1B ．nC ．n+1D ．nlogn nlogn；； 3．一个有n 个结点的图，最少有（个结点的图，最少有（ ）个连通分量，最多有（）个连通分量，最多有（ ）个连通分量。

）个连通分量。

A ．0B ．1C ．n-1D ．n4．在一个无向图中，所有顶点的度数之和等于所有边数（．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（等于所有顶点出度之和的（）倍。

A ．1/2 B ．2 C ．1 D ．45．下列哪一种图的邻接矩阵是对称矩阵？（．下列哪一种图的邻接矩阵是对称矩阵？（） A ．有向图．有向图 B B ．无向图．无向图 C C．AOV 网 D ．AOE 网 6．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（的度是（ ）。

A ．å=n i j i A 1],[ B ．[]å=n1j j ,i A C ．å=n i i j A 1],[ D ．å=n i j i A 1],[+ []å=n 1j i ,j A 7．下面哪一方法可以判断出一个有向图是否有环（回路）：A ．深度优先遍历．深度优先遍历 B. B. 拓扑排序拓扑排序 C. C. 求最短路径求最短路径 D. D. 广度优先遍历广度优先遍历8. 在图采用邻接表存储时，求最小生成树的在图采用邻接表存储时，求最小生成树的 Prim Prim 算法的时间复杂度为算法的时间复杂度为算法的时间复杂度为( )( )。

A. O(n) B. O(n+e) C. O(n 2) D. O(n 3)9. 求解最短路径的Floyd 算法的时间复杂度为算法的时间复杂度为( )( )。

数据结构作业系统_第七章答案(总12页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点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 {VertexType 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=[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex;if(k==j)return 1;if(visited[k]!=1)if(DfsReachable(g,k,j))return 1;}}return 0;}③同题要求。

数据结构第七章测验一、单选题 (共100.00分)1. 以下结构不是存储结构的（）A. 邻接表B. 逆邻接表C. 邻接矩阵D. 有向无环图正确答案：D2. 一个有向完全图有10个顶点，它共包含（）A. 45条边B. 100条边C. 45条弧D. 90条弧正确答案：D3. 图遍历的算法有（）A. 中序遍历B. 普里姆C. 佛洛依德D. 广度优先搜索正确答案：D4. 以下算法中，用于求解两点最短路径的算法是（）A. 克鲁斯卡尔B. 迪杰斯特拉C. 普里姆D. 深度优先搜索正确答案：B5. 以下描述错误的是（）A. 第一个顶点和最后一个顶点相同的路径称为回路B. 所有顶点不重复出现的路径称为拓扑路径C. 任意两个顶点都存在路径的无向图称为连通图D. 强连通图只包含一个强连通分量正确答案：B6. 已知某个有向图的邻接矩阵中，第i列包含1的总数为5，第i列对应顶点k，则（）A. 顶点k的度为5B. 顶点k的出度为5C. 顶点k的入度为5D. 不好说正确答案：C7. 已知有向图G=(V,E)，其中V={1,2,3,4,5,6,}，E={<2,1>,<3,2>,<1,3>,<5,3>,<1,5>,<2,4>,<1,6>}，则出度最大的点是（）A. 6B. 4C. 3D. 1正确答案：D8. 已知有向图G=(V,E)，其中V={1,2,3,4,5}，E={<2,1>,<3,2>,<1,3>,<5,3>,<1,5>,<4,3>}，则拓扑序列的起点是（）A. 2B. 4C. 3D. 1正确答案：B9. 已知无向图G=(V,E)，其中V={1,2,3,4,5,6,7,8}， E={(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8)}，从1出发，数字小的顶点优先，则深度优先搜索序列为（）A. 1 2 3 4 5 6 7 8B. 1 2 4 5 8 3 6 7C. 1 2 4 8 5 3 6 7D. 1 2 3 4 5 8 6 7正确答案：C10. 已知有向图G=(V,E)，其中V={a,b,c,d,e}，E={<a, e="">,<b, a="">,<c, b="">,<d, c="">,<e, c="">,<e, d="">}，从a出发，字母小的顶点优先，则广度优先搜索的序列是（）A. a e c d bB. a b d c eC. a d e c bD. a b c d e正确答案：A。

7.6习题一、名词解释（1）主关键字（2）平均查找长度（3）静态查找表（4）动态查找表（5）二叉查找树（6）哈希表二、填空题（1）静态查找表的存储结构主要采用顺序存储结构，如果需要，也可以采用链式存储结构，但当使用二分（折半）查找算法或（斐波那契数列）查找算法来查找时，要求查找表只能是顺序存储结构，并且查找表中的数据序列必须有序。

（2）通过中根序遍历一棵二叉查找树得到的数据序列必然是一个非降序（有序）序列。

（3）各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希查找。

*（4）如果对一个有序查找表SST进行折半查找，在最坏时要比较10次，那么对该查找表进行顺序查找时，在最坏时要比较210 -1 次。

解析：最坏情况要比较10次，说明树的高度是10。

而一棵深度为10的二叉树，最多有210 -1个结点。

*（5）深度为7的平衡二叉树至少有33 个结点。

解析：在节点最少的情况下，左右子树的高度差为1，则总节点数S（n）=S（n-1）+S（n-2）+1。

已知，初始值S(1) = 1，S(2) = 2，可以推出：S(3) = 4S(4) = 7S(5) = 12S(6) = 20S(7) = 33所以，高度为7的平制衡二百叉树最少结点数是33。

假设深度为n的平衡二叉树至少有F(n)个结点，那么F(n)满足F(n)=F(n-1)+F(n-2)+1。

三、简答题（1）请画出长度为8的有序查找表的折半查找判定树。

（2）折半查找的前提：顺序存储、查找表有序。

（3）已知关键字序列为{45，28，67，33，29，50}，二叉排序树初始为空，要求：①画出按正向（从关键字45开始）顺序插入结点建立的二叉排序树。

②画出按反向（从关键字50开始）顺序插入结点建立的二叉排序树。

（4）二叉排序树的平均查找长度：与结点个数和树的形态有关。

（5）设哈希表的地址空间为0~6，哈希函数H(key)=key % 7。

请对关键字序列{32，13，49，18，22，38}按线性探测再散列处理冲突的方法构造哈希表。