本文提供2021年數據結構考研真題答案及解析，以下為具體內容

1、已知一個棧的進棧序列是1，2， 3， ...， n，其輸出序列是p1，p2，p3，…，pn，若pn=1，則pi的值是（ ）。

A、i

B、n-i

C、n-i+1

D、不確定

2、設有向圖G=（V，E），頂點集V={V0，V1，V2，V3}， 邊集E={<v0，v1>，<v0，v2>，<v0，v3>，<v1，v3>}。若從頂點V0開始對圖進行深度優先遍歷，則可能得到的不同遍歷序列個數是（ ）。

A、2

B、3

C、4

D、5

3、對n（n≥2）個權值均不相同的字符構成哈夫曼樹，下列關于該哈弗曼樹的敘述中，錯誤的是（ ）。

A、該樹一定是一棵完全二叉樹

B、樹中一定沒有度為1的結點

C、樹中兩個權值最小的結點一定是兄弟結點

D、樹中任一非葉結點的權值一定不小于下一層任一結點的權值

4、若無向圖G=（V，E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數最少是（ ）。

A、6

B、15

C、16

D、21

5、已知循環隊列存儲在一維數組A[0..n-1]中， 且隊列非空時front和rear分別指向隊頭和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（ ）。

A、0，0

B、0，n-1

C、n-1，0

D、n-1，n-1

6、下列關于最小生成樹的說法中，正確的是（ ）。I. 最小生成樹的代價唯一 II. 所有權值最小的邊一定會出現在所有的最小生成樹中III. 使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同IV. 使用普里姆算法和克魯斯卡爾（ Kruskal）算法得到的最小生成樹總不相同

A、僅I

B、僅II

C、僅I、III

D、僅II、IV

7、若平衡二叉樹的高度為6，且所有非葉結點的平衡因子均為1，則該平衡二叉樹的結點總數為（ ）。

A、12

B、20

C、32

D、34

8、若散列表的長度為m，待散列的元素的個數為n，裝填因子為α，則散列表的平均查找長度為（ ）。

A、與m直接相關

B、與n直接相關

C、與α直接相關

D、與m、n和α都直接相關