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

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

1、下面關(guān)于倒排文件的說法中正確的是（ ）。

A、倒排文件是對主關(guān)鍵字建立索引的

B、倒排文件是對次關(guān)鍵字建立索引的

C、倒排序文件的優(yōu)點(diǎn)是維護(hù)簡單

D、采用倒排文件是為了節(jié)省存儲空間

2、下列術(shù)語中，（ ）與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。

A、循環(huán)隊列

B、堆棧

C、散列表

D、單鏈表

3、用DFS遍歷一個有向無環(huán)圖，并在DFS算法退棧返回時打印當(dāng)前頂點(diǎn)，則輸出的頂點(diǎn)序列是（ ）。

A、拓?fù)溆行虻?/p>

B、無序的

C、逆拓?fù)溆行虻?/p>

D、按頂點(diǎn)編號次序的

4、下面（ ）算法可用于求無向圖的所有連通分量。

A、廣度優(yōu)先遍歷

B、拓?fù)渑判?/p>

C、求最短路徑

D、求關(guān)鍵路徑

5、可以使用大O記號表示一個算法的時間復(fù)雜度。下列表示中正確的是（ ）。

A、

B、

C、

D、

6、設(shè)線性表非空，采用下列（ ）所描述的鏈表可以在O（1）時間內(nèi)在表尾插入一個新結(jié)點(diǎn)。

A、帶表頭結(jié)點(diǎn)的單鏈表，一個鏈表指針指向表頭結(jié)點(diǎn)

B、帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個鏈表指針指向表頭結(jié)點(diǎn)

C、不帶表頭結(jié)點(diǎn)的單鏈表，一個鏈表指針指向表的第一個結(jié)點(diǎn)

D、不帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個鏈表指針指向表的第一個節(jié)點(diǎn)

7、設(shè)主串為“abceabceyabceabceab”，子串為“abceabcea”，則在KMP匹配第一趟失配后下一趟匹配開始時，子串指針指示的字符是（ ）。

A、a

B、b

C、c

D、e

8、二叉樹中第5層上的結(jié)點(diǎn)個數(shù)最多為（ ），假定根節(jié)點(diǎn)層次為1。

A、8

B、15

C、16

D、32

9、設(shè)有以元素10，9，20，6，85，23，21，17 為葉結(jié)點(diǎn)的8路合并勝方樹，在輸出一個元素后，將有一個新元素補(bǔ)充到相應(yīng)的葉結(jié)點(diǎn)中。在重構(gòu)的勝方樹中，應(yīng)有（ ）個元素需要修正。

A、1

B、2

C、3

D、4

10、在一棵二叉搜索樹上搜索一個元素的平均時間復(fù)雜度為（ ）。

A、

B、

C、

D、