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

1、下列鏈表中，（ ）不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其它任何一個(gè)結(jié)點(diǎn)。

A、單循環(huán)鏈表

B、帶表頭的單鏈表

C、雙向鏈表

D、帶表頭的單循環(huán)鏈表

2、長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i（0≤i≤n）個(gè)位置插入一個(gè)新元素的算法的平均時(shí)間復(fù)雜度為（ ）

A、O(0)

B、O(1)

C、O(n)

D、O(n²)

3、森林F中有三棵樹(shù)，第一、二和三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1，m2 和m3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。

A、m1

B、m1+m2

C、m3

D、m2+m3

4、下述二叉樹(shù)中，（ ）滿足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序。

A、堆

B、哈夫曼樹(shù)

C、AVL樹(shù)

D、二叉搜索樹(shù)

5、一棵三叉樹(shù)中，已知度為3的結(jié)點(diǎn)個(gè)數(shù)等于度為2的結(jié)點(diǎn)數(shù)，且樹(shù)中葉結(jié)點(diǎn)數(shù)目為10，則度為2的結(jié)點(diǎn)數(shù)目為（ ）。

A、3

B、2

C、4

D、6

6、在線性表中采用對(duì)半搜索方法搜索元素，該線性表應(yīng)為（ ）。

A、有序表且順序存儲(chǔ)

B、有序表且鏈接存儲(chǔ)

C、無(wú)序表且順序存儲(chǔ)

D、無(wú)序表且鏈接存儲(chǔ)

7、散列文件一般采用（ ）解決沖突。

A、拉鏈法

B、線性探查法

C、偽隨機(jī)探查法

D、雙散列法

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

A、O(n*e)

B、O(n+e)

C、O(e)

D、O(n²)

9、下面（ ）算法可以判斷一個(gè)有向圖是否有環(huán)。

A、求最小代價(jià)生成樹(shù)

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

C、求最短路徑

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

10、分別采用直接插入和快速排序算法對(duì)下列四個(gè)序列進(jìn)行排序（由小到大）。使得直接插入排序時(shí)間最長(zhǎng)的序列是（ ），使得快速排序時(shí)間最短的序列是（ ） 。

A、 10，20，30，40，50，60，70

B、 70，60，50，40，30，20，10

C、 40，10，30，20，60，50，70

D、 40，20，10，30，50，70，60