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

山东大学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 中结点的程序。二叉树采用双链结构，结点形式为

可采用任何你熟识的算法语言，设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） 如何判断一个标识符的作用域？

（4） 实数运算应注意那几个问题?

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

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

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