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

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

A、倒排文件是對主關鍵字建立索引的

B、倒排文件是對次關鍵字建立索引的

C、倒排序文件的優點是維護簡單

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

2、下列術語中，（ ）與數據的存儲結構無關。

A、循環隊列

B、堆棧

C、散列表

D、單鏈表

3、用DFS遍歷一個有向無環圖，并在DFS算法退棧返回時打印當前頂點，則輸出的頂點序列是（ ）。

A、拓撲有序的

B、無序的

C、逆拓撲有序的

D、按頂點編號次序的

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

A、廣度優先遍歷

B、拓撲排序

C、求最短路徑

D、求關鍵路徑

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

A、

B、

C、

D、

6、設線性表非空，采用下列（ ）所描述的鏈表可以在O（1）時間內在表尾插入一個新結點。

A、帶表頭結點的單鏈表，一個鏈表指針指向表頭結點

B、帶表頭結點的單循環鏈表，一個鏈表指針指向表頭結點

C、不帶表頭結點的單鏈表，一個鏈表指針指向表的第一個結點

D、不帶表頭結點的單循環鏈表，一個鏈表指針指向表的第一個節點

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

A、a

B、b

C、c

D、e

8、二叉樹中第5層上的結點個數最多為（ ），假定根節點層次為1。

A、8

B、15

C、16

D、32

9、設有以元素10，9，20，6，85，23，21，17 為葉結點的8路合并勝方樹，在輸出一個元素后，將有一個新元素補充到相應的葉結點中。在重構的勝方樹中，應有（ ）個元素需要修正。

A、1

B、2

C、3

D、4

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

A、

B、

C、

D、