上海交通大学1997年数据结构及程序设计技术考研试题
上海交通大学1997年数据结构及程序设计技术考研试题试题编号：19
题一(6分)有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。(3在4之前出栈)
题二(4分)试写出进栈操作，出栈操作算法的时间复杂性。
题三(4分)已知KMP串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
题四(4分)设某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。试画出编码用的哈夫曼树。
题五(5分)已知某排序平衡二叉树T具有下列特点：(1)结点的关键字均在1到9范围内;(2)在T中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原T不相同;(3)在T中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原T相同的平衡树;(4)在T中插入某n3结点后立即删除它，得到的平衡树与原T不相同。试画出具有上述特点的最简单(结点个数最少)的平衡树T，并写明n1,n2,n3分别等于几?
题六(9分)某整型数组A的10个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将A中元素由小到大排序。
(1) 取第一个元素值6作为分割数，(2) 试写出快速排序第一次分隔后A中的结果。
(3) 用堆排序，(4) 试写出将第一个选出的数据放在A的最后位置上，(5) 将A调整成堆后的A中结果。
(6) 用基数为3的基数排序法，(7) 试写出第一次分配和收集后A中的结果。
题七(14分)某赋权有向图及它的单邻接表如下：
(1) 试写出深度优先搜索顺序。
(2) 画出深度优先生成树。
(3) 将该图作为AOE网络图，(4) 试写出C的最早发生时间及活动FC的最晚开始时间。
(5) 用Dijkstra算法计算源点A到各顶点的最短路径，(6) 试写出当计算出AD及AG的最短路径时，(7) A到其它各点路径(中间结点)的值。
始点
1 2 3
3 2
1 2 1 3
1 5
终点
请在下列各题的 (N) 处，填写适当的Pascal语句(或其它成份)，完成各题的程序。
题八(10分)下列程序输入一个正整数N(0
program exam8(input,output);
const maxn=9;
var a:array[1..maxn] of integer;{放全排序一个值}
s:set of 1..maxn;{放1到9各数字的集合}
n:integer
procedure load(j:integer);{将S中数字装入到a中}
var j,k integer;
begin
for j:=1 to n do
if j in s
then begin
s:= (1)
a[i]:=j;
if i
then (2)
else for k:=1 to n do writen(a[k]);
(3)
end
end{load};
begin {main}
readln(n); s:=[1..n]; load(1)
end.
题九(10分)下面的过程对二叉树进行后序遍历(非递归)。假设已有栈的一些操作过程说明。并说明树的结点类型：
type pointer= node;
node=record
data:integer ;
left,right :pointer
end;
procedure post(p:pointer);
var q:pointer;
begin
if p<> then
begin create_stack(s);{建立一个S栈，并初始化为空栈}
while (P<>nil) or not empty_stack(s){s栈不空} do
if p<>nil
then begin
push(s,p); {将P进栈}
push(s,p);{P作为标记进栈}
P:= (1)
end
else begin
pop(s,p);{将标记退出S栈}{退出到P中}
if p<>nil
then begin
push(s,nil){标记进栈}
(2) ;
end
else begin
(3) ;
write(q .data);{访问结点，打印结点数据}
end
end
end{post}
题十(8分)设结点的类型定义如下：
type
node=record data:integer; link:integer end;
在数组a中存放了10个 结点：
var a:array[1..10] of node;
假定在主程序中已经执行了下列语句：
for i:=1 to 10 do
begin a[i].data:=i, a[i].link:=0 end;
最初将10个结点看成分别属于10个集合，每个集合有且仅有一个结点，调用下面过程，判断data=m和data=n的两个结点是否在同一个集合中(最初肯定属于不同集合，除非m=n)，若不在同一集合中，则将这两个结点合并到一个集合中。否则，已在同一个集合中，什么也不做。(此方法用于Kruskal求最小生成树的算法中)
procedure merge_set(m,n:integer);
function find(k:integer):integer;
var f:integer;
begin
f:=k;
while a[k].link<>0 do f:=a[k].link;
(1) ;
end;
begin
m:=find(m); n:=frind(n);
if m<>n then (2)
end{merge_set}
题十一(14分)设有数组变量说明：
var a:array[1..n] of record key:integer; next:0..n end;
假设各元素的key已有值，并且假设最大值<=9999，再假定在主程序已执行下面语句，已将各元素组成一个链;
for i:=Ø to n-1 do a[i].next:=i+1;
a[i]:= Ø
下面是以10为基的基数排序法过程，将数组a按Key由小到大排序。
Procedure bucket_sorting;
Const maxkey=9999;
Var bucket,tail :array[0..9] of 0..n;
P,last:0..n;
i:=0..9;
d:integer;
begin
d:=1;
repeat
for i:=0 to 9 do tail[i]:= Ø;
{分解}
P：=a[0].next;{a[0].next是链的第一个结点}
While P<> Ø do
Begin i:=a[p].key div d mod 10;
If (1)
Then bucket[i]:=p
Else a[ (2) ].next:=p;
Tail[i]:=p;
(3)
end
{收集}
last:=0
for i:=0 to 9 do
if (4)
then begin
a[last].next:= (5) ;
last:= (6)
end;
a[last].next:= Ø;
d:= (7)
until d>maxkey
end{bucket_sorting}
题十二(12分)下面是一个判断二叉树是否是排序平衡树的函数说明，若是排序平衡树，则返回值为真，否则返回值假，另外，以参数的形式返回二叉树的高度和最大最小结点值。结点的类型定义与题九的定义相同。
Function isbalance(p:pointer;var h,min,max:integer)
Var hleft,hright,lmax,rmin:integer;
Begin
If p<>nil
then begin
if osbalance(p .left,hleft, (1) )
and isbalance(P .right,hright, (2) )
then begin
if hleft=0
then begin min:=p .data; lmax:=p .data-1 end;
if hright=0
then begin max:=p .data; rmin=p . data+1 end;
if hleft>hright
then h:=hleft+1 else h:=hright+1;
isbalanced:=(abs(hleft-hright)<=1)
and ( (3) )
and ( (3) )
end
else isbalanced:=false
end
else begin h:=0; isbalanced:=true end
end{isbalance} 谢谢楼主