《数据结构Ⅱ》在线平时作业2-00001

试卷总分:100  得分:100

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

1.上溢现象通常出现在

A.顺序栈的入栈操作过程中

B.顺序栈的出栈操作过程中

C.链栈的入栈操作过程中

D.链栈的出栈操作过程中

2.希尔排序的增量序列必须是

A.递增的

B.随机的

C.递减的

D.非递减的

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

A.n-1

B.n

C.n(n-1)/2

D.n(n-1)

4.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

A.A，B，C，D

B.D，C，B，A

C.A，C，D，B

D.D，A，B，C

5.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是

A.访问第i个元素的前驱

B.在第i个元素之后插入一个新元素

C.删除第i个元素

D.对顺序表中元素进行排序

6.算法分析的目的是

A.辨别数据结构的合理性

B.评价算法的效率

C.研究算法中输入与输出的关系

D.鉴别算法的可读性

7.引起循环队列队头位置发生变化的操作是

A.出队

B.入队

C.取队头元素

D.取队尾元素

8.若要在单链表中的结点p之后插入一个结点s，则应执行的语句是

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

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

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

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

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

A.都连通的无向图

B.都不连通的无向图

C.都连通的有向图

D.都不连通的有向图

10.二叉树中第5层上的结点个数最多为

A.8

B.15

C.16

D.32

11.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是

A.p=p->next;

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

C.p->next=p;

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

12.下列序列中，不构成堆的是

A.（1，2，5，3，4，6，7，8，9，10）

B.（10，5，8，4，2，6，7，1，3）

C.（10，9，8，7，3，5，4，6，2）

D.（1，2，3，4，10，9，8，7，6，5）

13.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为

A.n-1

B.ën/mû-1

C.é(n-1)/(m-1)ù

D.én/(m-1)ù-1

14.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是

A.不确定

B.0

C.1

D.2

15.对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为

A.（1，2，3，4，5，6，7，8）

B.（1，4，3，2，5，7，8，6）

C.（2，1，4，3，5，7，8，6）

D.（8，7，6，5，4，3，2，1）

16.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是

A.0

B.1

C.2

D.3

17.采用ISAM或VSAM组织的文件是

A.索引非顺序文件

B.顺序文件

C.索引顺序文件

D.散列文件

18.一个有向无环图的拓扑排序序列是

A.一定唯一的

B.一定不唯一的

C.不一定唯一的

D.都不对

19.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为

A.21

B.23

C.41

D.62

20.导致栈上溢的操作是

A.栈满时执行的出栈

B.栈满时执行的入栈

C.栈空时执行的出栈

D.栈空时执行的入栈