2002年1月福建自考数据结构真题02331

福建省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)