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

试卷总分:100  得分:100

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

1.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（　）。

A.e，d，c，b，a

B.d，e，c，b，a

C.d，c，e，a，b

D.a，b，c，d，e

2.在查找过程中，若同时还要做增、删工作，这种查找则称为（　）。

A.静态查找

B.动态查找

C.内查找

D.外查找

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

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

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

A.散列存储

B.顺序存储或链接存储

C.压缩存储

D.索引存储

5.在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（　）。

A.s->next=p->next;p->next=s;

B.q->next=s;s->next=p;

C.p->next=s->next;s->next=p;

D.p->next=s;s->next=q;

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

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

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

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

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

7.若用冒泡排序对关键字序列｛18，16，14，12，10，8｝进行从小到大的排序，所需进行的关键字比较总次数是（　）。

A.10

B.15

C.21

D.34

8.一个记录的关键字为（46，79，56，38，40，84），采用快速排序以第一个记录为基准得到的第一次划分结果是（　）。

A.（40，46，56，38，79，84）

B.（40，38，46，79，56，84）

C.（40，38，46，56，79，84）

D.（84，40，38，46，56，79）

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

A.插入

B.选择

C.交换

D.归并

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

A.O（n）

B.O（n log2n）

C.O（）

D.O（log2n）

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

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

c[i]=i；

A.O（1）

B.O（n）

C.O（log2n）

D.O（nlog2n）

12.在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（　）。

A.s->next=p->next;p->next=s;

B.q->next=s;s->next=p;

C.p->next=s->next;s->next=p;

D.p->next=s;s->next=q;

13.在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（　）。

A.S->next=P->next；P->next=S；

B.P->next=S->next；S->next=P；

C.P->next=P；P->next=S；

D.P->next=S；S->next=P；

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

A.正确性

B.易读性

C.健壮性

D.高效性

15.线性表是（　）。

A.一个有限序列，可以为空

B.一个有限序列，不能为空

C.一个无限序列，可以为空

D.一个无限序列，不能为空

16.图的广度优先搜索遍历类似于树的（　）。

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

17.具有m个结点的无向图的边数最多为（　）。

A.m+1

B.m（m-1）/2

C.m（m+1）

D.2m（m+1）

18.由4个结点构造出的不同的二叉树个数共有（　）。

A.8

B.10

C.12

D.14

19.以下哪一个术语与数据的存储结构无关？（　）。

A.顺序表

B.链表

C.散列表

D.队列

20.对n个不同的排序码进行冒泡排序，在元素无序情况下的比较次数为（　）。

A.n + 1

B.n

C.n - 1

D.n（n - 1）/2