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

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

1、算法的健壯性是指（ ）。

A、當(dāng)輸入不合法數(shù)據(jù)時，程序會采取應(yīng)急措施

B、算法是正確的

C、程序不會被病毒所染

D、算法執(zhí)行不會陷入無限循環(huán)

2、根據(jù)大O記號的定義，下列表示中不正確的是（ ）。

A、

B、

C、

D、

3、循環(huán)隊列存儲在一維數(shù)組q中，設(shè)數(shù)組的允許長度是maxSize，數(shù)組下標(biāo)從0開始。如果采用在循環(huán)隊列中至少保留一個空閑元素的方法來區(qū)分空隊列和滿隊列，判斷隊列為滿的條件是（ ）。

A、front=-rear

B、（front+1）%maxSize== rear

C、（rear+1）%maxSize==front

D、front+rear=maxSize

4、圖結(jié)構(gòu)是（ ）關(guān)系。

A、一對多

B、多對一

C、一對一

D、多對多

5、設(shè)有主串s=s1s2...sn和子串p=p1p2…pm。在字符串的KMP匹配算法中，當(dāng)某趟匹配在字符si和sj的比較匹配時，下趟匹配（ ）。

A、總是從字符si與p1的比較開始

B、可能從字符si+1與p1的比較開始

C、不可能從字符si+1與p1的比較開始

D、總是從字符si+1與p1的比較開始

6、設(shè)F是一個森林，B是由F變換得到的二叉樹。若F中有n個非葉結(jié)點，則B中右指針為空的結(jié)點有（ ）個。

A、n-1

B、n

C、n+1

D、n+2

7、下列編碼中，（ ）不是前綴編碼。

A、（00，01，10，11）

B、（0，1，00，11）

C、（0，10，110，111）

D、（1，01，000，001）

8、在圖采用鄰接矩陣存儲時，深度優(yōu)先遍歷算法的時間復(fù)雜度應(yīng)為（ ）。

A、O(n)

B、O(n+e)

C、O(n²)

D、O(n³)

9、下面關(guān)于B和B+樹的敘述中，不正確的是（ ）。

A、兩者都可用于文件的索引結(jié)構(gòu)

B、兩者都能有效地支持順序存取

C、兩者都能有效地支持隨機(jī)存取

D、兩者的葉子結(jié)點都在同一層次上

10、設(shè)有n個元素的序列，分別使用冒泡排序和合并排序?qū)ζ溥M(jìn)行排序，則所需的除元素列以外的輔助空間復(fù)雜度依次為（ ）。

A、O(1)和O(n)

B、O(1)和O(nlog₂n)

C、O(n)和O(1)

D、O(n)和O(n)