本文提供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
点击查看答案与解析
