一、单选题
1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。
A.7
B.8
C.6
D.5
正确答案：A
2、设图G=(V,VR)，其中: V={A,B,C,D,G}，
VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。
A.
B.
C.
D.
正确答案：C
3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。
A.n-1
B.n+2
C.n
D.n+1
正确答案：C
4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。
A.1
B.2
C.3
D.1/2
正确答案：B
5、一个无向连通图的生成树是该连通图的_____。
A.极小连通子图
B.强连通子图
C.连通子图
D.极大连通子图
正确答案：A
6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。
A.n(n+1)/2
B.（n-1）2
C. n2
D. （n+1）2
正确答案：C
7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。
A.O(n2)
B.O(n+e）
C.O(n*e）
正确答案：D
8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。
A.O(n）
B.O(n*e）
C.O(n+e）
D.O(n2)
正确答案：C
9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。
A.G'是G的连通分量
B.G'是G的一个无环子图
C.G'是G的极小连通子图且V=V'
D.G'是G的子图
正确答案：A
10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。
A.7
B.6
C.5
D.8
正确答案：B
11、 n个顶点的有向图为强连通图时，至少含有________。
A.n条弧
B.n(n-1)/2条弧
C.n(n-1)条弧
正确答案：A
12、如果从无向图的一个顶点出发，进行一次深度优先搜索能访问所有顶点，则该无向图是一个________。
A.连通图
B.强连通图
C.完全图
D.DAG图
正确答案：A
13、如图所示的有向图，共有________个强连通分量。
A.2
B.1
C.4
D.3
正确答案：A
14、在下图中，从顶点A出发进行深度优先遍历可得到的序列是_________。
A.ADCBG
B.ABDCG
C.ACDBG
D.ADGBC
正确答案：B
15、对图进行深度优先搜索遍历，需要借助的数据结构为________。
A.队列
B.广义表
C.栈
D.线索二叉树
正确答案：C
16、对图进行广度优先搜索遍历，需要借助的数据结构为________。
A.广义表
B.线索二叉树
C.栈
D.队列
正确答案：D
17、最小生成树是指________。
A.连通网的极小连通子图
B.由连通网得到的边数最少的生成树
C.由连通网得到的顶点数相对较少的生成树
D.连通网的所有生成树中权值之和最小的生成树
正确答案：D
18、在下图中，从顶点A出发进行广度优先遍历可得到的序列是_________。
A.AGBDC
B.ADGBC
C.ADCBG
D.ACDGB
正确答案：C
19、对如图所示的无向连通网，从顶点A出发，使用Prim算法得到的最小生成树是________。
A.
B.
C.
D.
正确答案：D
20、可借助于_________判别有向图中是否存在回路。
A.PRIM算法
B.迪杰斯特拉算法
C.FLOYD算法
D.拓扑排序算法
正确答案：D
21、如图所示的DAG图，其拓扑排序序列为_________。
A.ADBGC
B.ADGBC
C.AGBDC
D.ACDGB
正确答案：A
22、下列关于工程计划的AOE网的叙述中，不正确的是_________。
A.某个关键活动提前完成，可能会提前整个工程的完成时间
B.任何一个关键活动的提前完成，整个工程的完成时间都会提前
C.关键活动不按期完成，会影响整个工程的完成时间
D.所有关键活动都提前完成，会提前整个工程的完成时间
正确答案：B
23、使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。
A.O(n log n)
B. O(n2)
C. O(n3)
D. O(log n2)
正确答案：B
24、使用弗洛伊德算法，求任意2个顶点的最短路径，该算法的时间复杂度为
________。
A.O(n log n)
B.O(n2)
C. O(n3)
D. O(log n2)
正确答案：C
25、某无向图的邻接矩阵如下所示，可以得出，该图共有__________个顶点。
A.9
B.5
C.3
D.4
正确答案：C
二、判断题
1、如果n（n>2）个顶点的有向图有二个强连通分量，则至少有n-1条弧。（√）
2、n个顶点的无向图，至少需要n条边才可能是连通图。（×）
3、连通分量是指无向图的极小连通子图。（×）
4、无向图的邻接矩阵必然是对称矩阵。（√）
5、有n（n>1）个顶点，-2n+2条弧的有向图不一定是强连通图。（×）
6、图的邻接矩阵大小，不但与图的顶点数有关，而且与图的边数也有关。（×）
7、使用有向图的十字链表，能非常方便地计算出任意一个顶点的出度和入度。（√）
8、一个有n个顶点e条边的无向图的邻接表中，有2e个表结点。（√）
9、一个有n个顶点e条边的无向图的邻接多重表中，有2e个表结点。（×）
10、一个有n个顶点e条弧的有向图的逆邻接表中，有2e个表结点。（×）
11、一个有向图的邻接表和逆邻接表中的表结点个数一定相等。（√）
12、有向图有n个顶点e条弧，采用邻接表存储，则计算某顶点度的算法需要访问n+e个单链表的表结点。（×）
13、邻接表的空间复杂度为，与边（或弧）的条数无关。（×）
14、对于一个连通图，通过一次深度优先遍历，能访问到所有顶点。（√）
15、从无向图的任一顶点出发，进行一次广度优先搜素，都能访问到图的所有顶点。（×）
16、对于一个连通图，有唯一的一棵深度优先遍历生成树。（×）
17、当无向连通网中的边较少时，采用prim算法求其最小生成树效率较高。（×）
18、Kruskal算法适合求解边稠密图的最小生成树。（×）
19、某无向连通网只有唯一的一棵最小生成树，则该无向连通网个边上的权值互不相同。（×）
20、可以借助于拓扑排序算法来判断一个有向图是否有回路。（√）
21、在某AOV网中，顶点Vi到顶点Vj有路径，则该AOV网的任何拓扑排序序列中，Vi一定排在Vj的前面。（√）
22、需要借助于深度优先遍历算法来求得AOE网的关键路径。（×）
23、在某AOE网中， ak是从顶点Vi到顶点Vj的活动，则活动ak的最早开始时间等于Vi的最早发生时间。（√）
24、使用迪杰斯特拉算法，能求出有向网中任意2个顶点的最短路径。（√）
25、在求出有向网中任意2个顶点的最短路径时，FLOYED算法的时间效率优于使用迪杰斯特拉算法。（×）
7.1 选择题 1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为() A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n) 【答案】B 2. 设无向图的顶点个数为n,则该图最多有()条边。 A) n-1B)n(n-1)/2C)n(n+1)/2 【答案】B 3. 连通分量指的是() A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 【答案】B 4. n 个结点的完全有向图含有边的数目() A) n*n B) n(n+1) C) n/2 【答案】D 5. 关键路径是() A) AOE网中从源点到汇点的最长路径 B) AOE网中从源点到汇点的最短路径 C) AOV网中从源点到汇点的最长路径D) n2
D) n* (n-1) D) AOV网中从源点到汇点的最短路径 【答案】 A 6．有向图中一个顶点的度是该顶点的() A)入度B)出度C)入度与出度之和D)(入度+出度)12 【答案】C 7．有e 条边的无向图，若用邻接表存储，表中有()边结点。 A) e B) 2eC) e-1D) 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】 A 10．存储无向图的邻接矩阵一定是一个() A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的()倍 A) B) 1C) 2D) 4 答案】B 12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(
数据结构练习题（一） 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( )。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中( )是非线性结构。 A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( )。 A．2k-1 +1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( )。 A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4
9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为 __________个，树的深度为___________，树的度为_________。 4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 5.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 6.AOV网是一种___________________的图。 7.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 9.在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data next 2.
图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4
1、一个无向连通图的生成树是含有该连通图的全部顶点的（）。 A.极大连通子图 B.极大子图 C.极小子图 D.极小连通子图 正确答案：D 2、任何一个非空带权无向连通图（）最小生成树。 A.可能不存在 B.只有一棵 C.一定有多棵 D.有一棵或多棵 正确答案：D 3、用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合 U＝{1，2，3} 已选取的边的集合 TE＝{(1，2)，(2，3)} 要选取下一条权值最小的边，应当从（）组中选取。 A.{(3，4)，(3，5)，(4，5)，(1，4)}
B.{(4，5)，(1，3)，(3，5)} C.{(1，4)，(3，4)，(3，5)，(2，5)} D.{(1，2)，(2，3)，(3，5)} 正确答案：C 解析： C、U={1，2，3}，V-U={4，5，…}，候选边只能是这两个 顶点集之间的边。 4、对某个带权连通图构造最小生成树，以下说法中正确的是（）。Ⅰ.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一 定相同 Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成 树总不相同 A.仅Ⅱ B.仅Ⅱ、Ⅳ C.仅Ⅰ D.仅Ⅰ、Ⅲ 正确答案：C 解析： C、由一个带权连通图构造的最小生成树可能有多棵，但其 代价一定是唯一的；
权值最小的边可能不唯一，这些不唯一的最小权值边不一定都会出现在所有的最小生成树中； 当存在多条权值相同的边时，用普里姆（Prim）算法从不同顶点开始得到的最小生成树不一定相同； 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树不一定总不相同，如图中最小生成树唯一时，无论用哪种算法，得到的最小生成树都是相同的。 5、用Kruskal算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的边集合 TE＝{(1，2)，(2，3)，(3，5)} 要选取下一条权值最小的边，不可能选取的边是（）。 A.(2，4) B.(1，4) C.(3，6) D.(1，3) 正确答案：D 解析： D、选取(1，3)边会构成回路。 6、在用Prim和Kruskal算法构造最小生成树时，前者更适合于（）。 A.有向图
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 数据结构试卷（一）王彬 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（ c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____ ____、________、________和_______。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为_________，树的度为________。 4.后缀算式9 2 3 +- 10 2 / -的值为________。中缀算式（3+4X）-2Y/3对应的后缀算 式为______3 4X* + 2Y* / -_________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有_______个指针域，其中有________个指针域是存放了地址，有______________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有______个和______个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有_____条边，在一个具有n个顶点的有向 完全图中，包含有_____条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为__________________________、______________、_____________________和_____________________。 习题一 1．填空题 （1）数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是_________，R是________。 （2）存储结构可根据数据元素在机器中的位置是否连续分为＿＿＿＿，＿＿＿＿。 （3）算法的基本要求有＿＿＿＿＿，＿＿＿＿＿，＿＿＿＿，＿＿＿＿，＿＿＿＿。 （4）度量算法效率可通过＿＿＿＿＿＿＿，＿＿＿＿＿＿＿两方面进行。 2．简述下列术语： 数据数据元素数据对象数据结构存储结构数据类型。 3. 常用的存储表示方法有哪几种? 4.举例说明一下数据结构和算法的关系。 5.设有数据逻辑结构为B=（K，R），K={k1，k2，……，k9} r={ 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 第7章图 一、单选题 01、在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2 B．1 C．2 D．4 02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A．1/2 B．1 C．2 D．4 03、有8个结点的无向图最多有条边。 A．14 B．28 C．56 D．112 04、有8个结点的无向连通图最少有条边。 A．5 B．6 C．7 D．8 05、有8个结点的有向完全图有条边。 A．14 B．28 C．56 D．112 06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A．O(n) B．O(e) C．O(n+e) D．O(n2) 09、已知图的邻接矩阵，根据算法思想，则从顶点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 2 10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6 C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 6 11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历15、任何一个无向连通图的最小生成树。 A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在 ( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A．n、2e B．n、e C．n、n+e D．2n、2e 17、判断有向图是否存在回路，可以利用算法。 A．关键路径 B．最短路径的Dijkstra C．拓扑排序D．广度优先遍历 18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 19、求最短路径的Dijkstra算法的时间复杂度是___。A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。 A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。 A．第i行非∞的元素之和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 22、一个有n个顶点的无向图最多有条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 A．n B．(n-1)2 C．n-1 D．n2 24、对某个无向图的邻接矩阵来说，。 A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数 25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。 A．abecdf B．acfebd C．aebcfd D．aedfcb 26、已知图的表示如上题，若从顶点a出发按广度搜索法进 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构习题 第七章图 一、选择题 1、一个有n个顶点的无向图最多有（ C ）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有4个顶点的无向完全图有（ A ）条边。 A、6 B、12 C、16 D、20 3、具有6个顶点的无向图至少有（ A ）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 4、设连通图G的顶点数为n，则G的生成树的边数为（ A ）。 A、n-1 B、n C、2n D、2n-1 5、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ D ）和（ B ） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 6、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ B ）和（ D ）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 7、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ C ）和（ B ）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2 8、已知一个图如下，在该图的最小生成树中各边上权值之和为（ C ），在该图的最小生成树中，从v1到v6的路径为（ G ）。 A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 9、正确的AOE网必须是（ C ） A、完全图 B、哈密尔顿图 C、无环图 D、强连通图 10、已知一个图如下，则由该图得到的一种拓扑序列为（ A ）。 A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 11、下面结论中正确的是（ B ） A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 数据结构习题及解答 第1章 概述 【例1-1】分析以下程序段的时间复杂度。 for(i=0;i log) 得：T（n）=O(n2 【例1-4】有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n<=1) return(1);① else return(n*fact(n-1));② } 解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。 由此可得fact（n）的时间复杂度为O(n)。 习题1 一、单项选择题 1.数据结构是指（1. A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（3. D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4. B）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（5. C、），算法分析的两个主要方面是（A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（6. C、），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7. B）。 第七章 图 一、选择题 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 ．n 2 【清华大学 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 ．2n 5．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 ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学1999一、14】 A ．5 B ．6 C ．8 D ．9 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A ．邻接矩阵 B ．逆邻接表 C ．邻接多重表 D ．十字链表 E ．邻接表 【北京工业大学 2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接阵矩???? ? ???? ?=01 0101 010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 一、单选题 1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。 A.1 B.2 C.1/2 D.4 正确答案：B 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A.1/2 B.4 C.2 D.1 正确答案：D 3、具有n个顶点的有向图最多有（）条边。 n(n+1) C.n(n-1) D.n 正确答案：C 4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。 n/2 C.n D.2(n-1) 正确答案：D 5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 A.9 B.7 C.8 D.10 正确答案：A 6、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。 A.有向 B.非连通 C.强连通 D.连通 正确答案：D 7、下面（）算法适合构造一个稠密图G的最小生成树。 A.Kruskal算法 B.Prim算法 C.Floyd算法 D.Dijkstra算法 正确答案：B 8、用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。 A.队列 B.图 C.树 D.栈 正确答案：A 9、用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。 A.队列 B.树 C.图 D.栈 正确答案：D 10、深度优先遍历类似于二叉树的（）。 A.后序遍历 B.中序遍历 C.先序遍历 D.层次遍历 正确答案：C 11、广度优先遍历类似于二叉树的（）。 A.层次遍历 B.先序遍历 C.后序遍历 D.中序遍历 正确答案：A 12、图的BFS生成树的树高比DFS生成树的树高（）。 A.大或相等 B.小或相等 C.相等 D.小 正确答案：B 13、已知图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是（）。 A.0 1 3 4 2 5 6 B.0 2 4 3 1 5 6 C.0 1 3 6 5 4 2 D.0 3 6 1 5 4 2 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（） A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1B）n(n-1)/2C）n(n+1)/2 【答案】B 3．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 【答案】D 5．关键路径是（） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径D）n2 D）n*（n-1） D）AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。A）e B）2eC）e-1D）2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（） A）栈B）队列C）二叉树D）树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树 【答案】A 10．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）B）1C）2D）4 【答案】B 一、单选题 1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。 A.7 B.8 C.6 D.5 正确答案：A 2、设图G=(V,VR)，其中: V={A,B,C,D,G}， VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。 A. B. C. D. 正确答案：C 3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。 A.n-1 B.n+2 C.n D.n+1 正确答案：C 4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。 A.1 B.2 C.3 D.1/2 正确答案：B 5、一个无向连通图的生成树是该连通图的_____。 A.极小连通子图 B.强连通子图 C.连通子图 D.极大连通子图 正确答案：A 6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。 A.n(n+1)/2 B.（n-1）2 C. n2 D. （n+1）2 正确答案：C 7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。 A.O(n2) B.O(n+e） C.O(n*e） 正确答案：D 8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。 A.O(n） B.O(n*e） C.O(n+e） D.O(n2) 正确答案：C 9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。 A.G'是G的连通分量 B.G'是G的一个无环子图 C.G'是G的极小连通子图且V=V' D.G'是G的子图 正确答案：A 10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。 A.7 B.6 C.5 D.8 正确答案：B 11、 n个顶点的有向图为强连通图时，至少含有________。 A.n条弧 B.n(n-1)/2条弧 C.n(n-1)条弧(完整版)数据结构试题及答案
数据结构习题及答案
数据结构_第六章_图_练习题与答案详细解析(精华版)
数据结构习题与答案--图
数据结构习题和答案及解析
数据结构 图 作业及部分答案
数据结构各章习题及答案!
数据结构图练习题(附答案)
数据结构试题及答案(十套)
数据结构：图期末单元测试与答案
数据结构章节练习题 - 答案第7章 图
数据结构(图)习题与答案
相关主题
文本预览