该贪心算法的时间复杂度为(5)。
该贪心算法的时间复杂度为(5)。
第1题
试题五(共15分)
阅读以下说明和C++代码,填充代码中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对,则输出其中的一对即可)。程序运行时,先输入点的个数和一组互异的点的坐标,通过计算每对点之间的距离,从而确定出距离最近的点对。例如,在图5-1所示的8个点中,点(1,1)与(2,0.5)是间距最近的点对。
【C++代码】
include <iostream>
include <cmath>
using namespace std;
class GPoint {
private:
double x, y;
public:
void setX(double x) { this->x = x; }
void setY(double y) { this->y = y; }
double getX() { return this->x; }
double getY() { return this->y; }
};
class ComputeDistance {
public:
double distance(GPoint a,GPoint b) {
return sqrt《a.getX() - b.getX())*(a.getX() - b.getX())
+ (a.getY() - b.getY())*(a.getY() - b.getY()));
}
};
int main()
{
int i,j, numberOfPoints=0;
cout<<"输入点的个数:";
cin>>numberOfPoints;
(1) points= neW GPoint[numberOfPoints];//创建保存点坐标的数组
memset(points,0,sizeof(points));
cout <<"输入"<< numberOfPoints<<"个点的坐标:";
for(i=0;i<numberOfPoints; i++){
double tmpx, tmpy;
cin>>tmpx>>tmpy;
points[i].setX(tmpx);
points[i].setY(tmpy);
}
(2) computeDistance= new ComputeDistance();
int p1=0,p2=1;//p1和p2用于表示距离最近的点对在数组中的下标
double shortestDistance= computeDistance->distance(points[p1], points[p2]);
//计算每一对点之间的距离
for(i=0;i<numberOfPoints; i++){
for(j=i+1;j< (3) ;j++){
double tmpDistance=computeDistance-> (4) ;
if ( (5) ) {
p1=i; p2 =j;
shortestDistance= tmpDistance;
}
}
}
cout<<"距离最近的点对是:(";
cout"points[p1].getX()<<","<<points[pl].getY()<<")和(";
cout<<points[p2].getX()<<","<<points[p2].getY()<<")"<<endl;
delete computeDistance;
return 0:
}
第2题
阅读以下说明和流程图,回答问题将解答填入对应栏。
[说明]
本流程图实现采用递归函数来求一个整数数组中从元素0到元素n中的最小值。该算法思想是这样的,首先我们假设有一个求数组中最小元素的函数,然后,在求某一具有n的元素的数组的最小值时,只要求将前n-1的元素的最小值与第n个元素比较即可。不断地重复这一过程,直到数组中只剩下一个元素,那么它必定是最小值。
注:int min(int X,int y)为返回两数中最小数的函数。
int minInArray(int a[],int n)为返回数组中最小数的函数。
minA为数组中最小值。
[问题l]
将流程图的(1)~(4)处补充完整。
[问题2]
min()函数的定义为(5)。
第3题
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表,其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc,使得Lc中的元素按值非递减排列。程序流程图如下所示:
第4题
阅读以下说明和流程图,回答问题1至问题3。
[说明]
信息处理过程中经常需要将图片或汉字点阵做旋转处理。一个矩阵以顺时针方向旋转90°后可以形成另一个矩阵,如下图所示:
流程图2-1描述了对n*n矩阵的某种处理。流程图2-2是将矩阵A顺时针旋转90°形成矩阵B的具体算法。
请写出以下3*3单位矩阵沿顺时针方向旋转90°后所形成的矩阵。
第5题
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。
[函数2.1说明]
函数strcpy的功能是将字符串str2的内容复制到字符申str1。
[函数2.1]
(1) strcpy (char *slr1, const char *str2)
{ char * temp;
while( * str2!='\0') *cp++ =(2);
(3)='\0';
return str1;
}
[函数2.2说明]
函数int strcmp(const char *str1, const char *str2)的功能是按字典序比较两个字符串str1和str2的大小。当str1<str2时返回-1,当str1>str2时返回1,否则返回0。
[函数2.2]
int strcmp(const char *str1, const char *str2)
{ while( *str1= =* str2) {
if(* s1= =(4)) return 0;
s1++;
(5);
}
if( *str1<*str2) return -1;
return 1;
}
第6题
阅读以下程序说明和C++程序,将程序段中(1)~(5)空缺处的语句填写完整。
[说明]
C++语言本身不提供对数组下标越界的判断。为了解决这一问题,在以下[C++程序]中定义了相应的类模板,使得对于任意类型的二维数组,可以在访问数组元素的同时,对行下标和列下标进行越界判断,并给出相应的提示信息。
[C++程序]
include <iostream.h>
template <class T> class Array;
template <Class T> class ArrayBody {
friend (1);
T* tpBody;
int iRows,iColumns, iCurrentRow;
ArrayBody(int IRsz, int iCsz) {
tpBody =(2);
iRows = iRsz;
iColumns = iCsz;
iCurrentRow = -1;
}
Public:
T& operator[] (int j) {
bool row_error, column_error;
row_error = column_error =false;
try {
if (iCurrentRow < 0 || iCurrentRow >= iRows)
row_error = true;
if (j<0 || j>= iColumns)
column_error = true;
if (row_error == true || column_error == true)
(3);
}
catch(char){
if (row_error == true)
cerr << "行下标越界[" << iCurrentRow << "]";
if (column_error = true)
cerr << "列下标越界[" << j << "]";
cout << "\n";
}
return tpBody[iCurrentRow * iColumns + j];
}
~Arraygody(){delete[]tpBody;}
};
template <class T> class Array {
ArrayBody<T> tBody;
Public;
ArrayBody<T> & operator[] (int i) {
(4);
return tBody;
}
Array(int iRsz, int iCsz) :(5) { }
};
void main()
{
Array<int> a1(10,20);
Array<double> a2(3,5);
int b1;
double b2;
b1 = a1[-5][10]; //有越界提示:行下标越界[-5]
b1 = a1[10][15]; //有越界提示:行下标越界[10]
b1 = a1[1][4]; //没有越界提示
b2 = a2[2][6]; //有越界提示:列下标越界[6]
b2 = a2[10][20]; //有越界提示:行下标越界[10]列下标越界[20]
b2 = a2[1][4]; //没有越界提示
}
第7题
阅读下列说明和流程图,将应填入(n)处的语句写在对应栏内。
【说明】
下列流程图用于从数组K中找出一切满足:K(I)+K(J)=M的元素对(K(I),K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列,M是给定的常数。
【流程图】
此流程图1中,比较“K(I)+K(J):M”最少执行次数约为(5)。
第8题
【问题5】 【C代码3】中x,y是两个已定义的整型变量。对该程序段进行覆盖测试时,必须适当地选取测试用例。如表5-10所示给出了可供选择的4组测试用例。若要实现语句覆盖,则至少应采用的测试用例是(2);若要实现条件覆盖,则至少应采用的测试用例是(3);若要实现路径覆盖,则至少应采用的测试用例是(4)或(5)。 【C代码3】 int a:=0; if (x==O && y>2) a:=1 /*A语句*/ else { if (x<1 || y==1) else a:=2 /*B语句*/ }
【(2)~(5)空缺处供选择的答案】 A.Ⅰ和Ⅱ组 B.Ⅱ和Ⅲ组
C.Ⅲ和Ⅳ组 D.Ⅰ和Ⅳ组
E.Ⅰ、Ⅱ和Ⅲ组 F.Ⅱ、Ⅲ和Ⅳ组G.Ⅰ、Ⅲ和Ⅳ组 H.Ⅰ、Ⅱ和Ⅳ组
第10题
阅读以下说明和C++程序,将应填入(n)处的字句写在对应栏内。
【说明】
设计一个日期类Date包括年、月、日等私有数据成员。要求实现日期的基本运算,如某日期加上天数、某日期减去天数、两日期相差的天数等。
在Date类中设计如下重载运算符函数:
Date operator + (int days) : 返回某日期加上天数得到的日期。
Date operator - (int days) : 返回某日期减去天数得到的日期。
int operator - (Date&b): 返回两日期相差的天数。
【程序】
include<iostream.h>
int day tab[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},
{31,29,31,30,31,30,31,31,30,31,30,31}};
//day_tab二维数组存放各月天数,第一行对应非闰年,第二行对应闰年class Date
{
int year, month, day //年,月,日
int leap(int); //判断是否闰年
int dton(Date&)
Date ntod(int)
public:
Date() { }
Date (int y, int mint d) I year = y; month = m; day = d;}
void setday(intd){day = d;}
void setmonth(int m) {month = m;}
void setyear(int y) {year =y;}
int getday() {return day;}
int getmonth() {return month:}
int getyear() {return yea;}
Date operator + (int days) //+运算符重载函数
{
static Date date;
int number =(1)
date = ntod(number)
return date
}
Date operator - (int days) //-运算符重载函数
{
staffs Date date;
int number=(2);
number - = days;
date = ntod(number)
return date;
}
int operator - (Date &b) //-运算符重载函数
{
int days=(3);
return days;
}
void disp()
{
cout<<year<<"."<<month<<". "<<day<<endl;
}
};
int Date: :leap( int year)
if((4)) //是闰年
return 1; //不是闰年
else
return0:
}
int Date:: dton( Date &d) //求从公元0年0月0日到d日期的天数
{
inty,m,days =0;
for(y=1;y<=d. year;y++)
if((5))days+ =366; //闰年时加366天
else days + = 365; //非闰年时加365天
for(m =0;m<d. month-1;m++)
if((6))
days += day_tab[1] [m];
else
days +=day_tab[0] [m];
days + = d. day;
return days;
}
Date Date::ntod(intn) //将从元0年0月0日的天数转换成日期
{
int y=1,m = 1,d,rest = n,lp;
while(1)
{ if(leap(y))
if(rest<= 366) break;
else rest - = 366;
else //非闰年
if(rest = 365 ) break;
else rest-=365;
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!