数据结构1800题（答案全）(12)

PROCEDURE delmax (L:pointer);

VAR p,q,r:pointer; m:integer;

BEGIN

r:=L； p:=L↑.next;

IF p<>NIL THEN

[ m:=p↑.data; (1)________; p:=p↑.next;

WHILE p<>NIL DO

[ IF (2)________THEN [ (3)________ ; m:=p↑.data; ]

(4)________; p:=p↑.next; ]

q:=r↑.next; (5)______; dispose(q);

]

END;【北京科技大学 1998 二】

36．对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。

typedef struct node

{int data; struct node *next;

}linknode,*link;

void Insertsort(link L)

{ link p,q,r,u;

p=L->next; (1)______;

while((2)________)

{ r=L; q=L->next;

while((3)________&& q->data<=p->data) {r=q; q=q->next;}

u=p->next; (4)______; (5)______; p=u;

}

}【北京科技大学 2001 二 （10分）】

37．下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。

程序(a)（编者略去这个PASCAL程序）

程序（b）

typedef struct node{ int element; struct node *link;

}NODE;

NODE *A，*B，*C;

NODE *append (NODE *last,int e)

{ last->link=(NODE*) malloc (sizeof(NODE));

last->link->element=e;

return(last->link); }

NODE *difference(NODE *A,NODE *B)

{NODE *C,*last;

C=last=(NODE*) malloc (sizeof(NODE));

while (1)___

if (A->elementelement) { last=append(last,A->element); A=A->link; }

else if (2) ___ { A=A->link; B=B->link; } ELSE (3) ___ ;

while (4) __

{ last=append(last,A->element); A=A->link; }

(5) ___; last=C; C=C->link; free (last); return (C); }

/*call form:C=difference(A,B);*/【上海大学 2000 一、4 （10分）】

三．填空题

1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py

4 ．n-i+1

5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。

6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表

8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;

9．p^.prior s^.prior^.next

10． 指针 11．物理上相邻 指针 12．4 2

13．从任一结点出发都可访问到链表中每一个元素。

14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null

17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s;

19．(1) IF pa=NIL THEN return(true);

(2) pb<>NIL AND pa^.data>=pb^.data

(3) return(inclusion(pa,pb));

(4) pb:=pb^.next;

(5) return(false);

非递归算法：

(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next; …… 此处隐藏：266字，全部文档内容请下载后查看。喜欢就下载吧 ……