| 显示国家开放大学系统国家开放大学数据结构复习题所有答案 |
|
在最坏情况下，折半查找与二叉排序树查找性能比较，（ ）
A. 完全相同 B.折半查找性能好
C. 二叉排序树查找性能好 D.不能确定
|
答案是：B
|
|
哈希函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A．最大概率 B．最小概率
C．平均概率 D．同等概率
|
答案是：D
|
|
对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。+++++
A．以顺序存储方式 B．以链接存储方式
C．以索引存储方式 D．以散列存储方式
|
答案是：B
|
|
采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。
A．n B．n/2
C．(n+1)/2 D．(n-1)/2
|
答案是：C
|
|
有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。
A．45,24,53,12,37,96,30 B．37,24,12,30,53,4
|
答案是：B
|
|
顺序查找法与折半查找法对存储结构的要求是（ ）。
A．顺序查找与折半查找均只适用于顺序表
B．顺序查找与折半查找均既适用于顺序表，也适用于链表
C．顺序查找只是适用于顺序表
D．折半查找适用于顺序表
|
答案是：D
|
|
已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（ ）次。
A．3 B．4 C．5 D．6
|
答案是：C
|
|
有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。+++++
A．37/12 B．39/12 C．41/12 D．35/12
|
答案是：A
|
|
对二叉排序树进行（ ）遍历，可以使遍历所得到的序列是有序序列。
A．按层次 B．后序 C．中序 D．前序
|
答案是：C
|
|
在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。
A．3 B．4 C．6 D．8
|
答案是：B
|
|
顺序查找方法适合于存储结构为（ ）的线性表。
A．散列存储 B．索引存储
C．散列存储或索引存储 D．顺序存储或链接存储
|
答案是：D
|
|
对于一个无向图，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
A.0，2，3，4，5，1，6
B.0，2，3，5，1，6，4
C.0，
|
答案是：C. 0，2，3，5，6，1，4
|
|
已知图G的邻接矩阵如下所示：
从顶点1出发的广度优先搜索序列为（ ）。
A.1；2，3， 4；5；6
B.2；1，3，5；4；6
C.3；1，2，4；5；6
D.4；2，3，6；1；5
|
答案是：A. 1；2，3，4；5；6
|
|
采用邻接表存储的图的广度优先遍历算法类似于二叉树的按层次遍历。
|
答案是：对
|
|
一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。
|
答案是：对
|
|
任一个有向图的拓扑序列只有一个。
|
答案是：×
|
|
图G的某一最小生成树的代价一定小于其他生成树的代价。
|
答案是：×
|
|
有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。
|
答案是：对
|
|
一个有向图的邻接表和逆邻接表中的节点个数一定相等
|
答案是：对
|
|
对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
|
答案是：×
|
|
图的强连通分量是无向图的极大连通子图。
|
答案是：×
|
|
图的连通分量是无向图的极小连通子图。
|
答案是：×
|
|
用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。
|
答案是：×
|
|
有向图的邻接矩阵一定是非对称的。
|
答案是：×
|
|
无向图的邻接矩阵一定是对称的。
|
答案是：对
|
|
若连通图上各边权值均不相同，则该图的最小生成树是惟一的
|
答案是：对
|
|
具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
|
答案是：对
|
|
图的广度优先搜索序列是惟一的。
|
答案是：×
|
|
AOV网拓扑排序的结果是惟一的。
|
答案是：×
|
|
若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存
|
答案是：对
|
|
有n个结点的无向图中，若边数大于n-1，则该图是连通的。
|
答案是：×
|
|
对连通图进行深度优先遍历可以访问到该图中的所有顶点。
|
答案是：对
|
|
图的生成树是惟一的。
|
答案是：×
|
|
从源点到终点的最短路径是唯一的。
|
答案是：×
|
|
AOV网是一个带权的有向图。
|
答案是：×
|
|
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关
|
答案是：×
|
|
邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。
|
答案是：×
|
|
图的深度优先搜索序列和广度优先搜索序列不是惟一的。
|
答案是：对
|
|
已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ ）。
A. 将邻接矩阵的第i行删除
B. 将邻接矩阵的第i行元素全部置为0
C. 将邻接矩阵的第i列删除
D. 将邻接矩阵的第
|
答案是：B
|
|
设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1V2,E1E2则称（ ）。
A. G1是G2的子图
B. G2是G1的子图
C. G1是G2的连通分量
D. G2是G1的连通分量
|
答案是：A
|
|
在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A. 入边
B. 出边
C. 入边和出边
D. 不是出边也不是入边
|
答案是：A
|
|
在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（ ）。
A. 顶点序列
B. 边序列
C. 权值总和
D. 边的条数
|
答案是：A
|
|
已知一个图如下图所示，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
A. acfdeb
B. acfebd
C. acbdef
D. abecdf
|
答案是：D
|
|
已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。
A. O(n2)
B. O(n*e)
C. O(n+e)
D. O(2n)
|
答案是：C
|
|
采用邻接表存储的图，其深度优先遍历类似于二叉树的（ ）。
A. 中序遍历
B. 先序遍历
C. 后序遍历
D. 按层次遍历
|
答案是：B
|
|
下面（ ）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历
B. 拓扑排序
C. 求最短路径
D. 求关键路径
|
答案是：B
|
|
关键路径是事件结点网络中（ ）。
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
|
答案是：A
|
|
14.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
A．abecdf
B．acfebd
C．aedfcb
D．aebcfd
|
答案是：C
|
|
n个顶点的强连通图中至少含有( )。
A．n—l条有向边
B．n条有向边
C．n(n—1)／2条有向边
D．n(n一1)条有向边
|
答案是：B
|
|
在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（ ）。
难度：+
A．k
B．k+1
C．k+2
D．2k
|
答案是：B
|
|
G是一个非连通无向图，共28条边，则该图至少有（ ）个顶点。
A. 6
B. 7
C. 8
D. 9
|
答案是：D
|
|
图的深度优先遍历算法类似于二叉树的（ ）遍历。
A．先序
B．中序
C．后序
D．层次
|
答案是：A
|
|
无向图的邻接矩阵是一个（ ）。
A．对称矩阵
B．零矩阵
C．上三角矩阵
D．对角矩阵
|
答案是：A
|
|
下列有关图遍历的说法不正确的是（ ）。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
|
答案是：C
|
|
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，
则该图一定是（ ）。
A.完全图
B．连通图
C．有回路
一棵树
|
答案是：B
|
|
邻接表是图的一种（ ）。
A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构
|
答案是：B
|
|
在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A．入边
B．出边
C．入边和出边
D
|
答案是：B
|
|
对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A．n
B．e
C．2n
D．2e
|
答案是：D
|
|
一个具有n个顶点的有向完全图包含（ ）条边。
A．n（n1）
B．n（n1）
C． n（n1）/2
D． n（n1）/2
|
答案是：A
|
|
一个具有n个顶点的无向完全图包含（ ）条边。
A．n（n1）
B．n（n1）
C． n（n1）/2
D． n（n1）/2
|
答案是：C
|
|
目前为：
2/6
页
首页 上页 下页 尾页
|
