上海大学2000数据结构考研试题

《上海大学2000数据结构考研试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、消息来自上海大学考研论坛——启弘教育上海大学2000考研题一请完善下列程序,每小题在Pascal语言(a),c语言(b)中任选一题（共40分）注意：每个空格填一个表示式或一个语句。1下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[j]进行比较,第二趟对所有偶数的i,将a[i]和a[j]进行比较每次比较时若a[i]>a[i+1],.将二者交换,以后重复上述二趟过程,直至整个数组有序程序.(a)Procedureoeseort(vara:array[1..n]ofinteger);Varflag:boolean;i,t:integer;B

2、eginRepeatFlag:=false;Fori:=1tonstep2doIf(a[i]>a[i+1])then[flag:=(1);t:=a[i+1];a[i+1]:=a[j];(2)]fori:=(3)doif(a[i]>a[i+1])then[flag:=(4);t:=a[i+1];a[i+1]:=a[i];a[i]:=t;]until(5)end;程序（b）Voidoesort(inta[n]){intflag,i,t;do{flag:=0;for(i=1;i

3、2);}for(3)if(a[i]>a[i+1]){flag=(4);t=a[i+1];a[i+1]=a[i];a[i]=t;}}while(5);消息来自上海大学考研论坛——启弘教育}2下列算法实现求采用顺序结构存储的串和串的一个最长公共子串。程序（a）Proceduremaxcomstr(vars,t:orderstring;varindex,length:integer);Vari,j,klength1:integer;con:boolean;While(i<=s.len)do[J:=1;While(j<=t.len)do[If(s[i]=t[j]th

4、en[K:=1;length1:=1;con:=true;WhilecondoIf(1)then[Length1:=length1+1;k:=k+1;]else(2);if(length1>length)then[index:=i;length:=length1;](3)]else(4)](5)]end.程序(b)Voidmaxconstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while((i

5、;length1=1;con=1;while(con)if(1){length1=length1+1;k=k+1;}else(2);if(length1>length){index=i;length=length1;}(3);}else(4);}消息来自上海大学考研论坛——启弘教育(5)}}3设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数和叶子结点个数N0.N2NLNR,N0都是全局量，且在调用count(t)之前都置为0.程序(a)type

6、nodeptr=^nodetype;nodetype=recorddata:integer;lchild,rchild:nodeptr;end;varN2,NL,NR,N0:integer;procedurecount(t:nodeptr);beginift^lchild<>nilthenif(1)thenN2:=N2+1ElseNL:=NL+1ElseIf(2)thenNR:=NR+1ELSE(3);ift^.lchild<.nilthen(4);ift^.rchild<.nilthen(5);end;(*callform:ift<>nilthencoun

7、t(t);*)程序(b)typedefstructnode{intdata;structnode*lchild,*rchild;}NODE;intN2,NL,NR,N0;voidcount(NODE*t){if(t->lchild!=NULL)if(1)N2++;消息来自上海大学考研论坛——启弘教育ElseNL++;ElseIf(2)NR++;Else(3);if(t->lchild!=NULL)(4);if(t->rchild!=NULL)(5);}/*callform:if(t!=NULL)count(t);*/4.下面是一个求两个集合A和B之差C=A-

8、B的程序，即当且仅当e是A的一个元素，但不是B中的一