完整版C++程序设计第一章函数编程题.docx

完整版C++程序设计第一章函数编程题.docx

《完整版C++程序设计第一章函数编程题.docx》由会员分享，可在线阅读，更多相关《完整版C++程序设计第一章函数编程题.docx（24页珍藏版）》请在冰点文库上搜索。

完整版C++程序设计第一章函数编程题

6-1工作备忘录的生成（链表）（10分）

每天都要处理很多事务，为了更好地安排工作，希望在每天开始工作前，根据工作记录，生成工作备忘录。

首先输入工作记录数（大于0的一个整数），再逐条输入各条工作记录，每条工作记录包括：

工作名，开始时间，结束时间。

假设每项工作的开始时间均小于它的结束时间，并且各项工作的开始时间互不相同。

我们的工作是需要把这些工作记录按开始时间排序并输出，在输出时，如果某项工作与若干项工作冲突（在做该项工作时，需要同时做其它工作），则在该工作名前加'*'。

函数接口定义：

Node*add（Node*,Node*）;

voiddisplay（Node*）;

裁判测试程序样例：

#include

#include

usingnamespacestd;

structNode{

stringname;

intstart;

intend;

Node*next;

};

Node*add（Node*,Node*）;

voiddisplay（Node*）;

boolcheck（Node*head）{

if（head==NULL||head->next==NULL）returntrue;

Node*p=head->next;

if（head->start>p->start）returnfalse;

returncheck（p）;

}

intmain（）{

Node*head=NULL,*p;

inti,repeat;

cin>>repeat;

for（i=0;i

p=newNode;

cin>>p->name>>p->start>>p->end;

p->next=NULL;

head=add（head,p）;

}

if（!

check（head））cout<<"ERROR"<

display（head）;

return0;

}

/*请在这里填写答案*/

输入样例：

4

aaa1920

ccc169200

ddd153170

bbb20111

输出样例：

aaa1920

bbb20111

*ddd153170

*ccc169200

Node*add（Node*head,Node*p）{//把节点p插入到链表，按照任务的起始时间升序排列

Node*q=head,*s=head;

while（（q!

=NULL）&&（q->startstart））{//当前的q节点不是末尾，并且q节点的起始时间

早于p节点的起始时间

s=q;//s始终在q的前面

q=q->next;

}//直到当前节点NULL或者q的起始时间晚于p的起始时间

if（q==head）{//p应该接在链表的开始位置，即成为新的表头

p->next=head;

head=p;

}else{

p->next=q;

s->next=p;

}

returnhead;

}

voiddisplay（Node*head）{

Node*p=head,*q;

boolconflict;//用于标识是否有冲突

while（p!

=NULL）{//当前p节点不空，是有效任务

conflict=false;

q=head;

while（!

conflict&&q!

=p）{//检查p的开始时间是否小于p之前的任务的结束时间

if（q->end>p->start）{//p之前的任务的结束时间如果大于p的开始时间则冲突

conflict=true;

break;

}

q=q->next;

}

q=p->next;

while（!

conflict&&q!

=NULL）{//检查p的结束时间是否大于p之后的任务的开始时间

if（p->end>q->start）{//p之后的任务的开始时间如果大于p的结束时间则冲突

conflict=true;

break;

}

q=q->next;

}

if（conflict）{//当前任务与其它的任务时间冲突

cout<<"*";

}

cout<name<<""<start<<""<end<

p=p->next;

}

}

6-2函数调用（10分）

编写三个函数：

求两个整数的最大值、最小值、和。

分别用这三个函数作为实参，再写一个计算函数compute，对两个整数进行各种计算。

其中一个形参为指向具体算法函数的指针。

函数接口定义：

intmax（inta,intb）;

intmin（inta,intb）;

intsum（inta,intb）;

intcompute（inta,intb,int（*func）（int,int））;

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。

例如：

#include

usingnamespacestd;

intmax（inta,intb）;

intmin（inta,intb）;

intsum（inta,intb）;

intcompute（inta,intb,int（*func）（int,int））;

intmain（）{

inta,b,res;

cin>>a>>b;

res=compute（a,b,&max）;

cout<<"Maxof"<

res=compute（a,b,&min）;

cout<<"Minof"<

res=compute（a,b,&sum）;

cout<<"Sumof"<

return0;

}

/*请在这里填写答案*/

输入样例：

35

输出样例：

Maxof3and5is5

Minof3and5is3

Sumof3and5is8

intmax（inta,intb）{

if（a>b）{returna;

}else{returnb;}

}

intmin（inta,intb）{

if（a

}else{returnb;}

}

intsum（inta,intb）{returna+b;}

intcompute（inta,intb,int（*func）（int,int））{

return（*func）（a,b）;

}

6-3 函数指针（理科实验班） （7 分）

梦山高中现需要将某普通班的最优秀学生调整入理科实验班。

为此，将从两个方面考察学生，一是数学和英语两门课的总分；另一个是所有四门课的总分。

分别找出两科总分和全科总分的第一名，并从中决定调整人选。

输入将首先输入学生数n,（n为不超过80的正整数）;接下来依次输入各位学生的学号，数学、英语、语文、理科综合成绩。

学号及四科成绩均为不超过３００的正整数。

输出时：

第一行输出两科总分第一的学号，第二行输出四科总分第一的学号。

　约定在两位学生成绩相同时，优先选择学号较小的学生；各位学生的学号均不相同。

裁判测试程序样例：

#include

usingnamespacestd;

constintN=80;

structStudent{

intnum;

intscore[4];

};

/*请在这里填写答案*/

intmain（）

{

inti,j,k,n;

bools2（constStudent&,constStudent&）;

bools4（constStudent&,constStudent&）;

Studentst[N];

cin>>n;

for（i=0;i

cin>>st[i].num;

for（j=0;j<4;j++）cin>>st[i].score[j];

}

cout<

cout<

}

输入样例：

3

6148150120252

5148150117260

7145148128287

输出样例：

5

7

bools2（constStudent&s1,constStudent&s2）//比较s1和s2两位学生的数学+英语大小，如果s2的

大则返回true

{

if（s1.score[0]+s1.score[1]

if（s1.score[0]+s1.score[1]==s2.score[0]+s2.score[1]&&s1.num>s2.num）returntrue;

returnfalse;

}

bools4（constStudent&s1,constStudent&s2）//比较s1和s2两位学生的总分大小，如果s2的大则返回true

{

if（s1.score[0]+s1.score[1]+s1.score[2]+s1.score[3]<

s2.score[0]+s2.score[1]+s2.score[2]+s2.score[3]）

returntrue;

if（s1.score[0]+s1.score[1]+s1.score[2]+s1.score[3]==

s2.score[0]+s2.score[1]+s2.score[2]+s2.score[3]&&s1.num>s2.num）

returntrue;

returnfalse;

}

intselect（Students[],intn,bool（*p）（constStudent&s1,constStudent&s2））

{

intmaxIndex=0;

for（inti=1;i

{

if（（*p）（s[maxIndex],s[i]））maxIndex=i;

}

returns[maxIndex].num;

}

6-4二维数组（海绵城市）（7分）

根据海绵城市建设指挥部要求，怡山小学将对校内道路进行改造，铺设透水砖。

这样有些道路将不能通行。

为了不妨碍假期少先队的校内活动安排，大队宣传委员小黄需要知道一些关键的活动地点是否可以到达。

已知校内一共有20处建筑，分别标为1号楼，２号楼，......，２０号楼。

有些楼之间有道路连接，道路是双向的，如果Ａ楼与Ｂ楼间有道路，那么既可以从Ａ楼到Ｂ楼，也可以从Ｂ楼到Ａ楼。

首先将输入校内的道路数n,接下来分n行输入各条道路的信息，每行有两个整数（均在１和２０之间），代表这两座楼之间有道路连接。

　接下来输入查询数m,然后分m行输入要查询的楼间连路信息，每行有两个整数（均在１和２０之间）。

如果两楼之间可以通过一条路径到达（中途有可能经过其它楼），则输出两楼是连接的，否则输出两楼是断开的。

函数接口定义：

完成查询两建筑是否连通的函数test

裁判测试程序样例：

#include

usingnamespacestd;

constintN=21;

/*请在这里填写答案*/

intmain（）

{

inta[N][N]={0},n,m,i,j,k;

cin>>n;

for（i=0;i

cin>>j>>k;

a[j][k]=a[k][j]=1;

}

cin>>m;

for（i=0;i

cin>>j>>k;

cout<

if（test（a,j,k））cout<<"connected"<

}

return0;

}·

输入样例：

2

12

23

2

13

14

输出样例：

1-3connected

1-4disconnected

booltest（inta[N][N],intj,intk）//利用深度优先搜索找到一条从j到k的通路，若不存在则返回false

{

//维护一个一维数组，模拟栈的操作，从j开始深搜到一个邻居i且没有搜索过，则将i入栈，如果i==k则搜索成功

//维护一个一维数组，有N个元素，用于记录某个楼是否搜索过

intstack[N+1]={0};//存储从j开始走过的路径，如jmnt，表示从j开始经过mn走到了t

boolvisited[N+1]={false};

inttop=0;//top记录数组stack的最后一个元素的位置，

//首先j入栈

stack[++top]=j;

visited[j]=true;

while（top>0）//当前栈不空

{

intcur=stack[top--];//得到当前栈顶

//把与cur连接的所有未访问过的楼号压入栈

for（inti=0;i

{

if（a[cur][i]==1&&visited[i]==false）

{

stack[++top]=i;

if（i==k）returntrue;//访问到k则表示从j到k有通路

visited[i]=true;

}

}

}

returnfalse;

}

6-5引用作函数形参交换两个整数（10分）

设计一个void类型的函数Swap，该函数有两个引用类型的参数，函数功能为实现两个整数交换的操作。

裁判测试程序样例：

#include

usingnamespacestd;

voidSwap（int&x,int&y）{

    inttemp;

    temp=x;

    x=y;

    y=temp;

}

intmain（）{

inta,b;

cin>>a>>b;

Swap（a,b）;

cout<

return0;

}

输入样例：

35

输出样例：

53

6-6函数重载实现两数相加（15分）

设计一个重载函数add，该函数有两个参数，可以实现两个类型相同的参数相加的操作，函数返回相加的结果。

两个参数可以是整数、实数和字符串，但必须保证两个参数类型相同。

裁判测试程序样例：

#include

#include

#include

usingnamespacestd;

intadd（intx,inty）{

    returnx+y;

}

doubleadd（doublex,doubley）{

    returnx+y;

}

stringadd（stringx,stringy）{

    returnx+y;

}

intmain（）{

inta,b;

doublec,d;

strings1,s2;

cin>>a>>b;

cin>>c>>d;

cin>>s1>>s2;

cout<

cout<

（2）<

cout<

return0;

}

输入样例：

35

3.33335.555555

helloworld

输出样例：

8

8.89

helloworld

6-7带默认形参值的函数（10分）

设计一个带默认形参值的函数add，该函数有三个参数，可以实现三个整数类型的参数相加的操作，函数返回相加的结果。

默认形参值从右至左分别是30、20。

裁判测试程序样例：

#include

usingnamespacestd;

intadd（intx,inty=20,intz=30）{

    returnx+y+z;

}

intmain（）{

inta,b,c;

cin>>a>>b>>c;

cout<

cout<

cout<

return0;

}

输入样例：

123

输出样例：

51

33

6

6-8使用动态内存分配的冒泡排序（20分）

编程实现冒泡排序函数int*bubble_sort（intn）;。

其中n为数组长度（1≤n≤1000）。

函数接口定义如下：

int*bubble_sort（intn）;/*对长度为n的数组arr执行冒泡排序*/

请实现bubble_sort函数，使排序后的数据从小到大排列。

要求在bubble_sort函数内使用动态内存分配方式分配一个大小为n的数组，再读入待排序数据，排序完成后返回数组。

裁判测试程序样例：

#include

usingnamespacestd;

int*bubble_sort（intn）;/*对长度为n的数组执行冒泡排序*/

intmain（）{

intn;

cin>>n;

int*a=bubble_sort（n）;

for（inti=0;i

cout<

if（i

}

cout<

return0;

}

/*你的代码将嵌在这里*/

输入样例：

10

1516828139137142780122208325242165383532834125922

输出样例：

8353137141516821653222082592227801281392834132524

int*bubble_sort（intn）{

int*a=newint[n];

inti;

for（i=0;i

  cin>>a[i];

}

for（i=0;i

    for（intj=0;j

      if（a[j]>a[j+1]）{

          inttemp;

          temp=a[j+1];

          a[j+1]=a[j];

          a[j]=temp;

        }

    }

}

returna;

delete[]a;

}

6-9逆序字符串（10分）

设计一个void类型的函数reverse_string，其功能是将一个给定的字符串逆序。

例如，给定字符串为“hello”，逆序后为“olleh”。

函数接口定义如下：

/*函数原型参见main函数*/

裁判测试程序样例：

#include

#include

usingnamespacestd;

/*你的代码将嵌在这里*/

intmain（intargc,charconst*argv[]）

{

stringstr;

getline（cin,str）;//输入字符串

reverse_string（str）;//逆序字符串str

cout<

return0;

}

输入样例：

hello

输出样例：

olleh

voidreverse_string（string&str）{

   intn;

   chart;

   n=str.length（）;

   for（inti=0;i

       t=str[i];

       str[i]=str[n-1-i];

       str[n-1-i]=t;

    }

}

7-1时间换算（10分）

输入一个正整数repeat（0

输入一个时间数值，再输入秒数n，输出该时间再过n秒后的时间值，时间的表示形式为时:

分:

秒，超过24时从0时重新开始计时。

输出格式：

printf（"time:

%d:

%d:

%d\n",）;

输入输出示例：

括号内为说明，无需输入输出

输入样例:

3（repeat=3）

0:

0:

1

59（秒数n=59）

11:

59:

40

30（秒数n=30）

23:

59:

40

301（秒数n=301）

输出样例:

time:

0:

1:

0（0:

0:

01加上59秒的新时间）

time:

12:

0:

10（11:

59:

40加上30秒的新时间）

time:

0:

4:

41（23:

59:

40加上301秒的新时间）

#include

usingnamespacestd;

structTime

{

inthour;

intminute;

intsecond;

};

voidtimeCompute（Time&t,intsec）

{

inth,m,s;

inta;

s=t.second+sec;