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

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

1、设N是描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。static int fun(int N){ if(N==1) return 0; return 1 + fun(N/2);}

A、O(logN)

B、O(N)

C、(NlogN)

D、O(N)

2、一些随机产生的数采用线性链表存储，在下面这些排序方法中，（ ）的时间复杂度是最小的。

A、插入排序

B、快速排序

C、堆排序

D、归并排序

3、一个栈的输入序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是（ ）。

A、b c d a e

B、e d a c b

C、b c a d e

D、a e d c b

4、实现一个队列需要（ ）个栈。

A、1

B、2

C、3

D、4

5、下面（ ）是一棵满二叉树的结点个数。

A、8

B、13

C、14

D、15

6、下列序列中，哪一个是堆（ ）？

A、75，65，30，15，25，45，20，10

B、75，65，45，10，30，25，20，15

C、75，45，65，30，15，25，20，15

D、75，45，65，10，25，30，20，15

7、一棵Huffman树共有203个结点，对其Huffman编码，共能得到（ ）个不同的码字。

A、100

B、102

C、200

D、203

8、下面说法错误的是（ ）。

A、一个有n个顶点和n条边的无向图一定是有环的。

B、建立十字链表的时间复杂度和建立邻接表是相同的。

C、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

D、在某些图的应用问题中，如果需要找到表示同一条边的两个结点，那么采用邻接多重表比邻接表作为储存结构更为适宜。

9、图的广度优先遍历算法中使用列作为其辅助数据结构，那么在算法执行过程中每个顶点进队次数最多为（ ）。

A、1

B、2

C、3

D、4

10、设一个有向图G=（V，E），其中V={v1，v2，v3，v4，v5，v6}E={<v1，v2>，<v2，v3>，<v3，v6>，<v4，v2>，<v4，v5>，<v5，v6>}不属于该图的拓扑排序有序序列是（ ）。

A、v1 v2 v3 v4 v5 v6

B、v1 v4 v2 v3 v5 v6

C、v4 v5 v1 v2 v3 v6

D、v4 v1 v2 v3 v5 v6