一、选择题：（ 共70 题，每题1 分，满分70 分。其中1－55 题为中文题，56－70 题为英文题）。 下列各题A）、B）、C）、D）四个选项中，只有一个是正确的，请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。
（1）若一个子程序起始地址为3K，调用指令CALL 的内存地址为K+1，则执行CALL 指令所要执行指令的地址为（ ）。
A） 3K
B） 3K+1
C） 3K－1
D） K+2
（2）若逻辑变量X＝0，Y＝1，则执行按位加XY 以后的值为（ ）。
A） 1
B） 0
C） 10
D） 2
（3）一般情况下，操作数左移3 位的结果是原操作数（ ）。
A） 整除8
B） 乘以8
C） 整除4
D） 乘以4
（4） 设用一维数组A【1… n】来存储一个栈， 令A【n】 为栈底，用整型变量T 指示当前栈顶位置，A【T】为栈顶元素。当从栈中弹出一个元素时，变量T 的变化为（ ）。
A） T：＝T＋1
B） T：＝T－1
C） T 不变
D） T：＝n
（5）在排序方法中，关键码比较次数与记录的初始排列无关的是（ ）。
A）Shell 排序
B）归并排序
C） 直接插入排序
D）选择排序
（6） 对一棵非空的二叉树（设第0 层为根结点），那么其第i 层上至多有多少个结点（ ）。
A） i
B） 2i－1
C） 2i＋1
D） 2i
（7）对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准。在第一趟划分过程中，元素的移动次数最多的是哪一个序列？（ ）。
A） 70，75，68，23，10，16，90，82
B） 82，75，70，16，10，90，68，23
C） 70，75，82，90，23，16，10，68
D） 23，10，16，70，82，75，68，90
（8） 数组Q【0，n－1】作为一个环形队列，f 为当前队头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数总小于n，队列中元素的个数是什么？（ ）。
A）r－f
B）n+f－r
C）n+r－f
D）（n+r－f）mod n
（9）A＝｛x
x%26lt;100 且为质数｝，在A 上定义和·如下：xy＝max（x，y）， x·y＝LCM（x，y），x，y∈A， 这里LCM（x， y）表示x 与y 的最小公 倍数，则下面命题正确的是：（ ）。
Ⅰ 构成代数系统；
Ⅱ 构成代数系统；
A）只有Ⅰ
B） 只有Ⅱ
C） Ⅰ和Ⅱ
D）没有
（10）设V ′和E′分别为无向连通图G 的点割集和边割集，下面的说法中正确的是（ ）。
Ⅰ.G－E′的连通分支数p（G－E′）＝2。
Ⅱ. G－V′的连通分支数p（G－V′）一定等于G－E′的连通分支数 p（G－E′）。
Ⅲ. G－V′的连通分支数p（G－V′）≥2。
A） Ⅰ和Ⅱ
B） Ⅰ和Ⅲ
C） Ⅱ
D）没有
（11）设R，S 是集合A 上的二元关系，则下面命题是真命题的是（ ）。
A） 若R，S 是自反的，则R·S 是自反的
B） 若R，S 是反自反的，则R·S 是反自反的
C） 若R，S 是对称的，则R·S 是对称的
D） 若R，S 是传递的，则R·S 是传递的
（12）下面的谓词公式是有效式的是（ ）。
Ⅰ（x）（y）p（x，y） （y）（x）p（x，y）
Ⅱ┐（x）（p（x）→（y）q（y））∧（y）q（y）
Ⅲ （x）（p（x）∨q（x））→（（x）p（x）∨（y）q（y）
A）Ⅰ和Ⅱ
B）只有Ⅱ
C）只有Ⅲ
D）只有Ⅰ
（13）下面的符号集合中，是前缀码的是（ ）。其中B1＝｛0，10，110，1111｝、B2＝｛1，01，001，000｝、B3＝｛1，11，101，001，0011｝、B4＝｛b，c，aa，ac，aba，abb，abc｝
A） B1 和B2
B） B2 和B3
C） B1、B2和B4
D） B1、B2和B3
（14）下面命题的判断正确的是（ ）。
Ⅰ 完全图Kn（n≥1）都是哈密尔顿图；
Ⅱ 完全二部图Kn，m（n≥1，m≥1）都是欧拉图；
Ⅲ 任何平面图G 的对偶图G的对偶图G与G 同构。
A） 只有Ⅰ和Ⅱ为真
B） 只有Ⅲ为真
C） 只有Ⅱ为假
D）全为假
（15）已经获得除（ ）以外的所有运行所需资源的进程处于就绪状态。
A）存储器
B）CPU
C）外设
D）磁盘空间
（16） 在存储分配的策略中，（ ） 是程序员在编程时或者编译程序对源程序编译时直接指定存储区。
A）直接分配
B）间接分配
C）态分配
D）动态分配
（17）操作系统的作用是（ ）。
A） 把源程序编译为目标程序
B） 便于进行目标管理
C） 控制和管理系统资源的使用
