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

试卷总分:100  得分:100

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

1.在待排关键字序列基本有序的前提下，效率最高的排序方法是

A.直接插入排序

B.快速排序

C.直接选择排序

D.归并排序

 

2.一个具有1025个结点的二叉树的高h为

A.11

B.10

C.11至1025之间

D.10至1024之间

 

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

A.1.0

B.2.9

C.3.4

D.5.5

 

4.一棵树高为K的完全二叉树至少的结点是

A.2k –1

B.2k-1 –1

C.2k-1

D.2k

 

5.在线性表的下列运算中，不改变数据元素之间结构关系的运算是

A.插入

B.删除

C.排序

D.查找

 

6.有关二叉树下列说法正确的是

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

 

7.若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向

A.各自的头结点

B.各自的尾结点

C.各自的第一个元素结点

D.一个表的头结点，另一个表的尾结点

 

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

A.O（log2n）

B.O（1）

C.O（n）

D.O（n*log2n）

 

9.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为

A.数组的元素处在行和列两个关系中

B.数组的元素必须从左到右顺序排列

C.数组的元素之间存在次序关系

D.数组是多维结构，内存是一维结构

 

10.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为

A.O(1)

B.O(logn)

C.O(n)

D.O(n logn)

 

11.在一个单链表中，若删除*p结点的后继结点，则执行操作

A.q=p->next;p->next=q->next;free(q);

B.p=p->next;p->next=p->next->next;free(p);

C.p->next=q->next;free(p->next);

D.p=p->next->next;free(p->next);

 

12.为便于判别有向图中是否存在回路，可借助于

A.广度优先搜索算法

B.最小生成树算法

C.最短路径算法

D.拓扑排序算法

 

13.连通图是指图中任意两个顶点之间

A.都连通的无向图

B.都不连通的无向图

C.都连通的有向图

D.都不连通的有向图

 

14.能进行二分查找的线性表,必须以

A.顺序方式存储,且元素按关键字有序

B.链式方式存储,且元素按关键字有序

C.顺序方式存储,且元素按关键字分块有序

D.链式方式存储,且元素按关键字分块有序

 

15.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是

A.A[8，5]

B.A[3，10]

C.A[5，8]

D.A[0，9]

 

16.下面的说法中正确的是

    (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。

    (2)按二叉树定义，具有三个节点的二叉树共有6种。

A.(1)，(2)

B.(1)

C.(2)

D.(1)，(2)都错

 

17.以下与数据的存储结构无关的术语是

A.循环队列

B.链表

C.哈希表

D.栈

 

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

A.深度优先搜索算法

B.广度优先搜索算法

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

D.拓扑排序算法

 

19.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为

A.O(0)

B.O(1)

C.O(n)

D.O(n2)

 

20.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是

A.O(1)

B.O(n)

C.O(nlogn)

D.O(n2)

奥鹏，国开，广开，电大在线，各省平台，新疆一体化等平台学习
详情请咨询QQ：3494317897  微信：aopy98