- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
。
12.影响文件安全性的主要因素有： （41）
，（42）
，（43）
。
13.在为文件分配外空间时，所要考虑的问题主要有：（44）
，（45）
。
14.UNIX 系 统 中 ， 系 统 进 程 上 下 文 包 括 ：（46 ）
和 （ 47 ）
。
15.在UNIX系统中，管道可分为： （48）
和（49）
。
16.在UNIX系统中，为实现请求调页管理，在核心配置了以下四中数据结构：（50）
8. 设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y 的右子树 高度是31，x是y的左孩子。则确定x的后继最多需经过 （17） 中 间结点（不含后继 及x本身） 9. 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、
T3的结点数分别为 n1、n2、n3，则二叉树B的左子树中有 （18） 个结点，右 子树中 有 （19） 个结点。 10. 设有三对角矩阵如下图
置是
（A）A[2i](2i≦n)
（B）A[2i+1](2i+1≦n) (C)A[i/2]
(D)条件不充分，无法确定
5.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度 是
（A）4 （B）5 （C）6 （D）7
6.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S，一个 元素出栈后
，（ 51 ）
，（ 52 ）
，（ 53 ）
。
17.在UNIX系统中，系统向用户提供的用于对进程进行控制的系统调用：（1）fork 用于
（54）
；（2）exec用于（55）
；（3）exit 用于（56）
；（4）wait用于
（57）
；（5）getpid 用于（58）
；（6）nice用于（59）
。
18.LINUX脱胎于（60）
2000 年南京理工大学操作系统考研试题
考生注意：所有答案（包括填空题）按试题顺序写在答题纸上，写在试卷上不给
分。
一、填空题（30分，每题0.5分）
1.操作系统的特征主要有：（1）
，（2）
，(3)
(4)
。
2.操作系统的功能主要有：（5）
，（6）
，（7）
，（8）
，
（9）
。
3.进程的三种基本状态是： （10）
2000 年南京理工大学数据结构考研试题
一．在所给的A、B、C、D中选择一个最确切的（每题1.5分，共33分） 1.下面关于算法说法错误的是 （A）算法最终必须由计算机程序实现 （B）为解决某问题的算法同为该问题编写的程序含义是相同的 （C）算法的可行性是指指令不能有二义性 （D）以上几个都是错误的 2.下面说法错误的是 （1）算法原地工作的含义是指不需要任何额外的辅助空间
a a 11
12
a a a 21
22
23
a a a 32
33
342
...
A=
...
an-1,n a a n,n-1 nn
将带状区域中的元素al,j（│i-j│≤1）放在一维数组B中，则B的大小为 （20） ，元素在B中的位置是 （21） （下标从0开始计）
11. 三维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的 长度是2，则 a[2][3][4]的地址是 （22） 。（设a[0][0][0]的地址是1000， 数据以行为主方式存储）
进程同步机制应遵循的准则是： （13）
，（14）
， （15）
，
（16）
。
5.优先权调度算法的类型有：（17）
，（18）
。
6.产生死锁的必要条件有： （19）
，（20）
，（21）
，
（22）
。
7.程序的链接方法有以下三种：（23）
，（24）
，（25）
。
8.操作系统在设备分配时，考虑的因素主要有：（26）
五、某用户作业进入内存后形成 7 个进程，即 P1，P2，P3，P4，P5，P6，P7。 开始先 执行P1进程，P1结束后可以并发地执行P2，P3，P4三个进程；当P2， P3都结束后才 能执行P5进程，而P4和P5是可以并发执行的；当P4，P5都结 束后才能执行P6和P7两 进程，P6，P7可以并发地执行。当P6，P7都结束后整 个作业执行结束。试用信号量机 制解决上述七个进程的同步问题。（10分）
20设图如右所示，在下面的五个序列中符合深度优先遍历的序列有多少 aebd f c, a c f d
e b, a e d f c b,
a c f d c b,
aefdbc
(A)5个 (B)四个 (C)3个 (D)2个
21.（1）求从指定源点到其余各项点的地杰斯特拉（Dijkstra）最短路径算法中 弧上权
即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容 量至少应该是
（A）6 （B）4 （C）3 （D）2
7.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是
（ A）直接插入 （B）二分法插入 （C）快速排序 （D）归并排序
-2-
8.设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1,1，则T中的 叶子数位 （A）5 （B）6 （C）7 （D）8 9.在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 （A）G中有弧<Vi,Vj> （B）G中有一条从Vi到Vj的路径 （C）G中没有弧<Vi,Vj> （D）G中有一条从Vj到Vi的路径 10.有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据形成二叉排 序树，若 希望高度最小，则应选择下面那个序列输入 （A）45,24,53,12,37,96,30, （B）37,24,12,30,53,45,96 （C）12,24,30,37,45,53,96 （D）30,24,12,37,45，96,53 11.有关二叉树下列说法正确的是 （A）二叉树的度为2 （B）一棵二叉树的度可以小于2 （C）二叉树中至少有一个结点的度为2 （D）二叉树中任何一个结点的度都为2 12.设有一个按个元素的值排好序的线性表，且长度大于2，对给定的值k，分别 用顺序 查找法和二分查找法查找一个与k相等的元素，比较次数分别是s 和b， 在查找不成功 的情况下，正确的s和b的数量关系是 （Ａ）总有ｓ＝ｂ （Ｂ）总有ｓ＞ｂ （Ｃ）总有ｓ＜ｂ （Ｄ）与ｋ值大小有关 １３.下面关于Ｂ树和Ｂ＋树的叙述中，不正确的结论是 （Ａ）Ｂ树和Ｂ＋树都有能有效的支持顺序查找 （Ｂ）Ｂ树和Ｂ＋树都能有效的支持随机查找 （Ｃ）Ｂ树和Ｂ＋树都是平衡的多分树 （Ｄ）Ｂ树和Ｂ＋树都可用于文件索引结构 １４.某二叉树中序列为Ａ，B，C，D，E，F，G，后序序列为B，D，C，A，F，G， E，则前序序列是 （A）E,G,F,A,C,D,B （B）E,A,C,B,D,G,F （C）E,A,G,C,F,B,D （D）上面的都不对 15.上题的二叉树对应的森林包括多少棵树 （A）1 （B）2 （C）3 （D）概念是错误的 16.关于杂凑查找说法不正确的有几个 （1）采用链地址解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的 时间 是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集 （A）1 （B）2 （C）3 （D）4 17设森林F对应的二叉树为B，它有m个结点，B的跟为p，p的右子树结点个 数为n， 森林F中第一棵树的结点个数是 （A）m-n （B）m-n-1 （C）n+1 （D）条件不足，无法确定
计算时间约为10ms，则在图的顶点数为40时，计算时间约为
（4） ms。
4. 向一棵 m 阶 B-树插入操作时，当结点的关键字数为 （5） 则要分裂该结 点；删除
时，结点中关键字数为 （6） 时，可能需要同左或右兄弟合并。
5. 按13，24，37，90，53的次序形成二叉平衡树，则该二叉平衡树的高度是
操作系统。
二、简答题（20分，每题5分）
1.操作系统内核的功能有哪些？
2.进程的创建有哪些步骤？
3.实现虚拟存储管理的方法有哪几种？ 4.进程的死锁（Deadlock）与饿死（Starvation）有什么区别？
三、论述题（30 分，每题 10 分）
1.系统级安全管理主要采取哪些措施？ 2.现代计算机系统，提供给用户的逻辑地址空间都非常大，一般可达2的32次 方到2的64次方，这 样用户进程表所占用的内存相当大，如何解决这个问题？ 3.WindowsNT的环境子系统（EnvironmentSubsystem）主要包括哪些功能模块？
取表中第i个元素的时间与i 无关。
（2）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不
能增加。
（3）静态链表与动态链表在元素的插入、删除上类似，不需做元 素的
移动。
以上错误的是
（A）（1）、（2） （B）（1） C）（1）（2）（3） （D）（2）
4.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维 组 A[1,n]中，则二叉树中第i个结点（）i从1考试用上述方法编号的右孩子在 数组A中位
不能为负的原因在实际应用中无意义
（2）利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n3)
（图用零接矩阵表示）
（3）Floyed 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和 为负的
回路
上面不正确的是
（A）（1），（2），（3） （B）（1）
（C）（1），（3）
（D）（2），（3）
22.（1）在 AOE-网中，减小任一关键活动上的权值后，整个工程的工期也就相 应减
