2023 下半年程序员第二期模考试卷（程序设计）1、N 有有序整数数组存放在 a 中，利用二分查找法查找整数 key 在数组中的位置，若找到，则输出其值和对应的下标，反之，则输出“Not be found！”二分查找的基本思想是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。问题内容：请完成下列流程图，使该流程图实现二分查找。【流程图】试题答案：（1）N-1（2）high=nid-1 （3）key>a[mid]（4）low=mid+1（5）k=mid（6）k>=0最终流程图如下图所示：2、用快速排序中的划分思想进行实现如下功能：在 n 个元素的整型数组中，确定其第 i（1≤i≤n）小的数。具体算法如下：首先以第一个数为基准，进行快速排序。快速排序后，会以基准值为界，左侧的元素都比基准值要小，右侧的元素比基准值大。且排序完成后可以确定基准值是排在第 k 位，判断 k 与 i 的关系，如果 k<i 则下次只需对快速排序结果中排在基准值左侧的进行下一次递归；如果 k=i，表示刚好查找到第 i 小的元素；如果 k>i 则下次只需对快速排序结果中排在基准值右侧的进行下一次递归。C 代码实现如下（请将空白区域代码补充完整）。【C 代码】#include <stdio.h>#include<stdlib.h>int partition(int *a,int low,int high) {//以第一个为基准，利用快速排序找到它排序后所对应的下标int pivot=a[low];while(low<high){while(low<high&&a[high]>=pivot)high--;a[low]=a[high];while(low<high&&a[low]<=pivot)low++;a[high]=a[low];}a[low]=pivot;return low;}int select(int *a,int low,int high,int i){//select 函数实现查找 a 数组中，从 low~high 范围内找第 i 个最小值if(low==high)return （ 1 ）;//当只含有一个元素值，返回这个值int pivot= partition(a,low,high);//通过快速排序查找第一个元素的下标位置 int k= （ 2 ）;//确定第一个元素值从小到大排第几if(k==i)return （ 3 ）;//刚好一致时，返回对应元素值else if(i<k )return （ 4 ）; //i<k 时，用递归找其左侧范围内找第 i 个最小值elsereturn （ 5 ）; //反之，用递归找其右侧范围内找第 i 个最小值}int main(){int a[]={1,34,5,16,37,28,9,13,26};int result= select(a,0,sizeof(a)/sizeof(int)-1,2);printf("%d\n",result);return 0;}问题内容：试题答案：1）a[low]或者 a[high]2) pivot-low+13）a[pivot]4）select(a,low,pivot-1,i)5）select(a,pivot+1,high,i-k)3、阅读以下说明和 C 代码，填写程序中的空（1）~（5），将解答写入对应栏内。 【说明】Fibonacci 数列为 1,1,2,3,5,8,13,…其第一项和第二项为 1,后面每一项都是前面两项之和。【代码1】是采用数组来产生 Fibonacci 数列前 10 项。【代码 2】采用用递归函数来产生 Fibonacci 数列前10 项，请填补代码中的空缺，实现程序的功能。【代码 1】#include <stdio.h> int main(){int a[10],i;a[0]=1;a[1]=1;for(（ 1 ）;i<10;i++){a[i]= （ 2 ）;//对数组元素赋值printf("%d\t",（ 3 ）);//输出数组元素}return 0;}【代码 2】#include <stdio.h>int F(int n){if(（ 4 ）)return 1;return （ 5 ）;}int main(){int i;for(i=1;i<=10;i++){printf("%d\t",F(i));//输出数组元素}return 0;}问题内容：试题答案：（1）i=2（2）a[i-1]+a[i-2]（3）a[i]（4）n<=2（5）F(n-1)+F(n-2)4、函数 int maxOne(int arr[],int k，int n)的功能是递归方法求指定数组 arr 中后 K 个元素中的最大者，其中 arr 数组中元素个数为 n（n≥k），并将最大值作为函数值返回。下面用 C 语言代码实现这一功能，请将空白的部分补充完整。问题内容：【C 代码】#include <stdio.h>int maxOne(int a[],int k, int n)// 函数功能是递归方法求指定数组 arr 中后 K 个元素中的最大者{ int t; if(k==1) return （ 1 ） ; t=maxOne(（ 2 ）); if(a[n-1]<=t) return （ 3 ）; else return （ 4 ）;} int main () { int a[10]={1,3,7,89,12,2,65,3,56,8}; printf("最大值是：%d",（ 5 ）);// 得到数组 a 中后 5 个元素中的最大者 return 0;}试题答案：（1）a[n-1]（2）a,k-1,n-1 或者 a+n-k,k-1,k-1（3）t（4）a[n-1]（5）maxOne(a,5,10)5、阅读下列说明和 C++代码，填补代码中的空缺，将解答填入对应栏内。【说明】通过创建一个统一的外观类包装多个复杂的类，用于一键控制所有家电（灯、电视和空调等），可以起床后一次打开所有设备和睡觉前关闭所有设备。【C++代码】#include <iostream>using namespace std;//灯类class Light{public:void on(){ cout<<"打开了灯"<<endl; }void off(){ cout<<"关闭了灯"<<endl; }};//电视类class Television {public:void on(){ cout<<"打开了电视"<<endl; }void off(){ cout<<"关闭了电视"<<endl; }};//空调类class Aircondition {public:void on(){ cout<<"打开了空调"<<endl; }void off(){ cout<<"关闭了空调"<<endl; }};class Facade{private:Light light;Television television;Aircondition aircondition;//传参public:Facade(Light light,Television television,Aircondition aircondition) : （ 1 ） {} //起床后一键开电器void on(){cout<<"\n 起床了"<<endl;light.on();television.on();aircondition.on();}//睡觉时一键关电器void off(){cout<<"\n 睡觉了"<<endl;light.off();television.off();aircondition.off();}};int main(){//实例化电器类（ 3 ）;Television *television = new Television();Aircondition *aircondition = new Aircondition();//传参Facade *facade =（ 3 ）;（ 4 ）;//一键开启（ 5 ）;//一键关闭return 0;}程序执行结果如下：起床了打开了灯打开了电视打开了空调睡觉了关闭了灯关闭了电视关闭了空调问题内容：试题答案：（1）light ( light ) , television ( television ) , aircondition ( aircondition )（2）Light *light = new Light()（3）new Facade(*light,*television,*aircondition)（4）facade->on()（5）facade->off()6、阅读下列说明和 JAVA 代码，填补代码中的空缺，将解答填入对应栏内。【说明】 通过创建一个统一的外观类包装多个复杂的类，用于一键控制所有家电（灯、电视和空调等），可以起床后一次打开所有设备和睡觉前关闭所有设备。【JAVA 代码】//灯类class Light{ public void on(){ System.out.println("打开了灯"); } public void off(){ System.out.println("关闭了灯"); } } //电视类class Television { public void on(){ System.out.println("打开了电视"); } public void off(){ System.out.println("关闭了电视"); } } //空调类class Aircondition { public void on(){ System.out.println("打开了空调"); } public void off(){ System.out.println("关闭了空调"); } } class Facade{Light light;Television television;Aircondition aircondition;//传参public Facade(Light light,Television television,Aircondition aircondition){ （ 1 ）;（ 2 ）;（ 3 ）;} //起床后一键开电器public void on(){System.out.println("\n 起床了"); light.on(); television.on();aircondition.on();}//睡觉时一键关电器public void off(){System.out.println("\n 睡觉了"); light.off(); television.off();aircondition.off(); }}class FacadePattern{ public static void main(String[] args){//实例化电器类（ 4 ）; Television television = new Television();Aircondition aircondition = new Aircondition();//传参Facade facade = （ 5 ）;facade.on();//一键开启facade.off();//一键关闭}}程序执行结果如下：起床了打开了灯打开了电视打开了空调睡觉了关闭了灯关闭了电视关闭了空调问题内容：试题答案：（1）this.light = light（2）this.television = television（3）this.aircondition =aircondition（4）Light light = new Light()（5）new Facade(light,television,aircondition)