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

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

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

A、線性

B、樹

C、圖

D、集合

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

A、6

B、4

C、8

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

3、設二叉樹根結點的層次為1，在所有含135個結點的二叉樹中，最小高度是（ ）。

A、6

B、7

C、8

D、9

4、設A、X和Y是二叉樹B中的三個結點，X是A的左孩子，Y是X的左孩子。T是與B對應的樹：在T中，A是Y的（ ）。

A、孩子

B、兄弟

C、雙親

D、祖先（非雙親）

5、下面哪一種結構必定是完全二叉樹（ ）。

A、哈夫曼樹

B、二叉搜索樹

C、 AVL搜索樹

D、堆

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

A、3，3

B、3，4

C、4，4

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

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

A、連通圖

B、完全圖

C、有回路的圖

D、一棵樹

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

A、逆拓撲有序

B、拓撲有序

C、無序的

D、按關鍵字有序

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

A、兩路合并排序

B、冒泡排序

C、快速排序

D、簡單選擇排序

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

A、

B、

C、

D、