1、初级程序员 2015 下半年下午试题及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 说明 下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A1:n(n2)中，要求寻找最长递增子序列 AK:K+L-1(即 AKAK+1AK+L-1)。流程图中，用 Kj和 Lj 分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标 K 和长度 L。 例如，对于序列 A=1，2，4，4，5，6，8，9，4，5，8，将输出 K=4，L=5。 流
2、程图 （分数：15.00）_二、试题二(总题数：1，分数：15.00)2.阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 下面的代码运行时，从键盘输入一个四位数(各位数字互不相同，可以有 0)，取出组成该四位数的每一位数，重组成由这四个数字构成的最大四位数 max4 和最小四位数 min4(有 0 时为三位数)，计算 max4 与min4 的差值，得到一个新的四位数。若该数不等于 6174，则重复以上过程，直到得到 6174 为止。 例如，输入 1234，则首先由 4321-1234，得到 3087；然后由 8730-378，得到 8352；最后由 8532-2
3、358，得到 6174。 C 代码 #includestdio.h int difference(int a) ( int t,i,j,max4,min4; for(i=0; i3; i+)/*用简单选择排序法将 a0a3按照从大到小的顺序排列*/ t=i; for(j=i+1; _; j+) if(ajat) _; if(t!=i) int temp=at; at=ai; ai=temp; max4=_; min4=_; return max4-min4; int main() int n,a4; printf(“input a positive four-digit number:“);
4、scanf(“%d“, while(n!=6174) a0= _; /*取 n 的千位数字*/ a1=n/100%10; /*取 n 的百位数字*/ a2=n/10%10; /*取 n 的十位数字*/ a3= _; /取 n 的个位数字*/ n=difference(a); return 0; （分数：15.00）_三、试题三(总题数：1，分数：15.00)3.阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大
5、于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。 函数 quicksort(int a,int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素a0an-1中。 C 代码 #includestdio.h void quicksort(int a, int n) int i,j; int pivot=a0; /设置基准值 i=0; j=n-1; while (ij) while (i1 /大于基准值者保持在原位置 if (ij) ai =aj; i+; while(ij /不大于基准值者保持在原位置 if (i1) aj =ai;
6、 1-; ai=pivot; /基准元素归位 if (i1 ) _; /递归地对左孔序列进行快速排序 if (n-i-11 ) _; /递归地对右孔序列进行快速排序 int main() int i, arr =23,56,9,75,18,42,11,67; quicksort(_); /调用 quicksort 对数组 arr进行排序 for( i=0; isizeof(arr)/sizeof(int); i+ ) printf(“%dt“,arri); return 0; （分数：15.00）_四、试题四(总题数：1，分数：15.00)4.阅读以下说明和 C 代码，填补代码中的空缺，将解答
7、填入答题纸的对应栏内。 说明 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第 i 个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数 DelListElem(LinkList L,int i,ElemType *e)的功能是删除含头结点单链表的第 i 个元素结点，若成功则返回 SUCCESS，并由参数 e 带回被删除元素的值，否则返回 ERROR。 例如，某含头结点单链表 L 如下图(a)所示，删除第 3 个元素结点后的单链表如下图(b)所示。 （分数：15.00）_五、试题五(总题数：1，分数：15.00)5.阅读以下说明和
8、C+代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如下图所示，相应的C+代码附后。 （分数：15.00）_六、试题六(总题数：1，分数：15.00)6.阅读以下说明和 Java 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如下图所示。相应的Java 代码附后。 （分数：15.00）_初级程序员 2015 下半年下午试题答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.阅读以
9、下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 说明 下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A1:n(n2)中，要求寻找最长递增子序列 AK:K+L-1(即 AKAK+1AK+L-1)。流程图中，用 Kj和 Lj 分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标 K 和长度 L。 例如，对于序列 A=1，2，4，4，5，6，8，9，4，5，8，将输出 K=4，L=5。 流程图 （分数：15.00）_正确答案：()解析：n-1 Lj+1Lj LjL Kj i+1 解析 本题考查程序员在设计算法，理解并绘制程序流
10、程图方面的能力。 本题的目标是：在给定的一个整数序列中查找最长的连续递增子序列。查找的方法是：对序列中的数，从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面的数，则就是连续递增的情况；若发现后面的数并不大，则以前查看的数中，要么没有连续递增的情况，要么连续递增的情况已经结束，需要再开始新的查找。 为了记录多次可能出现的连续递增情况，需要动态记录各次出现的递增子序列的起始位置(数组下标 K1)和长度(Lj)。为了求出最大长度的递增子序列，就需要设置变量 L 和 K，保存迄今为止最大的 Lj 及其相应的 Kj。正如打擂台一样，初始时设置擂主 L=1，以后当 LiL 时，就将 Lj 放到
11、L 中，作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而 Kj 则随 LjL 而保存到 K 中。 由于流程图中最关键的步骤是比较 Ai与 Ai+1，因此对 i 的循环应从 1 到 n-1，而不是 1 到 n。最后一次比较应是“An-1An?”。因此(1)处应填 n-1。 当 AiAi+1成立时，这是递增的情况。此时应将动态连续递增序列的长度增 1，因此(2)处应填写Li+1Lj。 当 AiAi+1不成立时，表示以前可能存在的连续递增已经结束。此时的动态长度 Li 应与擂台上的长度 L 进行比较。即(3)处应填 LjL。 当 LjL 时，则 Lj 将做新的擂主(LjL)，同时执行
12、KjK。所以(4)处应填 Kj。 当 LjL 不成立时，L 不变，接着要从新的下标 i+1 处开始再重新查找连续递增子序列。因此(5)处应填i+1。长度 Lj 也要回到初始状态 1。 循环结束时，可能还存在最后一个动态连续子序列(从下标 Kj 那里开始有长度 Lj 的子序列)没有得到处理。因此还需要再打一次擂台，看是否超过了以前的擂主长度。一旦超过，还应将其作为擂主，作为查找的结果。二、试题二(总题数：1，分数：15.00)2.阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 下面的代码运行时，从键盘输入一个四位数(各位数字互不相同，可以有 0)，取出组成该四位数
13、的每一位数，重组成由这四个数字构成的最大四位数 max4 和最小四位数 min4(有 0 时为三位数)，计算 max4 与min4 的差值，得到一个新的四位数。若该数不等于 6174，则重复以上过程，直到得到 6174 为止。 例如，输入 1234，则首先由 4321-1234，得到 3087；然后由 8730-378，得到 8352；最后由 8532-2358，得到 6174。 C 代码 #includestdio.h int difference(int a) ( int t,i,j,max4,min4; for(i=0; i3; i+)/*用简单选择排序法将 a0a3按照从大到小的顺序排
14、列*/ t=i; for(j=i+1; _; j+) if(ajat) _; if(t!=i) int temp=at; at=ai; ai=temp; max4=_; min4=_; return max4-min4; int main() int n,a4; printf(“input a positive four-digit number:“); scanf(“%d“, while(n!=6174) a0= _; /*取 n 的千位数字*/ a1=n/100%10; /*取 n 的百位数字*/ a2=n/10%10; /*取 n 的十位数字*/ a3= _; /取 n 的个位数字*/
15、n=difference(a); return 0; （分数：15.00）_正确答案：()解析：j4 或等价形式 t=j a0*1000+a1*100+a2*10+a3 或等价形式 a3*1000+a2*100+a1*10+a0 或等价形式 n/1000 或等价形式 n%10 解析 本题考查 C 程序设计基本技能及应用。 题目要求在阅读理解代码说明的前提下完善代码。 由于 C 程序的执行是从 main 函数开始的，因此首先理解 main 函数的代码结构。显然，调用函数difference 时实参为数组 a，并且从注释中可以确定空(5)的内容为“n/1000”或其等价形式，空(6)处填写“n%1
16、0”或其等价形式。这样，数组元素 a0a3就依次保存了 n 值从左至右的各位数字。 接下来分析函数 difference 的代码结构。双重 for 循环是对数组 a 进行简单选择排序，目的是将数组中最大数字放入 a0，最小的数字放入 a3。处理思路是通过比较找出最大数字并用 t 记下最大数字所在数组元素的下标，第一趟需在 a0a3中进行选择，通过比较记下最大数字的下标，最后将最大数字交换至 a0，第二趟需在 a1a3中进行选择，通过比较记下这三个数中最大者的下标，并最大者交换至 a1，依次类推。因此，空(1)处应填入“j4”或其等价形式，以限定选择范围，空(2)处应填入“t=j”，以记下选择范
17、围内最大者的下标。 根据题目的说明部分，显然空(3)处应填入“a0*1000+a1*100+a2*10+a3”、空(4)处应填入“a3*1000+a2*100+a1*10+a0”，或其等价形式。三、试题三(总题数：1，分数：15.00)3.阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。 函数 quicksort
18、(int a,int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素a0an-1中。 C 代码 #includestdio.h void quicksort(int a, int n) int i,j; int pivot=a0; /设置基准值 i=0; j=n-1; while (ij) while (i1 /大于基准值者保持在原位置 if (ij) ai =aj; i+; while(ij /不大于基准值者保持在原位置 if (i1) aj =ai; 1-; ai=pivot; /基准元素归位 if (i1 ) _; /递归地对左孔序列进行快速排序 if (n-i-11
19、) _; /递归地对右孔序列进行快速排序 int main() int i, arr =23,56,9,75,18,42,11,67; quicksort(_); /调用 quicksort 对数组 arr进行排序 for( i=0; isizeof(arr)/sizeof(int); i+ ) printf(“%dt“,arri); return 0; （分数：15.00）_正确答案：()解析：ajpivot 或 aj=pivot 或等价形式 ai=pivot 或 aipivot 或等价形式 quicksort(a,i) 或 quicksort(a,j) 或等价形式 quicksort(a+
20、i+1,n-i-1) 或 quicksort(a+j+1，n-j-1) 或等价形式 注：a+i+1 可表示为 p=L-next; /*令 p 指向第 1 个元素所在结点*/ while(p +k; 上述代码执行时，k 的初始值为 1，同时 p 指向第一个元素结点。当找到第 i 个元素结点时，k 应等于 i，尚未到达第 i 个结点时，k 小于 i。因此，空(1)处应填入“ki”或其等价形式，使得没有达到第 i 个结点时继续查找。空(2)处应填入“p=p-next”，从而使得指针 p 沿着链表中的结点向第 i 个结点移动。 函数 DelListElem(LinkList L,int i, Elem
21、Type *e)的功能是删除含头结点单链表的第 i 个元素结点，若成功则返回 SUCCESS，并由参数 e 带回被删除元素的值，否则返回 ERROR。 根据注释，空(3)所在语句需要指向第一个结点之前的结点(即头结点)，显然此处应填入“p=L”。 空(4)所在语句令 q 指向待删除的结点，由于之前已经令 p 指向待删除结点的前驱结点，显然，此空应填入“p-next”。 空(5)所在语句通过参数 e 带回被删除结点的数据，由于此时只能通过指针 q 找到被删除的结点，所以应填入“*e=q-data”。五、试题五(总题数：1，分数：15.00)5.阅读以下说明和 C+代码，填补代码中的空缺，将解答填
22、入答题纸的对应栏内。 说明 在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如下图所示，相应的C+代码附后。 （分数：15.00）_正确答案：()解析：publicOrder this-stock 或(*this).stock Order* orderListi 或 *(orderList+i) placeOrders 解析 本题考查 C+语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。 先考查题目说明，在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。根据说明进行设计，题目
23、说明中给出了类图。涉及到股票(Stock)、股票代理(Broker)、股票操作指示(StockCommand)、买卖股票(Order 接口、BuyStock 与 SellStock 类)等类以及相关操作。 Stock 类定义了两个函数 buy()和 sell()，分别实现买和卖的操作。在构造函数中接收参数 name 和quantity，分别表示买卖股票的名称和数量，对当前所创建对象中的 name 和 quantity 赋值，用 this 表示区别当前对象，所以构造函数为： Stock(String name,int quantity) thiS-name=name; thiS-quantity
24、=quantity; Order 虚类声明纯虚函数 execute()：virtual void execute()=0；表示执行股票交易(即买和卖)的函数原型。 BuyStock 继承 Order，构造函数接收参数 stock，实现函数 execute()，进行股票买入，stock-buy()。SellStock 和 BuyStock 类似，继承 Order，构造函数接收参数 stock，实现函数 execute()，进行股票卖出，stock-sell()。 Broker 类实现接受客户的买卖指示 tackOrder()，接收 BuyStock 或者 SellStock 的实例，BuySto
25、ck 和SellStock 均是 Order 的子类，所以 BuyStock 和 SellStock 的实例也是 Order，因此 tackOrder0 所接收的参数用 Order 类型。接收到买卖指示之后，存入 vectorOrder*类型的 orderList 中，即orderList.push_back(order)。placeOrders()函数是实现将所有买卖股票的指示进行实际买入和卖出操作，即采用 for 循环，对每个 orderList 中的 Stock 实例，调用在 BuyStock 和 SellStock 中实现的execute()加以执行。 for(int i=0; ior
26、derList.Size();i+) orderListi-execute(); StockCommand 主要是根据操作指示进行股票交易，实现为一个函数 main()，其中创建欲进行交易的股票对象 aStock 和 bStock，创建买 aStock 卖 bStock 股票的对象 buyStockOrder 和 sellStockOrder 对象： Order*buyStockorder=new BuyStock(aStock); Order* sellStockOrder=new SellStock(bStock); 再创建股票代理 Broker 类的对象 broker，并接收买卖股票的指
27、示： broker-takeOrder(buyStockOrder); broker-takeOrder(sellStockOrder); 最后将所有买卖指示用 placeOrders()下执行命令： broker-placeOrders (); 主控逻辑代码在 main()函数中实现。在 main()函数中，先初始化 StockCommand 类的对象指针stockCommand，代码为： StockCommand* stockCommand=new StockCommand(); 即生成一个股票指示，并调用其 main()函数启动股票交易，即调用 stockCommand 的 main()
28、函数，实现股票的买卖指示的创建和执行。主控 main()函数中，使用完数组对象之后，需要用 delete 操作释放对象，对 stockCommand 对象进行删除，即 delete StockCommand; 因此，空(1)需要表示继承 Order 类的“public Order”；空(2)需要表示当前对象的 stock 属性，填入“this-stock”或“(*this).stock”；空(3)需要填入 BuyStock 和 SellStock 均能表示的父类“Order*”；空(4)需要 orderList 中每个对象指针调用 execute()，即填入“orderListi”或“*(or
29、derList+i)”；空(5)处为调用“placeOrders()”来下达执行命令。六、试题六(总题数：1，分数：15.00)6.阅读以下说明和 Java 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如下图所示。相应的Java 代码附后。 （分数：15.00）_正确答案：()解析：implements this.stock Order Order placeOrders() 解析 本题考查 Java 语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程
30、序思路，然后完成题目。 先考查题目说明，在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。根据说明进行设计，题目说明中给出了类图。涉及到股票(Stock)、股票代理(Broker)、股票操作指示(StockCommand)、买卖股票(Order 接口、BuyStock 与 SellStock 类)等类以及相关操作。 Stock 类定义了两个操作 buy()和 sell()，分别实现买和卖的操作。在构造函数中接收参数 name 和quantity，分别表示买卖股票的名称和数量，对当前所创建对象中的 name 和 quantity 赋值，用 this 表示区别当前对象，所以构造器
31、为： public Stock(String name,int quantity) this.name=name; this.quantity=quantity; Order 接口声明接口 execute()，表示执行股票交易(即买和卖)方法接口。 BuyStock 实现接口 Order：class BuyStock implements Order，构造器接收参数 stock，实现方法execute()，进行股票买入，stock.buy()。SellStock 和 BuyStock 类似，实现接口 Order，构造器接收参数 stock，实现函数 execute()，进行股票卖出，stock
32、.sell()。 Broker 类实现接收客户的买卖指示 tackOrder()，接收 BuyStock 或者 SellStock 的实例，BuyStock 和SellStock 均是 Order 的实现类，所以 BuyStock 和 SellStock 的实例也是 Order 类型，因此 tackOrder0所接收的参数用 Order 类型。接收到买卖指示之后，存入 ListOrder类型(具体对象类型为ArrayListOrder)的 orderList 中： orderList.push_back(order); placeOrders()函数是实现将所有买卖股票的指示进行实际买入和卖出
33、操作，即采用 for 循环，Java 自1.5 起支持 foreach 循环，对每个 orderList 中的 Stock 实例，调用在 BuyStock 和 SellStock 中实现的execute()加以执行。 for (Order order:orderList) order.execute(); StockCommand 主要是根据操作指示进行股票交易，主控逻辑代码实现在 main()方法中，其中创建欲进行交易的股票对象 aStock 和 bStock，创建买 aStock 卖 bStock 股票的对象 buyStockOrder 和sellStockOrder 对象： Order
34、buyStoCkOrder=new BuyStock(aStock); Order sellStoCkOrder=new SellStock(bStock); 再创建股票代理 Broker 类的对象 broker，并接收买卖股票的指示： broker.takeOrder(buyStockOrder); broker.takeOrder(SellStockOrder); 最后将所有买卖指示用 placeOrders()下执行命令： broker.placeOrders (); 因此，空(1)需要表示实现 Order 接口的关键字 implements；空(2)需要表示当前对象的 stock 属性，this.stock；空(3)需要 BuyStock 和 SellStock 均能表示的所实现的接口类型 Order；空(4)需要orderList 中每个对象的类型 Order 并能调用 execute()；空(5)处为调用 placeOrders()。
