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

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

1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

A、逻辑结构

B、存储结构

C、逻辑实现

D、存储实现

2、非线性结构中的每个结点（ ）。

A、无直接前趋结点

B、无直接后继结点

C、只有一个直接前趋结点和一个直接后继结点

D、可能有多个直接前趋结点和多个直接后继结点

3、双向链表中在某结点前做插入运算的时间复杂度为（ ）。

A、O(1)

B、O(n)

C、O(n2)

D、O(1og2n)

4、以下关于线性表的论述，不正确的为（ ）。

A、线性表中的元素可以是数字、字符、记录等不同类型

B、线性顺序表中包含的元素个数不是任意的

C、线性表中的每个结点都有且仅有一个直接前驱和一个直接后继

D、存在这样的线性表，即表中没有任何结点

5、从一个栈顶指针为top的链栈中刪除一个结点时，用x保存被删除的结点，应执行下列（ ）命令。

A、x=top; top=top->next;

B、top=top->next; x=top->data;

C、x=top->data;

D、x=top->data; top=top->next;

6、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为4和0，当从队列中删除一个元素，再加入三个元素后，front和rear的值分别为（ ）。

A、5和1

B、5和3

C、2和4

D、1和5

7、若字符串“ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度50%，则每个结点应存储（ ）个字符。

A、2

B、3

C、4

D、5

8、S1="good"，S2="morning"，执行函数SubStr (S2, 4, LenStr(S1))后的结果为（ ）。

A、"good"

B、"ning"

C、"go"

D、"morn"

1、试题答案：A

试题解析：

本题考查数据结构的相关概念。
逻辑结构指反映数据元素之间的逻辑关系的数据结构，是理论上的东西。其中的逻辑关系是指数据元素之间的前后关系，与数据元素本身的形式、内容、相对位置、个数是无关的。故本题选A。

2、试题答案：D

试题解析：

本题考查非线性结构的逻辑特征。
非线性结构的逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。 故本题选D。

3、试题答案：A

试题解析：

本题考查双链表插入操作的时间复杂度。
双向链表中在某结点前做插入运算时，只需要修改结点指针即可，不需要移动元素，所以其时间复杂度为O(1)。故本题选A

4、试题答案：C

试题解析：

本题考查线性表的特点。
带头结点的单链表是线性表，当其为空时，表中只剩下头结点这一个结点，此时该结点既无直接前驱也无直接后继。所以线性表中的每个结点都有且仅有一个直接前驱和一个直接后继这一说法错误。故本题选C。

5、试题答案：D

试题解析：

本题考查链栈的删除操作。
链栈中，栈顶指针top指向要删除的结点，所以先将该结点值赋值给x，再移动栈顶指针，即可实现删除结点并用x保存该结点的操作。故本题选D。

6、试题答案：B

试题解析：

本题考查循环队列。
循环队列中，每删除一个元素后队首指针要加1，即front=（front+1）%6，结果为5；每加入一个元素队尾指针加1，即rear=（rear+1）%6，加入三个元素后变为3。故本题选B。

7、试题答案：A

试题解析：

本题考查存储密度。
存储密度是指数据元素本身所占的存储量和整个结点结构所占的存储量之比。假设单链表数据元素本身的存储量为N，指针域所占的存储量为M，则存储密度为：N/（N+M）。题干给出每个指针占2个字节，且一个英文字符占1个字节。假设每个结点应该存储x个字符，则x/(x+2)=50％，解得x=2。故本题选A。

8、试题答案：B

试题解析：

本题考查substr函数。
substr(string,start,length)的作用是在字符串string中，截取从第start个字符开始的长度为length的字符串。SubStr (S2, 4, LenStr(S1))的作用是在字符串“morning”中，截取从‘n’开始的4个字符，其结果为“ning”。故本题选B。