一九九七年度初级程序员级上午试卷
试题1
从供选择的答案中，选出应填入下面叙述中__?__内的最确切的解答，把相应编号写在答卷的对应栏内。
在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是__a__ 排序。每次次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是__b__就组成一个堆，堆排序的平均执行时间和需附加的存储结点分别为__e__。
供选择的答案
a~c： ① 插入 ② 枚举 ③ 交换 ④ 归并
⑤ 基数 ⑥ 选择 ⑦ 希尔
d： ① 20、76、35、23、80、54 ② 20、54、23、80、35、76
③ 80、23、35、76、20、54 ④ 20、35、23、80、54、76
e： ① o（n2）和o（1） ② o（n log2 n）和o（1）
③ o（n log2 n）和o（n） ④ o(n2) t o(n)
试题2
从供选择的答案中，选出应填入下面叙述中__?__内最确切的解答，把相应编号写在答卷的对应栏内。
操作系统中，可以并行工作的基本单位是__a__,__a__ 也是核心调度及资源分配的基本单位，它是由__b__组成的，它与程序的重要区别之一是__c__。当因资源竞争可能会引起死锁时，可以有两种策略对付：__d__和__e__，其中__d__付出的代价较高。
供选择的答案
a： ① 作业 ② 函数 ③ 进程 ④ 过程
b： ① 程序、数据和p c b ② 程序、数据和标识符
③ 程序、标识符和p c b ④ 数据、标识符和p c b
c： ① 程序有状态，而它没有 ② 它有状态，而程序没有
③ 程序可占有资源，而它不可 ④ 它能占有资源，而程序不能
d、e： ① 死锁的避免和预防 ② 修改控制字
③ 死锁的检测和修复 ④ 撤消锁
⑤ 改写config文件 ⑥ 重新启动
试题3
从供选择的答案中，选出应填入下面叙述中__?__内的最确切的解答，把相应编号写在答卷的对应栏内。
关系数据模型是当前最常用的一种基本数据模型，它是用__a__结构来表示实体类型和实体间联系的。关系数据库的数据操作语言（dml）主要包括__b__两类操作，关系模型的关系运算是以关系代数为理论基础的，关系代数最基本的操作是__c__。设r和s为两个关系则r s表示r与s的__d__。若r和s的关系分别图示如下：
r： x y z s: y z w
x y z y z u
u y z y z w
z x u x u y
则r和s自然联接的结果是__e__。
供选择的答案
a： ① 树 ② 图 ③ 网络 ④ 二维表
b： ① 删除和插入 ② 查询和检索 ③ 统计和修改 ④ 检索和更新
c： ① 并、差、笛卡尔积、投影、联接 ② 并、差、笛卡尔积、选择、联接
③ 并、差、笛卡尔积、投影、选择 ④ 并、差、笛卡尔积、除法、投影
d： ① 笛卡尔积 ② 联接 ③ 联接 ④ 自然联接
e：
① ②
x w x y z w
x u x y z u
x w x y z w
u u u y z u
u w u y z w
z y z x u y
③ ④
x y z y z w x y z w
x y z y z u x y z u
x y z y z w x y z w
x y z x u y x x u y
u y z y z u u y z u
u y z y z w u y z w
u y z x u y u x u y
z x u y z u z y z u
z x u y z w z y z w
z x u x u y z x u y
试题4
从供选择的答案中，选出应填入下面叙述中__?__内的最确切的解答，把相应编号写在答卷的对应栏内。
程序语言的语言处理程序是一种__a__。__b__是两类程序语言处理程序，它们的主要区别之一在于__c__。常用的中间代码表示有前缀表示、后缀表示（逆波壮表示）、多元组等，它们都比中缀表示更有利于机器的机械性处理。若算术表达式为：
x+a*(y-b)-z/f
其中的算术运算符遵守先乖除后加减的运算规则。则上述表达式的前缀表示为__d__，后缀表示为__e__。
供选择的答案
a： ① 系统软件 ② 应用软件 ③ 实时系统 ④ 分布式系统
b： ① 高级语言程序和低级语言程序 ② 解释和序和编译程序
③ 编译程序和操作系统 ④ 系统程序和应用程序
c： ① 单用户与多用户的差别 ② 对用户程序的查错能力
③ 机器执行的效率 ④ 是否生成目标程序
d、e： ① +-x*a-yb/zf
② -+x*a-yb/zf
③ -+a*x-ybz/f
④ xayb-*+zf/-
⑤ abxy+*-zf/-
⑥ xayb-*+z/f-
试题5
从供选择的答案中，选出应填入下面叙述中__?__内的最确切的解答，把相应编号写在答卷的对应栏内。
在二叉排序树中，每个结点的关键码值__a__,__b__一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序树，最佳二叉排序树在结构上的特点是__c__.__d__不是二叉排序树，__e__是最佳二叉排序树。
供选择的答案
a： ① 比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
② 比左子树所有结点的关键码值小，比右子树所有结点的关键码值大