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

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

1、現(xiàn)實(shí)生活中具有譜系結(jié)構(gòu)的數(shù)據(jù)，在計(jì)算機(jī)中處理時(shí)一般采用（ ）結(jié)構(gòu)表示。

A、線性

B、樹

C、圖

D、集合

2、設(shè)后綴表達(dá)式為：“43*293/+2-/”，式中，每個(gè)操作數(shù)均為一位整數(shù)，則表達(dá)式的值為（ ）。

A、6

B、4

C、8

D、A、B、C三者都不是

3、設(shè)二叉樹根結(jié)點(diǎn)的層次為1，在所有含135個(gè)結(jié)點(diǎn)的二叉樹中，最小高度是（ ）。

A、6

B、7

C、8

D、9

4、設(shè)A、X和Y是二叉樹B中的三個(gè)結(jié)點(diǎn)，X是A的左孩子，Y是X的左孩子。T是與B對應(yīng)的樹：在T中，A是Y的（ ）。

A、孩子

B、兄弟

C、雙親

D、祖先（非雙親）

5、下面哪一種結(jié)構(gòu)必定是完全二叉樹（ ）。

A、哈夫曼樹

B、二叉搜索樹

C、 AVL搜索樹

D、堆

6、在有序表（10，20，30，40，50，60，70，80，90）中以對半搜索法查找元素30和45時(shí)，所需的關(guān)鍵字值間的比較次數(shù)分別為（ ）。

A、3，3

B、3，4

C、4，4

D、A，B，C三者都不是

7、假定從無向圖G的任何一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索，都可以訪問圖中每個(gè)頂點(diǎn)，則該圖一定是（ ）。

A、連通圖

B、完全圖

C、有回路的圖

D、一棵樹

8、用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（ ）。

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

B、拓?fù)溆行?/p>

C、無序的

D、按關(guān)鍵字有序

9、初始序列經(jīng)第一趟排序后，不能確定任何一個(gè)元素最終位置的排序算法是（ ）。

A、兩路合并排序

B、冒泡排序

C、快速排序

D、簡單選擇排序

10、快速排序和冒泡排序的最壞情況時(shí)間復(fù)雜度分別為（ ）。

A、

B、

C、

D、