北语20春《数据结构》作业2【标准答案】

20春《数据结构》作业2

试卷总分:100  得分:100

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

1.{图}

A.D

B.C

C.B

D.A

2.设数据结果A=(D,R)，其中D={1,2,3,4}，R={r}，r={<1,2>，<2,3>，<3,4>，<4,1>}，则数据结构A是___。

A.集合

B.线性结构

C.树型结构

D.图型结构

3.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，___次比较后查找成功。

A.8

B.5

C.4

D.11

4.线性表的链式存储结构是一种___。

A.顺序存取的存储结构

B.随机存取的存储结构

C.索引存取的存储结构

D.Hash存取的存储结构

5.若已知一个栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若p1=n，则pi为___。

A.不确定

B.n-i+1

C.n-i

D.i

6.栈的插入和删除操作在___进行。

A.栈顶

B.栈底

C.指定位置

D.任意位置

7.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为___。

A.7

B.6

C.5

D.4

8.深度为5的二叉树至多有___个结点。

A.32

B.31

C.16

D.10

9.

A.D

B.C

C.B

D.A

10.对一个满二叉树，m个叶子，n个结点，深度为h，则___。

A.n=h+m

B.n=2h-1

C.m=h-1

D.h+m=2n

11.

A.D

B.C

C.B

D.A

12.算法分析的两个主要方面是___。

A.空间复杂度和时间复杂度

B.正确性和简明性

C.数据复杂性和程序复杂性

D.可读性和文档性

13.下列关于数据结构基本概念的叙述中，正确的是______。

A.结点是有独立含义的数据最小单位

B.数据的逻辑结构分为表结构和树结构

C.数据的存储结构分为线性结构和非线性结构

D.数据元素是数据的基本单位

14.

A.D

B.C

C.B

D.A

15.在长度为n的顺表表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为___。

A.n-i+1

B.n-i

C.i-1

D.i

16.广义表（（a），a）的表头是___。

A.a

B.(a)

C.()

D.((a))

17.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用___。

A.非循环双链表

B.循环双链表

C.只有表尾指针没有表头指针的循环单链表

D.只有表头指针没有表尾指针的循环单链表

18.数组的逻辑结构不同于下列___的逻辑结构。

A.队列

B.线性表

C.树

D.栈

19.

A.D

B.C

C.B

D.A

20.线性表采用链式存储时，结点的存储地址___。

A.连续与否均可

B.必须是连续的

C.必须是不连续的

D.和头结点的存储地址相连续