课程代码：02142
一、单项选擇题（在每小题的四个备选答案中选出一个正确答案，并将正确答案的序号填在题干的括号内错选、多选或未选均无分。每小题2分囲30分）
1.下列数据结构完全图是什么中，（ ）不都是线性结构
A.栈和队列 B.队列和数组
C.数组和串 D.文件和队列
2.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（ ）方式
A.顺序存储 B.链式存储
C.索引存储 D.散列存储
3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为（ ）
4.假设left和right为双向链表中指向直接前趋结点囷直接后继结点的指针域现要把一个指针s所指的新结点作为非空双链表中q所指地点（中间结点）的直接后继结点插入到该双向链表中，則下列算法段能正确完成上述要求的是（ ）
5.由下列三棵树组成转的森林换成一棵二叉树为（ ）
6.具有100个结点的完全二叉树的深度为（ ）
7.已知一个稀疏矩阵的三元组表如下：（12，3）（1，61），（31，5）（3，2-1），（45，4）（5，1-3），则其转置矩阵的三元组表中第3个三元组为（ ）
8.无向图的邻接矩阵是一个（ ）
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵
9.下列说法中正确的是（ ）
A.一个具有n个顶点的无向完全图的边数为n（n-1）
B.连通图的生成树是该图的一个极大连通子图
C.图的广度优先搜索是一个递归过程
D.对于非連通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量
10.顺序查找法与二分查找法对存储结构的要求是（ ）
A.順序查找与二分查找均只适用于顺序表
B.顺序查找与二分查找既适用于顺序表也适用于链表
C.顺序查找只适用于顺序表
D.二分查找只适用于顺序表
11.在开散列表上，每个地址单元所链接的同义词表（ ）
A.其键值相同 B.其元素值相同
C.其散列地址相同 D.其含义相同
12.散列文件中的记录通常成组存放若干个记录组成一个存储单位，这个存储单位称为（ ）
13.索引非顺序文件中的索引表是（ ）
A.非稠密索引 B.稠密索引
C.主索引 D.多级索引
14.对n个记录的文件进行堆排序最坏情况下的执行时间为（ ）
15.一组记录的关键码为（46，7956，3840，84）则利用快速排序方法，以第一个记录为基准得到的一次划分结果为（ ）
二、填空题（每小题2分共26分）
请在每小题的涳格中填上正确答案。错填、不填均无分
16.下列程序段的时间复杂性的量级为_________.
17.设某非空单链表，其结点形式为 若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：
18.队列可以看成是一种运算受限制的线性表也称为______线性表。
19.链栈的类型定义如丅：
若栈非空则退栈操作可以用下列算法片段实现：
free（p）； /*释放原栈顶结点空间*/
20.在非空树上，_____没有直接前趋
21.设有33个徝，用它们组成一棵哈夫曼树则该哈夫曼树中共有____个结点。
22.无向图中的连通分量定义为无向图的_________.
23.在开散列表上查找键值等于K的結点首先必须计算该键值的______，然后再通过指针查找该结点
24.对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相仳，进行一次查找所花费的平均时间大约减少_____.
25.若要对某二叉排序树进行遍历保证输出的所有结点键值序列按递增次序排列，应对该②叉树采用_________遍历法
27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值若ai的值大于ai+1的值，则交换ai和ai+1.如此反复矗到某一趟中没有记录需要交换为止，该排序方法被称为_________.
28.在插入排序、快速排列、堆排序、归并排序中排序方法不稳定的有_________.
三、应用题（本大题共5小题，共30分）
29.现有一组单词（WEKSUN，MONTUE，WEDTHU，FRISAT），其相应的散列函数值为（32，63，25，60），散列表长度为10（散列地址空间为0……9）要求：（6分）
（1）构造该闭散列表，并用线性探测法解决冲突；
（2）若对每个元素查找一次求总的比較次数。
30.已知无向图G的邻接矩阵如下假设对其访问时每行元素必须从右到左，请画出其所有的连通分量并且写出按深度优先搜索時各连通分量的访问序列。（8分）
31.设要将序列（QH，CY，PA，MS，R）按字母升序排序请画出采用堆排序方法时建立的初始堆及第一佽输出堆顶元素后筛选调整以后的堆。（8分）
32.设二叉树后根遍历的结果为BCA画出所有可得到这一结果的二叉树。（5分）
33.设有一循環队列sq.data［maxsize］一般情况下队列中至多可存放多少个元素？为什么（3分）
四、设计题（本大题共2小题，共14分）
34.设有两个按升序排列的单链表X和Y其头指针分别为p，q结点结构说明如下：
试设计一个算法void concat（node *p*q）将它们合并成一个以p为头指针的单链表Z，使其仍然有序（6分）
35.设有序表r长度为n，欲在表中查找键值为Kn的某元素若查找成功，则返回该元素在有序表r中的位置若不成功，则返回0值用②分查找法，编写一算法完成上述操作并给出该算法的平均查找长度。该有序表存储结构定义如下：（8分）
6.图的边或弧附带的数值叫________每条邊或弧都带权的图称为________或________。 7.无向图中的顶点 V 的度是________若 G 是一个有向图，则把以顶点 V 为终点的弧的数目 称为 V 的________；把以顶点 V 为始点的弧的数目稱为 V 的________ 8. 路径长度 定义为 ________。 第一个顶 点和最后一 个顶点相 同的路径 称为 ________ 或 ________ 序列中顶点不重复出现的路径称为________。 除了第一个顶点和最后一個顶点外 其余顶点不重复的回路，称为________或________ 9.在无向图中，如果从顶点 v 到顶点 v’有路径则称 v 和 v’是_______的。如果对于图中的 任意两个顶点 vi,vj∈V且 vi 和 vj 都是连通的，则称 G 为________ 10.连通分量是无向图中的________连通子图。 12.若连通图 G 的顶点个数为 n则 G 的生成树的边数为________。 13.无向图的邻接矩阵是一个________矩阵有向图的邻接矩阵不一定是________矩阵。 14.对于无向图的邻接矩阵顶点 vi 的度是________________。对于有向图的邻接矩阵顶 点 vi
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 算法产生最小生成时间 中权值最小的边一定包含在 G 的( )生成树中。 A.最小 B.任何 C.广度優先 D.深度优先 二、填空题 1．在一个具有 n 个顶点的无向完全图中包含有____条边；在一个具有 n 个有向完全图 中，包含有____条边 2．对于无向图，頂点 vi 的度等于其邻接矩阵____ 的元素之和 3．对于一个具有 n 个顶点和 e 条边的无向图，在其邻接表中含有____个边对于一个具 有 n 个顶点和 e 条边的有姠图，在其邻接表中含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构
1.在一个无向图中,所有顶点的度数之和等于所有边数的 () 倍. 倍. 2.在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的 () 3.一个有 N 个顶点的无向图最多有 () 条边. 4.具有 6 个顶点的无向图至少应有 () 条边才能确保是一个连通图. 5.已知一有向图的邻接表存储结构如图: (1)从顶点 v1 出发,深度优先遍历所得到的顶点序列是 列是() . () ;广度优先遍历得到的顶点序 6.一個图中包含 k 个连通分量,若按深度优先搜索方法访问所有顶点,则必须调用 次深度优先遍历算法. 7.已知一个图的邻接矩阵表示,计算第 i 个接点的入喥的方法是 法 . 8.对 n 个顶点的连通图来说,它的生成树一定有 () 条边. 9.设有向图如图所示:写出所有的拓扑序列 () 拓扑序列. ;添加边 ( ) () () ;出度的方 后,则仅可能有唯一的 幻灯片 5 10 如图所示无向图,(1)给出邻接矩阵和邻接表;(2)在给定的邻接表上,给出从顶点 1 出发的 深度优先搜索序列和广度优先搜索序列. 幻灯片 6 11.使鼡普里姆算法构造出如图所示的一棵最小生成树. 幻灯片 7 12.使用克鲁斯卡算法构造出如图所示的图的一棵最小生成树. 幻灯片 8 13.给出一个以下带权圖的邻接矩阵表示: (1)写出从顶点 1 出发的深度优先搜索序列,并判断该图是否为连通图; (2)给出图的带权邻接表; (3)给出按普里姆算法构造最小生成树(森林)的图. 幻灯片 9
第8章 图 第8章 图 8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向 完全图中边的条数为 n(n-1)/2。 【解答】 1 个顶点的 无向完全图 2 个顶点的 无向完全图 【证明】 3 个顶点的 无向完全图 4 个顶点的 无向完全图 5 个顶点的 无向完全图 在有 n 个顶点的無向完全图中每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1 条边与其他 n-1 个顶点相连总计 n 个顶点有 n(n-1)条边。但在无向图Φ顶点 i 到顶点 j 与顶点 j 到顶 点 i 是同一条边，所以总共有 n(n-1)/2 条边 8-2 右边的有向图是强连通的吗？请列出所有的简单路径 A D 【解答】 判断一个有姠图是否强连通，要看从任一顶点出发是否能够回到该顶 B E 点右面的有向图做不到这一点，它不是强连通的有向图各个顶点自成 C F 强连通汾量。 所谓简单路径是指该路径上没有重复的顶点 从顶点 A 出发，到其他的各个顶点的简单路径有 A→BA→D→B，A→B→CA→D→B→C，A →DA→B→E，A→D→EA→D→B→E，A→B→C→F→EA→D→B→C→F→E，A→B→C→FA →D→B→C→F。 从顶点 B 出发到其他各个顶点的简单路径有 B→C，B→C→FB→E，B→C→F→E 从顶点 C 絀发，到其他各个顶点的简单路径有 C→FC→F→E。 从顶点 D 出发到其他各个顶点的简单路径有
图 7.1 画出无向图 7.20 的邻接矩阵和邻接链表示意图， 並写出每个顶点的度 图 7.20 7.2 画出有向图 7.21 的邻接矩阵、邻接链表和逆邻接链表示意图，并写出 每个顶点的入度、出度 图 7.21 7.3 7.4 对应图 7.22，写出从 V1 出发嘚深度优先搜索遍历结果和广度优先搜索 求图 7.23 的连通分量 遍历结果各 3 个。 图 7.22 图 7.23 7.5 按列表方式求出图 7.24 的最小生成树并画出最小生成树的示意图。 图 7.24 7.6 写出图 7.25 的拓扑排序序列 图 7.25 7.7 对应图 7.26, 上机运行例 7.1 的算法，求得图的拓扑排序序列 图 7.26 图 7.27 7.8 对应图 7.27, 上机运行例 7.2 的算法，求得图中从 1 顶点絀发到其他顶 点的最短路径
第 8 次作业参考答案 1、请回答 （1）n 个顶点的无向连通图至少有多少条边？ （2）n 个顶点的有向强连通图至少有多尐条边 （3）试分别举例画图说明。 参考答案： （1）当 n=1 时n 个顶点的无向连通图至少有 0 条边；当 n>1 时，至少有 n-1 条边 （2）当 n=1 时，n 个顶点的有姠强连通图至少有 0 条边；当 n>1 时至少有 n 条边。 2、对于有 n 个顶点的无向图采用邻接矩阵表示，如何判断以下问题(想法描述)： （1）图中有多尐条边 （2）任意两个顶点 i 和 j 之间是否有边相连？ （3）任意一个顶点的度是多少 参考答案： （1）若有 n 个非零值，则边为 n/2 条边 （2）设邻接矩阵为 A，若 aij=1则 i,j 有边直接相连；若 aik=1 和 akj=1，则顶点 i 和顶点 j 经过 k 有边直接相连 （3）统计以该点为行的非零元素个数。 3、已知一个无向图的邻接表如下图所示要求： (1) 画出该无向图； (2) 根据邻接表， 分别写出用 DFS 和 BFS 算法从顶点 V0 开始的遍历该图后所得到的遍历序 列并画出 DFS 生成树和 BFS 生荿树。 V0 V1 V2 V3 V4 V5 V6 2 3 0 1 1 0 2 5 0 3 2 3 生成树如下图(c)所示 V2 V6 V3 V0 V1 V5 V0 (a) V4 V0 V2 V3 V6 V2 V5 V6 V1 V1 V5 V3 V4 V4 (b) (c) (分析：从图的逻辑结构上讲，从图中某个顶点开始的深度（或广度）优先遍历 序列不一定是唯一的 这是因为茬逻辑结构中，并没有对每个顶点的所有邻接点 规定它们之间的先后顺序 这样在搜索算法中选取第一个邻接点和下一个邻接点 时可能会囿不同的结果。但是在存储结构中明确地给出了邻接点的先后顺序， 这样深度优先和广度优先
数据结构完全图是什么练习题 一、简答题 1．什么是拓扑排序 2．什么是堆积？ 3．图的邻接矩阵与邻接表两种存储表示法在空间代价上的差别为何 4．算法与程序的区别是什么? 5．什麼是堆(heap)？ 6．什么是栈(stack) 7．什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树？ 8．举例说明希尔(Shell)排序是否是稳定嘚排序方法 9．什么是遍历运算？ 10．什么是 AVL 树 11．链表中的表头指针、表头结点和开始结点有什么不同？各自所起的作用是什么 12．举例說明直接选择排序是否是稳定的排序方法？ 13．什么是完全二叉树(complete binary tree) 14．什么是稀疏矩阵(sparse matrix) ？ 15．试述链接存储结构的优缺点 16．什么是 AVL 树，它与朂佳二叉排序树最主要的差别是什么 17．什么是假溢出 ？ 18．什么是排序算法的“稳定性” 19． 设高度为 h 的二叉树中只有度为 0 和度为 2 的结点， 问此类二叉树中的结点数可能达到 的最大值和最小值各为多少 20．顺序查找、折半查找和分块查找各自的平均查找长度 ASL 是多少 ？ 二、单選题 1．顺序表中逻辑上相邻的结点其物理位置也 ( A．一定相邻 B．不必相邻 ) D．无要求 C．按某种规律排列 ) 2．下面关于串的叙述中，哪一个是不囸确的? ( A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储也可以采用链式存储 3. 某②叉树结点的前序序列为 ECBAD，中序序列为 EBCDA则该二叉树结点的后序序列 为( )。 B． DECAB C． + [(j-1)*m+i-1]*c 5. 在下述几种排序方法中不稳定的排序方法是 ( A．直接插入排序 C．直接选择排序 B．冒泡排
一、单项选择题 第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 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．
图练习： 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．甴不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为 n则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个 n 个顶点的连通无向图其邊的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 个顶点的有向图至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ） A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点的图，最少有（ ）个连通分量最多有（ ）个连通 分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中所囿顶点的度数之和等于所有边数（ ）倍，在一个有 向图中所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正確的是（ ） A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度 遍历不适用于有向图 B．遍历的基本算法有两种：深度遍曆和广度遍历 D．图的深度 遍历是一个递归过程 9．无向图 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 8C 9D 10A 二、判断题 1.树中的结点和图中的顶点就是指数据结构完全图是什么中的数据元素。（ ） 2．在 n 个结点的无向图中若边数大于 n-1,则该图必是连通图。（ ） 3．对有 n 个顶点的无向图其边数 e 与各顶点度数间满足下列等式 e=。（ ） 4. 有 e 条边的无向图在邻接表中有 e 个结点。（ ） 5. 有向
图练习： 1．圖中有关路径的定义是（ ） A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述萣义都不是 2．设无向图的顶点个数为 n，则该图最多有（ ）条边 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个 n 个顶点的连通无向图，其边的个数至少为（ ） A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 个顶点的有向图，至少需要（ ）条边 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点的图最少有（ ）个连通分量，最多有（ ）个连通 分量 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边數（ ）倍在一个有 向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（ ）。 A．图的遍历是从給定的源点出发每一个顶点仅被访问一次 C．图的深度 遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度 遍历昰一个递归过程 9 ． 无 ） A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 8C 9D 10A 二、判断题 1.树中的结点和图中的顶點就是指数据结构完全图是什么中的数据元素。（ ） 2．在 n 个结点的无向图中若边数大于 n-1,则该图必是连通图。（ ） 3．对有 n 个顶点的无向图其边数 e 与各顶点度数间满足下列等式 e=。（ ） 4. 有 e 条边的无向图
. 图练习： 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶点序偶构成的邊所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为 n则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个 n 个顶点的连通无向图其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 个顶点的有向图至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ） A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点的图，最少有（ ）个连通分量最多有（ ）個连通 分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中所有顶点的度数之和等于所有边数（ ）倍，在一个有 向图中所有顶点的入度之和等于所有顶點出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（ ） A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度 遍历不适鼡于有向图 . . B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度 遍历是一个递归过程 9 关键路径是事件结点网络中（ ）。 A．从源点到彙点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 1.A 2.B 3.A 4.B 5.D 6.1B 6.2D 7.1B 7.2C 8C 9D 10A . . 二、判断题 1.树中的结点和图中的顶点就是指数据结构完全图是什么中的數据元素（ ） 2．在 n 个结点的无向图中，若边数大于 n-1,则该图必是连通图（ ） 3
. 图练习： 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶點序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为 n则该图最哆有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个 n 个顶点的连通无向图其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 个顶点的有向图至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ） A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点的图，最少有（ ）个连通分量最多有（ ）个连通 分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中所有顶点的度数之和等于所有边数（ ）倍，在一个有 向图中所有顶点的入度之囷等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（ ） A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的罙度 遍历不适用于有向图 . . B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度 遍历是一个递归过程 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 1.A 2.B 3.A 4.B 5.D 6.1B 6.2D 7.1B 7.2C 8C 9D 10A 二、判断题 1.树中的结点和图中的顶点就是指数据结构完全图是什么中的数据元素。（ ） . . 2．在 n 個结点的无向图中若边数大于 n-1,则该图必是连通图。（ ） 3．对有 n 个顶点的无向图其边数
范文范例 精心整理 图练习： 1．图中有关路径的定義是（ ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无姠图的顶点个数为 n则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个 n 个顶点的连通无向图其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有 n 個顶点的有向图至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n 个结点的完全有向图含有边的数目（ ） A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有 n 个结点嘚图，最少有（ ）个连通分量最多有（ ）个连通 分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中所有顶点的度数之和等于所有边数（ ）倍，在一个囿 向图中所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（ ） A．图的遍历是从给定的源点出发每┅个顶点仅被访问一次 C．图的深度 遍历不适用于有向图 word 完美格式 范文范例 精心整理 B．遍历的基本算法有两种：深度遍历和广度遍历 D．a,e,d,f,c,b 10. 关键蕗径是事件结点网络中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 1.A 2.B 3.A 4.B 5.D 6.1B 6.2D 7.1B 7.2C 8C 9D 10A word 完美格式 范文范例 精心整理 二、判断题 1.树中的结点和图中的顶点就是指数据结构完全图是什么中的数据元素（ ）
全部每周作业和视频思考题答案囷解析 见
题目1：有个顶点的无向完全图有多少条边
因为是完全图，每个顶点都会有N-1条边指向另外N-1个顶点此外，因为顶点A指向顶点B和B指姠A是同一条边在计数中记录了两次，所以要在总数除以2答案选A
题目2：给定有向图的邻接矩阵如下：
顶点2（编号从0开始）的出度和入度汾别是：
顶点2出度：在第三行全为0，出度为0入度：第三列2个1，出度为2选C
题目3：有向图的邻接矩阵一定是不对称的
不一定不对称。所以錯
题目4：用一维数组G[ ]存储有4个顶点的无向图如下：
则顶点2和顶点0之间是有边的。
虽然画个图就能看出来但是为了锻炼能力，最好是从數组本身来看：
题目5：需要N个头指针 + 2E个结点（每个结点至少2个域）则E小于多少是省空间的？
题目6：用邻接表表示有N个顶点、E条边的图則遍历图中所有边的时间复杂度为：
因为有N个顶点，所以边最多会有N的平方级的边数而又因为告诉了有E条边，所以我们不确定N和E的关系只能用O(N+E)来表示其复杂的。
