云南开放大学数据结构（C#语言）（21秋）形考作业4

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 100 分)

1.下列算法的时间复杂度是（　）。

for(i=1;i<=n;i+ +)

c[i]=i；

A.O（1）

B.O（n）

C.O（log2n）

D.O（nlog2n）

2.算法在发生非法操作时可以做出处理的特性称为（　）。

A.正确性

B.易读性

C.健壮性

D.高效性

3.链表具有的特点是（　）。

A.可随机访问任一元素

B.插入、删除需要移动元素

C.不必事先估计存储空间

D.存储空间是静态分配的

4.快速排序算法在最坏情况下的时间复杂度为（　）。

A.O（n）

B.O（n log2n）

C.O（n2）

D.O（log2n）

5.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，它指向该结点的（　）。

A.直接前趋

B.直接后继

C.开始结点

D.终端结点

6.循环队列是空队列的条件是（　）。

A.Q - > rear = = Q - > front

B.（Q - > rear + 1）%maxsize = = Q - > front

C.Q - > rear = = 0

D.Q - > front = = 0

7.循环队列的特点之一是不会产生（　）。

A.上溢出

B.下溢出

C.队满

D.假溢出

8.记录的关键字序列为（7，6，8，4，3，5），采用快速排序以第一个记录为基准得到的第一次划分结果是（　）。

A.（5，3，6，4，7，8）

B.（3，5，6，4，7，8）

C.（6，4，3，5，7，8）

D.（5，6，3，4，7，8）

9.快速排序在（　）情况下最易发挥其长处。

A.被排序的数据中含有多个相同排序码

B.被排序的数据已基本有序

C.被排序的数据完全无序

D.被排序的数据中的最大值和最小值相差悬殊

10.顺序查找法适合于存储结构为（　）的线性表。

A.散列存储

B.顺序存储或链接存储

C.压缩存储

D.索引存储

11.最小生成树的构造可使用（　）。

A.prim算法

B.冒泡算法

C.迪杰斯特拉算法

D.哈夫曼算法

12.堆的形状是一棵（　）。

A.二叉排序树

B.满二叉树

C.完全二叉树

D.平衡二叉树

13.哈夫曼树是访问叶结点的带权路径长度（　）的二叉树。

A.最短

B.最长

C.可变

D.不定

14.已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（　）。

A.E

B.F

C.G

D.J

15.对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（　）。

A.1，2，3

B.3，2，1

C.3，1，2

D.2，1，3

16.一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点的值，则执行（　）。

A.x = top；top = top - > next；

B.x = top；top = top - > next；

C.top = top - > next；x = top - > data；

D.x = top - > data；top = top - > next；

17.堆排序是一种（　）排序。

A.插入

B.选择

C.交换

D.归并

18.链栈与顺序栈相比，比较明显的优点是（　）。

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

19.下列陈述中正确的是（　）。

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

20.最小生成树指的是（　）。

A.由连通图所得到的边数最少的生成树

B.由连通图所得到的顶点相对较少的生成树

C.连通图的所有生成树中权值之和最小的生成树

D.连通图的极小连通子图