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

试卷总分:100  得分:100

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

1.在一个具有k个结点的无向图中，要连通全部结点至少需要（　）。

A.k条边

B.k+1条边

C.k-1条边

D.k/2条边

2.若一个栈的输入序列是1，2，3，……，m，输出序列的第一个元素是m，则第ｉ个输出元素是（　）。

A.m - i

B.m – i + 1

C.i

D.不确定

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

A.上溢出

B.下溢出

C.队满

D.假溢出

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

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

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

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

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

5.用冒泡排序的方法对n个数据进行排序，第一趟共比较（　）对元素。

A.1

B.2

C.n-1

D.n

6.线性表是（　）。

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

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

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

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

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

A.8

B.10

C.12

D.14

8.在一棵二叉树中，第5层上的结点数最多为（　）。

A.8

B.15

C.16

D.32

9.存储时，结点的地址（　）。

A.必须是连续的

B.必须是不连续的

C.连续与否均可

D.必须有相等的间隔

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

A.顺序表

B.链表

C.散列表

D.队列

11.在一个具有m个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（　）。

A.O（1）

B.O（m）

C.O（m2）

D.O（log2m）

12.使用折半查找，线性表必须（　）。

A.以顺序方式存储

B.以链式方式存储，且元素已按值排好序

C.以链式方式存储

D.以顺序方式存储，且元素已按值排好序

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

A.随机访问

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

C.插入删除时不需移动元素

D.所需的空间与线性表成正比

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

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

B.x = top - > data；

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

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

15.在一个单链表中，若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；

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

A.E

B.F

C.G

D.J

17.用冒泡排序的方法对n个数据进行排序，第一趟共比较（　）对元素。

A.１

B.２

C.n-1

D.n

18.栈是限定在（　）处进行插入或删除操作的线性表。

A.端点

B.栈底

C.栈顶

D.中间

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

A.顺序表

B.链表

C.散列表

D.队列

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

A.最短

B.最长

C.可变

D.不定