当前位置：问答库＞考研试题

山东大学1992年硕士研究生入学试题

一 简答题（每小题3分）

（1） 设二叉树T 中有n 各顶点，其编号为1，2，3，…n. 若编号满足如下性质：

① T 中任一顶点v 的编号等于左子树中最小编号减1；

② 对T 中任一顶点v, 其右子树中最小编号等于其左子树中的最大编号加1。试

说明对二叉树中顶点编号的规则（按何种顺序编号）。

（2） 已知某工程有10道工序，每道工序的先驱工序和所需时间如下表所示。

① 试画出描述该工程计划的AOE 网络。

② 诈算出完成该工程的最短时间。

工序代号

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10 先驱工序 无 C1 C1

C1 C2,C4 C3 C3 C3,C4 C5,C6 C7,C8 所需时间 10 3 5

2 8 10 4 3 11 5

（3） 试叙述最优二叉检索树的定义。

（4） 社某文件经内排序后得到100个初始归并段(初始顺串), 若使用多路归并排序

算法，并要求三趟归并完成排序，文归并路数最少为多少？

（5） 按下属次序输入关键字：e,i,p,k,,m,l,b, 试画出A VL 树的构造与调整过程。（要

求画出每插入一个关键字检索树的形状及调整后的结果）。

二 (12分) 已知任意单链表如图1所示。Head 为表头指针，指向表的第一个元素，p

为指向表中任意结点的指针，试设计一个算法，将p 指向的结点和其后面结点交换位置（可采用任何高级语言描述算法）。

三 (13分) 设任意非空二叉树中结点按层次顺序依次编号为1,2, …,n(n>0),其存储结构

采用图2所示形式，其中i 表示结点的编号, L(i)的值是I 的左儿子的编号，R(i)的值是I 的右儿子的编号。若L(i),R(i)的值为0，表示结点I 无右儿子或左儿子。试设计算法： （1） 求出二叉树的高度。

（2）求出每个结点的层号（根结点层号为1）， 并填入D(i)中。（可采用任意高级语言，但要注明你所采用的高级语言的名