数据结构-作业3

参考教材：数据结构教程（Java语言描述)        作者：李春葆

1 . 容易 （4分）空的线性表就是所有元素尚未赋值的线性表。

错误

空的线性表就是长度为0的线性表。

2 . 容易 （4分）在一个含有n（n≥1）个元素的线性表中，所有元素值不能相同。

错误

在线性表中允许存在元素值相同的元素，但它们的位置是不同。

3 . 容易 （4分）线性表中每个元素都有一个前趋元素和一个后继元素。

错误

开始元素没有前趋元素，终端元素没有后继元素。

4 . 容易 （4分）线性表的长度是线性表占用的存储空间的大小。

错误

线性表的长度是指表中元素个数，属逻辑结构的概念，与线性表占用的存储空间大小无关。

5 . 容易 （4分）线性表的存储结构大小与线性表中元素类型有关。

正确

线性表的存储结构大小等于线性表中所有元素存储空间之和，而线性表中元素类型不同，每个元素所占用的存储空间大小也可能不同。

6 . 容易 （4分）线性表中的结点按前趋、后继关系可以排成一个线性序列。

正确

线性表是有限个相同性质的元素的序列。

7 . 容易 （4分）线性表是具有n个（）的有限序列。

A. 表元素

B. 字符

C. 数据元素

D. 数据项

线性表是具有n（n≥0）个数据元素的有限序列，本题答案为C。

8 . 容易 （4分）线性表是（） 。

A. 一个有限序列，可以为空

B. 一个有限序列，不可以为空

C. 一个无限序列，可以为空

D. 一个无限序列，不可以为空

线性表的定义有三点，即所有元素类型相同、元素个数有限、元素之间为线性关系（序列是指线性关系），另外线性表中元素个数可以为0，即空表。

9 . 容易 （4分）线性表有一个特点（） 。

A. 至少有两个元素，即开始元素和终端元素

B. 若没有开始元素，则一定没有终端元素

C. 每个元素必须有一个前趋元素

D. 任何一个元素都还可能既是开始元素又是终端元素

线性表可以是空表，此时既没有开始元素也没有终端元素。

10 . 容易 （4分）关于线性表的正确说法是（） 。

A. 每个元素都有一个前趋和一个后继元素

B. 线性表中至少有一个元素

C. 表中元素的排序顺序必须是由小到大或由大到小

D. 除第一个元素和最后一个元素外，其余每个元素有且仅有一个前趋和一个后继元素

线性表属典型的线性结构。

11 . 容易 （4分）有一个非空循环双链表，在结点p之后插入结点q的操作是q.next=p.next; p.next=q; q.prior=p; ______。

A. p.next=q;

B. q.prior.next=q;

C. q.next.prior=q;

D. q.next.next=q; 

12 . 容易 （4分）在长度为n的______ 上，删除尾结点的时间复杂度为O(1)。

A. 单链表

B. 双链表

C. 循环单链表

D. 循环双链表

13 . 容易 （4分）线性表的链式存储结构与顺序存储结构相比，优点是______。

A. 所有的操作算法实现简单

B. 便于随机存取

C. 便于插入和删除元素

D. 节省存储空间

14 . 容易 （4分）线性表采用链表存储时，存放所有存放元素的结点地址______。

A. 必须是连续的

B. 一定是不连续的

C. 部分地址必须是连续的

D. 连续与否均可以

15 . 容易 （4分）单链表的存储密度______。

A. 大于1

B. 等于1

C. 小于1

D. 不能确定

16 . 容易 （4分）对于单链表存储结构，以下说法中错误的是______。

A. 一个结点的数据成员用于存放线性表的一个数据元素

B. 一个结点的指针成员用于指向下一个数据元素的结点

C. 单链表必须带有头结点

D. 单链表中所有结点可以连续也可以不连续存放

17 . 容易 （3分）链表不具备的特点是______。

A. 可随机访问任一结点

B. 插入删除不需要移动结点

C. 不必事先估计存储空间

D. 所需空间与其长度成正比

18 . 容易 （3分）以下关于链表的叙述中，不正确的是______。

A. 结点中除元素值外还包括指针成员，因此存储密度小于顺序存储结构

B. 逻辑上相邻的元素物理上不必相邻

C. 可以根据头结点地址直接计算出第i个结点的地址

D. 插入、删除运算操作方便，不必移动结点

19 . 容易 （3分）若某线性表最常用的操作是查找序号i的元素和在末尾插入元素，则选择______存储结构最节省时间。

A. 顺序表

B. 带头结点的循环双链表

C. 单链表

D. 带尾结点的循环单链表

20 . 容易 （3分）将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数是______。

A. n

B. 2n-1

C. 2n

D. n-1

+ 3.0 分

21 . 容易 （3分）以下关于单链表的叙述中正确的是______。 Ⅰ.结点中除元素值外还包括指针成员，存储密度小于顺序表 Ⅱ.找第i个结点的时间为O(1) Ⅲ.在插入和删除操作时不必移动结点

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

22 . 容易 （3分）有一个长度为n（n>1）的带头结点的单链表h，另设有尾指针r（指向尾结点），执行______ 操作与链表的长度有关。

A. 删除单链表中的首结点

B. 删除单链表中的尾结点

C. 在单链表首结点前插入一个新结点

D. 在单链表尾结点素后插入一个新结点

23 . 容易 （3分）已知一个长度为n的单链表是递增有序的，所有结点值不相同，以下叙述中正确的是______。

A. 插入一个结点使之有序的算法的时间复杂度为O(1)

B. 删除最大值结点使之有序的算法的时间复杂度为O(1)

C. 找最小值结点的算法的时间复杂度为O(1)

D. 以上都不对

24 . 容易 （3分）知两个长度分别为m 和n 的递增单链表，若将它们合并为一个长度为m+n 的递减单链表，则最好情况下的时间复杂度是______。

A. O(n)

B. O(m)

C. O(m×n)

D. O(m+n)

25 . 容易 （3分）在一个双链表中，删除p结点（非尾结点）的操作是______。

A. p.prior.next=p.next; p.next.prior=p.prior;

B. p.prior=p.prior.prior; p.prior.prior=p;

C. p.next.prior=p; p.next=p.next.next;

D. p.next=p.prior.prior; p.prior=p.prior.prior; 

26 . 容易 （3分）在长度为n（n≥1）的双链表L中，在p结点之前插入一个新结点s的时间复杂度为______。

A. O(1)

B. O(n)

C. O(n2)

D. O(nlog2n)

27 . 容易 （3分）在长度为n（n≥1）的双链表中插入一个结点p（非尾结点）要修改______个指针成员。

A. 1

B. 2

C. 3

D. 4

28 . 容易 （3分）在长度为n（n≥1）的双链表中删除一个结点p（非尾结点）要修改______个指针成员。

A. 1

B. 2

C. 3

D. 4