1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 2 及答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：20，分数：56.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_2.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n 表示，则该算法的时间复杂度为(1)。（分数：2.00）A.O(lgn)B.O(nlgn)C.O(n)D.O(n 2 )3.下面的程序段违反了算法的(2)原则。 Void sam() int n=2; while(!odd(n) n+=2 p
2、rintf(n); （分数：2.00）A.有穷性B.确定性C.可行性D.健壮性4.拉斯维加斯(Las Vegas)算法是一种常用的(3)算法。（分数：2.00）A.确定性B.近似C.概率D.加密5.在分支限界算法设计策略中，通常采用(4)搜索问题的解空间。（分数：2.00）A.深度优先B.广度优先C.自底向上D.拓扑序列6.算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有(5)特性。（分数：2.00）A.正确性B.确定性C.可行性D.健壮性7.用迭代法求解方程 x 5 -x-1=0，下列迭代公式不可能正确的是(
3、6)。（分数：2.00）A.B.C.D.8.用递归算法实现 n 个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为(11)。（分数：2.00）A.nB.n/2C.log 2 nD.log 2 (n+1)9.贪婪法是一种(20)的算法。（分数：2.00）A.不求最优，只求满意B.只求最优C.求取全部可行解D.求取全部最优解10.快速排序算法采用的设计方法是(23)。（分数：2.00）A.动态规划法(Dynamic Programming)B.分治法(Divideand Conquer)C.回溯法(Backtracking)D.分枝定界法(Branch and Bound
4、)11.利用动态规划法求解每对节点之间的最短路径问题时，设有向图 G=V，E共有 n 个节点，节点编号1n，设 C 是 G 的成本邻接矩阵，用 D k (i,j)表示从 i 到 j 并且不经过编号比 k 还大的节点的最短路径的长度(D n (i,j)即为图 G 中节点 i 到 j 的最短路径长度)，则求解该问题的递推关系式为(28)。（分数：2.00）A.D k (i,j)=D k -1(i,j)+C(i,j)B.D k (i,j)=minD k -1(i,j),D k -1(i,j)+C(i,j)C.D k (i,j)=D k -1(i,k)+D k -1(k,j)D.D k (i,j)=m
5、inD k -1(i,j),D k -1(i,k)+D k -1(k,j)12.采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是(29)。（分数：2.00）A.当前所作出的决策不会影响后面的决策B.原问题的最优解包含其子问题的最优解C.问题可以找到最优解，但利用贪心法不能找到最优解D.每次决策必须是当前看来最优的决策才可以找到最优解为了解决进程间的同步和互斥问题，通常采用一种称为(1)机制的方法。若系统中有 5 个进程共享若干个资源 R，每个进程都需要 4 个资源 R，那么使系统不发生死锁的资源 R 的最少数目是(2)。（分数：4.00）A.调度B.信号量C.分派D.通信A.20B
6、.18C.16D.15某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入仓库提货，顾客离开时，审核员检验顾客提货是否正确。其工作流程如图 3-2 所示。为了利用 PV 操作正确地协调他们之间的工作，设置了两个信号量 S1 和 S2，且 S1 的初值为 2，S2 的初值为 1。在图中的 a 处应填写(3)，图中的 b，c 和 d 处应分别填写(4)。 （分数：4.00）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)和
7、V(S1)在一个单 CPU 的计算机系统中，有两台外部设备 R1，R2 和三个进程 P1，P2，P3。系统采用可剥夺式优先级的进程调度方案，且所有进程可以并行使用 I/O 设备，三个进程的优先级、使用设备的先后顺序和占用设备时间如表 3-1 所示。 （分数：4.00）A.60B.67C.78D.90A.70B.78C.80D.89因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和(16)。对于缓冲池 (大量缓冲区)的管理，采用生产者-消费者方式解决同步或互斥时，通常需要用(17)个信号量。（分数：4.00）A.请求与释放B.释放与保持C.释放与阻塞D.保持与等待A.1B.2C.3D.4主
8、存按字节编址，地址从 A4000H 到 CBFFFH，共有(21)字节。若用存储容量为 32K*8bit 的存储器芯片构成该主存，至少需要(22)片。（分数：4.00）A.80KB.96KC.160KD.192KA.2B.5C.8D.10容量为 64 块的 Cache 采用组相连方式映像，字块大小为 128 个字，每 4 块为一组。若主存容量为 4096 块，且以字编址，那么主存地址应为(23)位，主存区号应为(24)位。（分数：4.00）A.16B.17C.18D.19A.5B.6C.7D.8虚拟存储管理系统的基础是程序的(25)理论，这个理论的基本含义是指程序执行时往往会不均匀地访问主存储
9、器单元。根据此理论，Denning 提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时，如果它的工作集页面都在(26)内，能够使该进程有效地运行，否则会出现频繁的页面调儿调出现象。（分数：4.00）A.全局性B.局部性C.时间全局性D.空间全局性A.主存储器B.虚拟存储器C.辅助存储器D.U 盘MPEG-1 编码器输出视频的数据率大约为(37)。PAL 制式下其图像亮度信号的分辨率为(38)，帧速为(39)。（分数：6.00）A.128Kb/sB.320Kb/sC.1.5Mb/sD.15Mb/sA.352288B.576352C.720576D.1024720A.16 帧
10、/秒B.25 帧/秒C.30 帧/秒D.50 帧/秒软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 2 答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：20，分数：56.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：2.设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n 表示，则该算法的时间复杂度为(1)。（分数：2.00）A.O(lgn)B.O(nlgn) C.O(n)D.O(n 2 )解析：解析：运用数学递推公式，可以推算出数量级 O(nlgn)。
11、3.下面的程序段违反了算法的(2)原则。 Void sam() int n=2; while(!odd(n) n+=2 printf(n); （分数：2.00）A.有穷性 B.确定性C.可行性D.健壮性解析：解析：一个算法要求必须总是在执行有穷步之后结束，并月-每一步都可在有穷时间内完成。上述程序段违反了算法的有穷性性质，理论上将导致过程不可终止。4.拉斯维加斯(Las Vegas)算法是一种常用的(3)算法。（分数：2.00）A.确定性B.近似C.概率 D.加密解析：解析：概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最
12、优选择要省时，因此概率算法可以在很大程度上降低算法的复杂度。概率算法通常有两个优点。首先，较之那些我们所知的解决同问题最好的确定性算法，概率算法所需的运行时间或空间通常小一些；其次，迄今为止所发现的概率算法总是易于理解和实现的。概率算法可分为四类，分别是数值概率算法、蒙特卡罗算法(Monte Karlo)、拉斯维加斯算法(Las Vegas)和舍伍德算法(Sherwood)。5.在分支限界算法设计策略中，通常采用(4)搜索问题的解空间。（分数：2.00）A.深度优先B.广度优先 C.自底向上D.拓扑序列解析：解析：分支-限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条
13、件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优解。分支限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的儿子节点，然后再从当前节点表中选择下一个扩展节点。6.算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有(5)特性。（分数：2.00）A.正确性B.确定性C.可行性 D.健壮性解析：解析：一个算法具有下列 5 个重要特性。有穷性：一个算法必须总是在执行有穷步之后结束，且每步都可在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，读者
14、理解时不会产生二义性，并且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。综上所述，算法中的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明了算法的可行性特点。7.用迭代法求解方程 x 5 -x-1=0，下列迭代公式不可能正确的是(6)。（分数：2.00）A.B.C.D. 解析：解析：迭代法中要求迭代公式与原
15、方程有共同的不同点。其中显然选项 D 不符合。8.用递归算法实现 n 个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为(11)。（分数：2.00）A.nB.n/2C.log 2 nD.log 2 (n+1) 解析：解析：根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n/2：第三次调用时，栈中又加入了条查找记录，所确定
16、的查找区间中的元素最多为 n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次数为 log 2 (n+1)次，查找结束。9.贪婪法是一种(20)的算法。（分数：2.00）A.不求最优，只求满意 B.只求最优C.求取全部可行解D.求取全部最优解解析：解析：贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法(或称贪婪法)一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。10.快速排序算法采用的设计方法是(23)。（分数：2.00）A.动态规划法(Dynamic Programming)B.分治法(Divideand Conquer) C
17、.回溯法(Backtracking)D.分枝定界法(Branch and Bound)解析：解析：快速排序算法采用的设计方法是分治法。11.利用动态规划法求解每对节点之间的最短路径问题时，设有向图 G=V，E共有 n 个节点，节点编号1n，设 C 是 G 的成本邻接矩阵，用 D k (i,j)表示从 i 到 j 并且不经过编号比 k 还大的节点的最短路径的长度(D n (i,j)即为图 G 中节点 i 到 j 的最短路径长度)，则求解该问题的递推关系式为(28)。（分数：2.00）A.D k (i,j)=D k -1(i,j)+C(i,j)B.D k (i,j)=minD k -1(i,j),
18、D k -1(i,j)+C(i,j)C.D k (i,j)=D k -1(i,k)+D k -1(k,j)D.D k (i,j)=minD k -1(i,j),D k -1(i,k)+D k -1(k,j) 解析：解析：从“D k (i,j)表示从 i 到 j 并且不经过编号比 k 还大的节点的最短路径的长度”中，我们得到一个提示，在求 i,j 之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在 D k (i,j)=minD k -1(i,j),D k -1(i,k)+D k -1(k,j)中，D k (i,j)表示 i 到 j 不经过 k 的路径长度，而 Dk-1(I,k)+Dk-
19、1(k,j)表示 i 到 j 经过 k 的路径长度，且 min()函数用于找最小值，所以此式正确。12.采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是(29)。（分数：2.00）A.当前所作出的决策不会影响后面的决策B.原问题的最优解包含其子问题的最优解 C.问题可以找到最优解，但利用贪心法不能找到最优解D.每次决策必须是当前看来最优的决策才可以找到最优解解析：解析：动态规划策略设计算法的第一步通常是刻画最优解结构。当问题的最优解包含了子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。动态规划策略设计算法利用问题的最优子
20、结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。为了解决进程间的同步和互斥问题，通常采用一种称为(1)机制的方法。若系统中有 5 个进程共享若干个资源 R，每个进程都需要 4 个资源 R，那么使系统不发生死锁的资源 R 的最少数目是(2)。（分数：4.00）A.调度B.信号量 C.分派D.通信解析：A.20B.18C.16 D.15解析：解析：信号量取自交通管理中的信号灯的概念，借其含义用信号量来作为一种控制进程互斥和同步的变量，也就是通过控制信号量来控制进程的同步与互斥。对实现进程的同步和互斥而言，信号量是一种很有效的工具，现已被广泛地应用于单处理机系统、多处理机
21、系统和计算机网络中。有同类资源 m 个，供n 个进程共享，每个进程最多申请资源 x 个(1xm)，则有：n(x-1)m。当 nxm+ n 时，系统不会出现死锁。因为每个进程在得到 x-1 个资源后，均要申请最后一个资源。只要系统中还有一个资源，就可能使其中一个进程得到满足。当该进程执行结束，归还的资源可供其他进程使用，因而不会发生死锁。所以这里需要资源数最少为 5x(4-1)+1=16 个。某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入仓库提货，顾客离开时，审核员检验顾客提货是否正确。其工作流程如图 3-2 所示。为了利用 PV 操作正确地协调他们之间的工作，设置了
22、两个信号量 S1 和 S2，且 S1 的初值为 2，S2 的初值为 1。在图中的 a 处应填写(3)，图中的 b，c 和 d 处应分别填写(4)。 （分数：4.00）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)解析：解析：根据题意，S1 初值为 2，表示发货员；S2 初值为 1，表示审核员。 顾客进入，排队等待发货员发货 P(S1)；发货后 V(S1)，发货员给下一位顾客发货，该顾客等待审核员检验 P(S2)：检验
23、完后V(S2)，审核员继续给下一位等待审核的顾客检验。关键在于是审核员检验完后，发货员才给下一位顾客发货，亦即发货员等待审核员的检验结果，还是发货员发完货就处于空闲，可以给下一位顾客发货。所以应该是发完货就空闲，不用等待审核员的检验结果。因此，a，b，c，d 依次为 P(S1)、V(S1)、P(S2)、V(S2)。在一个单 CPU 的计算机系统中，有两台外部设备 R1，R2 和三个进程 P1，P2，P3。系统采用可剥夺式优先级的进程调度方案，且所有进程可以并行使用 I/O 设备，三个进程的优先级、使用设备的先后顺序和占用设备时间如表 3-1 所示。 （分数：4.00）A.60B.67C.78D
24、.90 解析：A.70 B.78C.80D.89解析：解析：根据题目的叙述，我们可以作出进程运行的时空图帮助解题。从如图 3-3 所示的时空图中我们可以看出三个进程运行完毕需要 100ms，CPU 工作了 90ms，所以 CPU 的利用率为 90%： R2 工作了70ms。所以 R2 的工作效率为 70%。因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和(16)。对于缓冲池 (大量缓冲区)的管理，采用生产者-消费者方式解决同步或互斥时，通常需要用(17)个信号量。（分数：4.00）A.请求与释放B.释放与保持C.释放与阻塞D.保持与等待 解析：A.1B.2C.3 D.4解析：解析：进程
25、的并发执行会导致对资源的竞争。如果多个进程由于竞争资源造成一种僵局，而无外力作用，这些进程都将无法向前推进，就造成了死锁。死锁的产生有以下四个必要条件。(1)互斥条件：在一段时间内某资源只能被一个进程占有。(2)请求和保持条件：进程在申请新的资源得不到满足时，对已获得的其他资源保持不放。(3)不可剥夺条件：进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放。(4)环路等待条件：在资源有向图中，存在环路。在 n 个缓冲区，m 个生产者和 k 个消费者的生产者-消费者问题中，可利用互斥信号量 mutex 使诸进程实现对缓冲池的互斥使用，利用资源信号量 empty 和 full 分别
26、表示缓冲池中空缓冲区和满缓冲区的数量。因此通常需要 3 个信号量。主存按字节编址，地址从 A4000H 到 CBFFFH，共有(21)字节。若用存储容量为 32K*8bit 的存储器芯片构成该主存，至少需要(22)片。（分数：4.00）A.80KB.96KC.160K D.192K解析：A.2B.5 C.8D.10解析：解析：内存地址从 A4000H 到 CBFFFH 共有 160K 个存储单元，而内存是按字节编址的，故内存共有160K 字节。若要用存储容量为 32K*8bit 的存储器芯片构成内存，至少要 160/32=5 片。容量为 64 块的 Cache 采用组相连方式映像，字块大小为
27、128 个字，每 4 块为一组。若主存容量为 4096 块，且以字编址，那么主存地址应为(23)位，主存区号应为(24)位。（分数：4.00）A.16B.17C.18D.19 解析：A.5B.6 C.7D.8解析：解析：由于主存容量为 4096 块，而每块为 128 字节，所以主存的总容量为 512K 字节，故主存地址应为 19 位。主存地址应分为区号、组号、组内块号、块内地址号。可以知道，块内地址号应为 7 位，用来表示 128 字节。一组为 4 块，则组内块号用 2 位表示。Cache 容量为 64 块，共分为 16 组，故组号需要用 4 位地址表示。剩余的即为区号，应为 6 位。虚拟存储
28、管理系统的基础是程序的(25)理论，这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据此理论，Denning 提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时，如果它的工作集页面都在(26)内，能够使该进程有效地运行，否则会出现频繁的页面调儿调出现象。（分数：4.00）A.全局性B.局部性 C.时间全局性D.空间全局性解析：A.主存储器 B.虚拟存储器C.辅助存储器D.U 盘解析：解析：虚拟存储管理系统的基础是程序的局部性理论。所谓程序局部性原理是指程序在执行时所呈现的局部性规律，即在一段较短时间内，程序的执行仅限于某个部分。局部性原理表现为两个方面：
29、时间局限性和空间局限性。工作集是指在进程运行时被频繁访问的页面集合。虽然程序只需少量的几页内存就可以运行，但为了使程序更有效地运行，必须使程序的工作集全部在内存当中，否则会使进程在运行中频繁出现中断，从而出现频繁的页面调入/调出现象。MPEG-1 编码器输出视频的数据率大约为(37)。PAL 制式下其图像亮度信号的分辨率为(38)，帧速为(39)。（分数：6.00）A.128Kb/sB.320Kb/sC.1.5Mb/s D.15Mb/s解析：A.352288 B.576352C.720576D.1024720解析：A.16 帧/秒B.25 帧/秒 C.30 帧/秒D.50 帧/秒解析：解析：MPEG-1 编码器输出视频的数据率大约为 1.5Mb/s。PAL 制式下其图像亮度信号的分辨率为352288 像素，帧速率为 25 帧/秒。我国采用的电视标准是 PAL 制，它规定视频每秒 25 帧，每帧 625 个扫描行。另一种常见的数字视频格式 NTSC 制，规定视频每秒 30 帧，每帧 525 个扫描行，它同样采用了隔行扫描方式，每一帧由两场组成，其图像大小是 720486 像素。此外，还有一种由法国开发的彩色电视广播标准 SECAM，称为顺序传送和存储彩色电视，它与 PAL 制式类似。
