2015下半年程序员考试真题及答案-下午卷.doc

发布时间：2022-10-10 发布人：admin 分类：说明书资料大小：1.58M 资料格式：doc 举报版权申诉

第1页 / 共19页

第2页 / 共19页

第3页 / 共19页

第4页 / 共19页

第5页 / 共19页

第6页 / 共19页

第7页 / 共19页

第8页 / 共19页

文本预览

2015 下半年程序员考试真题及答案-下午卷试题一（共 15 分）阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。【说明】下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n≥2)中，要求寻找最长递增子序列 A[K : K+L-1](即 A[K]

(3) Lj>L (4) Kj (5) i+1 【解析】本题考查程序员在设计算法，理解并绘制程序流程图方面的能力。本题的目标是：在给定的一个整数序列中查找最长的连续递增子序列。查找的方法是：对序列中的数，从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面的数，则就是连续递增的情况；若发现后面的数并不大，则以前查看的数中，要么没有连续递增的情况，要么连续递增的情况已经结束，需要再开始新的查找。为了记录多次可能出现的连续递增情况，需要动态记录各次出现的递增子序列的起始位置（数组下标 Kj）和长度（Lj）。为了求出最大长度的递增子序列，就需要设置变量 L 和 K，保存迄今为止最大的 Lj 及其相应的 Kj。正如打擂台一样，初始时设置擂主 L=1，以后当 Lj>L 时，就将 Lj 放到 L 中，作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而 Kj 则随 Lj→L 而保存到 K 中。由于流程图中最关键的步骤是比较 A[i]与 A[i+1]，因此对 i 的循环应从 1 到 n-1，而不是 1 到 n。最后一次比较应是“A[n-1]L。当则 Lj 将做新的擂主（Lj→L)，同时执行 Kj→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) j<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]〜a[3]就依次保存了 n 值从左至右的各位数字。接下来分析函数 difference 的代码结构。双重 for 循环是对数组 a 进行简单选择排序，目的是将数组中最大数字放入 a[0]，最小的数字放入 a[3]。处理思路是通过比较找出最大数字并用 t 记下最大数字所在数组元素的下标，第一趟需在 a[0]〜a[3]中进行选择，通过比较记下最大数 f 的下标，最后将最大数字交换至 a[0]，第二趟需在 a[1]〜a[3]中进行选择，通过比较记下这三个数中最大者的下标，并最大者交换至 a[1]，依次类推。因此，空（1）处应填入“j<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]”，或其等价形式。

试题三（共 15 分）阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。函数 quicksort(int a[], int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素 a[0]〜a[n-1]中。【C 代码】

【答案】 (1) a[j] > pivot 或 a[j]>= pivot 或等价形式 (2) a[i] <= pivot 或 a[i]pivot”，使得比基准值大者保持在序列后端。空（2）处应填入 “a[i] <= pivot"，使得不大于基准值者保持在前端。在完成 1 次划分后，基准元素被放入 a[i]，那么分出来的左子序列由 a[0]〜a[i-1]这 i 个元素构成，右子序列由 a[i+1]~a[n-1]构成，接下来应递归地对左、右子序列进行快排。因此，结合注释，空（3）应填入“quicksort(a，i)”或其等价形式，以对左子序列的 i 个元素进行快排，也可以用&a[0]代替其中的 a，它们是等价的，a 与&a[0]都表示数组的起始地址。空（4）所在代码实现对右子序列进行快排。右子序列由 a[i+1]~a[n-1]构成，其元素个数为 n-1-(i+1 )+1，即 n-i-1，显然元素 a[i+1]的地址为&a[i+1]或 a+i+1，所以空（4）

应填入“quicksort(a+i+1，n-i-1)” 或其等价形式。在 main 函数中，空（5 )所在代码首次调用函数 quicksort 对 main 函数中的数组 arr 进行快排，因此应填入“arr，sizeof(arr)/sizeof(int)”或其等价形式。

试题四（共 15 分）阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第 i 个元素。若找到，则返回指向该结点的指针，否则返回空指针。函数 DelListElem(LinkList L，int i，ElemType *e)的功能是删除含头结点单链表的第 i 个元素结点，若成功则返回 SUCCESS，并由参数 e 带回被删除元素的值，否则返回 ERROR。例如，某含头结点单链表 L 如图 4-1 (a)所示，删除第 3 个元素结点后的单链表如图 4-1 (b)所示。【C 代码】

分享到：

赞收藏

资料库

2015下半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料