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

试卷总分:100  得分:100

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

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

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

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

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

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

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

A.E

B.F

C.G

D.J

3.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（　）。

A.索引存储方法

B.顺序存储方法

C.链式存储方法

D.散列存储方法

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

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

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

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

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

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

A.m - i

B.m – i + 1

C.i

D.不确定

6.一个记录的关键字为（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）

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

A.二叉排序树

B.满二叉树

C.完全二叉树

D.平衡二叉树

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

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

c[i]=i；

A.O（1）

B.O（n）

C.O（log2n）

D.O（nlog2n）

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

A.插入

B.选择

C.交换

D.归并

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

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

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

A.k条边

B.k+1条边

C.k-1条边

D.k/2条边

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

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

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

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

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

13.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经（　）次比较后查找成功。

A.2

B.3

C.4

D.12

14.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（　）。

A.索引存储方法

B.顺序存储方法

C.链式存储方法

D.散列存储方法

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

A.散列存储

B.顺序存储或链接存储

C.压缩存储

D.索引存储

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

A.插入

B.选择

C.交换

D.归并

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

A.顺序表

B.链表

C.散列表

D.队列

18.以下关于数据的逻辑结构的叙述正确的是（　）。

A.数据的逻辑结构是数据间关系的描述

B.数据的逻辑结构反映了数据在计算机中的存储方式

C.数据的逻辑结构分为顺序结构和链式结构

D.数据的逻辑结构分为静态结构和动态结构

19.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（　）。

A.99

B.98

C.48

D.50

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

A.8

B.15

C.16

D.32