数据结构 第七章_智慧树知到答案2021年

第七章 查找：图的邻接表和邻接矩阵存储结构、图的深度和广度优先搜索遍历算法、图的最小生成树算法、有向无环图的基本应用（拓扑排序、关键路径及最短路径问题）。7.1查找表的定义:查找表的定义
7.2静态查找表:顺序查找表、二分查找表、索引顺序表
7.3二叉排序树:二叉排序树
7.4平衡二叉树:平衡二叉树
7.5哈希表:哈希表
7.1图的概述:图的逻辑结构、图的基本概念、图的抽象数据类型描述
7.2图的存储结构:图的类型、图的常见存储结构、邻接矩阵定义、邻接矩阵优缺点、图的邻接矩阵类的描述、图的邻接矩阵类基本操作实现、邻接表定义、邻接表的优缺点、邻接表与邻接矩阵比较、图的邻接表类的描述、图的邻接表类基本操作实现
7.3图的遍历:算法描述、广度优先遍历算法的实现、深度优先遍历算法的实现
7.4最小生成树:最小生成树的基本概念、Kruskal算法的基本思想、Prim算法的基本思想、Prim算法构造最小生成树
7.5最短路径:Dijkstra算法的基本思想、Dijkstra算法构造最短路径、Floyd算法的基本思想、Floyd算法构造最短路径
7.6拓扑排序:拓扑排序的基本概念、拓扑排序的实现
7.7关键路径:关键路径的基本概念、求关键活动的步骤

[单选题]有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率的情况下查找成功所需的平均比较次数为（ ）。选项:[35/12
, 39/12, 37/12, 43/12
]
[单选题]对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个，选项:[1, 4
, 3, 2]
[单选题]顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。选项:[O(n2), O(n1/2), O(1og2n)
, O(n)]
[单选题]设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。选项:[1, 2, 4
, 3]
[单选题]设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。选项:[93, 99
, 97, 91]
[单选题]设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。选项:[7
, 4, 5, 6]
[单选题]二叉排序树中左子树上所有结点的值均（ ）根结点的值。选项:[=, !=
, ＜, ＞]
[单选题]从n个结点的二叉排序树中查找一个元素时，最坏情况下时间复杂度为（ ）。选项:[O(n), O(n2), O(n1/2), O(1og2n)
]
[单选题]在平衡二叉树中，每个结点平衡因子的绝对值必须（ ）。选项:[大于1
, 小于1, 等于0, 小于等于1]
[单选题]深度为4的平衡二叉树中至少有（ ）个结点。选项:[10, 8, 7, 6
]
[单选题]已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应该（ ） 。选项:[将邻接矩阵的第i列删除, 将邻接矩阵的第i列元素全部置为0, 将邻接矩阵的第i行删除　, 将邻接矩阵的第i行元素全部置为0]
[多选题]以下说法正确的是：（　　）。选项:[无向图中的极大连通子图称为连通分量, 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点,  有向图的遍历不可以采用广度优先搜索方法, 图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点]
[判断题]有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。选项:[错, 对]
[单选题]含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。选项:[1, n-1, n/2, n]
[单选题]在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。选项:[s-1, s+1, s, n]
[单选题]对某个无向图的邻接矩阵来说，下列叙述正确的是( )。选项:[ 第i行与第i列上的非零元素的总数等于顶点vi的度数, 矩阵中非全零行的行数等于图中的顶点数, 第i行上的非零元素个数和第i列上的非零元素个数一定相等, 矩阵中的非零元素个数等于图中的边数]
[单选题]设无向图G=（V，E）和G´=（V´，E´），如果G´是G的生成树，则下面说法错误的是（ ）。选项:[G´为G的无环子图, G´为G的子图, G´为G的连通分量, G´为G的极小连通子图，且V=V´]
[多选题]判断一个有向图是否存在回路，可以用（ ）。选项:[深度优先遍历算法, 拓扑排序方法, 广度优先遍历算法, 求最短路径的方法]
[判断题]在AOE网中一定只有一条关键路径。选项:[错, 对]
[判断题]对任意一个图，从某顶点出发进行一次广度优先遍历或深度优先遍历，可访问图的所有顶点。选项:[对, 错]