2008北航计算机三套冲刺模拟题（一）
计算机专业综合(共 7 页)一(本题共 15 分，每题 5 分)
1
铁路进行列车调度时 , 常把站台设计成栈式结构的站台，如右图所示。试问：
(1) 设有编号为 1,2,3,4,5,6 的六辆列车 , 顺序开入栈式结构的站台 , 则可能的出栈序列有多少种 ?
(2) 若进站的六辆列车顺序如上所述 , 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列 , 如果不能 , 说明为什么不能 ; 如果能 , 说明如何得到 ( 即写出 " 进栈 " 或 " 出栈 " 的序列 ) 。
2 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出下图所示二叉树的存储表示。
3 如果一棵树有 n1 个度为 1 的结点 , 有 n2 个度为 2 的结点 , … , nm 个度为 m 的结点 , 试问有多少个度为 0 的结点 ? 试推导之。
二 (本题 10 分)
已知线性表中的元素以值递增有序排列，并以单链表为存储结构。试写一高效算法，删除表中所有值大于 mink 且小于 maxk 的元素(若表中存在这样的元素)，并分析你的算法的时间复杂度(注意： mink 和 maxk 是给定的两个参变量，它们的值为任意的参数)。
三 (本题 15 分)
设散列表为 HT[13], 散列函数为 H (key) = key %13 。用闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
四(本题共 15 分，第一题 9 分，第二题 6 分)
1 证明 { Ø , Ù , Ú , ® } 是联结词的一个完全集。
2 设 A 是由
生成的公式，
与 A 互为对偶式。
证明 ( 1 )若 A 是永真式，则
是永假式。 ⑵ 若 A 是永假式，则
是永真式。
五 (本题共 15 分)
设 A,B 是任意公式，证明公式
是永真式，其中 x 不是 A 的自由变元。
六：简答题(本题共 15 分，每题各 3 分)
1 从物理概念上来说明 P.V 操作中的信号量
2 设备管理中引入缓冲机制的主要原因是什么?
3 按序分配是防止死锁的一种策略，为什么可以防止死锁?
4 覆盖技术与虚拟技术有何本质不同?
5 在固定分区分配会出现何种碎片?为什么?
七：判断题(本题共 10 分，每题各 2 分)
1 系统调用是操作系统与用户程序的接口，库函数也是操作系统与用户程序的接口。( )
2 引入多道程序设计的主要目的为提高实时响应速度( )
3 最佳适应算法的空闲块是按大小递增顺序连在一起( )
4 只要使死锁产生的四个必要条件之一不成立，死锁就不会出现( )
5 原语是由若干条指令组成的程序段，是机器指令的扩充( )
八： ( 本题 15 分 )
在一个分页管理系统中，假如系统分配给一个作业的物理块数为 3 ，并且此作业的页面走向为 2 ， 3 ， 2 ， 1 ， 5 ， 2 ， 4 ， 5 ， 3 ， 2 ， 5 ， 2 。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。
九：填空题(本题 10 分，每个空各 1 分)
1. 如指令中给出形式地址为 D ，则间接寻址方式获得操作数的有效地址为( ) 。
2. 如果说变址寻址方式主要是面向用户的，那么基址寻址一般是面向( ) 的。
3. 在 CPU 的状态寄存器中，常设置以下状态位：零标志位( Z )，负标志位( N )，( ) 和( ) 。
4. 在组合逻辑控制器中，当一条指令取出后，组合逻辑网络的输出分两部分，其主要部分是产生执行该指令所需的( ) ，另一部分送到( ) ，以便在执行步骤较短的情况下，控制下缩短指令的执行时间。
5. 在微程序控制中，一个节拍中所需要的一组微命令，被编成一条( ) 。
6. 系统总线是用来连接( ) 的总线。
7. 输入输出的目的是实现( ) 和( ) 之间的信息传送。
十：(本题共 20 分，第一个题 5 分，第二个题 10 分，第三个题 5 分)
1 有一个 1024K×32 位的存储器，由 128K×8 位的 DRAM 构成。
问：( 1 )总共需要多少 DRAM 芯片。
(2) 采用异步刷新，如果单元刷新间隔不超过 8ms ，则刷新信号周期是多少?
2 CPU 执行一段程序时 , cache 完成存取的次数为 2420 次，主存完成存取的次数为 80
次，已知 cache 存储周期为 40ns ，主存存储周期为 240ns ，求 cache/ 主存系统的效率和平均访问时间。
3 试比较间接寻址和寄存器寻址
十一：(本题 10 分)
已知 CPU 的地址总线 16 根( A15-A0 ， A0 为低位)，双向数据总线 8 根( D7-D0 )，控制总线中与主存有关的信号有 MREQ (允许访存，低电平有效)， R/W (高电平为读命令，低电平为写命令)。
主存地址空间分配如下： 0-8191 为系统程序区，由只读存储芯片组成; 8192-32767 为用户程序区;最后(最大地址) 2K 地址空间为系统程序工作区。上述地址为十进制，按字节编址。现有如下存储器芯片：
EPROM ： 8K × 8 位(控制端仅有 CS )
SRAM ： 16K × 1 位， 2K × 8 位， 4K × 8 位， 8K × 8 位
请从上述芯片中选择适当芯片设计该计算机主存储器，画出主存储器逻辑框图，注意画出选片逻辑(可选用门电路及 3 ： 8 译码器 74LS138 )与 CPU 的连接，说明选哪些存储器芯片，选多少片。 顶！！！ 顶！！！