填空题(1998北京邮电大学)

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

答案解析

EA

【解析】

插入一个元素所需移动元素的平均个数:

插入一个元素所需移动元素的平均个数:

讨论

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

下列描述中,正确的是【 】

双向链表的优势是____________________。

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

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

函数 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)__; }}

试写出在双向链表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步应该是____________________;(写出该步对应的语句)。