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

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

1、设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中至少有（ ）个结点。

A、2h

B、2h-1

C、2h+1

D、h+1

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

A、1

B、k

C、n

D、n-k

3、已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时间。

A、堆排序

B、直接插入排序

C、快速排序

D、简单选择排序

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

A、429

B、432

C、435

D、438

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

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

1、试题答案：B

试题解析：

根据题干描述，画出符合要求的二叉树如下所示：

根据上图可知二叉树至少有2*（h-1）+1=2h-1，故本题选B。

2、试题答案：D

试题解析：

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

3、试题答案：B

试题解析：

堆排序和简单选择排序的时间复杂度不受序列初始状态影响，因此A和D错误。对于B，序列越有序，直接插入排序越节省时间，因此B正确。对于C，序列越有序，快速排序完成排序所需的时间越多，因此C错误。故本题选B。

4、试题答案：A

试题解析：

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

5、试题答案：A

试题解析：

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