考研数据结构及程序设计在线题库每日一练（六）

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

1、在一个双链表中，在p结点之后插入结点q的操作是（ ）。

A、q→prior=p;p→next=q;p→next→prior=q;q→next=p→next;

B、q→next=p→next;p→next→prior=q;p→next=q;q→prior=p;

C、p→next=q;q→prior=p;q→next=p→next;p→next→prior=q;

D、q→prior=p:p→next=q;q→next=p→next;p→next→prior=q;

2、设某链表中最常用操作是在链表尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。

A、单向链表

B、单向循环链表

C、双向链表

D、双向循环链表

3、查找哈希Hash表，不会发生冲突的哈希函数（ ）。

A、除留余数法

B、伪随机探测再散列法

C、直接地址法

D、线性探测再散列法

4、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序。

A、冒泡排序

B、希尔排序

C、快速排序

D、堆排序

5、设head(L)、tail(L)分别为取广义表表头、表尾的操作，则从广义表L=（（x，y，z），a，（u，v，w））中取出原子u的运算为（ ）。

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

B、tail(head(head(tail(L))))

C、head(tail(head(tail(L))))

D、head(head(tail(tail(L))))

1、试题答案：B

试题解析：

【考点】本题考查双链表的删除。
【解析】在一个双链表中，在p结点之后插入结点q的操作示意图如下所示，其中① q->next=p->next; ② p->next->prior=q; ③ p->next=q; ④ q->prior=p;。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查双向循环链表。
【解析】在单向链表、单向循环链表以及双向链表中，均需要从头到尾遍历整个链表才能找到尾元素的位置，花费时间长。而在双向循环链表中，通过头结点指针可以直接在O(1)的时间复杂度内找到尾元素的位置。在链表尾部插入或删除元素时，双向循环链表这一存储方式相较于其他三种而言，最能节省运算时间。故本题选D。

3、试题答案：C

试题解析：

【考点】本题考查哈希函数。
【解析】直接地址法散列函数的优点是简单、均匀，也不会产生冲突，但是这需要事先知道关键字的分布情况，它适合查找表较小且关键字分布连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。故本题选C。

4、试题答案：C

试题解析：

【考点】本题考查排序算法的综合比较。
【解析】分析如下：
A：若序列已有序时，选择冒泡排序进行一趟后，发现两两元素比较并未发生交换，即可确定此时序列已经有序，排序结束。
B：若序列已有序时，选择排序每一趟排序过程中都没有元素交换，直到步长为1时，整个排序过程结束。
C：在快速排序中，通过基准元素把序列分成两个部分，一般选择第一个元素为基准元素。若序列已经有序，进行第一趟排序时，第一个元素（最小元素）作为基准会将整个序列分成两部分，左部分为空，右部分为剩余元素。第一趟排序时，左部分无需排序，右部分继续进行快速排序，选取右部分第一个元素作为基准将整个序列分成两部分，左部分为空，右部分为剩余元素。这一过程中，每次分块只减少一个元素，n个元素需要进行n-1次分块才能结束整个快速排序，浪费时间耗时更长。这是快速排序最糟糕的情况，时间复杂度为O(n²)。
D：堆排序的最好、最坏、平均时间复杂度都是O(nlogn)。
综上所述，在待排序数据已有序时，花费时间反而最多的是快速排序。故本题选C。

5、试题答案：D

试题解析：

【考点】本题考查广义表表头和表尾操作。
【解析】tail(L)=（a，（u，v，w））；tail(tail(L))=（（u，v，w））；head(tail(tail(L)))=（u，v，w）；head(head(tail(tail(L))))=u。故本题选D。