全国计算机等级考试四级试题(二)-计算机等级考试

一、选择题:(共90题,分为1分题和2分题,满分120分,除标注2分题外,其它均为1分题。)

(1) 七进制 6656.25变为十进制数的表达式为
　　A．6*74+6*73+5*72+6*71+2*7-1+5*7-2
　　B．6*73+6*72+5*71+6*70+2*7-1+5*7-2
　　C．6*104+6*103+5*102+6*101+2*10-1+5*10-2
　　D．6*103+6*102+5*101+6*100+2*10-1+5*10-2

　　(2) 堆栈存储器存取数据的方式是
　　A．先进先出
　　B．随机存取
　　C．先进后出
　　D．不同于前三种方式

　　(3) 为解决CPU和主存的速度匹配问题,其实现可采用介于CPU和主存之间的 (2分)
　　A．光盘
　　B．辅存
　　C．cache
　　D．辅助软件

　　(4) 下面推理中哪些是正确的? (2分)
Ⅰ.前提: "x(F(x)→G(x) ), $xF(x)
结论: $xG(x)
Ⅱ.前提: $xF(x)→ "y(G(y)→H(y) ), $xL(x)→ $yG(y)
结论: $x(F(x)∧L(x) )→ $yH(y)
Ⅲ.前提: $xF(x), $xG(x)
结论: $x(F(x)∧G(x) )
Ⅳ.前提: $x(F(x)ˇG(x) )
结论: "yF(y)
　　A．Ⅰ与Ⅱ正确
　　B．Ⅲ与Ⅳ正确
　　C．Ⅰ、Ⅱ、Ⅲ都正确
　　D．只有Ⅰ正确

　　(5) 设f:R→R,f(x)=[x],其中R为实数集,[x]为小于等于x的最大整数, 下列哪个命题为真?
　　A．f是单射的,但不是满射的
　　B．f是满射的,但不是单射的
　　C．f是双射的
　　D．f既不是单射的,也不是满射的

　　(6) 设R是集合A={a,b,c}上的二元关系,且R={＜a,a＞,＜b,b＞}, 下列命题中哪些为真?
Ⅰ.R是自反的并且是传递的
Ⅱ.R是对称的并且是反对称的
Ⅲ.R是A上的等价关系
　　A．只有Ⅰ
　　B．只有Ⅱ
　　C．Ⅰ和Ⅱ
　　D．Ⅱ和Ⅲ

　　(7) 以2,2,3,3,1,1,1,1为顶点度数列的所有非同构的无向树的个数为 (2分)
　　A．4
　　B．5
　　C．6
　　D．8

　　(8) 6阶11条边的连通的简单的非同构的非平面图的个数为
　　A．3
　　B．4
　　C．5
　　D．6

　　(9) 设F(x):x为地球上的东西,G(x):x是静止不动的,命题"并不是地球上所有的东西都是静止不动的"的符号化形式中哪些正确?
Ⅰ. "x(F(x)→┐G(x))
Ⅱ. $x(F(x)∧┐G(x))
Ⅲ. ┐"x(F(x)→G(x))
　　A．只有Ⅰ正确
　　B．只有Ⅱ正确
　　C．Ⅰ和Ⅱ都正确
　　D．Ⅱ和Ⅲ都正确

　　(10) 设无向图G=,其中V={v1,v2,v3,v4,v5},E={(v1,v4),(v1,v4),(v4,v4), (v1,v2),(v2,v3),(v3,v4)},下列命题为真的是
　　A．G是欧拉图
　　B．G是哈密尔顿图
　　C．G是平面图
　　D．G是二部图

　　(11) 双链表的每个结点中包括两个指针:link1指向结点的后继结点,link2 指向结点的前驱结点。现要将指针q指向的新结点插入到指针p指向的双链表结点之后,下面的操作序列哪一个是正确的? (2分)
　　A．q↑.link1:=p↑.link1; p↑.link1:=q;
q↑.link2:=p; q↑.link1↑.link2:=q;
　　B．q↑.link1:=p↑.link1; q↑.link2:=p;
q↑.link1↑.link2:=q; p↑.link1:=q;
　　C．q↑.link2:=p; p↑.link1:=q;
q↑.link1:=p↑.link1; q↑.link1↑.link2:=q;
　　D．q↑.link2:=p; q↑.link1:=p↑.link1;
p↑.link1:=q; q↑.link1↑.link2:=q;

　　(12) 下列哪一棵不是AVL树?
(13) 对包含n个元素的散列表进行检过,平均检索长度
　　A．为O(log2n)
　　B．为O(n)
　　C．为O(n2)
　　D．不直接依赖于n

　　(14) 栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?
　　A．E、D、C、B、A、F
　　B．B、C、E、F、A、D
　　C．C、B、E、D、A、F
　　D．A、D、F、E、B、C

　　(15) 在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用二分法查找关键码值12,所需的关键码比较次数为
　　A．2
　　B．3
　　C．4
　　D．5

　　(16) 设有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X),问新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是不列哪个排序算法一趟扫描的结果? （2分）
　　A．起泡排序
　　B．初始步长为4的希尔排序
　　C．二路归并排序
　　D．以第一元素为分界元素的快速排序

　　(17) 在文件系统中,下列关于当前目录(工作目录)的叙述中,不正确的是:
　　A．提高文件目录检索速度
　　B．减少启动硬盘的次数
　　C．利于用全路径名查找文件
　　D．当前目录可以改变

　　(18) 为实现CPU与外部设备并行工作,必须引入的基础硬件是
　　A．缓冲区
　　B．通道
　　C．时钟
　　D．相联寄存器

　　(19) 若文件A的唇ㄕ呦Ｍ运杏没?包括其自身)可读写文件Ａ但不可执行Ａ,可用下列哪一个命令完成?
　　A．chown 777 A
　　B．chown 566 A
　　C．chmod 777 A
　　D．chmod 566 A

　　(20) 对磁盘上的索引文件可能采取的存取方式为:
Ⅰ.顺序存取
Ⅱ.随机存取
　　A．只有Ⅰ
　　B．只有Ⅱ
　　C．Ⅰ和Ⅱ
　　D．都不是

(21) 下面关于存储 管理 的叙述中正确的是:
　　A．存储保护的目的是限制内存的分配
　　B．在内存为M,有N个用户的分时系统中,每个用户占有 M/N的内存空间
　　C．在虚存系统中,只要磁盘空间无限大,作业就能拥有任意大的编址空间
　　D．实现虚存管理必须有相应硬件的支持

　　(22) 用P、V操作可以解决进程间的各种同步和互斥问题,下列说法中哪一个是正确的?
Ⅰ.两个P操作的顺序无关紧要
Ⅱ.用于互斥的P操作应在用于同步的P操作之前
Ⅲ.用于同步的P操作应用于互斥的P操作之前
　　A．只用Ⅰ
　　B．只有Ⅱ
　　C．只有Ⅲ
　　D．都不正确

　　(23) 在UNIX系统中,用于显示当前目录路径名的命令是
　　A．cd
　　B．pwd
　　C．ps
　　D．ls

　　(24) 有关系S(S",SNAME,SEX,AGE),查找年龄大于20岁的学生的姓名和年龄, 用如下的关系代数表达式表示正确吗?(其中π为投影操作符, δ为选择操作符) (2分)
Ⅰ.πSNAME.AGE(δAGE>20(S))
Ⅱ.δAGE>20(πSNAME.AGE(S))
　　A．只有Ⅰ正确
　　B．只有Ⅱ正确
　　C．都正确
　　D．都不正确

　　(25) 设事务T1和T2,对数据库中的数据X进行操作,可能有如下几种情形,请问哪一种情形不会发生冲突操作?
　　A．T1正在读X时,T2也要读X
　　B．T1正在读X时,T2要写X
　　C．T1正在写X时,T2也要写X
　　D．T1正在写X时,T2要读X

　　(26) 使用视图会给系统带来许多优点,但下面的列出的优点中,哪一条不是使用视图的优点?
　　A．提高数据独立性
　　B．提高数据 安全 性
　　C．使操作简便
　　D．减少存储空间

　　(27) Foxpro允许在同一幅屏幕上显示多个窗口,但只有一个窗口是活动的,这个活动窗口是?
　　A．鼠标指针所在的窗口
　　B．窗口的标题以高亮度显示的窗口
　　C．含有主菜单的窗口
　　D．含有对话框的窗口

　　(28) 数据库的安全性是指保护数据库,以防止不合法的使用而造成的数据泄露、更改或破坏,以下列出的措施中,哪一种措施不属于实现安全性的措施? （2分）
　　A．数据备份
　　B．授权规则
　　C．数据加密
　　D．用户标识和鉴别

　　(29) 表示概念模型的有效工具之一是E-R图,考虑下面的E-R图,若转换为关系模式,一般应能转换成多少个关系模式?
　　A．只有一个
　　B．只有二个
　　C．有三个
　　D．有三个以上

　　(30) 在关系数据库中,要求关系中的元组在组成主键的属性上不能有空值。这是遵守:（2分）
　　A．可靠性规则
　　B．安全性规则
　　C．实体完整性规则
　　D．引用完整性规则

　　编辑特别推荐:

　　全国计算机等级考试四级试题(一)

　　全国计算机等级考试四级试题(二)

　　全国计算机等级考试四级试题(三)

　　全国计算机等级考试四级试题(四)

　　(31) 关系R和S定义如下:
C D
36 12
R: S:
A B C
147 258 369

　　执行操作的R S的结果是(其中 为自然连接操作符) (2分)
A B C C D
14 25 36 36 12
 A)
　　B．
A B C D
14 25 36 12
　　
　　C．
　　D．
A B C D
147 258 369 120
C C D
369 360 120

　　 (32) 下面列出的技术中,哪一个(些)是ORACLE RDBMS用来实现分布式数据库管理的?
Ⅰ.位置透明的数据共享
Ⅱ.全局数据库名
Ⅲ.快照技术
Ⅳ.两阶段提交
　　A．只有Ⅰ和Ⅱ
　　B．只有Ⅲ和Ⅳ
　　C．只有Ⅰ
　　D．都是

　　(33) 软件工程方法学的研究内容包含软件开发技术和软件工程管理两部分, 其期望达到的最终目标是
　　A．消除软件危机
　　B．软件开发工程化
　　C．程序设计自动化
　　D．实现软件可重用

　　(34) 软件工程方法中普遍应用的方法之一是结构化生命周期方法(SLC方法),下述哪一个论述不具有SLC方法的主要特征?
　　A．严格定义需求
　　B．划分开发阶段
　　C．规范文档格式
　　D．分析控制流程

　　(35) 数据流图是用于表示软件模型的一种图示方法,在下列可采用的绘制方法中, 哪些是常采用的? （2分）
Ⅰ.自顶向下
Ⅱ.自底向上
Ⅲ.分层绘制
Ⅳ.逐步求精
　　A．全是
　　B．Ⅰ,Ⅲ和Ⅳ
　　C．Ⅱ,Ⅲ和Ⅳ
　　D．Ⅰ和Ⅲ

　　(36) 结构化分析方法是一种预先严格定义需求的方法, 它在实施时强调的是分析对象的
　　A．控制流
　　B．数据流
　　C．程序流
　　D．指令流

　　(37) 软件结构是软件模块间关系的表示, 下列术语中哪一个不属于对模块间关系的描述?
　　A．调用关系
　　B．从属关系
　　C．嵌套关系
　　D．主次关系

(38) 软件开发常使用的两种基本方法是结构化方法和原型化方法,在实际应用中,它们之间的关系常表现为 （2分）
　　A．相互排斥
　　B．相互补充
　　C．独立使用
　　D．交替使用

　　(39) 原型化方法是一类动态定义需求的方法,下列叙述中,哪一个不具有原型化方法的特征?
　　A．提供严格定义的文档
　　B．加强用户参与和决策
　　C．简化项目 管理
　　D．加快需求的确定

　　(40) 评审是对软件进行静态测试的一种方法,下述结论中,哪个是与软件评审无关的内容?
　　A．尽量发现错误
　　B． 检查 软件文档
　　C．根据评审标准
　　D．依靠测试信息

　　(41) 软件维护软件得以正常运行的重要环节,按照软件工程方法的理解,一般软件维护应该开始于
　　A．阅读设计文档
　　B．理解程序代码
　　C．分析软件结构
　　D．查阅测试记录

　　(42) 按照Ｍyers的说法,计算机系统分为若干层次。我们通常所指的体系结构是指
　　A．逻辑门体系结构
　　B．微代码体系结构
　　C．操作系统体系结构
　　D．指令集体系结构

　　(43) 根据操作数在CPU中的暂存机制可以对它进行分类,大家熟悉的Intel80X86系列就属于
　　A．堆栈型
　　B．累加器型
　　C．寄存器型
　　D．通用寄存器与累加器混合型

　　(44) 在指令码的优化中,能使平均码长最短的方法是
　　A．哈夫曼编码
　　B．曼彻斯特编码
　　C．等长码
　　D．等长扩展码

　　(45) 在cache的地址映射中,凡主存中的任意一块均可映射到cache 内的任意一块的位置上,这种方法称为
　　A．全相联映射
　　B．直接映射
　　C．组相联映射
　　D．混合映射

　　(46) 通道是重要的I/O方式,其中适合连接大量终端及打印机的通道是
　　A．数组多路
　　B．选择通道
　　C．字节交叉多路
　　D．字节突发多路

　　(47) 在Benchmark中,Whetstone属于
　　A．实程序
　　B．核心程序
　　C．简单基准程序
　　D．复合基准程序

　　(48) 某台计算机的速度比改进前提高了10倍,但它仅在50％的时间内可用,这样一来它的总加速比为 (2分)
　　A．5
　　B．1.4
　　C．1.8
　　D．0.5

　　(49) 数据流计算机开拓并行性的基础是 (2分)
　　A．同步性和函数性
　　B．异步性和函数性
　　C．同步性和自发性
　　D．异步性和自发性

　　(50) 在高速并行结构中,速度最快但通用性最差的是 (2分)
　　A．相联处理机
　　B．数据流处理机
　　C．阵列处理机
　　D．专用多功能单元

　　(51-53) 答案中给出了四种描述(或定义)与相应术语之间的对应关系,请指出哪一组对应关系是正确的。

　　(51) 描述: (2分)
a.信号的频率范围,在计算机 网络 中也用来表示数据传输速率。
b.一个周期性函数可以表示为无数不同振幅、频率与相位的正（余）弦函数之和。
c.信道容量是带宽与信噪比的函数。
d.最大信号传输速率（bps）是信道带宽（Ｈz）数值的两倍。
术语：
1.傅里叶(Fourier) 原理 2.带宽 3.Nyguist准则 4.Shannon定律
描述 术语
a 1
b 2
c 3
d 4
描述 术语
a 2
b 4
c 1
d 3
　　A．
　　B．
　　
描述 术语
a 2
b 1
c 4
d 3

　　C．
　　D．
描述 术语
a 2
b 1
c 3
d 4

　　(52) 描述: (2分)
a. 一种高性能的光纤令牌环网, 它的数据传输速率为100Mbps, 覆盖范围是200KM,可以连入的结点为1000个。
b. 这种网络保持着Ethernet的帧结构、接口与MAC方法等特点， 只是将每个比特的发送时间由100ns减少为10ns。
c. 这种网络将所有传送的信息都以短的、固定长度的信元(cell)形式发送。每个信元长度为53字节。这种网络是面向连接的，并且具有极高的数据传输速率。
d. 这种网络用于一个城市范围内的多个LAN的互连，它使用IEEE 802.6 协议。
术语：
1.FDDI 2.ATM 3.Fast Ethernet 4.DQDB
描述 术语
a 1
b 3
c 2
d 4
描述 术语
a 1
b 3
c 4
d 2
　　A．
　　B．
描述 术语
a 1
b 2
c 4
d 3

　　C．
　　D．
描述 术语
a 2
b 1
c 4
d 3

　　(53) 描述: (2分)
a. 这是一种只能放大或再生微弱信号的低层设备，可以用来驱动长的传输介质。
b. 这是一种存储转发设备，它能接收、过滤和转发不同 网络 进入的数据链路层的帧。
c. 这种设备在概念上与网桥相似，但它工作在网络层。它能将一条线路上进入的分组接收后转发到另一条线路上，这些线路可以属于不同的网络，并且使用不同的协议。
d. 这种设备可以将两个不同协议的网络应用层中的应用连接起来。
术语：
1. application gateway 2.bridge 3.repeater 4.multiprotocol router
描述 术语
a 1
b 4
c 3
d 2
描述 术语
a 3
b 2
c 1
d 4
　　A．
　　B．
 描述 术语
a 3
b 4
c 2
d 1

　　C．
　　D．
描述 术语
a 3
b 2
c 4
d 1

　　(54) OSI参考模型的三个主要概念是：
　　A．architecture,model,and switch
　　B．subnet,layer,and primitives
　　C．service,interface,and protocol
　　D．WAN,MAN,and LAN

　　(55) HDLC是一种具有编码透明性特点的协议。它不需要采用特殊编码去解释链路控制命令。这是由于它采用了比特插入与删除技术。根据HDLC协议，0 比特插入的范围是
　　A．帧的所有域
　　B．帧的信息域
　　C．除了标志(Ｆ)之外的其它域
　　D．除了帧校验序列(FCS) 之外的其它域

　　(56) 一种服务是通过一组特定的原语来实现的。服务可以分为确认(confirm) 与不确认( unconfirm) 两类。 在确认服务( confirm service) 中， 对应的原语是request、indication、response与confirm。不确认服务(unconfirm service) 相应的原语应该是
　　A．request,indication
　　B．request,response
　　C．request,indication,response
　　D．request,indication,confirm

　　(57) 假设一种简单的情况：一台在Internet上的主机要向另一台遵循OSI 协议标准的主机发送IP分组。OSI数据报协议(CLNP)是基于IP协议的。问题是IP 分组的报头带有一个32位的目的主机的Internet地址。OSI主机不能直接处理32 位的Internet地址。为了使两台主机能够通信，我们应该选择的网络互连设备是
　　A．repeater
　　B．bridge
　　C．multiprotocol router
　　D．switch

　　(58) 802.3协议的每个版本都规定了每个缆段的最大电缆长度,为了增加电缆长度。可以通过repeater将多个缆段连接起来，对于软件来说，由repeater连接的多个缆段
　　A．与单个缆段没什么不同
　　B．与单个缆段是不同的
　　C．构成了多个Ethernet网
　　D．构成了一个互连的LAN

　　(59) 大多数局域网在数据链路层提供的是
　　A．面向连接确认服务
　　B．无连接不确认服务
　　C．面向连接不确认服务
　　D．网络服务

　　(60) TCP/IP 模型的传输层有两个协议，第一个协议TCP是一种可靠的面向连接的协议，第二个协议UDP(User Datagram Protocol)是
　　A．一种可靠的面向连接的协议
　　B．一种不可靠的面向连接的协议
　　C．一种可靠的无连接协议
　　D．一种不可靠的无连接协议 　　(61) There are several periods in a computer，the shortest period is
　　A．Instruction period
　　B．Machine period
　　C．Beat period
　　D．CPU period

　　(62) Which set is empty?
　　A．｛xx is a real number and x2=9 B)｛xx is a real number and x2-1=0｝
C)｛xx is a real number and x2+1=0｝ D)｛xx is a real number and x=2x+1｝

　　(63) What is the relation represented in the exhibit shown below?
　　A．R={(1,2),(1,3),(1,4),(1,5)}
　　B．R={(1,1),(2,2),(3,3),(4,4),(5,5)}
　　C．R={(1,2),(1,3),(1,4),(2,3),(4,1),(4,5),(5,5)}
　　D．R={(1,2),(1,3),(1,4),(2,2),(2,3),(4,1),(4,4),(4,5)}

　　(64) What is the contrapositive of the following implication?“If it is raining，then I get wet.”
　　A．If I get wet，then it is raining.
　　B．If I am wet ，then if is raining.
　　C．If it is not raining, I do not get wet.
　　D．If I do not get wet，then it is not raining.

　　(65) Which property does R posses? (2 grades)
Let A={1,2,3,4} and let R ={<1,2>,<2,2>,<3,4>,<4,1>}
　　A．Symmetry
　　B．Reflexivity
　　C．Asymmetry
　　D．Antisymmetry

　　(66) When walking a tree, which traversal method yields a prefix, or Polish,form?
　　A．lnorder
　　B．Preorder
　　C．Postorder
　　D．Reorder

　　(67) ln the following statements about graph operations, which one is NOT correct?
(2 grades)
　　A．Spanning tree of a graph may not be unique.
　　B．Minimum spanning tree of a graph may not be unique.
　　C．Finding critical path is an operation on directed graph.
　　D．Finding critical path is an operation on undirected graph.

　　(68) Which traversal method for a binary tree does the following Pascal code illustrate? (2 grades)
procedure traverse(p:pointer);
begin
if p<>nil
then begin
traverse(p↑.left);
process(p);
traverse(p↑.right)
end
end;
　　A．lnorder
　　B．Preorder
　　C．Postorder
　　D．Reorder

　　(69) What storage scheme does MS-DOS use for storing files on a disk?
　　A．I-nodes
　　B．a linked list allocation
　　C．a continuous allocation
　　D．a linked list with index

　　(70) Which of the followings is NOT a condition for deadlock?
　　A．Starvation
　　B．Circular Wait
　　C．No Preemption
　　D．Mutual Exclusion

　　(71) Assume that an operating system uses a round-robin scheduler. The process’s quantum is 20 msec,and the context switch is 5 msec. What percentage of the CPU’s time is spent on administrative overhead? (2 grades)
　　A．5％
　　B．15％
　　C．20％
　　D．25％

　　(72) What state is a process in when it can’t run because it needs a resource to become available? (2 grades)
　　A．Ready
　　B．Interrupt
　　C．Blocked
　　D．Running

　　(73) The following sectors are requested from the disk:
11,1,36,16,34,9,12
What is the order of the sector reads if you are using the elevator algorithm?
(2 grades)
　　A．1,9,11,12,16,34,36
　　B．11,1,36,16,34,9,12
　　C．11,12,9,16,1,34,36
　　D．11,12,16,34,36,9,1

　　(74) What is the candidate key of a relational database?
　　A．A field with a constraint placed on it.
　　B．A set of fields that have no data in them.
　　C．A set of fields in a table used to identify a record uniquely.
　　D．Fields from multiple tables that are used for sorting records.

　　(75) What Normal From is the table shown in the exhibit? (2 grades)

　　emps tbl
emp_idemp_nameemp_phonedept_namedept_phonedept_mgrname
(1) emp_id→emp_name, emp_phone, dept_name(2) dept_name→dept_phone, dept_mgrname

　　A．1NF
　　B．2NF
　　C．3NF
　　D．BCNF

　　(76) Which operating system can Oracle database NOT be used in?
　　A．DOS
　　B．UNIX
　　C．Windows95
　　D．IBM Mainframes

　　(77) Which values are NOT permitted to be part of the primary key?
　　A．NULL
　　B．punctuation
　　C．special characters
　　D．alpha-numeric characters

　　(78) Which phase of the software engineering process results in the Software Requirements Specification?
　　A．definition phase
　　B．engineering phase
　　C．maintenance phase
　　D．development phase

　　(79) When drawing multilevel data flow chart of top-down, the balance between parent chart and son chart must be taken into account, and to pass judgment for the balance of the charts is regularly maintained by (2 grades)
　　A．Output data
　　B．Data dictionary
　　C．Processing number
　　D．Input data

　　(80) Which is the strictest form of cohesion?
　　A．logical
　　B．functional
　　C．procedural
　　D．coincidental

　　(81) Which is NOT a concept of White Box Testing? (2 grades)
　　A．You should execute all loops at their boundary conditions.
　　B．You should execute all interfaces at their boundary conditions.
　　C．You should execute all logical decisions on their true and false sides.
　　D．You should execute all independent paths within a module at least once.

　　(82) Prototyping method is a dynamic design process, it requires people who use prototyping method should have the following capability
　　A．Proficient program expertise
　　B．Immediately acquire requirement
　　C．Coordinate & organize eloquently
　　D．Handle tools smartly

　　(83) There are two styles in the evolution of instruction set , that is CISC and RISC. Which chip belongs to the RISC?
　　A．i APX 432
　　B．VAX-11/780
　　C．Motorola 68000
　　D．Power PC

　　(84) In advanced PC bus or local bus, which one has the fastest data throughput?
　　A．ISA
　　B．PCI
　　C．MCA
　　D．EISA

　　(85) There are many methods in the CPETT(short for Computer Performance Evaluation Tools and Techniques). One of them is the method that runs a Kernel as the load of a computer. So we call it
　　A．Monitor method
　　B．Benchmark method
　　C．Model method
　　D．Physical method

　　(86) There are two common types in page replacement algorithm: stack and non-stack strategies. When a real page number increase only stack algorithm can increase the hit rate monotonously. In the following replacement algorithm,which one belongs to non-stack strategy?(2 grades)
　　A．FIFO
　　B．LRU
　　C．PFF
　　D．OPT

　　(87) What binary number is encoded with Differential Manchester in the diagram below? (2 grades)
　　A．10110011100
　　B．11001100011
　　C．11000110010
　　D．00111001101

　　(88) Each host or router on the Internet has its own IP address. There are four IP addresses as followings. Which IP address is erronedus?
　　A．189.132.2.1
　　B．255.255.255.0
　　C．198.73.265.50
　　D．192.0.0.3

　　(89) When should Frequency Division Multiplexing be used?
　　A．when the attenuation on a medium is greater than 25％.
　　B．when the white noise on the medium exceeds 50％ of the medium’s bandwidth
　　C．when the achievable data rate of the medium exceeds the data rate of the digital signals to be transmitted
　　D．when the useful bandwidth of the medium exceeds the required bandwidth of the digital signals to be transmited

　　(90) The universe of hypertext servers that allow text, graphics, sound, and other multimedia files to be viewed togather and navigated via hypertext links. It is now the fastest growing area of the Internet. It is
　　A．Gopher
　　B．WWW
　　C．E-mail
　　D．FTP 二、论述题（两个论述题可任选其一，并只选其一，多选无效，满分30分。）
论述题１
本题要求设计一个学生试卷成绩输入、查询和成绩单输出系统(简称SRS)的数据结构和算法要点。问题描述如下：
要输入到SRS 系统中的每一份试卷成绩反映一个学生选修一门课程的考试结果，它包括以下数据项：学号、姓名、课程名、成绩。由于实行了灵活的选课制度，所以每个学生选修多少门课程，选修哪些课程都可以不同。要输入的多份试卷成绩并未按任何数据项排列顺序，它们以任意的顺序被输入到系统中来。
SRS系统要具有以下功能：①试卷成绩插入，将试卷成绩逐个插入到SRS系统的数据结构中。②学生成绩查询，给出学号查找该学生所选修的各门课程的考试成绩。③成绩单输出，按学号递增的顺序依次输出所有学生的学号、姓名，及其所选修的各门课程的课程名和成绩。（为简单起见，假设上述所有工作都在计算机内存中进行。）
请设计SRS系统的数据结构和算法要点，使上述三项操作都有较高的执行效率。从以下方面阐述你的设计：
(1) SRS系统的数据结构（15分）
①数据结构的Pascal语句描述
②数据结构的示意图
③数据结构的简单文字说明
(2) SRS系统的算法要点（10分）
（只要简单的文字说明，不必写出Pascal程序）
①试卷成绩插入
②学生成绩查询
③成绩单输出
(3) 简单陈述你的上述设计的理由（5分）
论述题２
在一个盗窃案件中，已知下列事实：
①甲或乙是窃贼。
②若甲是窃贼，做案时间不会发生在夜间12点钟以前。
③若乙的证词正确，在夜间12点钟时被盗物品所在房间灯光未灭。
④若乙的证词不正确，则做案时间发生在夜间12点钟以前。
⑤夜间12点钟被盗房间灯光灭了。
根据以上事实解答或论证以下各题：
(1) 将①～⑤中所出现的简单命题符号化，然后用命题符号写出①～⑤各复合命题的符号化形式。(10分)
(2) 以(1)中给出的5个复合命题为前提，判断甲、乙二人谁是窃贼(以符号形式给出)。(5分)
(3) 用命题逻辑推理理论写出(2)中结论的判断过程(要求写出每一步所用的推理规则)。(15分)

1997年全国 计算机等级 考试四级笔试试卷
答案及评分标准
一、选择题:(共90题,分为1分题和2分题,满份120分。带“*”的题为2分题，其余均为1分题。)
 1.B 2.C * 3.C * 4.A 5.D 　
 6.B * 7.B 8.B 9.D 10.C 　
* 11.C 12.B 13.D 14.C 15.C 　
* 16.D 17.C 18.B * 19.D 20.C 　
 21.D 22.C 23.B * 24.C 25.A 　
 26.D 27.B * 28.A 29.C * 30.C 　
* 31.A 32.D 33.B 34.D * 35.B 　
 36.B 37.D * 38.B 39.A 40.D 　
* 41.C 42.D 43.D 44.A 45.A 　
 46.C 47.D * 48.C * 49.B * 50.D 　
* 51.C * 52.B * 53.D 54.C 55.C 　
 56.A 57.C 58.A 59.B 60.D 　
 61.B 62.C 63.D 64.D * 65.D 　
 66.B * 67.C * 68.A 69.C 70.A 　
* 71.C 72.C * 73.D 74.C * 75.B 　
 76.A 77.A 78.A * 79.B 80.B 　
* 81.B 82.B 83.D 84.B 85.B 　
* 86.A * 87.B 88.C 89.D 90.B 　
二、论述题(两个论述题可任选其一,并只选其一,多选无效,满分30分)
论述题1评分参考：
本题可有多种不同的设计方案，下面给出其中一个较好的方案。
(1) 数据结构（15分，其中对三种操作的有效支持各4分，叙述的条理性3分。）
① 数据结构的Pascal语句描述
TYPE pptr=↑pnode;
 pnode=RECORD
 cname:string;
 score:0..100;
 next:pptr
 END;
 sptr=↑pnode;
 snode=RECORD
 sno:integer;
 sname:string;
 llink,rlink:sptr;
 plink:pptr
 END;
VAR t:sptr;
 ② 数据结构的示意图
 ③ 数据结构的简单文字说明
每个学生结点包含学生的学号和姓名，所有学生结点组织成一棵二叉排序树，用link-rlink法存储。
每份试卷成绩作为一个链表结点，包含课程名和成绩，每个学生的所有试卷成绩结点链接成一个单链表，并且二叉排序树的学生结点中有一个指针指向该单链表的第一个结点。
（2） 算法要点（10分，三种操作各3分，叙述的条理性1分）
① 试卷成绩插入，根据试卷的学号在二叉排序树中查找该学生结点。若找到，则在该学生结点所指的成绩链表中插入一个成绩结点；若未找到，则先在二叉排序树中插入一个新的学生结点，然后再往这个学生结点所指的（空的）成绩链表中插入一个成绩结点。
② 学生成绩查询，根据所给学号在二叉排序树中查找该学生结点，再在该结点所指的成绩链表中沿着指针读出所有成绩。
③ 成绩单输出。对二叉排序树进行对称序周游，在访问到每个学生结点时输出该结点指向的成绩链表中的所有成绩。
（3） 设计理由（5分）
① 学生结点组织成二叉排序树，使三种操作都有较高的效率:插入n个学生结点O(nlog2n),查找一个学生结点O(log2n),输出所有学生结点O(n)。
② 每个学生的所有成绩结点组织成链表，动态 申请 空间，适合于每个学生选修的课程数不等的实际情况，节省空间。
 论述题2评分参考：
本题考查考生是否具有较强的逻辑思维和逻辑推理能力，并且考查考生是否掌握了逻辑推理的主要步骤和推理规则。
（1） 的要点：考查考生命题符号化能力。（1）中含5个简单命题：
 p:甲是窃贼，
 q:乙是窃贼，
 r：做案时间发生在夜间12点钟以前，
 s:乙的证词正确，
 t:夜间12点钟被盗房间灯光未灭。
 （1）中含5个复合命题：
 p∨q, p→┐r, s→t, ┐s→r, ┐t,每个复合命题2分，（1）的分值为10。
（2） 的要点：考查考生逻辑思维能力。结论为乙是窃贼，符号化形式为q。(2)的分值为5。
（3） 的要点：考查考生逻辑推理步骤和规则的掌握情况，整个推理由下面9步组成
① s→t 前提引入
② ┐t 前提引入
③ ┐s ①②拒取式规则
④ ┐s→r 前提引入
⑤ r ③④假言推理
⑥ p→┐r 前提引入
⑦ ┐p ⑤⑥拒取式规则
⑧ p∨q 前提引入
⑨ q ⑦⑧析取三段论
每步1到2分，（3）的分值为15。