[计算机类试卷]软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷4及答案与解析.doc

1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 4及答案与解析 1 设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n表示，则该算法的时间复杂度为 (1)。 （ A） O(lgn) （ B） O(nlgn) （ C） O(n) （ D） O(n2) 2 下面的程序段违反了算法的 (2)原则。 Void sam() int n=2; while(!odd(n) n+=2 printf(n); （ A）有穷性 （ B）确定性 （ C）可行性 （ D）健 壮性 3 拉斯维加斯 (Las Vegas)算法是一种常用的 (3)算法。 （ A）确定性 （ B）近似 （ C）概率

2、 （ D）加密 4 在分支 限界算法设计策略中，通常采用 (4)搜索问题的解空间。 （ A）深度优先 （ B）广度优先 （ C）自底向上 （ D）拓扑序列 5 算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有 (5)特性。 （ A）正确性 （ B）确定性 （ C）可行性 （ D）健壮性 6 用迭代法求解 方程 x5-x-1=0，下列迭代公式不可能正确的是 (6)。 （ A） （ B） （ C） （ D） 7 用递归算法实现 n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为 (11)

3、。 （ A） n （ B） n/2 （ C） log2n （ D） log2(n+1) 8 贪婪法是一种 (20)的算法。 （ A）不求最优，只求满意 （ B）只求最优 （ C）求取全部可行解 （ D）求取全部最优解 9 快速排序算法采用的设计方法是 (23)。 （ A）动态规划法 (Dynamic Programming) （ B）分治法 (Divideand Conquer) （ C）回溯法 (Backtracking) （ D）分枝定界法 (Branch and Bound) 10 利用动态规划法求解每对节点之间的最短路径问题时，设有向图 G= V， E共有 n个节点，节点编号 1 n，

4、设 C是 G的成本邻接矩阵，用 Dk(i,j)表示从 i到 j并且不经过编号比 k还大的节点的最短路径的长度 (Dn(i,j)即为图 G中节点 i到 j的最短路径长度 )，则求解该问题的递推关系式为 (28)。 （ A） Dk(i,j)=Dk-1(i,j)+C(i,j) （ B） Dk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j) （ C） Dk(i,j)=Dk-1(i,k)+Dk-1(k,j) （ D） Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j) 11 采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是 (29)。 （

5、A）当前所作出的决策不会影响后面的决策 （ B）原问题的最优解包含其子问题的最优解 （ C）问题可以找到最优解，但利用贪心法不能找到最优解 （ D） 每次决策必须是当前看来最优的决策才可以找到最优解 12 为了解决进程间的同步和互斥问题，通常采用一种称为 (1)机制的方法。若系统中有 5个进程共享若干个资源 R，每个进程都需要 4个资源 R，那么使系统不发生死锁的资源 R的最少数目是 (2)。 （ A）调度 （ B）信号量 （ C）分派 （ D）通信 （ A） 20 （ B） 18 （ C） 16 （ D） 15 14 某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入

6、仓库提货，顾客离开时，审核员检验顾客提货是否正确。其工作流程如图3-2所示。为 了利用 PV操作正确地协调他们之间的工作，设置了两个信号量 S1和S2，且 S1的初值为 2， S2的初值为 1。在图中的 a处应填写 (3)，图中的 b， c和d处应分别填写 (4)。 （ A） P(S1) （ B） P(S2) （ C） V(S1) （ D） V(S2) （ A） P(S2)， V(S2)和 V(S1) （ B） P(S1)， V(S1)和 V(S2) （ C） V(S1)， P(S2)和 V(S2) （ D） V(S2)， P(S1)和 V(S1) 16 在一个单 CPU的计算机系统中，有两台

7、外部设备 R1， R2和三个进程 P1， P2，P3。系统采用可剥夺式优先级的进程调度方案，且所有进程可以并行使用 I/O设备，三个进程的优先级、使用设备的先后顺序和占用设备时间如表 3-1所示。假设操作系统的开销忽略不计，三个进程从投入运行到全部完成， CPU的利用率约为(5)%； R2的利用率约为 (6)%(设备的利用率指该设备的使用时间与进程组全部完成所占用时间的比率 )。 （ A） 60 （ B） 67 （ C） 78 （ D） 90 （ A） 70 （ B） 78 （ C） 80 （ D） 89 18 因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和 (16)。 对于缓冲池

8、(大量缓冲区 )的管理，采用生产者 -消费者方式解决同步或互斥时，通常需要用 (17)个信号量。 （ A）请求与释放 （ B）释放与保持 （ C）释放与阻塞 （ D）保持与等待 （ A） 1 （ B） 2 （ C） 3 （ D） 4 20 主存按字节编址，地址从 A4000H到 CBFFFH，共有 (21)字节。若用存储容量为 32K*8bit的存储器芯片构成该主存，至少需要 (22)片。 （ A） 80K （ B） 96K （ C） 160K （ D） 192K （ A） 2 （ B） 5 （ C） 8 （ D） 10 22 容量为 64块的 Cache采用组相连方式映像，字块大小为 128

9、个字，每 4块为一组。若主存容量为 4096块，且以字编址，那么主存地址应为 (23)位，主存区号应为 (24)位。 （ A） 16 （ B） 17 （ C） 18 （ D） 19 （ A） 5 （ B） 6 （ C） 7 （ D） 8 24 虚拟存储管理系统的基础是程序的 (25)理论，这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据此理论， Denning提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时，如果它的工作集页面 都在 (26)内，能够使该进程有效地运行，否则会出现频繁的页面调儿调出现象。 （ A）全局性 （ B）局部性 （ C）时间全

10、局性 （ D）空间全局性 （ A）主存储器 （ B）虚拟存储器 （ C）辅助存储器 （ D） U盘 26 MPEG-1编码器输出视频的数据率大约为 (37)。 PAL制式下其图像亮度信号的分辨率为 (38)，帧速为 (39)。 （ A） 128Kb/s （ B） 320Kb/s （ C） 1.5Mb/s （ D） 15Mb/s （ A） 352288 （ B） 576352 （ C） 720576 （ D） 1024720 （ A） 16帧 /秒 （ B） 25帧 /秒 （ C） 30帧 /秒 （ D） 50帧 /秒 软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 4答案与解析

11、 1 【正确答案】 B 【试题解析】 运用数学递推公式，可以推算出数量级 O(nlgn)。 2 【正确答案】 A 【试题解析】 一个算法要求必须总是在执行有穷步之后结束，并月 -每一步都可在有穷时间内完成。上述程序段违反了算法的有穷性性质，理论上将导致过程不可终止。 3 【正确答案】 C 【试题解析】 概 率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择要省时，因此概率算法可以在很大程度上降低算法的复杂度。概率算法通常有两个优点。首先，较之那些我们所知的解决同 问题最好的确定性算法，概率算法所需的运行时间或空间通常小一

12、些；其次，迄今为止所发现的概率算法总是易于理解和实现的。概率算法可分为四类，分别是数值概率算法、蒙特卡罗算法(Monte Karlo)、拉斯维加斯算法 (Las Vegas)和舍伍德算法 (Sherwood)。 4 【 正确答案】 B 【试题解析】 分支 -限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优解。分支 限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的儿子节点，然后再从当前节点表中选择下一个扩展节点。 5 【正确答案】 C 【试题解析】 一个

13、算法具有下列 5个重要特性。有穷性：一个算法必须总是在执行有穷步之后结束，且每 步都可在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。综上 所述，算法中的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明了算法的可行性特

14、点。 6 【正确答案】 D 【试题解析】 迭代法中要求迭代公式与原方程有共同的不同点。其中显然选项 D不符合。 7 【正确答案】 D 【试题解析】 根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中 又加入了一条查找记录，所确定的查找区间中的元素最多为 n/2：第三次调用时，栈中又加入了 条查找记录，所确定的查找区间中的元素最多为 n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次

15、数为 log2(n+1)次，查找结束。 8 【正确答案】 A 【试题解析】 贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法 (或称贪婪法 )一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。 9 【正确答案】 B 【试题解析】 快速排序算法采用的设计 方法是分治法。 10 【正确答案】 D 【试题解析】 从 “Dk(i,j)表示从 i到 j并且不经过编号比 k还大的节点的最短路径的长度 ”中，我们得到一个提示，在求 i,j之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在 Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+D

16、k-1(k,j)中， Dk(i,j)表示 i到 j不经过 k 的路径长度，而 Dk-1(I,k)+Dk-1(k,j)表示 i到 j经过 k的路径长度，且 min()函数用于找最小值，所以此式正确。 11 【正确答案】 B 【试题解析】 动态规划策略设计算法的第一步通常是刻画最优解结构。当问题的最优解包含了子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 12 【正确答案】 B 13 【正确答案】 C 【试题解析】 信号量取

17、自交通管理中的信号灯的概念，借其含义用信号量来作为一种控制进程互斥和同步的变量，也就是通过控制信号量来控制进程的同步与互斥。对实现进程的同步和互斥而言，信号量是一种很有效的工具，现已被广泛地应用于单处理机系统、多处理机系统和计算机网络中。有同类资源 m个，供 n 个进程共享，每个进程最多申请资源 x个 (1xm)，则有： n(x-1) m。当 nx m+ n 时，系统不会出现死锁。因为每个进程在得到 x-1个资源后，均要申请最后一个资源。只要系统中还有一个资源，就可能使其中一个进程得到满足。当该进程执行结束，归还的资源可供其他进程使用，因而不会发生死锁。所以这里需要资源数最少为 5x(4-1)

18、+1=16个。 14 【正确答案】 A 15 【正确答案】 C 【试题解析】 根据题意， S1初值为 2，表示发货员； S2初值为 1，表示审核员。 顾客进入，排队等待发货员发货 P(S1)；发货后 V(S1)，发货员给下一位顾客发货，该顾客等待审核员检验 P(S2)：检验完后 V(S2)，审核员继续给下一位等待审核的顾客检验。关键在于是审核员检验完后，发货员才给下一位顾客发货，亦即发货员等待审核员的检验结果，还是发货员发完货就处于空闲，可以给下一位顾客发货。所以应该是发完货就空闲，不用等待审核员的检验结果。因此， a， b，c， d 依次为 P(S1)、 V(S1)、 P(S2)、 V(S2

19、)。 16 【正确答案】 D 17 【正确答案】 A 【试题解析】 根据题目的叙述，我们可以作出进程运行的时空图帮助解题。从如图 3-3所示的时空图中我们可以看出三个进程运行完毕需要 100ms， CPU工作了90ms，所以 CPU的利用率为 90%： R2 工作了 70ms。所以 R2的工作效率为70%。 18 【正确答案】 D 19 【正确答案】 C 【试题解析】 进程的并发执行会导致对资源的竞争。如果多个进程由于竞争资源造成一种僵局，而无外力作用，这些进程都将无法 向前推进，就造成了死锁。死锁的产生有以下四个必要条件。 (1)互斥条件：在一段时间内某资源只能被一个进程占有。 (2)请求和

20、保持条件：进程在申请新的资源得不到满足时，对已获得的其他资源保持不放。 (3)不可剥夺条件：进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放。 (4)环路等待条件：在资源有向图中，存在环路。在 n 个缓冲区， m个生产者和 k个消费者的生产者 -消费者问题中，可利用互斥信号量 mutex使诸进程实现对缓冲池的互斥使用，利用资源信号量 empty和full分别表示缓冲池中空缓冲区和满缓冲区的 数量。因此通常需要 3个信号量。 20 【正确答案】 C 21 【正确答案】 B 【试题解析】 内存地址从 A4000H到 CBFFFH 共有 160K个存储单元，而内存是按字节编址的，故

21、内存共有 160K字节。若要用存储容量为 32K*8bit的存储器芯片构成内存，至少要 160/32=5片。 22 【正确答案】 D 23 【正确答案】 B 【试题解析】 由于主存容量为 4096块，而每块为 128字节，所以主存的总容量为 512K字节，故主存地址应为 19位。主存地址应分为区号、组号、组内块号、块内 地址号。可以知道，块内地址号应为 7位，用来表示 128字节。一组为 4块，则组内块号用 2位表示。 Cache容量为 64 块，共分为 16组，故组号需要用 4位地址表示。剩余的即为区号，应为 6位。 24 【正确答案】 B 25 【正确答案】 A 【试题解析】 虚拟存储管理

22、系统的基础是程序的局部性理论。所谓程序局部性原理是指程序在执行时所呈现的局部性规律，即在一段较短时间内，程序的执行仅限于某个部分。局部性原理表现为两个方面：时间局限性和空间局限性。工作集是指在进程运行时被频繁访问的页面集合。虽然程序只需少量 的几页内存就可以运行，但为了使程序更有效地运行，必须使程序的工作集全部在内存当中，否则会使进程在运行中频繁出现中断，从而出现频繁的页面调入 /调出现象。 26 【正确答案】 C 27 【正确答案】 A 28 【正确答案】 B 【试题解析】 MPEG-1编码器输出视频的数据率大约为 1.5Mb/s。 PAL制式下其图像亮度信号的分辨率为 352288像素，帧速率为 25帧 /秒。我国采用的电视标准是 PAL制，它规定视频每秒 25帧，每帧 625个扫描行。另一种常见的数字视频格式 NTSC制，规定视频每秒 30帧，每帧 525个扫描行，它同样采用了隔行扫描方式，每一帧由两场组成，其图像大小是 720486像素。此外，还有一种由法国开发的彩色电视广播标准 SECAM，称为顺序传送和存储彩色电视，它与 PAL制式类似。