浙江省2002年1月高等教育自學考試

數據結構試題

課程代碼：02331

一、單項選擇題(在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內。每小題2分，共38分)

1.某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是(     )的二叉樹。

  A.空或只有一個結點     B.高度等于其結點數

  C.任一結點無左孩子     D.任一結點無右孩子

2.下列排序算法中，時間復雜度不受數據初始狀態影響，恒為O(log₂n)的是(     )

  A.堆排序       B.冒泡排序

  C.直接選擇排序      D.快速排序

3.下列排序算法中，(     )算法可能會出現下面情況：初始數據有序時，花費的時間反而最多。

  A.堆排序       B.冒泡排序

  C.快速排序       D.SHELL排序

4.一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是(     )

  A. 2 3 4 1 5       B. 5 4 1 3 2

  C. 2 3 1 4 5       D. 1 5 4 3 2

5.設循環隊列中數組的下標范圍是1～n，其頭尾指針分別為f和r，則其元素個數為(      )

  A. r-f        B. r-f+1

  C. (r-f)  mod n+1     D. (r-f+n)  mod n

6.若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用(     )存儲方式最節省時間。

  A.單鏈表       B.雙鏈表

  C.帶頭結點的雙循環鏈表    D.單循環鏈表

7.在有n個結點的二叉鏈表中，值為非空的鏈域的個數為(     )

  A. n-1        B. 2n-1

  C. n+1        D. 2n+1

8.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數為(     )

  A. 0        B. 1

  C. 2        D.不確定

9.數組A［５］［６］的每個元素占5個單元，將其按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A［５，５］的地址為(     )

  A. 1140       B. 1145

  C. 1120       D. 1125

10.求最短路徑的DIJKSTRA算法的時間復雜度為(     )

  A. O(n)       B. O(n+e)

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

11.對有18個元素的有序表作二分查找，則查找A［3］的比較序列的下標依次為(      )

  A. 1，2，3       B. 9，5，2，3

  C. 9，5，3       D. 9，4，2，3

12.快速排序算法在最好情況下的時間復雜度為(     )

  A. O(n)       B. O(nlog₂n)

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