2025上半年程序员第二期模考试卷（应用技术）

希赛网2025上半年程序员第二期模考活动已结束，现将2025上半年程序员第二期模考试卷（应用技术）分享给大家。模考试卷PDF版本可在本文文首本文资料处或文末的资料下载栏目下载。

2025上半年程序员第二期模考试卷（应用技术）部分试题如下：

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的关系，如果i<k则下次只需对快速排序结果中排在基准值左侧的进行下一次递归；如果k=i，表示刚好查找到第i小的元素；如果i>k则下次只需对快速排序结果中排在基准值右侧的进行下一次递归。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个最小值

else

return （ 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+1

（3）a[pivot]

（4）select(a,low,pivot-1,i)

（5）select(a,pivot+1,high,i-k)