上海大学2000数据结构考研试题.doc
文本预览下载声明
上海大学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
显示全部