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