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

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

1、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。

A、O(1)

B、O(n)

C、O(m)

D、O(m+n)

2、G是一个连通图，共有28条边，则该图至少有（ ）个顶点。

A、6

B、7

C、8

D、9

3、下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A、堆排序

B、冒泡排序

C、快速排序

D、直接插入排序

4、含有10个结点的二叉树中，度为0的结点数个数为4，则度为2的结点个数为（ ）。

A、3

B、4

C、5

D、6

5、已知广义表A=((a,b,c),(d,e,f))，从A中取出原子e的运算是（ ）。

A、head(tail(head(tail(A))))

B、head(tail(tail(head(A))))

C、head(tail(A))

D、tail(head(A))

1、试题答案：C

试题解析：

将长度为n的单链表链接在长度为m的链表之后，需要将长度为m的单链表的尾结点的指针指向长度为n的单链表的头结点。根据单链表的特性，寻找单链表的尾结点需要从头开始遍历链表，因此其时间复杂度为O(m)，故本题选C。

2、试题答案：A

试题解析：

当该图为有向的完全连通图时，图的顶点数最少，此时图的顶点和边数满足n*（n-1）=e，带入边数=28，n*（n-1）≥28，解得n为6，则故本题选A。

3、试题答案：C

试题解析：

快速排序是把序列分块，若序列已经基本有序，则选取第一个数为枢纽时，第一块前面没有数，第二块是除了第一个数以外的所有值，每次分块仅减少一个值。分块的时间复杂度是O(n)，分了n次块，时间复杂度是O(n²)。故本题选C。

4、试题答案：A

试题解析：

根据二叉树的性质，对任何一棵二叉树，若终端结点为n₀，度为2的结点为n₂，则n₀=n₂+1。证明该性质：设n₁为二叉树中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，所以其结点总数为n=n₀+n₁+n₂。二叉树中，除根结点以外，其余结点均有一个分支进入，设分支总数为B，则有n=B+1。由于这些分支是由度为1或者度为2的结点射出的，所以有B=n₁+2*n₂。带入B=n-1可得，n₀+n₁+n₂-1=n1+2*n2，即n₀=n₂+1。故本题选A。

5、试题答案：A

试题解析：

可以运用head和tail函数取A中原子e的步骤如下：
（1）使用tail函数取出A中第二个元素构成的列表：tail(A)=((d,e,f))；
（2）使用head函数取出tail(A)的第一个元素：head(tail(A))=(d,e,f)；
（3）再使用tail函数取出head(tail(A))的尾巴部分：tail(head(tail(A)))=(e,f)
（4）最后使用head函数取出尾巴部分的第一个元素，即原子e：head(tail(head(tail(A))))=e
因此，A中原子e的运算为head(tail(head(tail(A))))= e。故本题选A。