2010年1月福建自考数据结构导论真题02142

全国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.以链接方式存储，且结点按关键字有序排列