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

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

1、下述关于顺序存储结构优点的说法，哪个是正确的（ ）。

A、插入运算方便

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

C、存储密度大

D、删除运算方便

2、假设根结点为第1层，深度为h层的二叉树至少有（ ）个结点（h>1）。

A、2h

B、2h-1

C、2h+1

D、2h-1

E、无答案

3、用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是（ ）。

A、入栈操作的复杂度为O（1）

B、出栈操作的复杂度为O（1）

C、删除底部元素的复杂度为O（1）

D、插入一个新的堆栈底部元素复杂度为O（1）

4、以下关于递归算法的论述，不正确的是（ ）。

A、递归算法的代码可读性好

B、递归算法可以提高程序运行效率

C、递归调用层次太深有可能造成堆栈溢出

D、递归调用层次太深会占用大量内存

5、设有字符集合{4，6，3，W，S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。则以下的出栈序列错误的是（ ）。

A、64WS3

B、4W36S

C、6W34S

D、WS436

6、在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。

A、有向图

B、无向图

C、树

D、矩阵

7、具有k个顶点的完全有向图的边数为（ ）。

A、k（k-1）

B、k（k-1）/2

C、 k2-1

D、k2+1

8、若线性表最常用的操作是增加或者删除某个元素， 则采用（ ）存储方式节省时间.

A、单链表

B、双链表

C、单循环链表

D、顺序表

9、由权为6，3，2，8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。

A、36

B、35

C、34

D、33

10、为了提高哈希表的查找效率，以下方法说法不正确的是（ ）。

A、设计好的哈希函数

B、增加哈希函数的个数

C、增大存储空间

D、采用更好的地址冲突解决方法

1、试题答案：C

试题解析：

本题考查数据结构的顺序存储。
顺序存储结构利用数据元素在存储器中的相对位置之间的特定关系来表示数据元素之间的逻辑关系，在存储器中是紧密排列的，因此相较于链式存储结构其存储密度更大，因此C选项正确。顺序存储结构在插入和删除时均需要移动大量元素，而链式存储结构可以通过指针的方式更方便的查找指定元素进行插入和删除，因此A和D选项错误。有些逻辑结构如树形结构等使用顺序结构没有链式结构方便，因此B选项错误。故本题选C。

2、试题答案：E

试题解析：

本题考查二叉树的性质。
本题目无正确答案，深度为h的二叉树最少的结点个数为h个，即每一层只有一个结点，最多的结点个数满二叉树的结点个数，为2h-1个结点。若将题目改为深度为h层的完全二叉树，则至少有2h-1个结点。

3、试题答案：C

试题解析：

本题考查栈的基本操作的时间复杂度。
栈具有后进先出的特性，只允许在表的一端进行插入和删除。在栈头部插入和删除的时间复杂度均为O（1），存在尾部指针时，在栈底插入的时间复杂度为O（1），删除O（n）。若不存在尾指针，在栈底插入和删除的时间复杂度均为O（n）。故本题选C。

4、试题答案：B

试题解析：

本题考查递归算法的性质。
递归算法的代码结构清晰，可读性较好，A选项正确。当调用层次较深时，函数多次调用，会增加额外的堆栈处理，因此可能会造成堆栈溢出问题，C选项正确，每次调用需要保存地址，参数等，会占用大量内存，D选项正确。递归算法每调用一次均增加时间和空间的开销，因此递归算法运行效率较低，B选项错误。故本题选B。

5、试题答案：D

试题解析：

本题考查栈的基本操作。
A选项6入栈再出栈，W入栈，4入栈，4出栈，W出栈，3入栈，S入栈，S出栈，3出栈。A选项可能实现，因此A正确。B选项6入栈，W入栈，4入栈，4出栈，W出栈，3入栈，3出栈，6出栈，S入栈，S出栈，B选项可能实现，因此B选项正确。C选项6入栈，6出栈，W入栈，W出栈，4入栈，3入栈，3出栈，4出栈，S入栈，S出栈，C选项可能实现，因此C选项正确。D选项6入栈，W入栈，W出栈，4入栈，3入栈，S入栈，S出栈，4应该在3之后出栈，因此该出栈序列不可能，D错误。故本题选D。

6、试题答案：B

试题解析：

本题考查网状数据结构的存储。
道路交通的点之间存在“多对多”的特点，而树是“一对多”的结构，矩阵是线性结构，因此C和D错误。道路交通是网络结构，一个城市可以到达多个城市，多个城市可以到达该城市，因此应该用图结构来存储。而城市A可以到城市B，城市B也可以到城市A，因此是一个无向图，本题应该选择B。故本题选B。

7、试题答案：A

试题解析：

本题考查图的性质。
有向完全图是指图中各边均有方向，并且每两个顶点之间都有两条方向相反的边连接成图。因此，图中的各个顶点均需要与除自身顶点以外的各个顶点相连，每个顶点连接k-1个顶点需要k-1条边，k个顶点需要k（k-1）条边。故本题选A。

8、试题答案：B

试题解析：

本题考查表的基本操作。
对于A，单链表删除某结点时需要遍历得到前驱节点，时间复杂度为O（n），若给定前驱结点，插入的操作时间复杂度为O（1）。对于B，双链表删除某结点时，可以通过q=p->prior方式获得，时间复杂度为O（1），若给定前驱结点，插入的操作时间复杂度为O（1）。单循环链表带尾指针时对最后一个元素或者第一个元素的插入删除较为方便，时间复杂度为O（1），否则为O（n）。顺序表插入和删除的操作时间复杂度均为O（n），因此本题双链表在插入和删除时时间复杂度最小。故本题选B。

9、试题答案：B

试题解析：

本题考查哈夫曼树的构造。
根据哈夫曼树的构造原理画出该树如下图所示：


求树的带权路径长度的方法为树中所有叶子结点的带权路径长度和，结点的带权路径的长度为树的根结点到该结点的路径长度与权值的乘积，因此得到该树的带权路径长度为8*1+6*2+2*3+3*3=35。故本题选B。

10、试题答案：B

试题解析：

本题考查哈希表的性质。
A选项设定一个好的哈希函数可以减少冲突的个数，即减少计算的次数，可以提高效率；C选项增大存储空间，记录的集合增大，减少冲突，提高效率；D选项减少冲突次数，减少计算时间，提高查找效率。而B选项哈希函数增加，会相应增加哈希计算的时间，降低哈希表的查找效率。故本题选B。