2008年下半年软件考试因故推迟了，这未尝不是一件好事，对于那些准备还不够充分的考生来说，现在正是查漏补缺的好时机，本站为您整理了考前练习题，希望对您有所帮助，祝您考出好成绩！
在分支-限界算法设计策略中，通常采用_(1)_搜索问题的解空间。
(1)A.深度优先
B.愣扔畔取
C.自底向上
D.拓扑序列
●在下列算法设计方法中，_(2)_在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决_(3)_问题。
(2)A.分治法
B.贪心法
C.动态规划方法
D.回溯法
(3)A.排序
B.检索
C.背包
D.0/1背包
●以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是_(4)_;该算法采用的设计方法是_(5)_。
(4)A.归并排序
B.插入排序
C.选择排序
D.冒泡排序
(5)A.分治法
B.贪心法
C.动态规划方法
D.回溯法
答案:BBCAA
进程PA不断地向管道写数据，进程PB从管道中读数据并加工处理，如下图所示。如果采用PV操作来实现进程PA和进程PB间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要_(1)_。
(1)A.1个信号量，信号量的初值为0
B.2个信号量，信号量的初值分别为0、1
C.3个信号量，信号量的初值分别为0、0、1
D.4个信号量，信号量的初值分别为0、0、1、1
●假设系统中有三类互斥资源R1、R2和R3，可用资源数分别为9、8和5。在To时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示。如果进程按_(2)_序列执行，那么系统状态是安全的。
资源最大需求量已分配资源数
进程R1 R2 R3R1 R2 R3
P16 5 21 2 1
P22 2 12 1 1
P38 0 12 1 0
P41 2 11 2 0
P53 4 41 1 3
(2)A.P1→P2→P4→P5→P3
B.P2→P1→P4→P5→P3
C.P2→P4→P5→P1→P3
D.P4→P2→P4→P1→P3
●某一非确定性有限自动机(NFA)的状态转换图如下图所示，与该NFA等价的正规式是_(3)_，与该NFA等价的DFA是_(4)_。
(3) A.0*|(0|1)0
B.(0|10)*
C.0*((011)0)*
D.0*(10)*
答案：B C B A
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.com/exam/
