第2章 线性表

一、单选题 1．线性表是( ) 。

(A) 一个有限序列，可以为空 (B) 一个有限序列，不能为空 (C) 一个无限序列，可以为空 (D) 一个无序序列，不能为空 2．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 3．与顺序表相比，用链表实现线性表的优点是（ ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 4．线性表的静态链表结构与顺序存储结构相比优点是( )。 (A)所有的操作算法实现简单 (B)便于随机存取 (C)便于插入和删除 (D)便于利用零散的存储器空间 5．循环链表的主要优点是( ) 。 (A)不在需要头指针了

(B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 6．下面关于线性表的叙述错误的是( )。

(A) 线性表采用顺序存储，必须占用一片地址连续的单元 (B) 线性表采用顺序存储，便于进行插入和删除操作 (C) 线性表采用链式存储，不必占用一片地址连续的单元 (D) 线性表采用链式存储，不便于进行插入和删除操作； 7．假设双链表结点的类型如下： typedef struct linknode { int data ; //数据域

struct linknode *llink;//指向前趋结点的指针域 struct linknode *rlink;//指向后继结点的指针域

- 9 -

} bnode

现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是( )。

(A) q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q (B) p->llink=q;q->rlink=p；p->llink->rlink=q;q->llink=p->llink (C) q->llink=p->rlink;q->rlink=p;p->link->rlink=q;p->llink=q (D) 以上都不对

8. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： （A）110 （B）108 （C）100 （D）120

9. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是( ) （A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序 10. 链式存储结构所占存储空间（ ）

（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值

（C） 只有一部分，存储表示结点间关系的指针

（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数

11. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表

12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ） （A）n （B）2n-1 （C）2n （D）n-1

13． 线性表L在以下哪种情况下适用于使用链式结构实现（ ） （A）需经常修改L中的结点值 （B）需不断对L进行删除插入 （C）L中含有大量的结点 （D）L中结点结构复杂

14．在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行（ ）。

- 10 -

（A） p=q->next; p->next=q->next （B） p=q->next; q->next=p （C） p=q->next; q->next; q->next=q （D） q->next=q=->next->next; q->next=q;

15． 在非空双向循环链表中，在由q所指的结点后面插入一个由p所指的结点的过程是依次执行：p->Llink=q,p->Rlink=q->Rlink,q->Rlink=p，（ ）。(括号中应该填上一条赋值语句) （A） q->Llink=p （B） q->Rlink->Llink=p （C） p->Rlink->Llink=p （D） p->Llink->Llink=p

二、判断题

1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 7．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

8. 如果没有提供指针类型的语言，就无法构造链式结构。

9. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

10. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 11. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 13. 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。 14. 一个循环链表可以由所给定的头指针或者尾指针唯一确定。 三、填空题

1．线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结

- 11 -

点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.

2．线性表的顺序存储结构通过________来直接反映数据元素之间的逻辑关系，而链式存储结构则通过_______间接反映数据元素之间的逻辑关系。

3．线性表的常见链式存储结构有________、________和________。

4．对于长度为n的非空线性表，插入或者删除一个数据元素的操作的时间复杂度为_______。 5．在一个单链表中指针p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。

6．在一个单链表中删除指针p所指结点（若存在），则需要修改指针的操作是_______。 7．对于一个长度为n的非空顺序表，删除它的第i个数据元素时，需要移动_____个其他数据元素。

8．在以H为头指针的带表头结点的单循环链表中，链表为空的条件为 。 9.在单链表中，每个结点包含有两个域，一个叫 域，另一个叫 域。

10.在下面数组a中存储着一个静态链表，表头指针为a[0].next，则该线性表为 。

a

0

1

2

3

4

5 6

7

8

data next 4 60 56 42 38 3 7 6 2 74 25 0 1 11．一元多项式f(x) =9x10-3x7+6x-5的单链表表示是____________。 四、解答题

1．何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2．简述带头结点和不带头结点的单链表的区别。

3．说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入操作和删除操作各自移动数据元素的方向？

4．在单链表和双向链表中，能否从当前结点出发访问到任一结点？ 5. 设有多项式

A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8

(1) 用单链表给出A(x)的存储表示。（画出单链表示意图） (2) 用单链表给出B(x)的存储表示。（画出单链表示意图）

- 12 -