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

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

1、下列数据中，（ ）是非线性数据结构。

A、栈

B、队列

C、完全二叉树

D、堆

2、设一个链表最常用操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。

A、带头结点的双循环链表

B、单循环链表

C、带尾指针的单循环链表

D、单链表

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

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

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

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

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

4、在下列排序方法中，（  ）方法可能出现这种情况: 在最后一趟开始之前， 所有的元素都不在其最终应在的正确位置上。

A、快速排序

B、冒泡排序

C、堆排序

D、插入排序

5、在一个双链表中，在ρ结点之前插入q结点的操作。

A、p->prior=q; q->next=p; p->prior->next-q; q->prior=p->prior;

B、q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;

C、q->next=p; p->next=q; q->prior->next =q; q->next=p;

D、p->prior->next=q; q->next=p; q->prior=p->prior; p->prior =q;

1、试题答案：C

试题解析：

线性结构是一个有序数据元素的集合，其特点是数据元素之间存在一对一的线性关系。栈和队列是线性数据结构，堆也可以看作是线性结构，一般存储在数组中。而完全二叉树根结点与子结点存在一对多的关系，一定是非线性结构。故本题选C。

2、试题答案：A

试题解析：

【考点】本题考查链表的选取。
【解析】
A带头结点的双循环链表：插入和删除都不需要遍历链表，较为容易。
B单循环链表：在末尾不管是插入还是删除元素，都需要从头遍历整个链表找到尾结点，比较费时。
C带尾指针的单循环链表：在末尾插入元素可以，但是在末尾删除元素时，需要从头到尾遍历获取要删除结点的前驱结点，比较费时。
D单链表：和单循环链表一样，在单链表中的末尾不管是插入还是删除元素，都需要从头遍历整个链表找到尾结点，比较费时。
综上所述，本题选A。

3、试题答案：B

试题解析：

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

4、试题答案：D

试题解析：

【考点】本题考查几种常见的排序算法。
【解析】
（1）快速排序：每一趟排序都可以确定枢轴元素的最终位置。
（2）冒泡排序：每一趟排序都可以确定一个最大或最小元素的最终位置。
（3）堆排序：每一趟都选取堆顶元素（最大或最小元素）加入有序序列，即可确定最大或最小元素的最终位置。
（4）插入排序：最后一趟插入的可能是最小元素，导致所有元素都不在其最终位置上。
综上所述，本题选D。

5、试题答案：D

试题解析：

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