第二章练习题

则执行（
）。
Ａ、s->next=p;p->next=s; Ｂ、s->next=p->next;p->next=s;
Ｃ、s->next=p->next;p=s; Ｄ、p->next=s;s->next=p;
11、在一个单链表中，已知 q 是 p 的前趋结点，若 q 和 p 之
间插入结点 s，则执行（
）。
} }
2、 status ListInsert(SqList &L,ElemType e) {ElemType *p,*q,*newbase; int j; if(L.length>=L.listsize){ newbase=(ElemType )realloc(L.elem, (L.listsize+LISTINCRMENT)
D
二、填空题
1、 没有；1
2、 表中一半；该元素的位置
3、 （1）FC （2）BIAG
4、 （1）HGBJ （2）HFDBJ
5、 （1）FAI （2）EGDAI
6、 n/2, n/4
7、 O(1 )
O(n)
8、 线性表
9、 插入和删除首元素时不必进行特殊处理
10、 其直接前趋结点的链域 11、 q->prior=p; 12、 前趋结点，后继结点 13、 必定，不一定
9、在一个单链表中，若删除 P 所指结点的后继结点，则执行
（
）。
Ａ、p->next=p->next->next
Ｂ、p=p->next;p->next=p->next->next Ｃ、p->next=p->next;
Ｄ、p=p->next->next;
10、在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，
结点后插入一个新结点的时间复杂度是（
）。
8、单链表是（ ）的链接存储表示。
9、单链表中设置头结点的作用是（ ）。
10、在单链表中，除首元结点外，任一结点的存储位置由
（
）指示。
11、在非空双向循环链表中，在结点 q 的前面插入结点 p 的
过程如下：
p->prior=q->prior;
q->prior->next=p;p->next=q;(
三、简答题 1、 宜采用链式存储结构，因为它使线性表的插入和删除操
作的时间复杂度为 O（1），而顺序存储结构的为 O（n）。 2、 首元结点是指链表中存储线性表中第一个数据元素的
结点。为了操作方便，通常在链表的首元结点之前附设一 个结点，称为头结点，该结点的数据域中不存线性表的数 据元素，其作用是为了对链表进行操作时，可以对空表、 非空表的情况以及对首元结点进行统一的处理。头指针是 指向链表第一个结点（头结点或首元结点）的指针。若链 表中附设头结点，则不管线性表是否为空表，头指针均不 为空，否则表示空表的链表的头指针为空。这三个概念对 单链表、双向链表和循环链表均适用。 3、 在等概率前提下，平均每插入一个元素需要移动的元素 个数为(0+1+2+…+n)/(n+1)=n/2。若元素插在 ai 与 ai+1 之 间（0<=i<=n-1）的概率为 2(n-i)/(n(n+1))，则平均每插入一 个元素所要移动的元素个数为：（2n+1）/3 四、设计题 1、
之后插入结点 s 的操作序列是（
）。
Ａ、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;
Ｂ、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;
Ｃ、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s;
Ｄ、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;
14、在一个长度为 n 的单链表上，设有头和尾两个指针，执
行（
）操作与链表的长度无关。
Ａ、删除单链表中的第一个元素 Ｂ、删除单链表中最后
一个元素 Ｃ、在单链表第一个元素前插入一个新元素
A、表元素 B、字符 C、数据元素 D、数据项 E、
信息
3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是
（ ）。
A、正确的 B、错误的 C、不一定，与具体结构有关。
4、线性表采用链式存储结构时，要求内存中可用存储单元的
地址（ ）。
A、必须是连续的 B、部分地址必须是连续的 C、一定
是不连续的 D、连续或不连续都可以。
的语句序列。
（1）删除 P 结点的直接后继结点的语句序列是（
）
（2）删除 P 结点的直接前趋结点的语句序列是（
）
A、P->next=P->next->next; B、P=P->Pnext->next;
C、while(P->next!=Q)P=P->next;
D、while(P->next->next=Q)P=P->next; E、Q=P; F、Q=P->next; G、P=L;
L.elem[j+1]=e; ++L.length; return OK; }
3、提示：两个表的公共元素指的是既存在于 A 表中，也存 在于 B 表中的元素，为了操作方便，先让单链表 C 带有一个 头结点 c，再后将其删除。 LinkList Inter_eq(LinkList a,LinkList b) {LinkList p,q,r,c;
下列功能： （1） 找出最小值结点，且显示该数值。 （2） 若该数值为奇数，则将其与直接后继结点的数
值交换。 （3） 若为偶数，则将其直接后继结点删除。
参考答案：
一、选择题
1、E，A 2、C 3、B 4、D 5、B 6、A 7、C 8、
B 9、A 10、B 11、C 12、C 13、D 14、A，C，
（１）表首插入Ｓ结点的语句序列是（
）。
（２）表尾插入Ｓ结点的语句序列是（
）。
Ａ、Ｐ->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;
void split(SqList A,SqList &B,SqList &C) {//采用顺序存储结构实现
int I;B.length=C.length=0; for(I=0;I<AS.length;I++)
{if(A.elem[i]>0){B.elem[B.length]=A.elem[i];B.length++;} else {C.elem[C.length]=A.elem[i];C.length++;}
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)
struct linknode *llink; ／／指向前趋结点的指针域
struct linknode *rlink; ／／指向后继结点的指针域
}bnode
现将一个 q 所指新结点作为非空双向链表中的 p 所指结点
的前趋结点插入到该双链表中，能正确完成此要求的语句段
是（
）。
Ａ、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;
第二章练习题
一、 选择题
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
2、线性表是具有 N 个（ ）的有限序列。
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
D、while(Q->next!=NULL){P=Q;Q=Q->next;}
E、while(P->next!=Q)P=P->next;
F、Q=P; G、Q=P->next; H、P=L; I、L=L->next;
J、free(Q);
5、已知 L 是带表头结点的非空链表，且 P 结点既不是首元