线性表练习题答案

WORD格式

一、 判断题

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

3 ．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE）

4．线性表中的元素可以是各种各样的， 但同一线性表中的数据元素具有相同的特

性，

此是属于同一数据对象。 （TRUE）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （ FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 （TRUE） 7．线性表的链式存储结构优于顺序存储结构。 （FALSE）

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 （ TRUE）

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 （TRUE） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE）

因

二、 单选题、 (请从下列A，B，C，D选项中选择一项 11．线性表是()。

)

(A) 一个有限序列，可以为空；(B)一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D)一个无序序列，不能为空。 答：A

12．对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（ (A)n/2(B)(n+1)/2(C)(n –1)/2(D)n 答：A

13．线性表采用链式存储时，其地址 (D) 。 (A) 必须是连续的；(B)部分地址必须是连续的； (C) 一定是不连续的；(D)连续与否均可以。 答：D

14．用链表表示线性表的优点是 （）。 (A)便于随机存取 (B) (C)

花费的存储空间较顺序存储少 便于插入和删除

）个元素。

(D)数据元素的物理顺序与逻辑顺序相同答：C

15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()存储方式最节省运算时间。 (A)单链表 (B) (C)

双链表 单循环链表

专业资料整理

WORD格式

(D)带头结点的双循环链表答：D

16.循环链表的主要优点是()。 (A)不再需要头指针了 (B) (C)

已知某个结点的位置后，能够容易找到他的直接前趋 在进行插入、删除运算时，能更好的保证链表不断开

(D)从表中的任意结点出发都能扫描到整个链表 答：D

18.单链表中，增加一个头结点的目的是为了（

）。

(A) 使单链表至少有一个结点(B)标识表结点中首结点的位置（C）方便运算的实现(D)说明单链表是线性表的链式存储答：

C

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

20.若某线性表中最常用的操作是取第

存储方式最节省运算时间（ B）。 (A) 单链(B)顺序表

表

(C) 双链表(D)单循环链表 答：B

i个元素和找第

i个元素的前趋元素，则采用（

）

21. 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是 _______。 A.110B.108 C.100D.120 答：B

[第5个元素的地址=100+2*(5-1)=108]

22. 不带头结点的单链表head为空的判定条件是______。 A.head==NULL;B.head->next==NULL; C.head->next==head;D.head!=NULL; 答：A

23. 带头结点的单链表head为空的判定条件是______。 A.head==NULL;B.head->next==NULL; C.head->next==head;D.head!=NULL; 答：B

24.在循环双链表的 p所指结点之后插入 s所指结点的操作是 _____。 A.p->right=s;s->left=p;p->right->left=s;s=->right=p->right; B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

专业资料整理

WORD格式

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

专业资料整理

WORD格式

D.s->left=p;s->right=p->right;p->right->left=s;p->right=s; 答：D

25.在一个单链表中， 已知

q所指结点是

p所指结点的前驱结点， 若q和 p之间插

在 入

s

结点，则执行 ______。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;答：C

26.从一个具有 n个结点的单链表中查找其值等于 x结点时，在查找成功的情况下，需 平均比较_____个结点。(参见网上讲义： 1.4.2例1_5) A.n;B.n/2;

C.(n-1)/2;D.(n+1)/2; 答：D

27.给定有n个结点的向量，建立一个有序单链表的时间复杂度

_______。

2

A.O(1);B.O(n ); C.O(n);D.O(nlogn); 答：C

四、算法设计题：

31. 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。

提示：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加 1，结点个数存储在变量 n中。 intcount(head,x) {

/*本题中head为链头指针，不含头结*/

点 node*p; intn=0; p=head; while(p!=NULL) {

if(p->data==x)n++; p=p->next; }

return(n); }

专业资料整理