南京大学2000年程序设计与数据结构考研试题
专业：计算机软件与理论，计算机应用
一. 填空题(16分)
1. 组成表达式的基本运算分量可以是____,_____,_____或由_____等四类
2. 与值参数对应的实在参数是_____,与变量参数对应的实在参数是__________
3. 指针类型是由_____及_______组成的集合。
4. 所谓的函数副作用是指_________________
5. 设有下列定义与说明：
const delta='a';espilon=1E-8;
type abc=(a,b,c);
pointer=| node; //打字注：|为向上箭头，下同
node=record d:0..255;
e:abc;
f:pointer
end;
var x:pointer;
又有下列对象：
a.false b.x |.f | c.(epsilon) d.x|.d e.delta f.[ ]
g.x|.e h.nil i.
j.a
根据上面的定义和说明按下面的要求填出这些对象的性质：
(1)_____________是常量
(2)_____________是变量
(3)_____________是集合表达式
(4)_____________是整型或实型表达式
二. 下列程序正确时指明输出结果，有错时指出出错位置及出错理由。(每题2分
，共8分)
1. program exl(output)
type two=(a,b);
var
variant:record
case two of
a
m:integer);
l:integer);
bn:integer);
o:integer);
end;
i：integer;
begin
variant. n:=1;
variant. o:=1;
variant. m:=1;
i:=variant.l;
writeln('exl=1')
end.
2. program ex2(output)
type rekord= record
a:integer;
b:boolean
end;
var
pointer：|record;
begin
new(pointer);
pointer:=nil;
pointer|.a:=l;pointer|.b:=true;
writeln('exp=nil');
end.
3. program ex3(output)
var
s:set of 0..10
begin
s:=[1];
if s in [ ] then s:=[2];
writeln('ex3=set')
end.
4. program ex4(output)
type
digits=(one,two,three,four);
subrange=one..two;
var
f:file of digits;
sub:subrange;
begin
rewrite(f);
write(f,three);
reset(f);
read(f,sub);
write('ex4=file')
end.
三. 阅读程序，将应填入____处的语句，表达式，或其他成分填在相应的答题栏
内(10分)
八皇后问题：设法在国际象棋棋盘上放置八个皇后，使得其中任何一个皇后所处的
行，列以及对角线上都不能有其他的皇后。
例如：八皇后问题的一个解：
*
*
*
*
*
*
*
*
Program eightqueen(output)
Var i:integer;q:boolean;
a：array[1..8] of boolean; {a[j]为true表示第j行上无皇后}
b：array[2..16] of boolean; {b[k]为true表示第k条对角线上没有皇后}
c：array[-7..7] of boolean;{c[k]为true表示第k条对角线上没有皇后}
x：array[1..8] of boolean;{x表示第I列上皇后的位置}
procedure try(____A______);
var j:integer;
begin j:=0;
repeat j:=j+1;_____B______;
if a[j] and b[i+j] and c[i-j] then
begin ___C____; a[j]:=false;b[i+j]:=false;c[i-j]:=false;
if i<8 then begin _____D_____
if not q then
begin a[j]:=true;b[i+j]:=true;c[i+j]:=true end
end else q:=true
end
until ____E_____
end{try};
begin for i:=1 to 8 do a:=true;
for i:=2 to 16 do b:=true;
for i:=-7 to 7 do c:=true;
try(1,q); if q then for i:=1 to 8 do write(x:4); writeln
end.
答题栏：A________ B_________
C__________D___________E___________________
四. 计算题(每题3分，共6分)
1. 设数组a的初值为 ( 2 1 3 )
a=( 3 3 1 )
( 1 2 1 )
执行语句：for i:=1 to 3 do
for j:=1 to 3 do
a[i,j]:=a[a[i,j],a[j,i]];
数组a的结果值是多少?
2.
Program ex5(output)
Var x,y:integer;
Procedure p(var x:integer;y:integer);
Begin y:=x+y;x:=y mod 4;
Write(x:4,y:4);
End;
Begin x:=4;y:=5;
P(y,x);writeln(x:4,y:4);
P(x,x);writeln(x:4,y:4);
P(y,x);writeln(x:4,y:4);
End;
执行该程序输出为：_________________________
五. 编程题(10分)
设有递归程序：
function f(n:integer):integer;
begin
if n=0 then f:=0;
else if n=1 then f:=1
else f:=f(n-1)+f(n-2)
end;
将它改成迭代程序(仍用function f……)
六. 填空(每空1分，共21分)
1. 评价算法的性能从利用计算机资源的角度看主要从__________方面进行分析。
2. 用数组G(其下标在0..n-1中，共有n个元素)表示一个环形队列，f为当前对
头元素的前一个位置，r为队尾元素的位置。假定队列中元素个数总小于n，求队列
中元素个数的公式是__________________________
3. 设堆栈S队列Q的初始状态为空，元素a，b，c，d，e，f依次通过堆栈S，一个
元素出栈后立即进入队列Q。若这6个元素出队列的顺序是b，d，c，f，e，a，则堆
栈S的容量至少应该是________.
4. 有向图中的结点前驱后继关系的特征是_____________________
5. 广义表中的元素可以是___________，所以其描述宜采用程序设计语言中的
_______来表示。
6. 用二分法查找一个线性表时，该线性表必须具有的特点是________________;
而分块查找法要求将待查找的表均匀地分成若干块且在块中诸记录的顺序可以是任
意的，但块与块之间_____________________
7. 采用散列技术来实现查找，需要解决的主要问题有：
(1)________________________________________________________
(2)________________________________________________________
8. 有向图G有n个顶点{v1，v2，…，vn}，它的邻接矩阵为A，A[i，j]=1表示vi到
vj存在邻接矩阵，而A[i，j]=0则不存在，故G中顶点vi的度为_____________，而
_____________为所有通过vk的存在行为的路径个数之和。
9. 设有函数f(n)=0.001n**4+3n**2+1
g(n)=4000n**3+213n**2+10**10
//打字注：n**4表示n的4次方
则称f(n)和n*g(n)是______________________
10. 一棵含有n个结点的k叉数，可能达到的最大深度为________和最小深度
__________
11. 设有程序段
for i:=1 to n do
for j:=1 to i do
begin p:=I*j;write(p);writeln end.
则执行语句"p:=i*j"的次数为____________且其时间复杂度为______________
12.设有向图G为 v1-->v3-->v4<--v2
(1) 写出所有的拓扑序列
_______________________________________________________
(2) 添加弧______后;则仅可能有唯一的拓扑序列。
13. 设有下列AOE网(其中vi(i=1,2,3…)表示事件，弧上表示活动的天数)
(1) 找出所有的关键路径___________________________________
(2) v3事件的最早开始时间为_______________________________
v1-6->v2-7->v3-9->v5-3->v6
v1-4->v4-8->v3-11->v6
v4-21->v6 //这是AOE网，相应结点自己连起来就可以
七. 填空或简答(每题4分，共20分)
1. 设有二叉树BT：
A (1)该二叉树BT是否为平衡二叉树?________
/ \ (2)其理由为____________
B C (3)如二叉树不是平衡二叉树，则调整BT使之成为平衡
\ / 二叉树BT‘：
E F _________________________
/
G
2. 设有类型position=0..maxsize;
LIST=RECORD n:position;
R:array[position] of element
END;
且有过程
procedure f(VAR L
IST)
VAR i,j:position;
Begin with L do
For I:=2 to n do
Begin R[0]:=R;j:=i-1;
While R[0].key<=R[j].key do
Begin R[j+1]:=R[j];j:=j-1 End;
R[j+1]:=R[0]
End
End;
(1)这个过程的功能为____________________
(2)这个算法是否稳定?______________________其理由为
_______________________
3. 写出计算一个广义表的原子结点个数的公式。
4. 在字符串运算中的模式匹配是常见的，KMP匹配算法是有用的方法。
(1) 其基本思想为___________________
(2) 对模式串P(=p1p2…pn)求NEXT数组时，NEXT是满足下列性质的k的最大值
或为0：_________________________________________________________
5. 如果有向图G中的顶点允许有不同的类型，而其弧也允许有不同的类型，那么
：
(1) 能否采用邻接矩阵描述G，并说明理由
(2) 能否采用邻接表描述G，如能描述，图示其表示。
八. 编程题(第1题3分，第2题6分，共9分)
1. 编写在有n个顶点的有向图图的邻接表上计算某个顶点v的出度的函数。
2. 编写判定给定的二叉树是否是二叉排序树的函数。
