线性表练习

一、选择题 1.表长为n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为( )，删除一个元素需要移动的元素的个数为( ) A. (n-1)/2 B .n C.n+1 D.n-1 E. n/2 F.(n+1)/2 G.(n-2)/2 E A

2.线性表是具有n个( )的有限序列。 A.表元素 B.字符 C.数据元素 D.数据项 E.信息。 C

3. “线性表的逻辑顺序与存储顺序总是一致的。”这个结论是( )。 A.正确的 B.错误的 C.不一定，与具体的结构有关 B

D 4.线性表采用链式存储结构时，要求内存中可用存储单元的地址( )。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 4.线性表采用链式存储结构时，要求内存中可用存储单元的地址( )。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 D

B 5.带头结点的单链表为空的判定条件是( )。 A.head==NULL B.head->next==NULL 5.带头结点的单链表为空的判定条件是( )。 A.head==NULL B.head->next==NULL C.head->next=head D.head!=NULL B

A 6.不带头结点的单链表head为空的判定条件是( )。 A.head==NULL B.head->next==NULL C.head->next=head D.head!=NULL A

C 7.非空的循环单链表head的尾结点P满足（ ）。 A.p->next==NULL B.p==NULL C.p->next==head D.p==head C

B 8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。 A.O(1) B.O(n) C.O(n2) D.O(log2n) B

A 9.在一个单链表中，若删除p所指结点的后继结点，则执行（ ）。 A.p->next=p->next->next; B.p=p->next;p->next=p->next->next; C.p->next=p->next; D.p=p->next->next; A

B 10.在一个单链表中，若在p所指点结点之后插入s所指结点，则执行（ ） A.s->next=p;p->next=s; B.s->next=p->next; p->next=s; C.s->next=p->next;p=s; D.p->next=s;s->next=p; B

C 11.在一个单链表中，已知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

C q->rlink=p; q->llink=p->llink; p->llink=q; 12.假设双链表结点的类型如下： typedef struct linknode{ int data; //数据域 struct linknode *llink; //指向前趋结点的指针域 struct linknode *rlink; //指抽后继点的指针域 }bnode 现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（ ）。 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->llimk=p->rlink;q->rlink=p; p->link->rlink=q;p->llink=q; C

D 13.如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（ ） A．p->rlink=s;s->llink=p; p->rlink->llink=s;s->rlink=p->rlink; B. p->rlink=s;p->rlink->llink=s; s->llink=p;s->rlink=p->rlink; C. s->llink=p;s->rlink=p->rlink; p->rlink=s;p->rlink->llink=s; D. s->llink=p;s->rlink=p->rlink; p->rlink->llink=s;p->rlink=s; D

A ,C,D 14.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行 ( )操作与链表的长度无关。 B.删除单链表中最后一个元素 C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 A ,C,D

二、填空题 1.在线性结构中，第一个结点＿＿＿前趋结点，其余每个结点有且只有＿＿＿＿个前趋结点。 没有 1

2.在顺序表中插入或删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。 表中一半 该元素的位置

⑥③ ②⑨①⑦ 3.已知L是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现： (1)表首插入S结点的语句序列是＿＿＿＿。 (2)表尾插入S结点的语句序列是＿＿＿＿。 ①P->next=S; ②P=L; ③L=S; ④P->next=S->next; ⑤S->next=P->next; ⑥S->next=L; ⑦S->next=NULL; ⑧while(P->next!=Q) P=P->next; ⑨while(P->next!=NULL) P=P->next; ⑥③ ②⑨①⑦

⑧⑦②⑩ ⑧⑥④②⑩ 4.已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。 (1)删除首元结点的语句序列是＿＿＿＿。 (2)删除尾元结点的语句序列是＿＿＿＿。 ① P=P->next; ② P->next=P->next->next; ③ while(P!=NULL) P=P->next ④ while(Q->next!=NULL) { P=Q; Q=Q->next;} ⑤ while(P->next!=Q) P=P->next; ⑥ Q=P; ⑦ Q=P->next; ⑧ P=L; ⑨ L=L->next; ⑩free(Q); ⑧⑦②⑩ ⑧⑥④②⑩

5.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 ① P->next=P->next->next; ② P=P->next->next; ③ while(P->next!=Q) P=P->next; ④ while(P->next->next=Q) P=P->next; ⑤ Q=P; ⑥ Q=P->next; ⑦ P=L; ⑧ L=L->next; ⑨ free(Q); ⑥①⑨ ⑤⑦④①⑨

6.已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点 ，平均要访问＿＿＿＿个结点，从n个结点的双链表中查找一个结点，平均要访问＿＿＿＿个结点。

7.对于一个具有n个结点的问题单链表，在已知p所指结点后插入一个新结点的时间复杂度是＿＿＿＿；在值域为给定值的结点后插入一个新结点的时间复杂度是＿＿＿＿。 O(1) O(n)

8.单链表是＿＿＿＿的链接存储表示。 线性表

9.单链表中设置头结点的作用是 ＿＿＿＿。 插入和删除首元素时不必进行特殊处理

10.在单链表中，除首元结点外，任一结点的存储位置由＿＿＿＿指示。 其直接前趋结点的链域

q->prior=p; 11.在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p; p->next=q;＿＿＿＿； q->prior=p;

12.在双向链表中，每个结点有两个指针域，一个指向＿＿＿＿，另一个指向＿＿＿＿。 前趋结点 后继结点

13.顺序表中逻辑上相邻的元素的物理位置＿＿＿＿紧邻。单链表中逻辑上相邻的元素的物理位置＿＿＿＿紧邻。 必定 不一定

OK