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

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

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

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

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

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

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

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

A、循環(huán)隊列

B、堆棧

C、散列表

D、單鏈表

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

A、拓撲有序的

B、無序的

C、逆拓撲有序的

D、按頂點編號次序的

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

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

B、拓撲排序

C、求最短路徑

D、求關鍵路徑

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

A、

B、

C、

D、

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

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

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

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

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

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

A、a

B、b

C、c

D、e

8、二叉樹中第5層上的結點個數(shù)最多為（ ），假定根節(jié)點層次為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、