《近年程序员考试考练题训练及答案(1)(1)（测练习题）》由会员分享，可在线阅读，更多相关《近年程序员考试考练题训练及答案(1)(1)（测练习题）（19页珍藏版）》请在金锄头文库上搜索。
1、近3年程序员考试专项习题训练3及答案试题一（共15分）阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。【说明】 下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组A1:n(n2)中，要求寻找最长递增子序列AK : K+L-1(即AKAK+1 L(4) Kj (5) i+1【解析】 本题考查程序员在设计算法，理解并绘制程序流程图方面的能力。 本题的目标是：在给定的一个整数序列中查找最长的连续递增子序列。查找的方法 是：对序列中的数，从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面的数，则就是连续递增的情况；若发现后面的数并不大，则
2、以前查看的数中，要么没有连续递增的情况，要么连续递增的情况已经结束，需要再开始新的查找。 为了记录多次可能出现的连续递增情况，需要动态记录各次出现的递增子序列的起始位置（数组下标Kj）和长度（Lj）。为了求出最大长度的递增子序列，就需要设置变量L和K，保存迄今为止最大的Lj及其相应的Kj。正如打擂台一样，初始时设置擂主 L=1，以后当LjL时，就将Lj放到L中，作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而Kj则随LjL而保存到K中。 由于流程图中最关键的步骤是比较Ai与Ai+1，因此对i的循环应从1到n-1，而 不是1到n。最后一次比较应是“An-1An?”。因此（1）处应填
3、n-1。 当AiAi+1成立时，这是递增的情况。此时应将动态连续递增序列的长度增1，因此（2）处应填写Lj+1Lj。 当AiL。 当则Lj将做新的擂主（LjL)，同时执行KjK。所以（4）处应填Kj。 当Lj L不成立时，L不变，接着要从新的下标i+1处开始再重新查找连续递增子序列。因此（5）处应填i+1。长度Lj也要回到初始状态1。 循环结束时，可能还存在最后一个动态连续子序列（从下标Kj那里开始有长度Lj 的子序列）没有得到处理。因此还需要再打一次擂台，看是否超过了以前的擂主长度， 一旦超过，还应将其作为擂主，作为查找的结果。试题二（共15分）阅读以下说明和C代码，填补代码中的空缺，将解答
4、填入答题纸的对应栏内。【说明】 下面的代码运行时，从键盘输入一个四位数（各位数字互不相同，可以有0)，取出组成该四位数的每一位数，重组成由这四个数字构成的最大四位数max4和最小四位数 min4 (有0时为三位数)，计算max4与min4的差值，得到一个新的四位数。若该数不等于6174，则重复以上过程，直到得到6174为止。 例如，输入1234，则首先由4321-1234，得到3087；然后由8730-378，得到8352；最后由8532-2358，得到6174。 【C代码】 【答案】(1) j4 或等价形式(2) t=j(3) a0* 1000+a1* 100+a2* 10+a3 或等价形式
5、(4) a3* 1000+a2* 100+a1* 10+a0 或等价形式(5) n/1000 或等价形式(6) n%10 【解析】 本题考查C程序设计基本技能及应用。 题目要求在阅读理解代码说明的前提下完善代码。 由于C程序的执行是从main函数开始的，因此首先理解main函数的代码结构。显然，调用函数difference时实参为数组a，并且从注释中可以确定空（5)的内容为“n/1000” 或其等价形式，空（6）处填写“n%10”或其等价形式。这样，数组元素a0a3就依 次保存了 n值从左至右的各位数字。 接下来分析函数difference的代码结构。双重for循环是对数组a进行简单选择排序，
6、 目的是将数组中最大数字放入a0，最小的数字放入a3。处理思路是通过比较找出最大数字并用 t 记下最大数字所在数组元素的下标，第一趟需在a0a3中进行选择，通过比较记下最大数f的下标，最后将最大数字交换至a0，第二趟需在a1a3中进行选择，通过比较记下这三个数中最大者的下标，并最大者交换至a1，依次类推。因此，空（1）处应填入“j pivot 或 aj= pivot 或等价形式(2) ai = pivot 或 aipivot”，使得比基准值大者保持在序列后端。空（2）处应填入 “ai = pivot，使得不大于基准值者保持在前端。 在完成1次划分后，基准元素被放入ai，那么分出来的左子序列由a
7、0ai-1这i 个元素构成，右子序列由ai+1an-1构成，接下来应递归地对左、右子序列进行快排。 因此，结合注释，空（3）应填入“quicksort(a，i)”或其等价形式，以对左子序列的i个元素进行快排，也可以用&a0代替其中的a，它们是等价的，a与&a0都表示数组的起始地址。 空（4）所在代码实现对右子序列进行快排。右子序列由ai+1an-1构成，其元素个数为n-1-(i+1 )+1，即n-i-1，显然元素ai+1的地址为&ai+1或a+i+1，所以空（4）应填入“quicksort(a+i+1，n-i-1)” 或其等价形式。 在main函数中，空（5 )所在代码首次调用函数quicks
8、ort对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。 例如
9、，某含头结点单链表L如图4-1 (a)所示，删除第3个元素结点后的单链表如图4-1 (b)所示。【C代码】 【答案】(1) knext(3) p = L(4) p-next(5) *e = q-data 【解析】 本题考查C语言的指针应用和运算逻辑。 本问题的图和代码中的注释可提供完成操作的主要信息，在充分理解链表概念的基础上填充空缺的代码。 函数GetListElemPtr(LinkList L, int i)的功能是在L为头指针的链表中查找第i个元素，若找到，则返回指向该结点的指针，否则返回空指针。描述查找过程的代码如下， 其中k用于对元素结点进行计数。 上述代码执行时，k的初始值为1，同
10、时p指向第一个元素结点。当找到第i个元素结点时，k应等于i，尚未到达第i个结点时，k小于i。因此，空（1）处应填入“knext”, 从而使得指针p沿着链表中的结点向第i个结点移动。 函数DelListElem(LinkList L, int i, ElemType *e)的功能是删除含头结点单链表的第i 个元素结点，若成功则返回SUCCESS，并由参数e带回被删除元素的值，否则返回 ERROR。 根据注释，空（3）所在语句需要指向第一个结点之前的结点（即头结点），显然此处应填入“p=L”。 空（4）所在语句令q指向待删除的结点，由于之前已经令p指向待删除结点的前驱结点，显然，此空应填入“p-next”。 空（5）所在语句通过参数e带回被删除结点的数据，由于此时只能通过指针q找到被删除的结点，所以应填入“*e = q-data”。试题五（共15分）阅读以下说明和C+代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】 在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类 图如图5-1所示，相应的C+代码附后。【C+代码】 【答案】(1) public Order (2
