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

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

1、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数等于（ ）。

A、顶点v的度

B、顶点v的出度

C、顶点v的入度

D、依附于顶点v的边数

2、二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为（ ）。

A、429

B、432

C、435

D、438

3、不带头结点的单链表head为空的判定条件是（ ）。

A、

B、

C、

D、

4、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、后序遍历

C、中序遍历

D、先序遍历

5、在线性表中最常用的操作是存取第i个元素及其前驱的值，采用（ ）存储方式最省时间？

A、顺序表

B、带头结点的单向链表

C、带头指针的双向循环链表

D、带头指针的单向循环链表

1、试题答案：C

试题解析：

邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧），因此顶点v在表结点中出现次数=指向v的边数=顶点v的入度，故本题选C。

2、试题答案：A

试题解析：

add(A[9][7])=add(A[0][0])+(7*12+9)*3=150+429，故本题选A。

3、试题答案：A

试题解析：

不带头结点的单链表head为空，表示该链表中没有任何节点，即链表为空。因此，判定该链表是否为空需要判断链表的头指针head是否为NULL。故本题选A。

4、试题答案：D

试题解析：

深度优先遍历算法是图的遍历方式之一，其遍历过程类似于二叉树的先序遍历。在深度优先遍历中，我们从某个顶点开始遍历，依次访问该顶点的所有邻接顶点，然后依次对每个邻接顶点进行递归遍历，直到所有能到达的顶点都被访问到。这个过程就类似于二叉树的先序遍历，先访问根节点，再递归遍历左子树和右子树。故本题选D。

5、试题答案：A

试题解析：

在顺序表中，可以通过下标直接定位到第i个元素及其前驱，时间复杂度为O(1)。而在链式存储结构中，需要遍历链表找到第i个元素及其前驱，时间复杂度为O(n)。因此，顺序表存储方式最省时间。故本题选A。