问答题(1994北京大学)

已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->rlink=q且q->llink=p),请写出删除q所指结点的程序段。

答案解析

p->rlink=q-rlink;
if(q->rllink!=null)
q->rlink->llink=p;
delete(q);

讨论

线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。【 】

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

双向链表的优势是____________________。

将下图所示的s所指点加到p所指点之后,其语句应为【 】

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】

试写出在双向链表da中的插入操作算法,算法中插入位置的获取可直接引入getnodep(da,i),其中参数da为双向链表,i是要插入的数据,要求算法中含有双向链表da的结点结构描述。

假设有两个按元素值递增有序排列的线性表A和B,均以带头结点的单链表作为存储结构,编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C,并要求利用原表(A表和B表)的结点空间存放表C。

线性表采用单循环链表存储的主要特点是【 】

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步:p->llink=q;p->rlink=q->rlink;q->rlink=p;第4步应该是____________________;(写出该步对应的语句)。

没有提供指针类型的语言,无法构造链式结构,该说法【 】