计算机专业综合(共 6 页)
一： (本题共 15 分，每题 5 分)
1 试证明：若借助栈可由输入序列 1, 2, 3, …, n 得到一个输出序列 p1, p2, p3, …, pn ( 它是输入序列的某一种排列 ) ，则在输出序列中不可能出现以下情况，即存在 i < j < k ，使得 pj < pk < pi 。 ( 提示：用反证法 )
2
列出右图所示二叉树的叶结点、分支结点和每个结点的层次
3 试分别找出满足以下条件的所有二叉树：
(1) 二叉树的前序序列与中序序列相同;
(2) 二叉树的中序序列与后序序列相同;
(3) 二叉树的前序序列与后序序列相同。
二：(本题 10 分)
已知线性表中的元素以值递增有序排列，并以单链表为存储结构。试写一高效的
算法，删除表中所有值相同的多余元素(使得运算后的线性表中所有元素的值均不相同)，并分析你的算法的时间复杂度。
三：(本题 15 分)
编写递归算法判别给定二叉树是否为完全二叉树，是则返回 1 ，否则返回 0 。分析：基于按层次顺序遍历的搜索策略较为适宜，设一个布尔数组记录访问过的结点。
四(本题共 15 分，第一题 9 分，第二题 6 分)
1 证明 { Ø , ® }, { Ø , Ù } 和 { Ø , Ú } 都是联结词的完全集
2 证明 (P ® Q) ∨ ¬(P ® Q) 为永真式.
五(本题 15 分)
归纳证明：若 t 是项， A 是公式，则
也是公式。
六：简答题(本题共 15 分，每题各 3 分)
1 什么是按序分配?
2 交换技术与虚存中使用的调入调出技术有何相同与不同之处?
3 如何实现设备独立性?
4 引起 “ 进程切换 ” 的时机有哪些?
5 进程具有哪些基本特征?
七：判断题(本题共 10 分，每题各 2 分)
1 系统调用是操作系统与外界程序之间的接口，它属于核心程序.在层次结构设计中，它最靠近硬件。( )
2 引入进程可以改善系统的资源利用率、提高吞吐量，但增加了系统的空间和时间开销。( )
3 在没有虚存的系统中，采用覆盖技术就可以利用较小的存储空间处理较大的程序。( )
4 文件目录必须常驻内存。( )
5 进程从一个状态到另一个状态的转换，都是靠使用不同的原语来实现的。 ( )
八： ( 本题 15 分 )
兄弟俩共同使用一个存折 amount 初值为 0 ，每次限存或取 10 元，存钱与取钱的进程分别为：
存钱 取钱
m 1 amount m 2 amount
m 1 m 1 +10 m 2 m 2 -10
amount m 1 amount m 2
由于兄弟俩可能同时存钱或取钱，因此两个进程是并发的，若哥哥先存了两次钱，但在第三次存钱的时候，弟弟正在取钱，请问最后存折上可能出现的值?如何用 P.V 操作实现两并发进程的互斥执行?
九：填空题(本题 10 分，每个空各 1 分)
1 .微指令格式可分为( )和( )两类，其中( )用较长的微程序结构换取较短的微指令结构。
2 .对 1/O 数据传送的控制方式，可分为：( )方式、( )方式、( )方式、( ) 方式等 。
3 采用 DMA 方式传送数据是由 DMA 接口来控制数据在( )和( )之间传输。
4 通道程序在内存中的首地址由( )给出。
十：(本题共 20 分，第一个题 5 分，第二个题 10 分，第三个题 5 分)
1 有一个16 K×16 位的存储器，由 1K×4 位的 DRAM 芯片构成(芯片是 64×64 结构)。问：
(1) 共需要多少 RAM 芯片?
(2) 存储体的组成框图
1 Cache 做在 CPU 芯片内有什么好处?
2 假设某计算机指令长度为 20 位，具有双操作数、单操作数、无操作数三类指令格式，每个操作数地址规定用 6 位表示。 问：若操作码字段固定为 8 位，现已设计出 m 条双操作数指令， n 条无操作数指令，在此情况下，这台计算机最多可以设计出多少条单操作数指令?
十一：(本题 10 分)
说明总线结构对计算机系统性能的影响。
