2002年度软件设师(高级程序员)上午试卷及答案.doc

2002年度软件设计师（高级程序员）上午试卷及答案● 常规的数据加密标准DES采用__(l)__。位有效密钥对____(2)__位的数据块进行加密。 (1) A. 56 B. 64 C. 112 D. 128 (2) A. 32 B. 64 C. 128 D. 256 　 ●在面向对象技术中，多态有多种不同的形式，其中__(3)__和__(4)__称为通用多态，__(5)__和强制多态称为特定多态. (3) A. 参数多态 D. 过载多态 C. 隐含多态 D. 重置多态 (4) A. 重置多态 B. 过载多态 C. 隐含多态 D. 包含多态 (5) A. 参数多态 D. 隐含多态 C. 过载多态 D. 包含多态 　 ● 已知一不确定的有穷自动机（NFA）如下图所示，采用于集法将其确定化为 DFA 的过程如下表示。 I I0 I1 {S，1，2，3 } {1，3，4，5，Z} {2，3} {1，3，4，5，Z} T1 T3 {2，3} {4，5，Z} {2，3} T2 {6} T3 T1 {1，3，4，5，6，Z} {5，Z} {6} T3 {5，Z} {5，Z} {6} T3 状态集 T1 中不包括编号为__(6)__的状态；状态集 T2 中的成员有__(7)__；状态集 T3 等于__(8)__；该自动机所识别的语言可以用正规式__(9)__表示。? (6) A. 2 B. 4 C. 3 D. 5 (7) A. 1,3,4,5,Z B. 2,3 C. 6 D. 4,5,Z (8) A. {Z} B. {6} C. {4,5,Z} D. { } (9) A. (0|1)* B. (0*|1*)*001 C. (0*|1*)*0(0|1)* D. (0*|1*)0(0|1)* ●与正规式 (alb)* 等价的正规式为__(10)__。 (10) A. a*|b* B. a*b* C. (a*b*)* D. (ab)* 　 ●算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有__(11)__特性。 (11) A. 正确性 B. 确定性 C. 能行性 D. 健壮性 ??? ●快速排序算法采用的设计方法是__(12)__。 (12) A. 动态规划法 (Dynamic Programming) B. 分治法 (Divide and Conquer) C. 回溯法 (Backtracking) D. 分枝定界法 (Branch and Bound) 　 ●在数据压缩编码的应用中，哈夫曼（Huffman）算法可以用来构造具有__(13)__的二叉树，这是一种采用了__(14)__的算法。 (13) A. 前缀码 D. 最优前缀码 C. 后缀码 D. 最优后缀码 (14) A. 贪心 D. 分治 C. 递推 D. 回溯 ?? ●用递归算法实现 n 个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为__(15)__ 。 (15) A. n B. [n/2] C. [Log2n] D. [Log2(n+1)] ●设有 7 项任务，分别标记为 a、b、c、d、c、f 和 g，需要若干台机器以并行工作方式来完成，它们执行的开始时间和完成时间如下表所示： 时间 任 务 a b c d e f g 开始时间 0 3 4 9 7 1 6 结束时间 2 7 7 11 10 5 8 在最优分配方案中完成这些任务需要，__(16)__台机器。 (16) A. 2 B. 3 C. 4 D. 5 　 ●下述函数中渐进时间最小的是__(17)__ 。 (17) A. T1(n) = nlog2n + 100log2n B. T2(n) = nlog2n + 100log2n C. T3(n) = n2 - 100log2n D. T4(n) = 4nlog2n - 100log2n ●对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序（增量为 5 ）得到__(18)__，快速排序（选第一个记录为基准元素）得到__(19)__，链式基数(基数为10排)序得到__(20)__，二路归并排序得到__(21)__，堆排序得到__(22)__。 (18) A. 2,4,6,8,10,12,16,18,20,28,30 B. 6,2,10,4,8,12,28,30,20,16,18 C. 12,2,10,20,6,18,4,16,30,8,28 D. 30,10,20,