单项选择题 内存按字节编址，地址从A4000H～CBFFFH，共 1 字节，若用存储容量32K×8bit的存储芯片构成内存，至少需要 2 片。 在流水线结构的计算机中，频繁执行 3 指令时会严重影响机器的效率。当有中断请求发生时，采用不精确断点法，则将 4 。 6. 某计算机系统的可靠性结构如下图所示，若所构成系统的每个部件的可靠度均为0.9，即R=0.9，则该系统的可靠度为______。
A.0.891 B.0.989l C.0.9 D.0.99
B
系统的可靠性是指从它开始运行(t=0)到某时刻t这段时间内能正常运行的概率，用R(t)表示。
系统可靠性模型有串联系统、并联系统和N模冗余系统。
①串联系统：组成系统的所有子系统都能正常工作时，系统才能工作。各子系统失效率分别用λ
1 ，λ
2 ，…，λ
n 表示，则系统失效率λ=λ
1 +λ
2 +…+λ
n ；各子系统可靠性分别用R
1 ，R
2 ，…，R
n 表示，则系统可靠性R=R
1 ×R
2 ×…×R
n 。
②并联系统：组成系统的子系统中只要有一个能正常工作时，系统就能工作。若各子系统失效率均为用λ表示，则系统失效率
；各予系统可靠性分别用R
1 ，R
2 ，…，R
n 表示，则系统可靠性为R=1-(1-R
1 )×(1-R
2 )×…×(1-R
n )。
③N模冗余系统：N模冗余系统由N个(N=2n+1为奇数)相同的子系统和一个表决器组成。在N个子系统中，只有n+1个或n+1个以上的子系统能正常工作，系统才能正常工作。假设表决器是完全可靠的，每个子系统的可靠性为R
0 ，则系统可靠性为：
。
题中是并联和串联的综合。计算如下：R
sys =1-(1-R)×(1-R×(1-(1-R)×(1-R)))=0.9891。
设有一个存储器，容量是256KB，cache容量是2KB，每次交换的数据块是16B。则主存可划分为 7 块，cache地址需 8 位。 软件维护工作越来越受到重视，因为维护活动的花费常常要占用软件生存周期全部花费的 14 %左右，其工作内容为 15 。为了减少维护工作的困难，可以考虑采取的措施为 16 。 有限状态自动机M的状态转换矩阵如下表所示，对应的DFA状态图为 28 ，所能接受的正则表达式表示为 29 。
0
1
q0
q1
—
q1
q2
—
q2
q2
q2
在UML提供的图中，可以采用 30 对逻辑数据厍的建模； 31 用于接口、类和协作的行为建模，并强调对象行为的事件顺序； 32 用于系统的功能建模，并强调对象之间的控制流。 34. 对数列{46，79，56，38，40，84)建立大顶堆，则初始堆为______。
A.79，46，56，38，40，84 B.84，79，56，38，40，46 C.84，79，56，46，40，38 D.56，84，79，40，46，38
B
堆的定义：n个元素的序列{k1，k2，…，kn}当且仅当满足如下的关系式时才称之为堆：
或
，相应的称为小顶堆或大顶堆。
判断堆的办法是把序列看成一棵完全二叉树，按层序遍历，若树中的所有非终端节点的值均不大于(或不小于)其左右孩予的节点的值，则该序列为堆。
初始堆建立方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有
的节点K
i 都没有子节点，以这样的K
i 为根的子树已经是堆，因此初始堆可从完全二叉树的第(
)个节点开始，通过调整，逐步使以
、
、…、K
2 、为根的子树满足堆的定义。
37. 对序列{25，57，48，37，12，82，75，29}进行二路归并排序，第二趟归并后的结果为______。
A.25，57，37，48，12，82，29，75 B.25，37，48，57，12，29，75，82 C.12，25，29，37，48，57，75，82 D.25，57，48，37，12，82，75，29
B
所谓“归并”是将两个或两个以上的有序文件合并成为一个新的有序文件。归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过“逐趟归并”使整个序列中的有序予序列的长度逐趟增大，直至整个记录序列为有序序列止。2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列。具体做法：把一个有n个记录的无序文件看成是由n个长度为1的有序予文件组成的文件，然后进行两两归并，得到
个度为2或1的有序文件，再进行两两归并，如此重复，直至最后形成一个包含n个记录的有序文件为止。
其排序过程如下，此即该题答案。
25 57 48 37 12 82 75 29
①25 57 37 48 12 82 29 75
②25 37 48 57 12 29 75 82
③12 25 29 37 48 57 75 82
关系模式R(U，F)，其中U={A，B，C，D，E}，F={AC→E，E→D，A→B，B→D}。关系模式R的候选键是 45 ， 46 是无损连接并保持函数依赖的分解。46.
A.ρ={R1 (AC)，R2 (ED)，R3 (AB)} B.ρ={R1 (ABC)，R2 (ED)，R3 (ACE)} C.ρ={R1 (ABC)，R2 (ED)，R3 (AE)} D.ρ={R1 (ACE)，R2 (ED)，R3 (AB)}
B
根据函数依赖进行判断。
·候选码(Candidate Key)：若关系中的某一属性和属性组的值能唯一的标识一个元组，则称该属性或属性组为候选码，简称码。
·主码(Primary Key)：若一个关系有多个候选码，则选定其中一个为主码。通常在关系模式主属性上加下划线表示该属性为主码属性。
·主属性(PIimary Attribute)：包含在任何候选码中的诸属性称为主属性，不包含在任何候选码中的属性称为非码属性。
·外码(Foreign Key)：如果关系模式R中的属性或属性组，非该关系的码，但都是其他关系的码，那么该属性集对关系模式R而言是外码。
·全码(All-Key)：关系模型的所有属性组是这个关系模型的候选码，称为全码。
·超键：在关系模式中，能唯一标识元组的属性集称为超键(Super Key)。
对于候选键，则因A→B，故若AB是超键，则A也是超键，故AB不可能是候选键。又
，故若ABC也不可能是候选键。同理，因E→D，ED也不可能是候选键。这样就只剩选项A了，可以验证AC确实是该关系的候选键。
类的实例化过程是一种实例的合成过程，而不仅仅是根据单个类型进行的空间分配、初始化和绑定。指导编译程序进行这种合成的是 47 。重置的基本思想是通过 48 机制的支持，使得子类在继承父类界面定义的前提下，用适用于自己要求的实现去置换父类中的相应实现。 OMT是一种对象建模技术，它定义了三种模型，其中 49 模型描述系统中与时间和操作顺序有关的系统特征，表示瞬时的行为上的系统的“控制”特征，通常可用 50 来表示。 53. 某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。
A．O(n) B．
C．O(n
2 ) D．O(1)
B
由时间代价严格推出时间复杂度比较复杂，对于这种题，可用特例验证，不过需要注意的是特例不能取太少，至少n取到5，这样规律基本就可以确定了。
T(1)=1
T(2)=2T(1)+2=4
T(3)=2T(1)+3=5
T(4)=2T(2)+4=12
T(5)=2T(2)+5=13
很容易排除D选项，其递增速率介于O(n)和O(n
2 )之间，故选B
。
计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为 55 ；对应时间复杂度为 56 。 递归算法的执行过程一般来说可先后分成 57 和 58 两个阶段。 59. 下列排序方法中，最好情况下，时间复杂度为O(n)的算法是______。
A.选择排序 B.归并排序 C.快速排序 D.直接插入排序
D
各种排序算法性能比较如下：
排序方法
平均时间
最好情况
最坏情况
辅助存储
稳定性
选择排序
O(n2 ) O(n2 ) O(n2 ) O(1) 不稳定
插入排序
O(n2 ) O(n) O(n2 ) O(1) 稳定
冒泡排序
O(n2 ) O(n2 ) O(n2 ) O(1) 稳定
希尔排序
O(n1.25 ) ——
——
O(1) 不稳定
快速排序
O(nlogn) O(nlogn) O(n2 ) O(nlogn) 不稳定
堆排序
O(nlogn) O(nlogn) O(nlogn) O(1) 稳定
归并排序
O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
基数排序
O(d(n=rd)) O(d(n=rd)) O(d(n=rd)) O(rd) 稳定
在Linux操作系统中提供了大量的网络配置命令工具，其中不带参数的route命令用来查看本机的路由信息， 63 命令也可以完成该功能；命令“route add 0.0.0.0gw 192.168.0.1”的含义是 64 。 根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与 66 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 67 。从文法描述语言的能力来说， 68 最强， 69 最弱，由四类文法的定义可知： 70 必是2型文法。 Most computer systems are 71 to two different groups of attacks：insider attacks and outsider attacks．A system that is known to be 72 to an outsider attack by preventing 73 from outside can still be vulnerable to the insider attacks accomplished by abusive usage of 74 users．Detecting such abusive usage as well as attacks by outsides not only provides information on damage assessment,but also helps to prevent future attacks．These attacks are usually 75 by tools referred to as Intrusion Detection Systems． 
；各予系统可靠性分别用R1，R2，…，Rn表示，则系统可靠性为R=1-(1-R1)×(1-R2)×…×(1-Rn)。 
。 
或
，相应的称为小顶堆或大顶堆。 
的节点Ki都没有子节点，以这样的Ki为根的子树已经是堆，因此初始堆可从完全二叉树的第(
、
、…、K2、为根的子树满足堆的定义。 
个度为2或1的有序文件，再进行两两归并，如此重复，直至最后形成一个包含n个记录的有序文件为止。 
，故若ABC也不可能是候选键。同理，因E→D，ED也不可能是候选键。这样就只剩选项A了，可以验证AC确实是该关系的候选键。
C．O(n2) D．O(1)
。 
深色：已答题 浅色：未答题