上海交通大学一九九八年硕士研究生入学考试试题
试题名称：数据结构和程序设计技术
试题编号：１９
题一（２０分）判断题：若认为下列命题正确，打“a“，反之打“r“
１、 数据元素是数据的最小单位（ ）
２、 队列逻辑上是一个下端口和上端能增加又能减少的线性表（ ）
３、 任何一个递归过程都可以转换成非递归过程。（ ）
４、 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ）
５、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ ）
６、 两*树是树的一种特殊情况（ ）
７、 在树中，如果从结点K出发，存在两条分别到达K’，K”的长度相等的路径，由结点K’和k”互为兄弟（ ）
８、 线索两*树的优点是便于在中序遍历下，查找前趋和后继结点（ ）
９、 n个结点的两*树有多种，其中树高最小的两*树排序树是最佳的（ ）
１０、 最佳两*排序树的任何子树都是最佳的（ ）
１１、 设T为一棵平衡树，在其中插入一个结点N，然后立即删除该结点得到T1，T与T1必定相同（ ）
１２、 一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）
１３、 任何有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一（ ）
１４、 当改变网上某一关键路上任一关键活动后，必将产生不同的关键路径（ ）
１５、 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）
１６、 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省( )
１７、 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关（ ）
１８、 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不稳定的（ ）
１９、 堆排序是稳定的排序方法（ ）
２０、 在分配排序时，最高位优先分配法比最低位优先分配法简单（ ）
题二、（１５分）试证明：若借助栈由输入序列1,2,…n得到输出序列为p1,p2,…pn,（它是输入序列的一个排序），则在输出序列中不可能出现这样的情形：存在着I<j<k,使pj<pk<pi。
题三、（１２分）假定有下列n*n矩阵（n为奇数） a11 0 …. 0 a1n
0 a22….a2,n-1 0
Ａ＝ . .
. .
. .
an1 0…. 0 ann
如果用一维数组Ｂ按行主次序存储Ａ的非零元素，问 １）Ａ中非零元素的行下标与列下标的关系；
２）给出Ａ中非零元素aij的下标（i,j）与Ｂ中的下标Ｒ的关系；
３）假定矩阵中每个元素占一个存储单元，且Ｂ的起始地址为Ａ０，给出利用aij的下标（i,j）定位在Ｂ中的位置公式。
题四（８分）试找出分别满足下面条件的所有二*树：
１） 前序序列和中序序列相同；
２） 中序序列和后序序列相同；
３） 前序序列和后序序列相同。
题五（１５分）在二*树中查找值为X的结点，试编写算法（用Ｃ语言）打印值为X的结点的所有祖先，假定值为X的结点不多于１个，最后，试分析该算法的时间复杂性。（若不加分析，直接写出结果，按零分算）
题六（１０分）设如下带权有向图，试利用求每对顶点之间最短路径的 Floyd算法，给出代价邻接矩阵，矩阵序列Ａ（i）(i=1,2,3)以及最短路径 PATH<i,j> (1<=i,j<=3)
6 Á
4 2
À
3
11
Â
题七(12分)已知a数组元素共５个，依次为12,10,5,3,1;b数组元素共４个，依次为4,6,8,15，则执行如下所示的过15,12,10,8,6,5,4,3,1，数组a,b,c的长度分别为l=5,m=4,n=9，请在程序中方框内填入正确的成份，以完成上述要求。
Procedure Sort
Var i,j,k,x:integer:
d:array[1..m] of integer;
begin
for i:=1 to m do d
:=
i:=1;j:=1;k:=1;
while(i<=l) and (j<=m) do
begin
if a>d
then begin
end;
else begin
end;
c[k]:=x;
end;
while do
begin
c[k]:=a; k:=k+1;i:=i+1
end;
while do
begin
c[k]:=d[j]; k:=k+1;j:=j+1
end;
end;{sort}
题八（８分）已知如下一棵三阶Ｂ＿树，试画出插入关键字B,L,P,Q,R以后的树形。
