数据库结构与算法作业,高分50+50,请高手忙

Question

1. 非空的循环单链表head的尾节点（由p所指向）满足（）。
A. p->next=NULL
B. p=NULL
C. p->next=head
D. p=head

2. 设一数组的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。
A. 3,2,5,6,4,1
B. 1,5,4,6,2,3
C. 2,4,3,5,1,6
D. 4,5,3,6,2,1

3. 线性表是（）。
A. 一个有限序列，可以为空
B. 一个有限序列，不能为空
C. 一个无限序列，可以为空
D. 一个无限序列，不能为空

4. 完成堆排序的全过程需要( )个纪录大小的辅助空间。
A. 1
B. n
C. nlog2n
D. |nlog2n|

5. 对n个记录的文件进行堆排序，最坏情况下的执行时间为( )。
A. O(log2n)
B. O(nlogn)
C. O(n)
D. O(n2)

6. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用()存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表

7. 一个有n个顶点的无向图最多有（）条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n

8. 一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（）。
A. 128
B. 127
C. 126
D. 255

9. 以下数据结构中不属于线性数据结构的是（）。
A. 线性表
B. 队列
C. 二叉树
D. 栈

10. 顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储

11. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左二叉树和右二叉树
D. 各结点只有一个儿子的二叉树

12. 用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15。，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（）。
A. 选择排序
B. Shell排序
C. 归并排序
D. 快速排序

13. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。 在第一趟划分过程中，元素移动次数最多的序列是 ()。
A. 82，75，70，16，10，90，68，23
B. 23，10，16，70，82，75，68，90
C. 70，75，68，23，10，16，90，82
D. 70，75，82，90，23，16，10，68

14. 数据的存储结构包括顺序、链接、散列和（）四种基本类型。
A. 线性
B. 数组
C. 集合
D. 索引

15. 在一个循环队列中，队首指针指向队首元素的( )位置。
A. 后一个
B. 前一个
C. 当前
D. 以上都不是

16. 组成数据的基本单位是（）。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量

17. n个顶点的连通图至少有（）条边。
A. n-1
B. n
C. n+1
D. 0

18. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为()。
A. 10，15，14，18，20，36，40，21
B. 10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，21
D. 15，10，14，18，20，36，40，21

19. 下列数据结构中，能用二分法进行查找的是()。
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表

20. 设单链表中指针P指着结点A ，若要删除A之后结点（若存在），则需要修改指针的操作为（）。
A. p->next=p->next->next
B. p=p->next
C. p=p->next->next
D. P->next=p

Answer 1

1a 2b 3a 4a 5 nlog2 n
6c 7c 8b 9c 10b
11c 12d 13c 14d 15c
16c 17a 18a 19a a

Answer 2

1 c
2 b
3 a
4 a
5 a
6 c
7 c
8 a
9 c
10 a
11 c
12 a
13 d
14 c
15 b
16 c
17 a
18 a
19 a
20 a

Answer 3

1 c