1996年上海复旦大学数据结构与操作系统考研真题.doc

发布时间：2022-09-15 发布人：admin 分类：说明书资料大小：0.20M 资料格式：doc 举报版权申诉

第1页 / 共4页

1996年上海复旦大学数据结构与操作系统考研真题.doc.pdf-第2页.jpg

第2页 / 共4页

1996年上海复旦大学数据结构与操作系统考研真题.doc.pdf-第3页.jpg

第3页 / 共4页

1996年上海复旦大学数据结构与操作系统考研真题.doc.pdf-第4页.jpg

第4页 / 共4页

文本预览

1996 年上海复旦大学数据结构与操作系统考研真题一、名词解释（10 分） 1.程序状态字 2.可重入程序 3.工作集 4.无限等待二、作业说明书假设并发系统中有 8 个程序 P1，P2….P8 他们之间具有下述的优先关系，试写出相应的并发程序。（10 分）三、一般系统要求以显式打开文件，其目的是什么?有的系统则不必这样，简述这两种方法的优缺点。（10 分）四、丰菲波那契数列由下式所定义∶Fn=1（n=1），Fn=1（n=2），Fn=F（n-1+F（n-2）（n≥3）二叉树 T 的深度 d（T）由下式所定义∶d（T=0 （T 为空二叉树），d（T=max{d（Tl），d（Tr）}+1 （T 为非空二叉树）上式中 TI 和 Tr 分别为 T 的根结点的左、右子树。试证明深度为 d 的平衡二叉树的最少结点个数为 Nd=F（d+2）-1 （10 分）五、对于给定的 n 阶方阵 a[1n，1.n]，我们规定按顺时针盘旋的次序把 a 中的元素依次存放在 b[1.n*m]中（见下图）。如果 a[，j]存放在 b[k]中，那么，请给出求解 k 的计算公式。（10 分）

七、对于给定的线性链表 head，下面的程序过程实现了按结点值非降次序输出链表中的寸。所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在空框处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。（20 分）

八.设 G 是一个用邻接表表示的连通无向图。对于 G 中某个顶点 v，若从 G 中删去顶点 v 及与顶点 v 相关联的边后，G 变成由两个或两个以上非空连通分量所组成的图，则称 v 是原来图 G 的一个关节顶点。如下图中，只有顶点 4 和顶点 6 是关节顶点，而其它顶点都不是关节顶点。试叙述寻找图 G 的所有关节顶点的算法，并用算法语言（PASCAL 或 C）编写一个实现你所给出的算法的程序。（20 分）

分享到：

赞收藏

资料库

1996年上海复旦大学数据结构与操作系统考研真题.doc

相关推荐

考研

热门标签

最新资料