初级程序员下午试题-63.pdf

初级程序员下午试题-63

(总分：120.00，做题时间：90分钟)

一、试题一(总题数：1，分数：15.00)

1.【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组
R[1.n]进行排
序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插
入到恰当
位置(假设R[]中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R[0..n])2．每循环一次插入一个R[i]循环：i以1为步长，从2到n，反
复执行
①准备
X<-R[i]；(1)；high<-i-1;
②找插入位置
循环：当(2)时，反复执行
(3);

若X.key<R[mid].key
则high<-mid-1
否则(4)
③后移
循环：j以-1为步长，从(5)，反复执行
R[j+1]<-R[j]
④插入

R[low]<-X

3．算法结束

(分数：15.00)
填空项1:_______________(正确答案：low<-1(2)low<＝high(3)mid<-int((low+high)/2)
(4)low<-mid+1

(5)i-1到low)

解析：[解析]这是一个通过自然语言描述二分插入排序的过程。整个过程由一个大循环来完成，在
大循环中又包含两个循环，第一个循环是一个二分查找过程，第二循环是后移过程。
查找过程是在有序序列R[1]．R[i-1]中查找R[i]的过程，这是一个典型的折半查找过程。初始时指
针low指向第一个元素，即R[1]，指针hish指向第后一个元素，因此(1)空处应填写“low-
1”。要查找R[i]，先与中间元素进行比较，中间元素使用mid指向，因此，(3)空处应填入
“mid<-int((low+high)/2)”。当R[i]<R[mid]时，则在前半部分查找，将high<-mid-1，如果
R[i]>R[mid]时，则在后半部分查找，因此(4)空处应填“low<-mid+1”。那什么时候结束呢?显
然，一种情况是已经找该元素，由于题目中已经假设元素互不相同，这种情况不会发生，二
是没有找到该元素，即指针low和指针high之间的没有元素了，所以(2)空处应填写
“low≤high”。(5)空所在循环是进行数据移动，结合下面语句，可以判断循环是从i-1开始，到
什么时候结束呢?通过分析，可以知道，最终要把R[i]放在R[low]的位置，循环要到low时结
束，因此(5)空处应填写“i-1到low”。
二、试题二(总题数：1，分数：15.00)

2.1说明】
【函数2.1说明】函数stremp()是比较两个字符串s和t的大小。若s<t函数返回负数；若s=t函
数返回0；若s>t，函数返回正数。
【函数2.1】
intstrcmp(char*s,char*t)
while(*s&&*t&&(1))
s++;t++;

return(2);

【程序2.2说明】
在n行n列的矩阵中，每行都有最大的数，本程序求这n个最大数中的最小一个。【程序2.2】
#include<stdio.h>

#defineN100
inta[N][N];
voidmain()
introw,col,max,min,n;

/*输入合法n(n<100)，和输入n×n个整数到数组a的代码略*/
for(row=0;row<n;row++)
for(max=a[row][0],col=1;col<n;col++)

if((3))max=a[row][col];
if((4))min=max;
elseif((5))min=max;

(分数：15.00)
填空项1:________________(正确答案：*s==*t(2)*s-*t(3)a[row][col]>max(4)row==0(5)
max<min)

解析：[解析]*s和*t相等才执行循环体。返回二者差值，恰好符合题目要求。
当前值比max大，则把它赋给max。max是本行最大值。初始化min为第一行的max。该行的
max比min小，则将max赋给min。
三、试题三(总题数：1，分数：15.00)

3.【说明】
函数move(int*a，intn)用于整理数组a[]的前n个元素，使其中小于0的元素移到数组的前端，
大于0的元素移到数组的后端，等于0的元素留在数表中间。
令a[0]～a[low-1)小于0(初始为空)；a[low]-a[i-1]等于0(初始为空)；a[i]～a[high]还未考察，当
前
考察元素为a[i]。a[high+1]～a[n-1]大于0(初始为空)。
【函数】
move(int*a,intn)

inti,low,high