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

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

一简答题（每小题3分）

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

T 中任一顶点v 的编号等于左子树中最小编号减1；对T 中任一顶点v, 其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。

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

试画出描述该工程计划的AOE 网络。诈算出完成该工程的最短时间。

工序代号

C1C2C3C4C5C6C7C8C9C10

先驱工序无C1C1C1C2,C4C3C3C3,C4C5,C6C7,C8

所需时间1035281043115

（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)中。（可采用任意高级语言，但要注明你所采用的高级语言的名

称）。

四（17分）设两个高次多项式为a n x n +an-1x n-1+…a 1x+a0b m x m +bm-1x m-1+…b 1x+b0

其中：a i (i=0,1,2,3…,n),b j(j=0,1,2,…,m) 为任意指定的常数，m,n 为非负整数。要求：（1）定义一种能有效表示多项式的数据类型；

（2）编写PASCAL 程序，读入两个多项式，求其乘积，并以适当形式输出结果。五（13分）设整数X 1,X 2, …,X N 已存放在数组A 中，编写一PASCAL 递归程序，

输出从这n 个数中取出所有k 个数的所有组合（k<=n）。

例：若A 中存放的数是1，2，3，4，5，k 为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321

六（10分）设有两个文件变量定义如下：

f:FILE of RECORD

X:REAL;N:INTEGRE;B:BOOLEAN; END; G:TEXT 要求：（1）说明这两个文件在存储格式上有什么不同？

（2）编一PASCAL 过程，将文件F 中数据以适当形式写入文件G 。（3）编一PASCAL 过程，将（2）中形成的文件G 中数据写入文件F 。

七(5分) 写出到达---定值数据流方程，并说明其在编译优化中的应用。八（15分）对NFAM=({0,1,2,3,4},{a,b},f,{0},{4}),其中f 定义为：

f(0,a)={1,2}f(0,b)={1,3}f(1,a)={1,2}f(1,b)={1,3}f(2,a)={4}f(2,b)=Φf(3,a)=Φf(3,b)={4}f(4,a)={4}f(4,b)={4}

要求：（1）给出M 的状态转换图；

（2）写出M 对应的正责文法G ，使得L(M)=L(G);

（3）将NFAM 确定化为DFAM （4）将M 状态最小化。

，

，

；

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

一

解答下列问题（每小题4分，共16分）

（1）已知图的邻接表如图一所试，写出从顶点A 开始按深度优先遍历规则图中顶点

的遍历次序。

（2）已知度为4的树中度为1的结点数为n 1, 度为2的结点数为n 2, 度为3的结点数

为n 3, 度为4的结点数为n 4，求出这棵树中终端结点（叶结点）的个数，并要求写出计算推演过程。

（3）在四阶B 树中（如图2所示），插入关键字87，试画出插入调整后树的形状。（4）已知初始文件F={25,37,16,20,65,80,14,33,82,19,70},写出利用Shell 排序算法，

每一遍排序结束时文件的状态（注明你选取的增量序列

）

二（12分）写出按层次顺序打印任意二叉树T 中结点的程序。二叉树采用双链结构，结点形式为

DATA

LSON

可采用任何你熟识的算法语言，设T 指向二叉树的根结点。

三（12分）设任意n 个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂度为0(n) ）。

四（10分）回答下列PASCAL 语句中的概念：

（1）两个变量类型相同指什么，下面两个变量是否类型相同，为什么？

V AR A:Array[1..10]of real;

B:Array[1..10]of real;

（2）有序类型有哪些？有什么共同特点？（3）如何判断一个标识符的作用域？

RSON

（4）实数运

算应注意那几个问题?

五（15分）编写一个PASCAL 程序，从TEXT 文件中读一段英文，设单词之间由一个或多个空格或逗点分隔，统计并输出每个单词在该段文中出现的次数，以及每个字母出现的次数（不分大小写）。

六（15分）设Listhead 为一单链表的头指针，单链表的每个结点由一个整数域DATA 和指针域NEXT 组成，整数在单链表中是无序的。编一PASCAL 过程，将Listhead 链中结点分成一个奇数和一个偶数，分别由P,Q 指向，每个链中的数据按由小到大排列。程序中不得使用NEW 过程申请空间。

七（5分）构造语言{ai b j |j>I>0}相应的文法。

八（5分）下列文法G 是否是二义文法，为什么？

G:E→I|(E)|EAEA →+|-|*|/

九（10分）循环语句for I:=E1down to E2do S

目标代码结构如下：A:=E1;B:=E2;I:=A;

L1if I-B<0then goto L2S I:=I-1Goto L1L2

试写出语义子程序。