考研数据结构A在线题库每日一练（七十一）

本文提供考研数据结构A在线题库每日一练，以下为具体内容

1、线性表采用链表存储时地址（ ）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续不连续都可以

2、具有n个结点的满二叉树，其叶子结点有（ ）个。

A、n/2

B、(n-1)/2

C、(n+1)/2

D、n/2-1

3、n个顶点的强连通图至少有（ ）条边。

A、n

B、n+1

C、n-1

D、n(n-1)

4、在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是（ ）。

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法

5、一个具有n个顶点的无向图最多有（ ）边。

A、n(n-1)

B、n

C、n(n-1)/2

D、2n

1、试题答案：D

试题解析：

线性表的链式存储结构其地址可以连续可以不连续，而线性表的顺序存储结构其地址必须是连续的，故本题选D。

2、试题答案：C

试题解析：

对任何一棵二叉树，若终端结点为n₀，度为2的结点为n₂，则n₀=n₂+1。满二叉树仅含有叶子结点和度为2的结点，因此n=n₀+n₂=2*n₀-1，解得n₀=(n+1)/2，故本题选C。

3、试题答案：C

试题解析：

一个强连通图表示其中任意两个顶点都有至少一条有向路径相互连通。当一个有向图中存在一个简单环，并且它包含了图中的所有结点，那么这个图就是一个强连通图，并且只有n条边。故本题选C。

4、试题答案：B

试题解析：

Dijkstra算法是一种贪心算法，用于解决带有非负权边的有向图或无向图的单源最短路径问题，它以始点为中心向外层层扩展，直到扩展到终点为止。因为该算法是基于边的权值为非负数的前提条件设计的，如果有负权边，会导致该算法失效。而Kruskal算法和Prim算法则是用于求解带权图的最小生成树问题的算法，与Dijkstra算法求解最短路径问题的目标不同。Floyd算法是用于求解带权图的多源最短路径问题的算法，虽然可以处理带有负权边的情况，但是要求不存在负权回路。故本题选B。

5、试题答案：C

试题解析：

无向图中每个顶点最多与n-1个顶点相连，而对于n个顶点，总共可以有n(n-1)条边，但每条边会被计算两次，因此最终结果为n(n-1)/2。故本题选C。