东大22年春学期《数据结构ⅡX》在线平时作业1【标准答案】

试卷总分:100  得分:100

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

1.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为

A.n-1

B.n

C.n+l

D.2n

2.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于

A.1.0

B.2.9

C.3.4

D.5.5

3.对长度为n的关键字序列进行堆排序的空间复杂度为

A.O（log2n）

B.O（1）

C.O（n）

D.O（n*log2n）

4.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为

A..(v0，v1，v2，v5，v4，v3)

B.(v0，v1，v2，v3，v4，v5)

C.(v0，v1，v5，v2，v3，v4)

D..(v0，v1，v4，v5，v2，v3)

5.n个顶点的有向完全图中含有向边的数目最多为

A.n-1

B.n

C.n(n-1)/2

D.n(n-1)

6.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用

A.数据元素的相邻地址表示

B.数据元素在表中的序号表示

C.指向后继元素的指针表示

D.数据元素的值表示

7.倒排文件的主要优点是

A.便于进行插入和删除运算

B.便于进行文件的恢复

C.便于进行多关键字查询

D.节省存储空间

8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为

A.DEBAFC

B.DEFBCA

C.DEBCFA

D.DEBFCA

9.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是

A.1234

B.4132

C.4231

D.4213

10.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为

A.5

B.6

C.16

D.17

11.一棵具有 n个结点的完全二叉树的树高度（深度）是

A.ëlognû+1

B.logn+1

C.ëlognû

D.logn-1

12.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

13.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是

A.head(tail(LS))

B.tail(head(LS))

C.head(tail(head(tail(LS))))

D.head(tail(tail(head(LS))))

14.稠密索引是在索引表中

A.为每个记录建立一个索引项

B.为每个页块建立一个索引项

C.为每组记录建立一个索引项

D.为每个字段建立一个索引项

15.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用

A.深度优先搜索算法

B.广度优先搜索算法

C.求最小生成树的prim算法

D.拓扑排序算法

16.下述哪一条是顺序存储结构的优点

A.存储密度大

B.插入运算方便

C.删除运算方便

D.可方便地用于各种逻辑结构的存储表示

17.判定“带头结点的链队列为空”的条件是

A.Q.front==NULL

B.Q.rear==NULL

C.Q.front==Q.rear

D.Q.front!=Q.rear

18.下列数据结构中，属于非线性数据结构的是

A.栈

B.队列

C.完全二叉树

D.堆

19.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为

A.470

B.471

C.472

D.473

20.一棵完全二叉树上有1001个结点，其中叶子结点的个数是

A.250

B.500

C.254

D.以上答案都不对