全國2010年1月高等教育自學考試

數據結構導論試題

課程代碼：02142

一、單項選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.下述文件中適合于磁帶存儲的是（      ）

A.順序文件 B.索引文件

C.散列文件 D.多關鍵字文件

2.某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為（      ）

A.acbed B.becab

C.deabc D.cedba

3.含有n個結點的二叉樹用二叉鏈表表示時，空指針域個數為(      )

A.n-1 B.n

C.n+1 D.n+2

4.在一個圖中，所有頂點的度數之和與圖的邊數的比是(      )

A.1∶2 B.1∶1

C.2∶1 D.4∶1

5.長度為n的鏈隊列用單循環鏈表表示，若只設頭指針，則出隊操作的時間復雜度為(      )

A.O(1) B.O(1og₂n)

C.O(n) D.O(n²)

6.下述幾種排序方法中，要求內存量最大的是(      )

A.插入排序 B.快速排序

C.歸并排序 D.選擇排序

7.對n個不同值進行冒泡排序，在元素無序的情況下比較的次數為(      )

A.n-1 B.n

C.n+1 D.n(n-1)／2

8.對線性表進行二分查找時，要求線性表必須(      )

A.以順序方式存儲

B.以鏈式方式存儲

C.以順序方式存儲，且結點按關鍵字有序排列

D.以鏈接方式存儲，且結點按關鍵字有序排列