数据结构 图 练习题

图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组成的图进行拓扑排序。

1、3个结点可构成棵不同形态的树。

2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。

3、一个图的_______表示法是唯一的，而______表示法是不唯一的。

4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。

7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

9、n个顶点的连通图的生成树有n-1条边。

10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。

11、3个节点可以构成 5 棵不同形态的二叉树。

12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。

13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。

14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型 B．存储方式 C．结构 D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front= (front+1)%(m-1)C．front=(front-1)%m D．front=(fro nt+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。

第七章图一、选择题1．图中有关路径的定义是（）。

A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。

A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图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,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。

A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。

A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。

3.2数据与结构练习题1.下列不属于简单数据类型的是（）A.浮点型B.整型C.列表D.布尔型2.根据下面数据结构图回答下列问题：（1）上图树结构中的根是。

（2）H，I，J是的子树。

（3）树结构的数据节点之间关系是。

（4）生活中的树结构的例子有。

3.图结构中数据之间的关系是（）A. 一对一B.多对多C. 一对多D. 多对一4.线性结构数据之间的关系是（）A. 一对一B.多对多C. 一对多D. 多对一5.队列属于（）A.线性结构B.树结构C.图结构D.以上均不是6.在线性数据结构中，当前元素的后一位元素被称为（）A. 首元素B.前趋元素C. 尾元素D. 后继元素7.全国航运图属于（）A.线性结构B.树结构C.图结构D.以上均不是8.在python中[]是用来创建（）A.集合B.列表C.元组D.字典9.在python中{}是用来创建（）A.集合B.列表C.元组D.字典10.由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构是（）A．图结构B．选择结构C．线性结构D．树结构11.下列不属于复合数据类型的是（）A.元组B.整型C.列表D.集合参考答案：第1题：C第2题：(1)A (2)D (3)一对多（4）行政区划、书的目录、磁盘文件的存储结构第3题：B第4题：A第5题：A第6题：D第7题：C第8题：B第9题：A第10题：C第11题：B。

图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组成的图进行拓扑排序。

数据结构练习题习题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. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

1、一个无向连通图的生成树是含有该连通图的全部顶点的（）。

A.极大连通子图B.极大子图C.极小子图D.极小连通子图正确答案：D2、任何一个非空带权无向连通图（）最小生成树。

A.可能不存在B.只有一棵C.一定有多棵D.有一棵或多棵正确答案：D3、用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)}要选取下一条权值最小的边，不可能选取的边是（）。

数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.?4.以下数据结构中( )是非线性结构。

A. 队列B. 栈C. 线性表D. 二叉树5.设有一个二维数组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．6966.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据7.二叉树的第k层的结点数最多为( )。

A．2k-1 +1 D. 2k-18.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。

<A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，39.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。

A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

一．选择题1． 一个有n 个顶点的无向图最多有（）条边。

A. nB. n(n-1)C.n(n-1)/2D.2n2． 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。

A .5 B.6 C.7 D.83． 具有n 个顶点且每一对不同的顶点之间都有一条边的图被称为（）A.线性图B.无向完全图C.无向图D.简单图 4． 具有4个顶点的无向完全图有（）条边。

A.6B.12C.16D.205． G 是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A.6B.7C.8D.9 6． 存储稀疏图的数据结构常用的是（）A.链接矩阵B.三元组C.链接表D.十字链表7． 对一个具有n 个顶点的图，采用链接矩阵表示则该矩阵的大小为（）A.nB.(n-1)2C.(n+1)2D.n 28． 设连通图G 的顶点数为n ，则G 的生成树的边数为（）A.n-1B.nC.2nD.2n-19． N 个顶点的无向图的链接表中结点总数最多有（）个。

A.2nB.nC.n/2D.n(n-1) 10． 对于一个具有n 个顶点和e 条边的无向图，若采用链接表表示，则表向量的大小为（），所有顶点链接表的结点总数为（）。

A.nB.n+1C.n-1D.2nE.e/2F.e G .2e H.n+e11．从链接矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101010A 可以看出，该图共有（）个顶点。

如果是有向图，该图共有（）条弧；如果是有向图，则共有（）条边。

A.9B.3C.6D.1E.5F.4 G .2 H.0 12． 在有向图的链接表存储结构中，顶点V 在表结点中出现的次数是（）A.顶点v 的度B.顶点v 的出度C.顶点v 的入度D.依附于顶点v 的边 13． 在用链接表表示图的情况下，建立图的算法的时间复杂度为（）A.O(n+e)B.O(n 2)C.O(n *e)D.O(n 3) 14． 用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（）。