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

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

1、若一个具有n个顶点，k条边的无向图是一个森林（N>K），则该森林中必有（ ）棵树。

A、1

B、k

C、n

D、n-k

2、已知某非空二叉树采用顺序存储结构，树中结点的数据信息按完全二叉树的层次序列依次存放在一个一维数组中，即则该二叉树的后序遍历序列为（ ）。

A、G，D，B，E，F，H，C，A

B、G，B，D，E，H，C，F，A

C、G，D，B，H，E，F，C，A

D、B，G，D，E，H，C，F，A

3、图中有关路径的定义是（ ）。

A、由不同顶点所形成的序列

B、由不同边所形成的序列

C、由顶点和相邻顶点序偶构成的边所形成的序列

D、上述定义都不对

4、若线性表最常用的操作是存取第i个元素及其前驱的值，则采取（ ）存储方式最节省时间。

A、单链表

B、双链表

C、顺序表

D、单向循环链表

5、一个图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先遍历算法。

A、1

B、k-1

C、k

D、k+1

1、试题答案：D

试题解析：

根据树的性质可知，树的顶点数=边数+1。在本题中，假设k条边均在一棵树上，则需要k+1个顶点，剩余顶点每个顶点即为一棵树，因此总的树的个数=n-(k+1)+1=n-k，故本题选D。

2、试题答案：C

试题解析：

按照二叉树的顺序存储结构画出这棵二叉树如下：

得出上述树结构的后序遍历序列为：G、D、B、H、E、F、C、A。故本题选C。

3、试题答案：C

试题解析：

选项A中，仅仅指出路径由不同顶点所构成的序列，但并没有明确说明这些顶点是如何连接起来的；选项B中，仅仅指出路径由不同边所构成的序列，但并没有明确说明这些边是连接哪些顶点的。因此，这两个选项都没有给出完整的路径定义。图论中，路径指的是图中从一个顶点到另一个顶点的一系列边构成的序列。在有向图中，路径由一系列有向边连接的顶点构成；在无向图中，路径由一系列无向边连接的顶点构成。路径的长度是指路径上所有边的权值之和。由于路径是由顶点和相邻顶点的边构成的，因此选项C描述了路径的定义是正确的。故本题选C。

4、试题答案：C

试题解析：

顺序表最适合存取第i个元素及其前驱的值。因为顺序表中的元素在物理上是相邻的，所以访问第i个元素和其前驱的值可以通过简单的指针操作和算术运算来实现。而对于链表来说，要访问第i个元素及其前驱的值需要从链表头开始遍历，时间复杂度较高。双向链表可以存取前驱元素，但也不如顺序表快速。因此，选项C顺序表是最佳选择。故本题选C。

5、试题答案：C

试题解析：

由于一个无向图的每个连通分量都可以看作一个独立的图，因此要遍历整个图，就需要遍历每个连通分量。而深度优先遍历算法正好可以遍历一个连通分量。因此，对于包含k个连通分量的图，就需要调用k次深度优先遍历算法才能访问所有结点。故本题选C。