数据结构考研分类复习真题 第二章 线性表[19]

．循环链表a和b的结点值为字母其中a表非递减有序下面的程序欲构造一个递增有序的循环链表c其中结点的值为同时在ab两链表中出现的字母且c中字母不重复请补上程序中空缺的部分并估计算法的时间复杂度（设ab的结点数分别为mn）

TYPE

link=^node;

node=RECORD

key:char; next:link

END;

PROC jj(ab:link; VAR c:link);

VAR pqrs:link;

BEGIN

new(c);c^next:=c; q:=a; p:=a^next;

WHILE p<>a DO

[ （）

WHILE p^key=p^next^key DO [q:=p; p=p^next];｛跳过相同字母｝

r:=b^next ; （） ;

WHILE r^key <>p^key DO r:=r^next;

IF r<>b THEN

[ s:=p; q^next:=p^next; （） ;

s^next:=c^next; c^next:=s; c:=s ]

ELSE [ q:=p; p:=p^next ]

]; c:=c^next

END;

算法时间复杂度为O （） 【北京工业大学 四 (分)】

以下程序的功能是实现带附加头结点的单链表数据结点逆序连接请填空完善之

void reverse(pointer h)

/* h为附加头结点指针类型pointer同算法设计第题*/

{ pointer pq;

p=h>next; h>next=NULL;

while( () )

{q=p; p=p>next; q>next=h>next; h>next= () ; }

}【西南交通大学 一】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []