出自:国家开放大学数据结构复习题

二叉树只能采用二叉链表来存储
具有n个结点的二叉树，采用二叉链表存储，共有n+1个空链域
二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。
已知一棵树的先序序列和后序序列，一定能构造出该树。
二叉树的遍历就是按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。
哈夫曼树只存在着双支结点，不存在单支结点。
哈夫曼树一定是完全二叉树或满二叉树
有一棵树如图所示，回答下面问题：
（1）这棵树的根结点是（ ）；
（2）这棵树的叶子结点是（ ）；
（3）这棵树的度是（ ）；
（4）这棵树的深度是（ ）；
（5）c结点的孩子结点是（ ）；
（6）c结点的父母结点是（ ）。
A. 3 B. 4 C. a D. e、f E. b、e、d、g
由如图所示的二叉树，回答以下问题：（6.4）
（1）其中序遍历序列（ ）；
（2）其前序遍历序列（ ）；
（3）其后序遍历序列（ ）；
A. gdbeihfca B. gbaechif C. abdgcefhi
以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。该树的带权路径长度为（ ）
A. 61 B. 62 C.63 D.65
以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。权重值为4的叶结点的哈夫曼编码为（ ）
A. 000 B. 001 C.010 D.10
在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。
A．1/2
B．1
C．2
D．4
一个具有n个顶点的无向完全图包含（ ）条边。
A．n（n1）
B．n（n1）
C． n（n1）/2
D． n（n1）/2
一个具有n个顶点的有向完全图包含（ ）条边。
A．n（n1）
B．n（n1）
C． n（n1）/2
D． n（n1）/2
对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A．n
B．e
C．2n
D．2e
在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A．入边
B．出边
C．入边和出边
D．不是入边也不是出边
邻接表是图的一种（ ）。
A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，
则该图一定是（ ）。
A.完全图
B．连通图
C．有回路
一棵树
下列有关图遍历的说法不正确的是（ ）。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
无向图的邻接矩阵是一个（ ）。
A．对称矩阵
B．零矩阵
C．上三角矩阵
D．对角矩阵
图的深度优先遍历算法类似于二叉树的（ ）遍历。
A．先序
B．中序
C．后序
D．层次
G是一个非连通无向图，共28条边，则该图至少有（ ）个顶点。
A. 6
B. 7
C. 8
D. 9
在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（ ）。
难度：+
A．k
B．k+1
C．k+2
D．2k
n个顶点的强连通图中至少含有( )。
A．n—l条有向边
B．n条有向边
C．n(n—1)／2条有向边
D．n(n一1)条有向边
14.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
A．abecdf
B．acfebd
C．aedfcb
D．aebcfd
关键路径是事件结点网络中（ ）。
A. 从源点到汇点的最长路径　
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
下面（ ）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历
B. 拓扑排序
C. 求最短路径
D. 求关键路径
采用邻接表存储的图，其深度优先遍历类似于二叉树的（ ）。
A. 中序遍历
B. 先序遍历
C. 后序遍历
D. 按层次遍历
已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。
A. O(n2)
B. O(n*e)
C. O(n+e)
D. O(2n)
已知一个图如下图所示，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
A. acfdeb
B. acfebd
C. acbdef
D. abecdf
在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（ ）。
A. 顶点序列
B. 边序列
C. 权值总和
D. 边的条数
在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A. 入边
B. 出边
C. 入边和出边
D. 不是出边也不是入边
设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1V2,E1E2则称（ ）。
A. G1是G2的子图
B. G2是G1的子图
C. G1是G2的连通分量
D. G2是G1的连通分量
已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ ）。
A. 将邻接矩阵的第i行删除
B. 将邻接矩阵的第i行元素全部置为0
C. 将邻接矩阵的第i列删除
D. 将邻接矩阵的第i列元素全部置为0
图的深度优先搜索序列和广度优先搜索序列不是惟一的。
邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关
AOV网是一个带权的有向图。
从源点到终点的最短路径是唯一的。
图的生成树是惟一的。
有n个结点的无向图中，若边数大于n-1，则该图是连通的。
若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存
AOV网拓扑排序的结果是惟一的。
图的广度优先搜索序列是惟一的。
具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
若连通图上各边权值均不相同，则该图的最小生成树是惟一的
无向图的邻接矩阵一定是对称的。
有向图的邻接矩阵一定是非对称的。
用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。
图的连通分量是无向图的极小连通子图。
首页 <上一页 3 4 5 6 7 下一页> 尾页