2021年數(shù)據(jù)結(jié)構(gòu)考研真題答案及解析（二）

本文提供2021年數(shù)據(jù)結(jié)構(gòu)考研真題答案及解析，以下為具體內(nèi)容

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

A、i

B、n-i

C、n-i+1

D、不確定

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

A、2

B、3

C、4

D、5

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

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

B、樹中一定沒有度為1的結(jié)點

C、樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點

D、樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值

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

A、6

B、15

C、16

D、21

5、已知循環(huán)隊列存儲在一維數(shù)組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、下列關(guān)于最小生成樹的說法中，正確的是（ ）。I. 最小生成樹的代價唯一 II. 所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中III. 使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同IV. 使用普里姆算法和克魯斯卡爾（ Kruskal）算法得到的最小生成樹總不相同

A、僅I

B、僅II

C、僅I、III

D、僅II、IV

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

A、12

B、20

C、32

D、34

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

A、與m直接相關(guān)

B、與n直接相關(guān)

C、與α直接相關(guān)

D、與m、n和α都直接相關(guān)