上海交通大学1989年研究生考试数据结构及程序设计技术试题
一、1〕填空（12分） 函数P（N）判定N是否为质数 P（N）＝TURE如果N是质数 FALSE如果N不是质数 其中N大于等于2，请在程序划线处填入正确语句： typeNumtype=2maxitn; functionP1(x,k:numtype):boolean; begin if_______thenp1:=ture elsep1:=_______and p1(x,k 1) end; functionp(x:numtype):boolean; begin p:=p1(x,_______) end; 2）（8分） 函数F定义如下： functionF(x:integer):integer; Vary,u:integer; Begin Y:=0;u:=1; Whileu<=xdo Begin Y:=y-1; U:=u 2*y 1 End; F:=y End 问：A。F（12）＝？B。F的功能？ 二（20分） 设文件P.PAS中存有一语法正确的PASCAL源程序，其中字母均为小写。请写一程序，输出P.PAS中第一个保留字begin所在行。 提示：设OPEN语句格式为 OPEN（<文件变量>，<文件名>） 三（共30分，每题6分） 1、已知一棵四次树，其结点数据场之值为一英文大写字母。现给出该二叉树的前序周游结构（按前序打印数据场之值）及每个结点的次数如下： 前序：A,B,C,F,G,D,H,J,K,M,N,E,I 次数：4,0,2,0,0,1,1,3,0,0,1,0,1,0 试画一图形表示该四次树。 2、有人说：“队列和栈都是优先队列的特殊情况”，这句话对吗？如果不对，请说明理由。如果正确，回答为什么并给出如果用优先队列实现栈和队列的方法。 3、已知如图所示的有向图，试求出： 每个结点的最早完成时间TE值及最晚完成时间TL值。 求出关键活动及关键路径。4、采用多阶段合并分类法合并若干条磁带上的文件为一有序文件，当最初合并段不是标准fibonacci数时。可以补充适当的空段。试问，补充的空段在各条磁带上应如何分布？为什么？ 5、有一棵完全二叉树，其叶子结点分布在最下面二层上。设叶子结点个数为L，请问该二叉树由根至所有叶子结点的路径长度之和为多少？给出证明。 四（15分） 已知一棵分类二叉树，其结点数据之值为一正整数。现给定一个正整数，设计一个完整的过程删除设计之值为该正整数的结点并仍保持分类二叉树的特性不变。 五（15分） 以数偶形式给出一个无向图的所有的边并设该无向图的顶点的数据之值为一正整数。比如，输入数偶<1,2>表示数据之值为1及2的两个结点之间有一条无向边。设计一个过程，要求实现：1、以邻接多重表的形式存贮该无向图。2、对该图进行深度为主的遍历（打印结点数据场之值）。
页:
[1]