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

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

1、给定下列有向图和初始结点V1，按深度优先遍历的结点序列为（ ）。

A、V1，V3，V4，V5，V2

B、V1，V2，V3，V4，V5

C、V1，V2，V5，V3，V4

D、V1，V2，V4，V5，V3

2、下面哪一方法可以判断出一个有向图是否有环（即回路）（ ）。

A、求节点的度

B、拓扑排序

C、求最短路径

D、求关键路径

3、当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[1..n]中时，数组中第i个结点的左孩子为（ ）。

A、A[2i]（2i=<n）

B、A[2i+1]（2i+1=<n）

C、A[i/2]

D、无法确定

4、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

5、设森林F中有4棵树，其结点个数分别为n1，n2，n3，n4，那么当森林F转换成一棵二叉树后，则根结点的右子树上有（ ）个结点。

A、n1-1

B、n1

C、n1+n2+n3+1

D、n2+n3+n4

1、试题答案：D

试题解析：

图的深度优先遍历的方法为：从图中某顶点v出发，访问顶点v，依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。根据该思想，仅有D符合，故本题选D。

2、试题答案：B

试题解析：

判断有向图是否存在环有两种方法，分别为深度遍历和拓扑排序，若深度遍历中有结点被第二次访问到则证明有环。拓扑排序的思想为每次找入度为0的点，添加到输出队列，然后将与此点相连的结点入度减1，重复上述过程直至删除所有结点。若存在结点无法删除，则证明有环。故本题选B。

3、试题答案：A

试题解析：

当完全二叉树顺序存储在一维结构中时，从上到下从左往右从1开始编号，结点i的左孩子为2*i，右孩子为2*i+1，双亲结点为i/2。若结点从0开始编号，结点R[i]的双亲结点的下标为(i-1)/2；结点R[i]若存在左孩子，其下标为2*i+1；若存在右孩子，其下标为2*i+2。故本题选A。

4、试题答案：A

试题解析：

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1)，因为只需要将新结点插入到p之后，然后更新指针即可。而在给定值为x的结点后插入一个新结点的时间复杂度为O(n)，因为需要先遍历整个链表找到值为x的结点，然后再进行插入操作。故本题选A。

5、试题答案：D

试题解析：

将森林T转换成一棵二叉树，可以将森林中每棵树的根结点作为新二叉树的一个叶子结点，并且将其他树的根结点依次作为前一棵树根结点的右儿子。因此，根结点的右子树上的结点数目就等于除了第一棵树之外的其他树的结点数目之和，即n2+n3+n4。故本题选D。