全国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(1og2n)

　　C.O(n) D.O(n2)

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