20xx上半年程序员模拟试题四上午答案word版(编辑修改稿)

20xx上半年程序员模拟试题四上午答案word版(编辑修改稿)内容摘要：

在大型的科学计算与复杂问题求解时，具体的算法针对具体问题，可以有无数种。 但一般常用类型有：迭代法、递推法、回溯法、递归法、贪婪法、穷举法、规划法等。 递归算法是常用算法之一，它的基本思想是把一个大的问题 (不妨设规模为 N)分解为一些规模较小的问题，从这些较小问题的解，构造出大问题的解，而这些规模较小的问题，用同样的方法分解成更小的问题 ，并从更小问题的解，构造出较小的问题。 不断地分解问题成更小的问题，一层层下去，一般来说，分解到最后的小问题 (例如N=1 时 )应该是可直接求解的。 依据上述思想，递归算法的过程一般分为递推和回归两个阶段。 在递推阶段把复杂问题逐级推到简单一点的问题的求解。 在递推到小问题能直接求解时，递推终止。 在回归阶段，则从所获得的最简单的直接解，逐级返回，得到大问题的解。 软考社区 ()中国软考资讯、交流中心。 提供 软考 历年试题，模拟试题， 电子教程 ， 软考新闻 ， 各地软考办 ， 软考经验心得 等。 软考社区论坛： ●散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。 因为散列函数不是一对一的关系，所以选择好的 (35) 方法是散列文件的关键。 (35) A．散列函数 B．除余法中的质数 C．冲突处理 D．散列函数和冲突处理 【解析】在散列法中，选择好的散列函数和冲突处理方法是其关键。 ●最佳二叉搜索树是 (36)。 (36) A．关键码个数最少的二叉搜索树 B．搜索时平均比较次数最少的二叉搜索树 C．所有结点的左子树都为空的二叉搜索树 D．所有结点的右子树都为空的二叉搜索树 【解析】最佳二叉搜索树是搜索时平均比较次数最少的二叉搜索树。 ●已知有二维数组 A［ 0．． n1］［ 0．． n1］，其中当 i+j=n 时， A［ i］［ j］≠ 0，现在要将 A数组压缩存储到一维数组 T［ 0..m］，其中 mn。 数组 T 的第一个元素 T［ 0］ =A［ 1］［ n1］ T［ 1］ =A［ 2］［ n2］，……，依次类推，那么放入 A［ i］［ j］ (i+j=n)的元素是 (37)。 (37) A． T［ i+j］ B． T［ i*n+j］ C． T［ i］ D． T［ i1］ 【解析】由题可知，除第 0 行外，每一行只存储一个元素，因此 i行应存放在 T［ i1］之中。 ●将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行 关键字比较 (38) 次。 (38) A． n B． n21 C． 2n1 D． 2n2 【解析】由于两个表有序，最少比较是一个表的最大结点，比另一个表的所有结点小。 如 {l， 2， 3}和 {4， 5， 6}。 我们只要将表中第一个结点 (最小结点 )，和另个表中所有结点比较，比较次数为另个表的表长。 ●对于一个具有 n 个结点和 e 条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为 (39)。 (39) A． 2e B． e/4 C． e／ 2 D． n+2e 【解析】用邻 接表表示无向图，图中每条边在邻接表中会出现两次，因此，对于一个具有 n个结点和 e 条边的无向图，所有边链表中边结点的总数为 2e。 ●在需要经常查找结点的前驱与后继的场合中，使用 (40) 比较合适。 (40) A．单链表 B．循环链表 C．链栈 D．双链表 【解析】双链表，一个链指向前驱结点，一个链指向后继结点。 ●在操作系统中，对信号量 S 的 P 原语操作定义中，使进程进入相应等待队列等待的条件是 (41)。 (41) A． S0 B． S=0 软考社区 ()中国软考资讯、交流中心。 提供 软考 历年试题，模拟试题， 电子教程 ， 软考新闻 ， 各地软考办 ， 软考经验心得 等。 软考社区论坛： C． S≠ 0 D． S0 【解析】 P(S)原语操作为： 1)将信号量 S 的值减 1，即 S=S1； 2)如果 S≥ 0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 ●下面几个方面中： Ⅰ．语法Ⅱ．语义Ⅲ．语句Ⅳ．语用 程序设计语言的定义一般应包括 (42)。 (42) A．Ⅰ、Ⅱ和Ⅲ B．Ⅰ、Ⅱ和Ⅳ C．Ⅰ、Ⅱ、Ⅲ和Ⅳ D．Ⅰ、Ⅲ和Ⅳ 【解析】程序设计语言的定义一般应包括语法、语义和语用几个方面。 语法是指记号的组合规则；语义指记号的特定意义；而语用是指程序与使用者的关系。 ●下面是关于 CPU 与主存储器之间的 Cache 的叙述，其中正确的是 (43)。 (43) A． Cache 存放的只是主存储器中某一部分内容的映象 B． Cache 能由用户直接访问 C．位于主板上的 L2 Cache 要比与 CPU 封装在一起的 L2 Cache 速度快 D．位于主板上的 L2 Cache 要比与 CPU 做在一基片上的 L2 Cache 速度快 【解析】 Cache 负责解决主存与 CPU 之间速度的协调问题。 Cache 中存放着主存的一部分副本 (主存中的部分内容 )，不能由用户直接访问。 Cache 可以有多级，离 CPU 越近的，速度越快。 ●某电视台拟将他人已出版的《卫生小常识》 VCD光盘在该电视台的 生活 节目中播放，那么，该电视台 (44)。 (44) A．可以不经该 VCD 光盘出版者许可，但必须向其支付报酬 B．既不必经该 VCD 光盘出版者许可，也不必向其支付报酬 C．既须经该 VCD 光盘出版者许可，也须向其支付报酬 D．只须经该 VCD 光盘出版者许可，但不必向其支付报酬 【解析】我国的《中华人民共和国著作权法》第四十五条规定：电视台播放他人的电影作品和以类似摄制电影的方法创作的作品、录像制品，应当取得制片者或者录像制作者许可，并支付报酬；播放他人的录像制品，还应当取得著作权人许可，并支付报酬。 ● (45) 是面向对象程序设计语言不同于其他语言的主要特点。 是否建立了丰富的 (46) 是衡量一个面向对象程序设计语言成熟与否的一个重要标志。 (47) 是在类及子类之间自动地共享数据和方法的一种机制。 (45) A．继承性 B．消息传递 C．多态性 D．封装性 (46) A．函数库 B．类库 C．数据库 D．方法库 (47) A．调用 B．引用 C．消息传递 D．继承 【解析】面向对象程序设计语言的主要特点是继承性、封装性和多态性，但由于面向过程的程序设计语言本身也具有一定的封装性和多态性。 面向对象程序设计语言对程序员开放的不再是函数库，而是类库。 丰富的类库可以软考社区 ()中国软考资讯、交流中心。 提供 软考 历年试题，模拟试题， 电子教程 ， 软考新闻 ， 各地软考办 ， 软考经验心得 等。 软考社区论坛： 加速软件的开发，减少开发人员的劳动，提高软件的质量，具有重要的意义。 当今成熟的面向对象设计语言都具有 丰富的类库。 子类通过对父类的继承可以立刻拥有父类的成员变量和成员方法。 ●白盒测试方法一般适合用于 (48) 测试。 (48) A．单元 B．系统 C．集成 D．回归 【解析】 白盒测试中，源程序对测试人员开放，允许测试人员根据程序的结构设计和选择相应的测试用例，以达到遍历程序的所有逻辑路径的目的，因此白盒测试适用于单元测试。 ●在 YUV彩色空间中对 YUV分量进行数字化，对应的数字化位数通常采用 Y： U： V= (49)。 (49) A． 8： 4： 4 B． 8： 4： 2 C． 8： 2： 4 D． 4： 8： 2 【解析】在现代彩色电视系统中，通常采用三管彩色摄像机或彩色 CCD 摄像机，它把摄得的彩色图像信号，经分色棱镜分成 RGB 3个分量信号，再经过放大和γ校正得到 RGB，经矩阵变换电路得到亮度信号 Y、色差信号RY(记为 U)及 BY(记为 V)，最后发送端将 Y、 U 及 V 3个信号进行编码，用同一信道发送出去。 这就是我们常用的 YUV彩色空间。 在 YUV彩色空间，数字化后通常为 Y： U： V=8： 4： 4 或 Y： U： V=8： 2： 2，即把亮度信号 Y 的每个像素都数字化为 8bit(256 级亮度 )，而 U、 V色差信号。