数据结构与算法 C++编程能力评估
C++编程能力评估
题目1
向类SeqList中插入数据，请根据main函数中的调用，完成Insert和output函数。
- Input
5
1 2 3 4 5
2 9
- Output
1 2 3 4 5
1 2 9 3 4 5
- Answer
#include<iostream>
#include<stdlib.h>
using namespace std;
class SeqList
{
private:
int * data;
int last; // index of the last element
public:
SeqList ( int sz );
~SeqList ( )
{
delete [ ] data;
}
void input ();
void output() ;
void Insert ( const int &x, int i);
} ;
SeqList::SeqList ( int sz )
{
if ( sz > 0 )
{
data = new int[sz];
last = -1;
}
}
void SeqList:: input()
{
cin >>last;
for (int i=0; i<last; i++)
cin>>data [i];
last--;
}
void SeqList::output()
{
bool fi=false;
for(int i=0; i<=last; i++)
{
if(!fi)
{
fi=!fi;
cout<<data[i];
}else{
cout<<' '<<data[i];
}
}
cout<<endl;
}
void SeqList::Insert(const int& x, int i)
{
for(int i1=last;i1>=i;i1--){
data[i1+1]=data[i1];
}
data[i]=x;
last++;
}
int main()
{
SeqList myList(50);
myList.input();
myList.output();
int where,value;
cin >>where;
cin >>value;
myList.Insert(value,where);
myList.output ();
return 1;
}
题目2
已知一块靶场大小为m*n（m行n列），每个点上都有一面旗子，我们的炮兵发射炮弹，炮弹一次只能炸掉一面旗子，每次炮弹的落点坐标都有记录，问你几炮过后，靶场还剩下几面旗子呢？
- Input
有若干行，第一行为两个整数m,n，以空格分隔，都是整数，且1<=m<=n<=100；
接下来有若干行，每行有两个整数x,y，代表炮弹落点的坐标（行、列坐标，编号从0开始）。
3 3
1 1
1 1
99 99
- Output
一个整数，代表最后靶场上剩余的旗子数。
提示：炮弹可能打在同一个位置，也可能脱靶，但保证在100*100的范围内。
8
- Answer
#include <iostream>
#define N 105
using namespace std;
int main()
{
bool data[N][N];
for(int i=0;i<N;i++){
for(int i2=0;i2<N;i2++){
data[i][i2]=false;
}
}
int m,n;
cin>>m>>n;
int res=m*n;
int x,y;
while(cin>>x>>y){
data[x][y]=true;
}
for(int i=0;i<m;i++){
for(int i2=0;i2<n;i2++){
if(data[i][i2]){
res--;
}
}
}
cout<<res<<endl;
return 0;
}
题目3
买房面积不要求太大，环境不要求太好，只要单价够便宜就已经很满足啦~现在挑选了一些房源，请你帮忙选一选，哪个最适合呢？小本本上记录了房子的名称（字母和数字组成，无空格）、面积和总价，你来帮编个程序自动计算一下吧。
- Input
第一行为一个整数N(1<=N<=100)，表示接下来有N套房源信息；
接下来有N行，每行包括房源名称(不超过100个字符)、面积和总价（double类型，小数点后保留两位），以空格分隔。
3
Tangdaowan0101 50 50
Jiangshan1314 49 50
Jinshatan1111 51 50
- Output
Jinshatan1111 51.00 50.00
仅一行，为最适合的房源信息，以空格分隔，末尾换行。
测试用例保证没有单价重复的情况。
- Answer
#include <stdio.h>
#include <string.h>
#include<limits.h>
typedef struct
{
char name[101];
double area;
double sum;
double avg;
} House;
int Gethouse(House*h,int n){
double res=INT_MAX;
int res_num=0;
for(int i=0;i<n;i++){
h[i].avg=h[i].sum/h[i].area;
if(h[i].avg<res){
res=h[i].avg;
res_num=i;
}
}
return res_num;
}
int main()
{
int n,i,flag = 0;//n有几行
scanf("%d",&n);
House h[n];
for (i = 0; i < n; i ++)
scanf("%s%lf%lf",h[i].name,&h[i].area,&h[i].sum);
flag= Gethouse(h,n);
printf("%s %.2f %.2f\n",h[flag].name, h[flag].area, h[flag].sum);
return 0;
}
题目4
实现链表的输入（已实现）、输出和删除成员函数。
输入时，根据endtag确定是否结束输入；
删除时，根据下标（从0开始）。
注意，输入的顺序跟存放的顺序以及输出的顺序是相反的。
- Input
1 2 3 4 5 0
2
- Output
5 4 3 2 1
5 4 2 1
- Answer
#include "stdlib.h"
#include "iostream"
#include<cstdlib>
using namespace std ;
class List; //前视定义,否则友元无法定义
class LinkNode
{
friend List; //链表结点类的定义
private:
LinkNode *link;
int data;
public:
LinkNode(const int & item, LinkNode *ptr = NULL)
{
data=item;
link=ptr;
}
LinkNode (LinkNode *ptr = NULL)
{
link=ptr;
}
~LinkNode() {};
};
class List
{
//单链表类的定义
private:
LinkNode *first; //指向首结点的指针
public:
List ()
{
first = new LinkNode (); // 带头结点
}
~List ()
{
MakeEmpty(); //析构函数
}
void MakeEmpty ( ); //链表置空
int Remove ( int i );
void input(int endTag);
void output();
};
void List:: MakeEmpty ( )
{
LinkNode *q;
while ( first->link != NULL )
{
q = first->link;
first->link = q->link;
delete q;
}
};
void List :: input (int endTag)
{
LinkNode *newnode;
int val;
cin>>val;
while(val!=endTag)
{
newnode=new LinkNode (val);
newnode->link=first->link;
first->link=newnode;
cin>>val;
}
}
int List::Remove(int i)
{
LinkNode*tmp=first;
for(int i2=0;i2<i;i2++){
tmp=tmp->link;
}
LinkNode*tmp1=tmp->link;
tmp->link=tmp->link->link;
delete(tmp1);
}
void List::output()
{
int fi=0;
LinkNode*tmp=first->link;
while(tmp!=NULL)
{
if(fi++)
{
cout<<' '<<tmp->data;
}
else
{
cout<<tmp->data;
}
tmp=tmp->link;
}
cout<<endl;
}
int main()
{
List l;
l.input(0); //0为输入的结束数字
l.output ();
int index;
cin>>index; //要删除的元素的下标，下标从0 开始
l.Remove(index);
l.output (); //删除后输出
return 0;
}
最后修改于 2019-03-28