程序员-3期（PX014） 初级程序员2015下半年试题及解答 2015年下半年软考程序员下午试卷参考答案版.docx

试题一（共15分） 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组A[1:n](nge;2)中，要求寻找最长递增子序列A[K : K+L-1](即A[K]lt;A[K+1]lt;hellip;lt;A[K+L-1])。 流程图中，用Kj和Lj分别表示动态子序列的起始下标和长度，最后输出 . 最长递增子序列的起始下标K和长度L。 例如，对于序列A={1，2，4，4，5，6，8，9，4，5，8}，将输出 K=4，L=5。 【流程图】 注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值 【答案】 n-1 Lj+1rarr;Lj LjL Kj i+1 【解析】本题考查程序员在设计算法，理解并绘制程序流程图方面的能力。 本题的目标是：在给定的一个整数序列中查找最长的连续递增子序列。查找的方法 是：对序列中的数，从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面的数，则就是连续递增的情况；若发现后面的数并不大，则以前查看的数中，要么没有连续递增的情况，要么连续递增的情况已经结束，需要再开始新的查找。 为了记录多次可能出现的连续递增情况，需要动态记录各次出现的递增子序列的起始位置（数组下标Kj）和长度（Lj）。为了求出最大长度的递增子序列，就需要设置变量L和K，保存迄今为止最大的Lj及其相应的Kj。正如打擂台一样，初始时设置擂主 L=1，以后当LjL时，就将Lj放到L中，作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而Kj则随Ljrarr;L而保存到K中。 由于流程图中最关键的步骤是比较A[i]与A[i+1]，因此对i的循环应从1到n-1，而 不是1到n。最后一次比较应是“A[n-1]lt;A[n]?”。因此（1）处应填n-1。 当A[i]lt;A[i+1]成立时，这是递增的情况。此时应将动态连续递增序列的长度增1，因此（2）处应填写Lj+1rarr;Lj。 当A[i]lt;A[i+1]不成立时，表示以前可能存在的连续递增已经结束。此时的动态长度 Lj应与擂台上的长度L进行比较。即（3）处应填LjL。 当则Lj将做新的擂主（Ljrarr;L)，同时执行Kjrarr;K。所以（4）处应填Kj。 当Lj L不成立时，L不变，接着要从新的下标i+1处开始再重新查找连续递增子序列。因此（5）处应填i+1。长度Lj也要回到初始状态1。 循环结束时，可能还存在最后一个动态连续子序列（从下标Kj那里开始有长度Lj 的子序列）没有得到处理。因此还需要再打一次擂台，看是否超过了以前的擂主长度， 一旦超过，还应将其作为擂主，作为查找的结果。 试题二（共15分） 阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的代码运行时，从键盘输入一个四位数（各位数字互不相同，可以有0)，取出组成该四位数的每一位数，重组成由这四个数字构成的最大四位数max4和最小四位数 min4 (有0时为三位数)，计算max4与min4的差值，得到一个新的四位数。若该数不等于6174，则重复以上过程，直到得到6174为止。 例如，输入1234，则首先由4321-1234，得到3087；然后由8730-378，得到8352；最后由8532-2358，得到6174。 【C代码】 【答案】 (1) jlt;4 或等价形式 (2) t=j (3) a[0]* 1000+a[1]* 100+a[2]* 10+a[3] 或等价形式 (4) a[3]* 1000+a[2]* 100+a[1]* 10+a[0] 或等价形式 (5) n/1000 或等价形式 (6) n%10 【解析】本题考查C程序设计基本技能及应用。 题目要求在阅读理解代码说明的前提下完善代码。 由于C程序的执行是从main函数开始的，因此首先理解main函数的代码结构。显然，调用函数difference时实参为数组a，并且从注释中可以确定空（5)的内容为“n/1000” 或其等价形式，空（6）处填写“n%10”或其等价形式。这样，数组元素a[0]#12316;a[3]就依 次保存了 n值从左至右的各位数字。 接下来分析函数difference的代码结构。双重for循环是对数组a进行简单选择排序， 目的是将数组中最大数字放入a[0]，最小的数字放入a[3]。处理思路是通过比较找出最大数字并用 t 记下最大数字所在数组元素的下标，第一趟需在a[0]#12316;a[3]中进行选择，通过比较记下最大数f的下标，最后将最大数字交换至a[0]，第二趟需在a[1]#12316;a[3]中进行选择，通过比较记下