张铭数据结构与算法课后答案

张铭数据结构与算法课后答案

【篇一：第7章图 数据结构 张铭 复习题】

题

（ c ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。 a．1/2b. 1 c. 2 d. 4 （ b ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 a．1/2b. 1 c. 2 d. 4 （ b ）3. 有8个结点的无向图最多有条边。

a．14b. 28 c. 56 d. 112 （ c ）4. 有8个结点的无向连通图最少有条边。

a．5b. 6 c. 7 d. 8 （ c ）5. 有8个结点的有向完全图有条边。 a．14b. 28 c. 56 d. 112 （ b ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

a．栈b. 队列c. 树 d. 图 （ a ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 a．栈b. 队列c. 树 d. 图 （

）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 1 3 4 2 5 6 d. 0 3 6 1 5 4 2

（ 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 5d. 0 1 2 3 4 5 6 （ 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 1b. 0 1 2 3 c. 0 1 3 2d. 0 3 1 2 （ a ）14. 深度优先遍历类似于二叉树的

a．先序遍历b. 中序遍历 c. 后序遍历 d. 层次遍历 （ d ）15. 广度优先遍历类似于二叉树的

a．先序遍历b. 中序遍历 c. 后序遍历 d. 层次遍历 （ b ）16. 任何一个无向连通图的最小生成树

a．只有一棵 b. 一棵或多棵 c. 一定有多棵 d. 可能不存在 二、填空题（每空1分，共20分）

1. 图有、等存储结构，遍历图有等方法。 2. 有向图g用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的

3. 如果n个顶点的图是一个环，则它有 （以任意一顶点为起点，得到n-1条边） 4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为2 5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 6. 设有一稀疏图g，则g采用存储较省空间。 7. 设有一稠密图g，则g采用存储较省空间。 8. 图的逆邻接表存储结构只适用于图。

9. 已知一个图的邻接矩阵表示，删除所有从第i 10. 图的深度优先遍历序列 不是 惟一的。

11. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为2；若采用邻接

表存储时，该算法的时间复杂度为 o(n+e) 。

12. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为2若采用邻接

表存储，该算法的时间复杂度为o(n+e) 。 13. 图的bfs生成树的树高比dfs

14. 用普里姆(prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为2斯卡尔(kruskal)算法的时间复杂度是o(elog

15. 若要求一个稀疏图g的最小生成树，最好用 克鲁斯卡尔 16. 若要求一个稠密图g的最小生成树，最好用

17. 用dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度径的。

18. 拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。 三、简答题

1. 【严题集7.1①】已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。 答案：

2. 【严题集7.7②】请对下图的无向带权图：

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）! 邻接矩阵为：

??043??????40559????? ???3550550?7?6?5?

??9?703?5?4? ? ??????65?30220?? ?6? ????54??60?? → →

→ → → → → → → → → → → → → → → ^→ → → ^ → → →

→ ^ ^

→ → 先罗列：f---2---g

a—3--cf—3—ea—4---bd—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）

【篇二：第3章栈和队列 数据结构 张铭复习题】

一、填空题（每空1分，共15分）

1. 向量、栈和队列都是栈顶插入和删除元素；对于队列只能在队尾 插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为 栈底 。 3.

4. 在一个循环队列中，队首指针指向队首元素的位置。 5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 向栈中压入元素的操作是先 ，后 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后。 8. 带表头结点的空循环双向链表的长度等于。 解： head

二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

错，不一定吧？调用子程序或函数常用，cpu中也用队列。

（ √）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ √）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 错，有可能。

三、单项选择题（每小题1分，共20分） （b）1.栈中元素的进出原则是

Ａ．先进先出 Ｂ．后进先出Ｃ．栈空则进 Ｄ．栈满则出

（c）2.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为 Ａ．i Ｂ．n=iＣ．n-i+1 Ｄ．不确定

解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。 （若不要求顺序出栈，则输出序列不确定）

（b）3.判定一个栈st（最多元素为m0）为空的条件是