第1题:
●试题一
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置,后移元素后将该元素插入到恰当位置(假设R[]中的元素互不相同)。
【算法】
1.变量声明
X:DataType
i,j,low,high,mid,R0..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.算法结束
●试题一
【答案】(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],指针high指向第后一个元素,因此(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"。
第2题:
N个有序整数数列已放在一维数组中,给定下列程序中,函数fun()的功能是:利用折半查找算法查找整数m在数组中的位置。若找到,则返回其下标值:反之,则返回-1。
折半查找的基本算法是:每次查找前先确定数组中待查的范围:low和high(low<high),然后把m与中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元素中的值,则下一次的查找范围放在中间位置之后的元素中;反之,下次查找范围落在中间位置之前的元素中。直到low>high,查找结束。
请改正程序中的错误,使它能得出正确的结果。
注意:不要改动main函数,不得增行或删行,也不得更改程序的结构。
试题程序:
include <stdio.h>
define N 10
/*************found*********************/
void fun(int a[],int m)
{ int low--0,high=N-l,mid;
while (low<=high)
{ mid=(low+high)/2;
if(m<a[mid])
high=mid-1;
/*************found*********************/
else if(m>=a [mid])
low=mid+1;
else return(mid);
}
return(-1);
}
main ()
{ int i,a[N]={-3,4,7,9,13,24,67,89,100,180},k,m;
printf ("a数组中的数据如下: ");
for(i=0;i<N;i++) printf("%d",a[i]);
printf ("Enter m: "); scanf ("%d", &m);
k=fun (a,m);
if (k>=0) printf ("m=%d, index=%d\n",m, k);
else printf("Not be found!\n");
}
第3题:
●试题六
阅读以下说明和C++程序,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
设计一个类模板Sample用于对一个有序数组采用二分法查找元素下标。
【C++程序】
#include<iostream.h>
#define Max 100∥最多元素个数
template<class T>
class Sample
{
T A[Max]:∥存放有序数序
int n:∥实际元素个数
public
Sample(){}∥默认构造函数
Sample(T a[],int i);∥初始化构造函数
int seek(T c);
void disp()
{
for(int i=0;i<n;i++)
cout<<A[i]<<"";
cout<<end1:
}
};
template<class T>
Sample<T>::Sample(T a[],int i)
{
n=i;
for(intj=0;j<i;j++)
(1) ;
}
template<class T>
int Sample<T>::seek(T c)
{
int low=0,high=n-1,mid;
while( (2) )
{
mid=(low+high)/2;
if( (3) )
return mid;
else if( (4) )
low=mid+l;
else
(5) ;
}
return-1;
}
void main()
{
char a[]="acegkmpwxz";
Sample<char>s(a,1。);
cout<<"元素序列:";s.disp();
cout<<"元素′g′的下标:"<<s.seek(′g′)<<endl;
}
●试题六
【答案】(1)A[j]=a[j](2)low<=high(3)A[mid]==c(4)A[mid]<c(5)high=mid-1
【解析】在主函数中,首先由类模板实例化成Sample<char>模板类。(1)空所在处为构造函数的声明,将参数中的值赋值到类的成员变量中,所以(1)空应填入"A[j]=a[j]"。
成员函数seek()采用二分法查找元素下标,变量low和high分别表示查找区间的下标,如果查询到目标,则返回相应的下标,若没有查询到,则其结束的条件即(2)空的内容为"low<=high"。根据二分法的原理,当中间的元素恰好等于目标元素时,则返回其下标,所以(3)空应填入"A[mid]==c";若中间的元素小于目标元素时,则mid+1作为新的查找区间的起始下标,所以(4)空应填入"A[mid]<c";否则mid-1作为新的查找区间的结束下标,所以(5)空应填入"high=mid-1"。
第4题:
The desirable properties of a marine fuel oil should include .
A.high flash point and high viscosity
B.low flash point and high viscosity
C.low heating value and high sulphur content
D.high heating value and low sulphur content
第5题:
阅读以下说明和C++程序,将应填入(n)处的字句写在对应栏内。
【说明】
设计一个类模板SamPle用于对一个有序数组采用二分法查找元素下标。
【C++程序】
include < iostream. h >
define Max 100 //最多元素个数
template < class T >
class Sample
{
T A[Max]: //存放有序数序
int n: //实际元素个数
public
Sample( ) { } //默认构造函数
Sample(T a[] ,int i); //初始化构造函数
int seek(T c);
void disp( )
{
for(int i=0;i <n;i ++)
cout<<A[i] <<" ";
cout<<endl:
} } template < class T >
Sample <T>: :Sample(T a[ ],int i)
{
n=i:
for( intj =0;j < i;j ++ )
(1);
}
template < class T >
int Sample < T >:: seek( T c)
{
int low =0,high = n-1 ,mid;
while((2))
{
mid = (low + high)/2;
if((3))
return mid;
else if( (4) )
low=mid+|;
else
(5);
}
return-1;
}
void main( )
{
char a[ ] ="acegkmpwxz";
Sample < char > s(a, 1);
cout<<"元素序列:" ;s. disp( );
cout<<"元素'g'的下标:"<<s. seek('g') <<endl;
}
第6题:
●试题三
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数move(int*a,int n)用于整理数组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,int n)
{
int i,low,high,t;
low=i=0;high=n-1;
while( (1) )
if(a[i]<0)
{
t=a[i];a[i]=a[low];a[low]=t;
(2) ;i++;
}
else if( (3) )
{t=a[i];a[i]=a[high];a[high]=t;
(4) ;
}
else (5) ;
}
●试题三
【答案】(1)i<=high(2)low++(3)a[i]>0(4)high--(5)i++
【解析】程序的说明已经对程序的功能和相关变量解释得很清楚了,这儿就不再重复了。由变量i、变量low和变量high的含义和初值可以判断,i至high之间的元素还未处理,因此while循环条件是"i<=high"或其等价形式,这就是(1)空所填写的内容。
(2)空所在语句块是处理当a[i]<0的情况,显然这时需要将a[i]与a[low]进行交换,交换后需要将i和low都要向后移动,因此(2)空处应填写"low++"或其等价形式。
(3)空需要填写执行(4)空所在语句块的条件,由(4)空所在语句块的可以判断,它是处理当a[i]>0的情况,因此(3)空处应填写"a[i]>0"或其等价形式。当a[i]>0时,需要将a[i]与a[high]进行交换,交换后需要将high都要向前移动,因此(4)空处应填写"high--"或其等价形式。注意这时i不能向后移动,因为交换后的a[i]还没有处理,需要循环的下一趟进行处理。
当a[i]=0情况,当a[i]=0时,不需要进行元素交换,只需将i向后移动就可以了,因此(5)空处应填写"i++"或其等价形式。
第7题:
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置,后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)
[算法]
1.变量声明
X: Data Type
i,j,low, high,mid,r:0..n
2.每循环一次插入一个R[i]
循环:i以1为步长,从2到n,反复执行。
(1)准备
X←R[i];(1); high←i-1;
(2)找插入位置
循环:当(2)时,反复执行。
(3)
若X.key<R[mid].key
则high←mid-1;
否则 (4)
(3)后移
循环:j以-1为步长,从(5),反复执行。
R[j+1]←R[j]
(4)插入
R[low]←X
3.算法结束
第8题:
A、HIGH、LOW、MIDDLE
B、LOW、MIDDLE、HIGH
C、MIDDLE、LOW、HIGH
D、HIGH、MIDDLE、LOW
第9题:
阅读以下函数说明和C语言函数,将应填入(n)处的字句写在对应栏内。
[说明1]
本程序输入一字符串,并将其中的大写字母变成小写字母。
[C函数1]
include<stdio.h>
void main()
{ int i=0;
char s[120];
printf("Enter a string.\n");
scanf("%s",s);
while( (1) ){
if( (2) )
s[i]=s[i]-'A'+'a';
i++;
}
printf("%s\n",S);
}
[说明2]
本程序用二分法,在已按字母次序从小到大排序的字符数组list[len]中,查找字符c,若c在数组中,函数返回字符c在数组中的下标,否则返回-1。
[C函数2]
int search(char list[],char c,int len)
( intlow=0,high=len-1,k;
while( (3) );
k=(10w+high)/2;
if( (4) ) return k;
else if( (5) )high=k-1;
else low=k+1;
return -1;
}
第10题:
阅读下列说明、流程图和算法,将应填入(n)处的字句写在对应栏内。
【流程图说明】
下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法;以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于Array[i],并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。
【算法说明】
将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int Array[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[],int L,int H)的功能是实现数组Array中元素的递增排序。
【算法】
void sort(int Array[],int L,int H){
if (L<H) {
k=p(Array,L,H);/*p()返回基准数在数组Array中的下标*/
sort((4));/*小于基准数的元素排序*/
sort((5));/*大于基准数的元素排序*/
}
}