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

上海大学2000考研题 一 请完善下列程序,每小题在Pascal语言(a),c语言(b)中任选一题（共40分） 注意：每个空格填一个表示式或一个语句。 1 下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[j]进行 比较,第二趟对所有偶数的i,将a[i]和a[j]进行比较每次比较时若a[i]a[i+1],.将二 者交换,以后重复上述二趟过程,直至整个数组有序 程序.(a) Procedure oeseort(var a:array[1..n] of integer); Var flag:boolean; i,t:integer; Begin Repeat Flag:=false; For i:=1 to n step 2 do If(a[i]a[i+1]) then [flag:= (1); t:=a[i+1]; a[i+1]:=a[j]; (2) ] for i:= (3) do if (a[i]a[i+1]) then [flag:= (4) ; t:=a[i+1];a[i+1]:=a[i]; a[i]:=t; ] until (5) end; 程序（b） Void oesort (int a[n]) {int flag,i,t; do { flag:=0; for(i=1;in;i++,i++) {flag = (1); t=a[i+1];a[i+12]=a[i]; (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） Procedure maxcomstr(var s,t:orderstring;var index,length:integer); Var i,j,klength1:integer; con:boolean; While(i=s.len) do [ J:=1; While (j=t.len) do [ If (s[i]=t[j] then [ K:=1; length1:=1;con:=true; While con do If (1) then [ Length1:=length1+1;k:=k+1; ] else (2); if(length1length) then [ index:=i; length:=length1; ] (3) ] else (4) ] (5) ] end. 程序(b) Void maxconstr(orderstring*s,*t; int index, length) { int i,j,k,length1,con; index=0;length=0;i=1; while((is.len) { if (s[i]= =t[j]) { k=1;length1=1;con=1; while(con) if (1) { length1=length1+1;k=k+1; } else (2) ; if (length1length) { index=i; length=length1; } (3) ; } else (4) ; } (5) } } 设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有 非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿 子的结点个数和叶子结点个数N0.N2NLNR,N0都是全局量，且在调用count(t)之 前都置为0. 程序(a) type nodeptr=^n