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