顺序表中逻辑上相邻的元素在物理存储位置上相邻,链表结构中逻辑上相邻的

假设以带头结点的单链表表示有序表,单链表的类型定义如下:

typedef struct node{

DataType data;

struct node next

)LinkNode, LinkList;

编写算法,从有序表A中删除所有和有序表B中元素相同的结点。

下面的算法是用冒泡排序法完成对文件中各个记录按关键字递增次序排序,请仔细阅读程序并把未完成的部分填上。

void bubblesort (SeqList R)

{

int i,;

Boolean exchange;

for (i-1:i

{

exchange-false;

for (j=n-1;j (1)

if(R[+1]. key

{

R[o]=R[j+1];

R[j+1]= (2) ;

(3) =R[0];

exchange=true;

}

if(!exchange)

(4)

}

}

(1)

(2)

(3)

(4)

阅读下列函数F并回答问题

(1)已知如题图所示的二叉树以二叉链表作存储结构rt为指向根结点的指针写出执行函数调用F(rt)的输出结果。

(2)说明函数F的功能题图

void(BinTreeT)

StackS;

if(T)

{

InitStack(&.S);

Push(&S,NULL);

while(T)

{

printf("%c",T->data);

if(T->rchild)Push(&.S,T->rchild);

f(T->Ichild)T=T->lchild;

elseT=Pop(&.S);

}

}

(1)

(2)

算法 MergeList的功能是归并两个有序链表La和b为有序链表Lc。请在空缺处填入合适的内容,使其成为一个完整的算法。

LinkList MergeList(LinkList La, LinkList Lb)

{ }//归并两个有序链表La和Lb为有序链表Lc

ListNode *pa, pb,; LinkList Lc;

pa=la->next;pb=lb->next;//pa和pb分别指向两个链表的开始结点

Le==La;//用La的头结点作为Lc的头结点

while(pa! =NULL&.&.pb! =NULL)

pe->next=pa; pe-pa;pa=pa->next;

}

else{

pe->next-pb: (1) spb=pb->next;

}

}

p->next-pa!-null?(2):pb;//插入链表剩余部分

(3) ;//释放Lb的头结点

return Lc;//返回合并后的表

}

(1)

(2)

(3)

已知用有序链表存储整数集合的元素。阅读算法f30,并回答下列问题:

(1)写出执行f30(a,b)的返回值,其中a和b分别为指向存储集合{2,4,5,7,9,12}和{2,4,5,7,9}的链表的头指针。

(2)简述算法f30的功能。

(3)写出算法f30的时间复杂度。

int f30(LinkList ha, LinkList hb)

{

//LinkList//是带有头结点的单链表

//ha和hb分别为指向存储两个有序整数集合的链表的头指针

LinkList pa,pb;

pa=ha->next;

pb=hb->next;

while(pa & pb & pa->data==pb->data)

pa-pa->next;

pb=pb→next;

}

if(==NULL &.& pb= =NULL) return 1;

else return 0;

}

(1)

(2)

(3)

画出下列广义表的图形表示:

(1)A=(a,(b,c))

(2)B=(a,d)=((a,(b,c)),d)

画出下面两个广义表的图形表示:

(1)A=()

(2)B=(a,(b,c))

分别写出删除单向循环链表和双向循环链表中指针p所指的结点的直接后继结点(非尾结点)的对应语句。

画出题图所示的树对应的二叉树。

顺序表中逻辑上相邻的元素在物理存储位置上相邻,链表结构中逻辑上相邻的