最新版数据结构1800题含完整答案详解

请补上程序中空缺的部分,并估计算法的时间复杂度。(设a,b的结点数分别为m,n) TYPE

link=^node; node=RECORD

key:char; next:link END;

PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN

new(c);c^.next:=c; q:=a; p:=a^.next; WHILE p<>a DO [(1)___;

WHILE p^.key=p^.next^.key DO [q:=p; p=p^.next];{跳过相同字母} r:=b^.next ; (2)_____;

WHILE r^.key <>p^.key DO r:=r^.next; IF r<>b THEN

[ s:=p; q^.next:=p^.next; (3) ; s^.next:=c^.next; c^.next:=s; c:=s ] ELSE [ q:=p; p:=p^.next ] ]; c:=c^.next;

END;

算法时间复杂度为O(4)___ 【北京工业大学 2000 四 (15分)】

30. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。 void reverse(pointer h)

/* h为附加头结点指针;类型pointer同算法设计第3题*/ { pointer p,q;

p=h->next; h->next=NULL; while((1)________)

{q=p; p=p->next; q->next=h->next; h->next=(2)________; } }【西南交通大学 2000 一、9】

31. 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法,该算法用L返回逆置后的链表的头指针,试在空缺处填入适当的语句。

void reverse(linklist &L){

p=null;q=L; while(q!=null)

{ (1) ; q->next=p;p=q;(2)___ ; }

(3)_____;

}【北京理工大学 2001 九、1 (6分)】

32.下面程序段是逆转单向循环链表的方法,p0 是原链表头指针,逆转后链表头指针仍为p0。

(可以根据需要增加标识符) p:= p0; q0:=NIL;

WHILE (1)________ DO

BEGIN (2)________; (3)________;(4)______;(5)________ END;

p^.next:= q0; p0 ^.next:=p; p0:=p;【中国人民大学 2000 二、1(4分)】 33.一个无头结点的线性链表(不循环)有两个域。数据域data,指针域 next,链首head,下面算法用read(num)读入数据,当num小于0时,输入结束。建立一个数据以递增序组成的链表。

PROC insert( head, x);

{在链首为head的表中按递增序插入x} new(r);r^.data:=x; IF head=NIL

THEN[ head:=(1) _____; r^.next:= (2)________ ] ELSE IF (3)___ THEN [r^ .next:=head; head:=r] ELSE [p:=head;

WHILE (4)___ AND (p^.next≠NIL ) DO[q:=p; (5)___ ]; IF (6)___ THEN [ q^ .next:=(7)___; r^.next:= (8)____; ] ELSE [p^.next:=(9)____; r^.next:= (10)___; ]

] ENDP;

PROC creat(head);

head:= (11)______; read(num); WHILE num>0 DO

[ insert(head,num); read(num) ] ENDP;【南京理工大学 1999 三、4(11分)】

34. 一元稀疏多项式以循环单链表按降幂排列,结点有三个域,系数域coef ,指数域exp和指针域 next;现对链表求一阶导数 ,链表的头指针为ha,头结点的exp域为 –1。

derivative(ha)

{ q=ha ; pa=ha->next; while( (1)_______)

{ if ( (2)____) { ( (3)__); free(pa); pa= ( (4) _); }

else{ pa->coef ( (5) ___); pa->exp( (6)___); q=( (7) __);} pa=( (8)________); }

} 【南京理工大学 2000 三、3(10分)】

35.下面是删除单链表L中最大元素所在结点的类PASCAL语言算法,请在横线填上内容,完成其功能。

TYPE pointer =↑node; node=RECORD

data:integer; next: pointer END;

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.线性表有两种存储结构:一是顺序表,二是链表。试问:

(1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?

(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?【西安电子科技大学 1999软件 二、1 (5分)】

2.线性表的顺序存储结构具有三个弱点:其一,在作插入或删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点,试讨论之。【重庆大学 2000 二、5】 3.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?

【北京航空航天大学 1998 一、2(4分)】

4.线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。请用类PASCAL语言描述这两种结构。【华北计算机系统工程研究所1999一、2(10分)】

5.线性表(a1,a2,?,an)用顺序映射表示时,ai和ai+1(1<=i

【东南大学 1996 一、1 (5分)】

6. 说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。

【厦门大学 2000 五、1 (14%/3分)】

7. 试述头结点,首元结点,头指针这三个概念的区别. 【武汉交通科技大学 1996 二、2 (3分)】【西安电子科技大学2001计应用 二、1(5分)】 8. 已知有如下定义的静态链表: TYPE component=RECORD

data:elemtp; next:0..maxsize END

VAR stalist:ARRAY[0..maxsize] OF component;

以及三个指针:av指向头结点,p指向当前结点,pre指向前驱结点,现要求修改静态链表中next域中的内容,使得该静态链表有双向链表的功能,从当前结点p既能往后查找,也能往前查找:

(1) 定义next域中的内容。(用老的next域中的值表示); (2) 如何得到当前结点p的前驱(pre)的前驱,给出计算式;

(3) 如何得到p的后继,给出计算式;【中科院计算所 2000 四(10分)】 9. 在单链表和双向链表中,能否从当前结点出发访问到任何一个结点?

【西安电子科技大学1999计应用一、1 (5分)】

10. 如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单向链表?

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4