算法与数据结构答案2023秋

第六章测试

1.无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A:a,e,b,c,f,d B:a,c,f,e,b,d C:a,e,d,f,c,b D:a,b,e,c,d,f
答案:C
2.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={,,,,,,,,},G的拓扑序列是（ ）。

A:V1,V3,V2,V6,V4,V5,V7 B:V1,V2,V5,V3,V4,V6,V7 C:V1,V3,V4,V6,V2,V5,V7 D:V1,V3,V4,V5,V2,V6,V7 3.要连通具有n个顶点的有向图，至少需要（ ）条边。
A:n-l B:2n C:n+1 D:n 4.在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）
A:对 B:错 5.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）
A:错 B:对 6.设无向图的顶点个数为n，则该图最多有（ ）条边。
A:n-1 B:n(n-1)/2 C:n(n+1)/2 D:n*n 7.下列哪一种图的邻接矩阵是对称矩阵？（ ）
A:无向图 B:AOV网 C:AOE网 D:有向图 8.下面哪一方法可以判断出一个有向图是否有环（回路）：（ ）。
A:拓扑排序 B:求最短路径 C:求关键路径 D:深度优先遍历 9.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为
A:k2 B:k1 C:k1-k2 D:k1+k2 10.下列说法不正确的是（ ）。
A:图的深度遍历不适用于有向图 B:图的遍历是从给定的源点出发每一个顶点仅被访问一次 C:图的深度遍历是一个递归过程 D:遍历的基本算法有两种：深度遍历和广度遍历 1.如果一个有向图中，任意两个顶点之间都有有向路径相通，那么这个有向图就是强连通的。（ ）
A:对 B:错 2.当图是稠密图时，即边数|E|很接近顶点的平方|V|2。（ ）
A:对 B:错 3.对图的每一个顶点访问一次且只访问一次的过程称为图的遍历。（ ）
A:错 B:对 4.生成树就是将n个顶点连接在一起，且无环的一棵树。（ ）
A:对 B:错 5.将n个顶点连在一起最多需要n-2条边。（ ）
A:错 B:对 6.在拓扑排序过程中，要利用一个辅助的数据结构来进行排序，这个结构是什么（ ）
A:栈 B:树 C:图 D:队列 7.贪婪算法的特点。（ ）
A:在算法的每一步，必须做出若干可能的选择中的一个。 B:这种策略通常是不能保证找到所求解问题的全局最优解。 C:可以得到局部最优解。 D:贪婪策略主张所做的选择在当时是最好的选择。