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

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

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

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

B、帶表頭的單鏈表

C、雙向鏈表

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

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

A、O(0)

B、O(1)

C、O(n)

D、O(n²)

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

A、m1

B、m1+m2

C、m3

D、m2+m3

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

A、堆

B、哈夫曼樹

C、AVL樹

D、二叉搜索樹

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

A、3

B、2

C、4

D、6

6、在線性表中采用對半搜索方法搜索元素，該線性表應為（ ）。

A、有序表且順序存儲

B、有序表且鏈接存儲

C、無序表且順序存儲

D、無序表且鏈接存儲

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

A、拉鏈法

B、線性探查法

C、偽隨機探查法

D、雙散列法

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

A、O(n*e)

B、O(n+e)

C、O(e)

D、O(n²)

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

A、求最小代價生成樹

B、拓撲排序

C、求最短路徑

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

10、分別采用直接插入和快速排序算法對下列四個序列進行排序（由小到大）。使得直接插入排序時間最長的序列是（ ），使得快速排序時間最短的序列是（ ） 。

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