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

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

1、图1是一个有向无环图，其拓扑排序结果为（ ）。

A、v0、v1、v2、v4、v5、v3、v6

B、v1、v0、v3、v4、v5、v2、v6

C、v1、v0、v3、v4、v5、v6、v2

D、v1、v0、v3、v4、v6、v2、v5

2、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个。

A、1

B、2

C、3

D、4

3、用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是（ ）。

A、入栈操作的复杂度为O(1)

B、出栈操作的复杂度为O(1)

C、删除底部元素的复杂度为O(1)

D、插入一个新的堆栈底部元素复杂度为O(1)

4、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。

A、N1-1

B、N2-1

C、N2+N3

D、N1+N3

5、下面关于线性表的叙述中，错误的是哪一个（ ）。

A、线性表采用顺序存储，必须占用一片连续的存储单元

B、线性表采用顺序存储，便于进行插入和删除操作

C、线性表采用链式存储，不必占用一片连续的存储单元

D、线性表采用链式存储，便于插入和删除操作

1、试题答案：D

试题解析：

【考点】本题考查拓扑排序的思想。 

【解析】拓扑排序中，只有入度为0的点才可以添加到拓扑序列中。A选项中，V5的入度来自结点V2 V3 V4，而V3不在V5之前的拓扑序列中，因此A选项错误。同理，B选项中V5之前的拓扑序列中应该有V2。C选项与B选项问题一致。故本题选D。

2、试题答案：D

试题解析：

本题考查散列表的构造。
用H（K）=K %9作为散列函数，对线性表的关键字进行散列，求得四个关键字的散列地址为1，分别为55、64、46、10。故本题选D。

3、试题答案：C

试题解析：

本题考查栈的基本操作的时间复杂度。
栈具有后进先出的特性，只允许在表的一端进行插入和删除。在栈头部插入和删除的时间复杂度均为O(1)，存在尾部指针时，在栈底插入的时间复杂度为O(1)，删除O(n)。若不存在尾指针，在栈底插入和删除的时间复杂度均为O(n)。故本题选C。

4、试题答案：A

试题解析：

本题考查森林转化为二叉树。
森林转化为二叉树的过程：首先，T1、T2和T3先分别转化为二叉树，除根结点以外，其它结点都转化为根结点的左孩子。接着，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子。最终实现森林到二叉树的转化。根据此过程易知，二叉树B的根结点的左子树的结点数为N1-1。故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查顺序表和链表的特点。
【解析】线性表采用顺序存储，即顺序表，系统必须为其分配一片连续的空间，可以随机查找，但是不便于进行插入和删除操作。因为，在顺序表中进行插入和删除操作时，可能需要移动大量元素。线性表采用链式存储，即链表，其中各个结点通过指针两两连接，不需要占用一片连续的存储单元。在链表中进行插入和删除操作时，只需要修改指针指向即可，非常方便。故本题选B。