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

将长度为n的单向链表链接在长度为m的单向链表之后的算法的时间复杂性为( )。【哈尔滨工业大学2005二、1(1分)】

A．O(1)

B．O(n)

C．O(m)

D．O(m+n)

假设某个不设头指针的无头结点单向循环链表的长度大于1，S为指向链表中某个结点的指针。算法f30的功能是，删除并返回链表中指针S所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。

typedef struct node{

DataType data;

struct node *next;

}*LinkList;

DataType f 30(LinkList s){

LinkList pre,p;

DataType e;

pre=s;

p=s—＞next;

while( (1) ){

pre=p;

(2) ；

}

pre—＞next= (3) ;

e=p—＞data;

free(p);

return e;

}

已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

下面程序中函数creat用于建立一个带头结点的单向链表，新产生的结点总是插在链表的末尾，单向链表的头指针作为函数值返回。将程序补充完整。 include＜stdiao.h＞ struct list {char data; struct list * next;}； struct list * creat() { struct list *h，*p，*q; char ch； h＝【 】malloc(sizeof(struct list)); p=q=h；ch=getchar(); while(ch!＝?) { p＝【 】malloc(sizeof(struct list)); p-＞data＝ch;q-＞next=p；q=p；ch=getchar()； } p-＞next＝\0； 【 】； }

如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表? 【中国人民大学2001二、4(2分)】

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

以下函数creat用来建立一个带头结点的单向链表，新产生的结点总是插在链表的末尾。单向链表的头指针作为函数值返回。请填空。 include ＜stdio.h＞ struct list { char dara； struct list *next； }； struct list *creat() { struct list *h，*p，*q； char ch； h= (struct list (*) malloc (sizeof (struct list))； ______; ch=getchar()； while(ch!=?) { p=(struct list*) malloc) sizeof (struct list))； p-＞data=ch； ______; q=p； ch=getchar()； } p-＞next=\0； ______： }

两个长度为n的双链表，节点类型相同，若以h1为头指针的双链表是非循环的，以h2为头指针指针的双链表是循环的，则( )。

A.对于非循环双链表来说，删除首节点的操作，其时间复杂度都是O(n)

B.对于循环双链表来说，删除首节点的操作，其时间复杂度都是O(n)

C.对于非循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1)

D.对于循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1)

写一算法检测单向链表中是否存在环

(whether there is a loop in a link list),

要求算法复杂度(Algorithm's complexity 是

O(n)) 并只使用常数空间(space is O(c)).

注意，你只知道一个指向单向链表头的指针。

链表的长度是不定的，而且环出现的地方也是不定

的，环有可能在头，有可能在中间。而且要求是检

测, 不能破坏环的结构.

对于长度为n(n≥1)的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为( )。

A.O(1)

B.O(n)

C.O(n2)

D.O(nlog2n)