C++程序设计第一章函数编程题.doc

第一章1/136-1工作备忘录的生成（链表）(10分)每天都要处理很多事务，为了更好地安排工作，希望在每天开始工作前，根据工作记录，生成工作备忘录。首先输入工作记录数（大于0的一个整数），再逐条输入各条工作记录，每条工作记录包括：工作名，开始时间，结束时间。假设每项工作的开始时间均小于它的结束时间，并且各项工作的开始时间互不相同。我们的工作是需要把这些工作记录按开始时间排序并输出，在输出时，如果某项工作与若干项工作冲突（在做该项工作时，需要同时做其它工作），则在该工作名前加'*'。函数接口定义：Node*add(Node*,Node*);voiddisplay(Node*);裁判测试程序样例：#includeiostream#includestringusingnamespacestd;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-startp-start)returnfalse;returncheck(p);}intmain(){Node*head=NULL,*p;inti,repeat;cinrepeat;for(i=0;irepeat;i++){p=newNode;cinp-namep-startp-end;p-next=NULL;head=add(head,p);}if(!check(head))coutERRORendl;display(head);return0;}/*请在这里填写答案*/输入样例：4aaa1920ccc169200ddd153170bbb20111输出样例：第一章2/13aaa1920bbb20111*ddd153170*ccc169200Node*add(Node*head,Node*p){//把节点p插入到链表，按照任务的起始时间升序排列Node*q=head,*s=head;while((q!=NULL)&&(q-startp-start)){//当前的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-endp-start){//p之前的任务的结束时间如果大于p的开始时间则冲突conflict=true;break;}q=q-next;}q=p-next;while(!conflict&&q!=NULL){//检查p的结束时间是否大于p之后的任务的开始时间if(p-endq-start){//p之后的任务的开始时间如果大于p的结束时间则冲突conflict=true;break;}q=q-next;}if(conflict){//当前任务与其它的任务时间冲突cout*;}coutp-namep-startp-endendl;p=p-next;}}第一章3/136-2函数调用(10分)编写三个函数：求两个整数的最大值、最小值、和。分别用这三个函数作为实参，再写一个计算函数compute，对两个整数进行各种计算。其中一个形参为指向具体算法函数的指针。函数接口定义：intmax(inta,intb);intmin(inta,intb);intsum(inta,intb);intcompute(inta,intb,int(*func)(int,int));裁判测试程序样例：在这里给出函数被调用进行测试的例子。例如：#includeiostreamusingnamespacestd;intmax(inta,intb);intmin(inta,intb);intsum(inta,intb);intcompute(inta,intb,int(*func)(int,int));intmain(){inta,b,res;cinab;res=compute(a,b,&max);coutMaxofaandbisresendl;res=compute(a,b,&min);coutMinofaandbisresendl;res=compute(a,b,&sum);coutSumofaandbisresendl;return0;}/*请在这里填写答案*/输入样例：35输出样例：Maxof3and5is5Minof3and5is3Sumof3and5is8intmax(inta,intb){if(ab){returna;}else{returnb;}}intmin(inta,intb){if(ab){returna;}else{returnb;}}intsum(inta,intb){returna+b;}intcompute(inta,intb,int(*func)(int,int)){return(*func)(a,b);}第一章4/136-3函数指针（理科实验班）（7分)梦山高中现需要将某普通班的最优秀学生调整入理科实验班。为此，将从两个方面考察学生，一是数学和英语两门课的总分；另一个是所有四门课的总分。分别找出两科总分和全科总分的第一名，并从中决定调整人选。输入将首先输入学生数n,(n为不超过80的正整数);接下来依次输入各位学生的学号，数学、英语、语文、理科综合成绩。学号及四科成绩均为不超过３００的正整数。输出时：第一行输出两科总分第一的学号，第二行输出四科总分第一的学号。约定在两位学生成绩相同时，优先选择学号较小的学生；各位学生的学号均不相同。裁判测试程序样例：#includeiostreamusingnamespacestd;constintN=80;structStudent{intnum;intscore[4];};/*请在这里填写答案*/intmain(){inti,j,k,n;bools2(constStudent&,constStudent&);bools4(constStudent&,constStudent&);Studentst[N];cinn;for(i=0;in;i++){cinst[i].num;for(j=0;j4;j++)cinst[i].score[j];}coutselect(st,n,s2)endl;coutselect(st,n,s4)endl;}输入样例：3614815012025251481501172607145148128287输出样例：57bools2(constStudent&s1,constStudent&s2)//比较s1和s2两位学生的数学+英语大小，如果s2的大则返回true{if(s1.score[0]+s1.score[1]s2.score[0]+s2.score[1])returntrue;if(s1.score[0]+s1.score[1]==s2.score[0]+s2.score[1]&&s1.nums2.num)returntrue;returnfalse;}第一章5/13bools4(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.nums2.num)returntrue;returnfalse;}intselect(Students[],intn,bool(*p)(constStudent&s1,constStudent&s2)){intmaxIndex=0;for(inti=1;in;i++){if((*p)(s[maxIndex],s[i]))maxIndex=i;}returns[maxIndex].num;}6-4二维数组（海绵城市）(7分)根据海绵城市建设指挥部要求，怡山小学将对校内道路进行改造，铺设透水砖。这样有些道路将不能通行。为了不妨碍假期少先队的校内活动安排，大队宣传委员小黄需要知道一些关键的活动地点是否可以到达。已知校内一共有20处建筑，分别标为1号楼，２号楼，......，２０号楼。有些楼之间有道路连接，道路是双向的，如果Ａ楼与Ｂ楼间有道路，那么既可以从Ａ楼到Ｂ楼，也可以从Ｂ楼到Ａ楼。首先将输入校内的道路数n,接下来分n行输入各条道路的信息，每行有两个整数（均在１和２０之间），代表这两座楼之间有道路连接。接下来输入查询数m,然后分m行输入要查询的楼间连路信息，每行有两个整数（均在１和２０之间）。如果两楼之间可以通过一条路径到达（中途有可能经过其它楼），则输出两楼是连接的，否则输出两楼是断开的。函数接口定义：完成查询两建筑是否连通的函数test裁判测试程序样例：#includeiostreamusingnamespacestd;constintN=21;/*请在这里填写答案*/intmain(){inta[N][N]={0},n,m,i,j,k;cinn;for(i=0;in;i++){cinjk;a[j][k]=a[k][j]=1;}cinm;第一章6/13for(i=0;im;i++){cinjk;coutj'-'k'';if(test(a,j,k))coutconnectedendl;elsecoutdisconnectedendl;}return0;}·输入样例：2122321314输出样例：1-3connected1-4disconnectedbooltest(inta[N][N],intj,intk)//利用深度优先搜索找到一条从j到k的通路，若不存在则返回false{//维护一个一维数组，模拟栈的操作，从j开始深搜到一个邻居i且没有搜索过，则将i入栈，如果i==k则搜索成功//维护一个一维数组，有N个元素，用于记录某个楼是否搜索过intstack[N+1]={0};//存储从j开始走过的路径，如jmnt，表示从j开始经过mn走到了tboolvisited[N+1]={false};inttop=0;//top记录数组stack的最后一个元素的位置，//首先j入栈stack[++top]=j;visited[j]=true;while(top0)//当前栈不空{intcur=stack[top--];//得到当前栈顶//把与cur连接的所有未访问过的楼号压入栈for(inti=0;iN;i++){if(a[cur][i]==1&&visited[