帮你掌握数据结构(第七章系列经典试题及答案) - 图文
更新时间:2024-02-27 05:21:01 阅读量: 综合文库 文档下载
- 前端需要掌握数据结构吗推荐度:
- 相关推荐
一、单选题(每题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出发按深度优先遍历的结点序列是
?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??A.0 2 4 3 1 5 6
B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2
建议:0 1 3 4 2 5 6
( 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 3 4 2 5 6 ( B )10. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是
A. 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 (建议:0 1 2 3 4 5 6) ( C )11. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是
A. 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6
1
( D )12. 已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是
A.0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3
( A )13. 已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是
A.0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
( A )14. 深度优先遍历类似于二叉树的
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 ( D )15. 广度优先遍历类似于二叉树的
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 ( A )16. 任何一个无向连通图的最小生成树
A.只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 (注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一)
二、填空题(每空1分,共20分)
1. 图有 邻接矩阵 、 邻接表 等存储结构,遍历图有 深度优先遍历 、 广度优先遍历 等方法。
2. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 出度 。
3. 如果n个顶点的图是一个环,则它有 n 棵生成树。 (以任意一顶点为起点,得到n-1条边)
4. n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为 O(n2) 。
5. n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 O(n+e) 。
6. 设有一稀疏图G,则G采用 邻接表 存储较省空间。
7. 设有一稠密图G,则G采用 邻接矩阵 存储较省空间。
8. 图的逆邻接表存储结构只适用于 有向 图。
9. 已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。
10. 图的深度优先遍历序列 不是 惟一的。
2
11. n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为 O(n2) ;若采用邻接
表存储时,该算法的时间复杂度为 O(n+e) 。
12. n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为 O(n2) ;若采用邻接
表存储,该算法的时间复杂度为 O(n+e) 。
13. 图的BFS生成树的树高比DFS生成树的树高 小或相等 。
14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ;用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。
15. 若要求一个稀疏图G的最小生成树,最好用 克鲁斯卡尔(Kruskal) 算法来求解。
16. 若要求一个稠密图G的最小生成树,最好用 普里姆(Prim) 算法来求解。
17. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。
18. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。
三、简答题(每题6分,共24分)
1. 【严题集7.1①】已知如图所示的有向图,请给出该图的:
(1) 每个顶点的入/出度; 顶点 (2) 邻接矩阵; 入度 (3) 邻接表; 出度 (4) 逆邻接表。
答案:
1 2 3 4 5 6
3
2. 【严题集7.7②】请对下图的无向带权图:
(1) 写出它的邻接矩阵,并按普里姆算法求其最小生成树; (2) 写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。
解:设起点为a。可以直接由原始图画出最小生成树,而且最小生成树只有一种(类)!
邻接矩阵为:
??043??????40559???? ?
最小生成树→ ???3550550?7?6?5?
??9?703?5?4? ? ??????65?30220?? ?6? ????54??60??
PRIM算法(横向变化): V b c d e f g h U V-U Vex a a a a a a a {a} {b,c,d,e,f,g,h} lowcost 4 3 ∞ ∞ ∞ ∞ ∞ Vex a 0 c a a a c {a,c} {b, d,e,f,g,h} lowcost 4 5 ∞ ∞ ∞ 5 Vex 0 0 c b a a c {a,c,b} {d,e,f,g,h} lowcost 5 9 ∞ ∞ 5 Vex 0 0 0 d d d d {a,c,b,d } {e,f,g,h} lowcost 7 6 5 4 Vex 0 0 0 d d d 0 {a,c,b,d ,h {e,f,g } lowcost 7 6 5 } Vex 0 0 0 d g 0 0 {a,c,b,d ,h ,{ f,e } lowcost 7 2 g} Vex 0 0 0 f 0 0 0 {a,c,b,d ,h ,{e } lowcost 3 g, f } Vex 0 0 0 0 0 0 0 {a,c,b,d ,h ,{ } lowcost g, f, e } 邻接表为: a → b 4 → c 3
b → a 4 → c 5 → d 5 → e 9 ^ c → a 3 → b 5 → d 5 → h 5 ^ d → b 5 → c 5 → e 7 → f 6 → g 5 → h 4^ e → b 9 → d 7 → f 3 ^ f → d 6 → e 3 → g 2 ^
4
g h → d 5 → f 2 → h → g 6 6 ^ ^
→ c 5 → d 4 克鲁斯卡尔算法步骤 (按边归并,堆排序): 先罗列:f---2---g a—3--c f—3—e a—4---b d—4—h
(a,b,c) (e,f,g) (d,h) 取b—5—d, g—5--d 就把三个连通分量连接起来了。
3. 【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
4. 【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。
解:最短路径为:(a,c,f,e,d,g,b)
5
四、 【2001年计考研题】给定下列网G: (10分)
(1) 用邻接矩阵表示法画出网G的存储结构图;
(2) 画出该图按Kruskal算法(克鲁斯卡尔算法)来构造的最小生成树。
1 试着找出网G的最小生成树,画出其逻辑结构图; 2 用两种不同的表示法画出网G的存储结构图;
3 用C语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型。 解:1. 最小生成树可直接画出,如右图所示。 2. 可用邻接矩阵和邻接表来描述: ??12??4????12?20?89??????20?15??12?????15???10?? ?48???6?????9??6????????1210?????A B———————C E————F G————D 描述存储结构的数据类型可参见教材或电子教案: 注:用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //假设的最大顶点数(可取为7) Typedef enum {DG, DN, AG,AN } GraphKind; //有向/无向图,有向/无向网Typedef struct ArcCell{ //弧(边)结点的定义 VRType adj; //顶点间关系,无权图取1或0;有权图取权值类型 InfoType *info; //该弧相关信息的指针 }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]; Typedef struct{ //图的定义 VertexType vexs [MAX_VERTEX_NUM ] ; //顶点表,用一维向量即可
邻接表为: a b c d e f g → b 12 → a 12 → b 20 → c 15 → a 4 → b 9 → c 12 → e 4 → c 20 → d 15 → g 10 → b 8 → e 6 → d 10 ^
AdjMatrix arcs; //邻接矩阵 Int Vernum, arcnum; //顶点总数(7),弧(边)总数(9) GraphKind kind; //图的种类标志 }Mgraph; 8 12 6
^ ^
→ e → g ^ ^
→ f → f 9 ^
五、算法设计题(每题10分,共30分)
1. 【严题集7.14③】编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
解:Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {
6
InitALGraph(G); scanf(\
if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\
if(a<0) return ERROR; //边数不能为负 G.arcnum=a;
for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 2. 【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w) ,即删除一条边的操作。(如果要删除所有从第i个顶点出发的边呢? 提示: 将邻接矩阵的第i行全部置0 ) 解://本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 3. 【严题集7.22③】试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。 int visited[MAXSIZE]; //指示顶点是否在当前路径上 7 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。) int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level=1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc,level--) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist_path_DFS 附加题:【严题集7.27④】采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。 (注1:一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注2:此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。) int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 { { if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 8 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 9
正在阅读:
帮你掌握数据结构(第七章系列经典试题及答案) - 图文02-27
学校食堂安全教育培训记录05-23
2017学业水平测试主观题答题模板09-12
杨金才-美国文学的中国视野_英文_05-21
低压电力线载波抄表系统03-13
那件事真让我难以忘怀作文500字06-21
孟良崮一行心得体会03-05
最新-统计工作抽样调查方法工作心得 精品03-13
南山中学高2015级12月模拟考试03-14
- 2009中西部家居博览会总体策划
- 2009 Revit 1级工程师学生用
- 天津地铁建设工程试验检测机构管理办法(TJDT-ZY-AQ-29)
- 新四年级数学暑期班第七次教案
- 机械制造企业隐患排查治理检查表 - 图文
- 2008届全国百套高考数学模拟试题分类汇编-103概率与统计解答题 -
- 职场健身防病试题及答案
- Excel操作技巧大全II - --数据输入和编辑技巧
- 南开大学2018春季《行政管理学》离线作业考核答案
- 2015年医师定考简易程序试卷及答案
- 新《预算法》对行政事业单位预算管理的挑战解读
- 轴的课件
- 电动汽车充电桩设计 毕业论文
- 必修2、选修2-1、1-1期末模拟试题2
- 桌面远程运维管理系统实施-可行性研究报告120306
- 西气东输水土保持工程工作总结 - 图文
- 正宁县基本县情及经济社会发展情况简介
- SATWE参数设置(巨详细)
- 儒家法思想研究综述
- 生活家政服务电子商务平台建设运营整合方案书【审报完稿】
- 数据结构
- 第七章
- 试题
- 掌握
- 答案
- 图文
- 系列
- 经典
- 智力障碍辅导手册
- 金融人力资源调研报告-推荐word版(9页)
- 丹东市旅游发展“十一五”规划
- 电信创业就业部艺术教育成果展新闻稿
- 液化气瓶管理规定
- 《多细胞生物体的结构层次》导学案
- 关于“在课堂中激发高中生政治学习兴趣”的几点思考
- 浅析《重庆晚报》副刊2011改版后的特色
- 小学三年级课外阅读题及答案
- 智能小区安防系统毕业设计 - 图文
- 四川大学网络教育 古代汉语上 第一次网上作业答案
- 《化学原理2》A
- 生产设备智能巡检管理系统 - 图文
- 个人健康管理计划3篇
- 新概念第二册lesson8教案
- 投标工作如何开展 - 图文
- 儿童注意力符号测查 - 图文
- 2015四川大学计算机网络期末复习要点
- 高三政治试题精选2018届高考政治第一轮单元复习检测试题4
- 农产品市场体系