一、填空题(每空 2 分，共 36 分)
1. 处理机高级调度又称__________或长程调度，其调度对象是________。
2. 在段页式系统中(无快表)，为获得一条指令或数据，都需三次访问内存： 第一次从内存中取得______________;第二次从内存中取得________;
第三次从内存中取得指令或数据。
3. 所有同步机制都应遵循下述四条准则：__________、忙则等待、有限等 待、___________。
4. 在操作系统环境下，进程对资源共享的方式主要有__________方式和
___________方式。
5. 后缀表达式 3 2 * 4 – 5 6 3 / * + 的值为_____，表达式 c*(b+2)+(2-a)/3 对 应的后缀表达式为____________________。
6. 用链式存储结构实现二叉树，每个结点除数据域外还包含指向左右子结 点的链接指针，在这种存储结构下，n 个结点的二叉树共有______个指 针域，其中________个指针域存放了地址，而________个指针域存放的 是空指针。
7. 无向图的遍历过程中，选择出发顶点 v0 的次数等于该图的_________的 个数。
8. 线索二叉树是利用结点中的空闲字段来记录__________次序的二叉树。
9. 设有三对角矩阵 (aij)n×n (1≤i, j≤n)，将其三条对角线上的元素逐行地存于 数组 B[3n-2]中，使得 B[k]= aij，数组下标从 0 开始，则用 i, j 表示 k 的下 标变换公式为 k =________，用 k 表示 i, j 的下标变换公式为 i =_______， j =_________。
二、判断下列说法的正误，并纠正其中错误的说法(每小题 3 分，共 18 分)
1. 在使用优先级进程调度策略时，不存在高优先级进程等待低优先级进程 的情况。
2. 处于同一个进程中的多个线程，CPU 寄存器对于每个线程来说是私有的。
3. 从一个小根堆中查找具有给定键值的元素，在最坏情况下需要 lgn 次比 较操作。
4. Huffman 树的结点个数一定是偶数。
5. 在一个包含 n 个元素的线性表中查找指定元素，采用折半查找比采用顺 序查找所需时间少。
6. 广义表 (a, (b, c)) 的表头是 a，表尾是 (b, c)。
三、简答题(每小题 5 分，共 30 分)
1. 进程控制块(PCB)中的进程控制信息主要包括哪些内容?
2. 简述多道批处理系统的优缺点。
3. 简述操作系统的主要任务和功能。
4. 假设 fork()调用成功，则下面的程序可能的输出有哪些?
main() { int pid;
pid = fork(); printf(“%d, ”, pid);
}
5. 一个用高级语言编写的程序在计算机上运行时所消耗的时间一般取决于 哪些因素?什么是算法的时间复杂度?
6. 画出和下列已知访问序列对应的森林： 森林的先序次序访问序列为：NHMCLIBKDFJEAG; 森林的中序次序访问序列为：MCHLNBIFDJAGEK。
四、(8 分)试编写算法，计算 i!·2i (i=0,1,…,n-1) 的值并依次存入整数数组 a[MAXSIZE]中。假设计算机中允许的最大整数为 MAXINT。
五、(16 分)求证：若一棵二叉树的先序序列是 u1 , u2 , , un ，则其中序序列是 u p1 , u p2 , , u pn 当且仅当序列1,2, , n 可通过一个栈得到序列 p1 , p2 , , pn 。
六、(12 分)假设以三元组 (F, C, L/R) 的形式输入一棵二叉树的各条边(其中 F 表示父结点标识，C 表示子结点标识，L/R 表示 C 为 F 的左子结点或右子 结点)，且在输入的三元组序列中，C 是按层次顺序出现的。设结点的标识 是字符类型。F=’^’时 C 为根结点标识，若 C 也为’^’，则表示输入结束。试 根据上述信息完成下列各题。
1. (4 分)已知一组有效的三元组输入序列为：^AL ABL ACR BDL BER CFR EGL EHR FIL ^^L，请画出其所对应的二叉树;
2. (8 分)试编写算法，由输入的三元组序列建立二叉树的二叉链表。
七、(12 分)现有如下两个并发进程在一个单处理器系统上运行：
P1: {P2: {
shared int x;shared int x;
x = 10;x = 10;
while (1) {while (1) {
x = x - 1;x = x - 1;
x = x + 1;x = x + 1;
if (x != 10)if (x != 10)
printf("x is %d",x);printf("x is %d",x);
}}
}}
两个进程分时占用处理器使得各自语句交替执行。而在描述进程的源语言 中，“x = x – 1”和“x = x + 1”并非原子操作，它们各由三条指令完成， 用汇编语言描述如下：
x = x + 1:
LDR0, X/* 将数据从 X 内存位置加载到寄存器 R0 */
INCRR0/* R0 值增 1 */
STRR0, X/* 将 R0 中的值存回 X 内存位置 */
x = x - 1:
LDR0, X/* 将数据从 X 内存位置加载到寄存器 R0 */
DECRR0/* R0 值减 1 */
STRR0, X/* 将 R0 中的值存回 X 内存位置 */
根据上述信息完成下列各题：
1. (3 分)写出一个可能的语句执行序列，直到打印出"x is 10";
2. (5 分)写出一个可能的语句或原子指令执行序列，直到打印出"x is 8";
3. (4 分)利用信号量机制修改上述并发进程 P1 和 P2，使得 printf()永 远得不到执行。
