第2章 线性表

一、 选择题

1. 表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均

次数为（ e ），删除一个元素需要移动的元素个数为（ a ）。【＊＊，★】

A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2

2. 线性表是具有N 个（ ）的有限序列。【＊】

A、表元素 B、字符 C、数据元素 D、数据项 E、信息

3. “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。【＊】

A、正确的 B、错误的 C、不一定，与具体结构有关。

4. 线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。【＊，★】

A、必须是连续的 B、部分地址必须是连续的

C、一定是不连续的 D、连续或不连续都可以。

5. 带头结点的单链表为空的判定条件是（ ）。【＊】

A、head==NULL B、head->next==NULL

C、head->next==head D、head!=NULL

6. 不带头结点的单链表head 为空的判定条件是（ ）。【＊】

A、head==NULL B、head->next==NULL

C、head->next==head D、head!=NULL

7. 非空的循环单链表head 的尾结点P 满足（ ）。【＊】

A、P->NEXT=NULL B、p=NULL

C、p->next==head D、p==head

8. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。【＊，★】

A、O(1) B、O(n) C、O(n2) D、O(nlog2n)

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;

10. 在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（ ）。【＊，★】

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;

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;

12. 假设双链表结点的类型如下：【＊＊，★】

typedef struct linknode{

int data; //数据域

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

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

}bnode;

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

A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;