2019年数据结构考研真题答案及解析（五）

本文提供2019年数据结构考研真题答案及解析，以下为具体内容

1、以下数据结构中，属于逻辑结构的是（ ）。

A、顺序表

B、哈希表

C、有序表

D、单链表

2、以下算法的时间复杂度为（ ）。void fun(int n){ int i=1; while(i <= n) i = i*2; }

A、O(n)

B、O(n²)

C、O(nlog₂n)

D、O(log₂n)

3、线性表是一个具有n个（ ）有限序列。

A、数据表

B、字符

C、数据元素

D、数据项

4、下列哪一条是顺序存储的优点（ ）。

A、存储密度大

B、插入运算方便

C、删除运算方便

D、可方便地运用于各种逻辑结构的存储表示

5、线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（ ）存储方式。

A、单链表

B、双链表

C、循环链表

D、顺序表

6、对于一个线性表既要能够进行快速的插入和删除，又要求存储结构能够反映数据间的逻辑关系，则应采用（ ）。

A、顺序存储方式

B、链式存储方式

C、散列存储方式

D、以上均可以

7、在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（ ）操作与链表的表长有关。

A、删除单链表中的第一个元素

B、删除单链表中的最后一个元素

C、在单链表第一个元素前插入一个元素

D、在单链表最后一个元素后插入一个元素

8、在双链表中向p所指结点之前插入一个结点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;

9、静态链表中的指针表示（ ）。

A、下一个元素的地址

B、内存的地址

C、下一个元素在数组中的位置

D、左链或者右链指向元素的地址

1、试题答案：C

试题解析：

顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，也描述存储结构和数据运算。而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述了元素之间的逻辑关系，属于逻辑结构。故本题选C。

2、试题答案：D

试题解析：

假设共进行k次循环体执行，即有2^k=n，解得k= log₂n。因此，算法的时间复杂度为O(log₂n)。故本题选D。

3、试题答案：C

试题解析：

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列，表中元素之间的关系是一对一的。故本题选C。

4、试题答案：A

试题解析：

A：相较于链式存储而言，顺序存储中的每个结点仅存储数据信息，不存储结点指针，所以其存储密度更大。
B、C：采用顺序存储不便于元素的插入和删除，因为有可能需要移动大量元素。
D：对于树状、图形结构这些逻辑结构而言，顺序存储并不是很方便。
综上所述，本题选A。

5、试题答案：B

试题解析：

A、C：对于单链表、循环链表而言，从头遍历第i个位置即可存取第i个元素，但是不方便查找其前驱元素的值。
B：对于双链表而言，从头遍历第i个位置即可存取第i个元素，且存在指向前驱和后继的指针，所以存取其前驱和后继元素的值也很方便。
D：对于顺序而言，查到第i个元素非常方便，但是插入或删除第i个元素时，需要移动大量元素，所以不便于存取第i个元素及其前驱和后继元素的值。
综上所述，本题选B。

6、试题答案：B

试题解析：

A：在顺序存储方式中，插入和删除一个元素可能需要移动大量元素，不是很方便。
B：链式存储方式中的各个结点通过指针相连接，插入和删除一个元素时，只需要修改指针指向即可，很方便。
C：散列存储方式不能反映元素之间的逻辑关系。
综上所述，本题选B。

7、试题答案：B

试题解析：

删除单链表中的最后一个元素时，需要遍历整个链表找到最后一个元素的前驱结点。而选项A、C、D中的操作不需要遍历链表即可完成。因此，只有执行删除单链表中的最后一个元素的操作与链表的表长有关。故本题选B。

8、试题答案：D

试题解析：

在双链表中向p所指结点之前插入一个结点q的操作示意图如下，由此知本题选D。

9、试题答案：C

试题解析：

静态链表中数组的每一个结点包含一个数据域data和一个游标cur，数据域data用来存放数据元素，而游标cur相当于单链表中的next指针，用于存放该元素的后继在数组中的下标。因此，静态链表中的指针表示下一个元素在数组中的位置。故本题选C。