1999年度高级程序员上午试卷
/uploads/soft/1_080827113659.doc
试题1
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
给定结点的关键字序列（F、B、J、G、E、A、I、D、C、H），对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同。但中间结果是不同的。
Shell排序的第一趟扫描（步长为5）结果应为＿A＿。
冒泡排序（大数下沉）的第一趟起泡的效果是＿B＿．
快速排序的第一趟结果是＿C＿。
二路归并排序的第一趟结局是 ＿D＿。
若以层次序列来建立对应的完全二叉树后采用筛选法建堆，其第一趟建的堆是＿E＿。
供选择的答案：
A：①（B、F、G、J、A、D、I、E、H、C） ②（B、F、G、J、A、E、D、I、C、H）
③（A、B、D、C、E、F、I、J、G、H） ④（C、B、D、A、E、F、I、G、J、H）
B：①（A、B、D、C、F、E、I、J、H、G） ②（A、B、D、C、E、F、I、H、G、J）
③（B、F、G、E、A、I、D、C、H、J） ④（B、F、G、J、A、E、D、I、C、H）
C：①（C、B、D、A、F、E、I、J、G、H） ②（C、B、D、A、E、F、I、G、J、H）
③（B、A、D、E、F、G、I、J、H、C） ④（B、C、D、A、E、F、I、J、G、H）
D：①（B、F、G、J、A、E、D、I、G、H） ②（B、A、D、E、F、G、I、J、H、C）
③（A、B、D、C、E、F、I、J、G、H） ④（A、B、D、C、F、E、J、I、H、G）
E：① ②
③ ④
试题2
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
给定数据结构（V，E），V为结点的有限集合，V＝｛V1，V2，V3，V4，V5，V6，V7，V8｝，E是V上关系的集合。
E＝｛<V1，V2>，<V3，V4>，<V5，V8>，<V5，V6>，<V1，V3>，<V4，V7>，<V4，V5>，<V2，V4>，<V4，V6>｝它所对应的图形是 _A_ ，这是 _B_ 。
图的存储结构主要有邻接表和 _C_ ，若用邻接表来存储一个图，则需要保存一个 _D_ 存储的结点表和若干个 _E_ 存储的关系表（又称边表）。
供选择的答案：
A：① ②
③ ④
B：① 树 ② 无向图 ③ 有向图 ④ 无向图
C：① 转移矩阵 ② 邻接矩阵 ③ 状态矩阵 ④ 优先矩阵
D：① 顺序 ② 链接 ③ 散列 ④ 分块
E：① 顺序 ② 链接 ③ 散列 ④ 索引
试题3
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
假设某程序语言的文法如下：
S → S ａ T ∣ T
T → T b R ∣ R
R → P d R ∣ P
P → f S g ∣ e
其中：VT＝｛a，b，d，e，f，g ｝；VN＝｛S，T，R，P｝；S是开始符号。那么，此方法是_A_方法。这种文法的语法分析通常采用优先矩阵，优先矩阵给出了该文法中各个终结符之间的优先关系（大于，小于，等于，无关系）。在上述文法中，某些终结符之间的优先关系如下：
b _B_ a ； f _C_ g ； a _D_ a ； d _E_ d 。
供选择的答案：
A：① 正则文法 ② 算符文法 ③ 二义文法 ④ 属性文法
B～E：① 大于 ② 小于 ③ 等于 ④ 无关系
试题4
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
进程是操作系统中的一个重要概念。进程是一个具有一定独立功能的程序在某个数据集合上的一次 _A_ 。
进程是一个_B_的概念，而程序是一个_C_的概念。
进程的最基本状态有_D_。在一个单处理机中，若有6个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有_E_个。
供选择的答案：
A：① 单独操作 ② 关联操作 ③ 运行活动 ④ 并发活动
B：① 静态 ② 动态 ③ 逻辑 ④ 物理
C：① 物理 ② 逻辑 ③ 动态 ④ 静态
D：① 就绪、运行、隐蔽 ② 停止、就绪、运行 ③ 运行、就绪、阻塞 ④ 就绪、撤消、运行
E：① 5 ② ③ 1 ④ 4
试题5
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
软件设计中划分模块的一个准则是_A_。两个模块之间的耦合方式中，_B_耦合的耦合度最高，_C_耦合的耦合度最低。一个模块内部的内聚种类中_D_内聚的内聚度最高，_E_内聚的内聚度最低。
供选择的答案：
A：① 低内聚低耦合 ② 低内聚高耦合 ③ 高内聚低耦合 ④ 高内聚高耦合
B、C：① 数据 ② 非直接 ③ 控制 ④ 内容
D、E：① 偶然 ② 逻辑 ③ 功能 ④ 过程
试题6
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
OMT是一种对象建模技术，它定义了三种模型，它们分别是 _A_ 模型，_B_ 模型，和 _C_ 模型，其中，_A_ 模型描述了系统中对象的表态结构，以及对象之间的联系、_B_模型描述系统中与时间和操作顺序有关的系统特征，表示瞬时行为上的系统的“控剂”特征，通常可用_D_来表示；_C_模型描述了与值的变换有关的系统特征，通常可用_E_来表示。
供选择的答案：
A：① 对象 ② 功能 ③ ER ④ 静态
B：① 控制 ② 时序 ③ 动态 ④ 实时
C：① 对象 ② 功能 ③ 变换 ④ 计算
D、E：① 类图 ② 状态图 ③ 对象图 ④ 数据流图
试题7
从供选择的答案中，选出应填入下面叙述中的_?_内的最确切的解答，把相应编号写在答卷的对应栏内。
最常用的一种基本数据模型是关系数据模型，它用统一的 _A _ 结构来表示实体及实体之间的联系。关系数据库的数据操作语言（DML）主要包括 _B_ 两类操作。
关系运算以关系代数为理论基础，关系代数的最基本操作是并、差、笛卡尔积、_C_ 。用R ∣×∣ S表示关系 R和关系 S的 _D_。
设关系R和关系S图示如下：
|
R： |
A |
B |
C |
|
S: |
B |
C |
D |
|
T: |
A |
B |
C |
D |
|
|
a |
b |
c |
|
|
b |
c |
d |
|
|
a |
b |
c |
d |
|
|
b |
b |
f |
|
|
b |
c |
e |
|
|
a |
b |
c |
e |
|
|
c |
a |
d |
|
|
a |
d |
b |
|
|
c |