2008北航计算机三套冲刺模拟题（三）
计算机专业综合(共 页)一： (本题共 15 分，每题 5 分)
1 设有一个双端队列，元素进入该队列的顺序是 1, 2, 3, 4 。试分别求出满足下列条件的输出序列。
(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列;
(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列;
(3) 既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。
2 试证明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2 。
3 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索 , 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同 ?
(1) 搜索失败 ;
(2) 搜索成功 , 且表中只有一个关键码等于给定值 k 的对象 ;
(3) 搜索成功 , 且表中有若干个关键码等于给定值 k 的对象 , 要求一次搜索找出所有对象。
二.(本题 10 分)
设计一个将两个带有表头结点的循环链表合并成一个循环线性表的[wiki]算法[/wiki]。
三：(本题 15 分)
按层次顺序 ( 同一层自左至右 ) 遍历二叉树的算法
四 (本题共 15 分，第一题 6 分，第二题 9 分)
1 若公式 A 既不是永真式，也不是永假式，则 A 的每个替换实例一定既不是永真式，也不是永假式。对吗?
2. 证明
联结词集合是极小完全集。
五：(本题 15 分)
设 A 是由
生成的公式。证明： A 是永真式当且仅当每个[wiki]命题[/wiki]变元在 A 中出现[wiki]偶数[/wiki]次。
六：简答题(本题共 15 分，每题各 3 分)
1 进程在系统中有哪几种基本状态，状态如何发生变化?
2 什么是 “ 抢占式优先级调度 ” 和 “ 非抢占式优先级调度 ” ?
3 何谓存储总线?何谓 I/O 总线?各有何特点?
4 进程控制块( PCB )中应该包括哪些内容，其[wiki]作用[/wiki]是什么?
5 微程序控制器如何产生微指令?微指令、微程序与机器指令之间的对应关系如何?
七：判断题(本题共 10 分，每题各 2 分)
1 .进程之间的状态变化，一定在 PCB 中反映出来。( )
2 .当进程完成 I/O 后，进程的状态由等待变为运行。( )
3 .中断屏蔽是不允许发生中断。 ( )
4 .O . S的特征之一为并行性，所谓并行性是指多个进程同时处于运行状态 ( )
5 多道程序的引入，主要是为了提高 CPU 及其它资源的利用率。 ( )
八： ( 本题 15 分 )
在一个同时容纳 4 个进程的操作系统中，假设在一段时间内有 6 个作业提交，提交的时间为：
作业号 提交时间 估计运行时间(分)
Job1 8:00 60
Job2 8:20 35
Job3 8:25 20
Job4 8:30 25
Job5 8:35 5
Job6 8:40 10
系统采用短作业优先的调度算法，作业一旦被调度进入内存后不再中途退出，在内存中的 4 个进程其运行的优先次序取决于当时各进程实际剩余的运行时间。
( 1 )按照所选择的调度算法，分别给出上述 6 个作业执行的时间序列。
( 2 )计算在上述调度算法下，作业的平均周转时间。
九：填空题(本题 10 分，每个空各 1 分)
1 在不改变中断响应次序的条件下，通过 ( ) 可以改变中断处理次序。
1 在常见的微机系统中，磁盘常采用 ( ) 方式与主存交换数据
2 中断接口一般包含 ( ) 、 ( ) 、 ( ) 和控制逻辑基本组成。
3 中断裁决机制： ( ) 、 ( ) 、 ( ) 。
4 在通道程序的控制下，通道对 ( ) 进行数据传输控制。
十：(本题共 20 分，第一个题 5 分，第二个题 10 分，第三个题 5 分)
1 设有一个具有 20 位地址和 32 位字长的存储器，问：
(1) 该存储器能存储多少个字节的[wiki]信息[/wiki]?
(2) 如果存储器由 512k×8 位的 SRAM 芯片组成，需多少片?
2 存储器的层次结构主要体现在什么地方?为什么要分这些层次?计算机如何管理这些层次?
3 某机字长为 32 位，其存储容量是 64KB ，按字编址它的寻址范围是多少?
十一：(本题 10 分)
某 8 位微型机地址码为 18 位，若使用 4K×4 位的 RAM 芯片组成模块板结构的存储器，试问：
( 1 )该机所允许的最大主存空间是多少?
( 2 )若每个模块板为 32K×8 位，共需几个模块板?
( 3 )每个模块板内共有几片 RAM 芯片?
( 4 )共有多少片 RAM ?
( 5 ) CPU 如何选择各模块板?
[[i] 本帖最后由 心在尘世外 于 2008-4-26 11:18 AM 编辑 [/i]] 太棒了