希賽網(wǎng)2025上半年程序員第二期?？蓟顒右呀Y(jié)束，現(xiàn)將2025上半年程序員第二期?？荚嚲恚☉眉夹g(shù)）分享給大家。模考試卷PDF版本可在本文文首本文資料處或文末的資料下載欄目下載。

2025上半年程序員第二期模考試卷（應用技術(shù)）部分試題如下：

1、

N有有序整數(shù)數(shù)組存放在a中，利用二分查找法查找整數(shù)key在數(shù)組中的位置，若找到，則輸出其值和對應的下標，反之，則輸出“Not be found！”

二分查找的基本思想是：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

問題內(nèi)容：請完成下列流程圖，使該流程圖實現(xiàn)二分查找。

【流程圖】

試題答案：

（1）N-1

（2）high=nid-1

（3）key>a[mid]

（4）low=mid+1

（5）k=mid

（6）k>=0

最終流程圖如下圖所示：

2、

用快速排序中的劃分思想進行實現(xiàn)如下功能：在n個元素的整型數(shù)組中，確定其第i（1≤i≤n）小的數(shù)。

具體算法如下：

首先以第一個數(shù)為基準，進行快速排序?？焖倥判蚝螅瑫曰鶞手禐榻?，左側(cè)的元素都比基準值要小，右側(cè)的元素比基準值大。且排序完成后可以確定基準值是排在第k位，判斷k與i的關系，如果i<k則下次只需對快速排序結(jié)果中排在基準值左側(cè)的進行下一次遞歸；如果k=i，表示剛好查找到第i小的元素；如果i>k則下次只需對快速排序結(jié)果中排在基準值右側(cè)的進行下一次遞歸。C代碼實現(xiàn)如下（請將空白區(qū)域代碼補充完整）。

【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函數(shù)實現(xiàn)查找a數(shù)組中，從low~high范圍內(nèi)找第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時，用遞歸找其左側(cè)范圍內(nèi)第i個最小值

else

return （ 5 ）; //反之，用遞歸找其右側(cè)范圍內(nèi)第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;

}

問題內(nèi)容：

試題答案：

（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)