填空题(2012北京工业大学)

双向链表的优势是____________________。

答案解析

查找结点的前驱;在表尾插入、删除操作

【解析】

和单链表相比,双向链表更便于查找结点的前驱、后继,便于在表尾的插入、删除操作

讨论

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

将长度为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步应该是____________________;(写出该步对应的语句)。

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

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成,已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。例如,某单链表如图所示,逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下:typedef struct Node{ int data, struct Node *next;}Node, *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置, headptr为头指针 LinkList p,s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}