上海交通大学1997年硕士研究生入学考试试题数据结构及程序设计技术
试题编号：１９题一（６分）有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。（３在４之前出栈）
题二（４分）试写出进栈操作，出栈操作算法的时间复杂性。
题三（４分）已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
题四（４分）设某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。试画出编码用的哈夫曼树。
题五（５分）已知某排序平衡二叉树Ｔ具有下列特点：（１）结点的关键字均在1到9范围内；（２）在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；（３）在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；（４）在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？
题六（９分）某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
（1）取第一个元素值６作为分割数，（2）试写出快速排序第一次分隔后Ａ中的结果。
（3）用堆排序，（4）试写出将第一个选出的数据放在Ａ的最后位置上，（5）将Ａ调整成堆后的Ａ中结果。
（6）用基数为３的基数排序法，（7）试写出第一次分配和收集后Ａ中的结果。
题七（１４分）某赋权有向图及它的单邻接表如下：
（1）试写出深度优先搜索顺序。
（2）画出深度优先生成树。
（3）将该图作为ＡＯＥ网络图，（4）试写出Ｃ的最早发生时间及活动ＦＣ的最晚开始时间。
（5）用Dijkstra算法计算源点Ａ到各顶点的最短路径，（6）试写出当计算出ＡＤ及ＡＧ的最短路径时，（7）Ａ到其它各点路径（中间结点）的值。
始点
123
32
1213
15
终点
请在下列各题的（N）处，填写适当的Pascal语句（或其它成份），完成各题的程序。
题八（１０分）下列程序输入一个正整数N(０<n<10)，打印1,2,….,n各数字的全排列，例如输入n=3,打印123,132,213,231,312,321
programexam8(input,output);
constmaxn=9;
vara:array[1..maxn]ofinteger;{放全排序一个值}
s:setof1..maxn;{放１到９各数字的集合}
n:integer
procedureload(j:integer);{将Ｓ中数字装入到a中}
varj,kinteger;
begin
forj:=1tondo
ifjins
thenbegin
s:=(1)
a[i]:=j;
ifi<n
then(2)
elsefork:=1tondowriten(a[k]);
(3)
end
end{load};
begin{main}
readln(n);s:=[1..n];load(1)
end.
题九（１０分）下面的过程对二叉树进行后序遍历（非递归）。假设已有栈的一些操作过程说明。并说明树的结点类型：
typepointer=node;
node=record
data:integer;
left,right:pointer
end;
procedurepost(p:pointer);
varq:pointer;
begin
ifp<>then
begincreate_stack(s);{建立一个Ｓ栈，并初始化为空栈}
while(P<>nil)ornotempty_stack(s){s栈不空}do
ifp<>nil
thenbegin
push(s,p);{将Ｐ进栈}
push(s,p);{P作为标记进栈}
P:=（１）
end
elsebegin
pop(s,p);{将标记退出Ｓ栈}{退出到Ｐ中}
ifp<>nil
thenbegin
push(s,nil){标记进栈}
（２）；
end
elsebegin
（3）；
write(q.data);{访问结点，打印结点数据}
end
end
end{post}
题十（８分）设结点的类型定义如下：
type
node=recorddata:integer;link:integerend;
在数组a中存放了１０个结点：
vara:array[1..10]ofnode;
假定在主程序中已经执行了下列语句：
fori:=1to10do
begina[i].data:=i,a[i].link:=0end;
最初将１０个结点看成分别属于１０个集合，每个集合有且仅有一个结点，调用下面过程，判断data=m和data=n的两个结点是否在同一个集合中（最初肯定属于不同集合，除非m=n），若不在同一集合中，则将这两个结点合并到一个集合中。否则，已在同一个集合中，什么也不做。（此方法用于Kruskal求最小生成树的算法中）
proceduremerge_set(m,n:integer);
functionfind(k:integer):integer;
varf:integer;
begin
f:=k;
whilea[k].link<>0dof:=a[k].link;
(1);
end;
begin
m:=find(m);n:=frind(n);
ifm<>nthen(2)
end{merge_set}
题十一（１４分）设有数组变量说明：
vara:array[1..n]ofrecordkey:integer;next:0..nend;
假设各元素的key已有值，并且假设最大值＜＝９９９９，再假定在主程序已执行下面语句，已将各元素组成一个链；
fori:=Øton-1doa[i].next:=i 1;
a[i]:=Ø
下面是以10为基的基数排序法过程，将数组a按Key由小到大排序。
Procedurebucket_sorting;
Constmaxkey=9999;
Varbucket,tail:array[0..9]of0..n;
P,last:0..n;
i:=0..9;
d:integer;
begin
d:=1;
repeat
fori:=0to9dotail[i]:=Ø;
{分解}
P：＝a[0].next;{a[0].next是链的第一个结点}
WhileP<>Ødo
Begini:=a[p].keydivdmod10;
If(1)
Thenbucket[i]:=p
Elsea[(2)].next:=p;
Tail[i]:=p;
(3)
end
{收集}
last:=0
fori:=0to9do
if(4)
thenbegin
a[last].next:=(5);
last:=(6)
end;
a[last].next:=Ø;
d:=(7)
untild>maxkey
end{bucket_sorting}
题十二（12分）下面是一个判断二叉树是否是排序平衡树的函数说明，若是排序平衡树，则返回值为真，否则返回值假，另外，以参数的形式返回二叉树的高度和最大最小结点值。结点的类型定义与题九的定义相同。
Functionisbalance(p:pointer;varh,min,max:integer)
Varhleft,hright,lmax,rmin:integer;
Begin
Ifp<>nil
thenbegin
ifosbalance(p.left,hleft,(1))
andisbalance(P.right,hright,(2))
thenbegin
ifhleft=0
thenbeginmin:=p.data;lmax:=p.data-1end;
ifhright=0
thenbeginmax:=p.data;rmin=p.data 1end;
ifhleft>hright
thenh:=hleft 1elseh:=hright 1;
isbalanced:=(abs(hleft-hright)<=1)
and((3))
and((3))
end
elseisbalanced:=false
end
elsebeginh:=0;isbalanced:=trueend
end{isbalance}
页:
[1]