考研计算机复试上机

题目描述

输入一系列整数，将其中最大的数挑出，并将剩下的数进行排序。

输入

输入第一行包括1个整数N,1<=N〈=1OOO,代表输入数据的个数。

接下来的一行有N个整数。

输出

可能有多组测试数据，对于每组数据，

第一行输出一个整数，代表N个整数中的最大值，并将此值从数组中去除，将剩

下的数进行排序。

第二行将排序的结果输出。

样例输入

41342

样例输出

4123

#include<iostream>

usingnamespacestd;

typedefintElemType;

^defineMAX1000〃运行输入的数据的最大数目

voidSpecialSort(ElemType*array,int&num);//进行特殊排序，num为数据的

数目

voidPrint(ElemType*array,intnum);〃打印结果

intmain()

(

ElemTypearray[MAX];

intn;〃数据的数目

do

cout<<z/Inputthenumberofelements//;

cin>>n;

}while(n<l||n>MAX);

cout«z，Input，，«n<<，/elements:zz<<endl;

for(inti=0;i<n;++i)cin»array[i];

SpecialSort(array,n);

Print(array,n);

return0;

)

voidSpecialSort(ElemType*array,int&num)

(

〃直接插入排序

for(inti=l;i<num;++i)

if(array[i"array[iT])〃后面的比前面的数据小就进行挪动数据

(

ElemTypetmp=array[i];

for(intj=i-l;j>=0&&array[j]>tmp;-j)

array[j+1]=array[j];

array[j+l]=tmp;

)

-num;//num减1,实际上最大的数据还是存在的

)

voidPrint(ElemType*array,intnum)

(

cout«z，\nMaximumElement:〃<<array[num]<<endl;

cout«zzElementsorderedbydescend:，z«endl;

for(inti=0;i<num;++i)

cout<<array[i]<<z，〃；

cout«endl;

1187:最小年龄的3个职工

时间限制：1Sec内存限制：32MB

提交：45解决：17

题目描述

职工有职工号，姓名，年龄.输入n个职工的信息，找出3个年龄最小的职工打

印出来。

输入

输入第一•行包括1个整数N,k=N<=30,代表输入数据的个数。

接下来的N行有N个职工的信息：

包括职工号（整数），姓名（字符串，长度不超过10）,年龄（l〈=age<=100）。

输出

可能有多组测试数据，对于每组数据，

输出结果行数为N和3的较小值，分别为年龄最小的职工的信息。

关键字顺序：年龄》工号》姓名，从小到大。

样例输入

5501Jack6102Nathon100599Lily79923Lucy15814Mickle65

样例输出

501Jack6923Lucy15814Mickle65

#include<I0STREAM>

usingnamespacestd;

constintN=30;

typedefstructWorker

{

intNo;〃职工号

charname[30];〃姓名

intage;〃年龄

Worker()〃无参的构造函数

No=0;

memset(name,30,0);

age=0;

)

//设置参数

voidSet(intpl,char*p2,intp3)

(

No=pl;

strcpy(name,p2);

age=(p3>0&&p3<=100)?p3:0;

)

}Worker;

〃按照职工的年龄排序，只排出n个中的最小3个就停止

//针对数据量很大的信息，最好用堆排序

//数据量小的话，用冒泡或者简单选择排序就可行了

voidSortByAge(Worker*p,intn);

voidSwap(Worker*p,Worker*q);〃两个职工交换位置

voidPrint(Worker*p,intn);〃输出年龄最小的3个职工信息

〃到处是指针对吧！

〃这就到处程序的可读性不好了，主要是想练练手

〃指针很神奇的，学C/C++的话一定要用的得灵活才行

intmain()

(

intn;

do

(

cout<<，，Inputthenumberofworkers(1-30):;

cin>>n;

}while(n<l||n>30);

Worker*pwork=newWorker[30];

intno,age;

charname[30];

cout«z?InputtheNo.,NameandAgeofeachworker/z<<endl;

for(inti=0;i<n;++i)

cin>>no>>name>>age;〃输入职工的参数

//设置职工的参数

(p\vork+i)->Set(no,name,age);

)

SortByAge(pwork,n);〃处理职工信息

〃输出信息

cout«//\ntheinfoyouwant:，/«endl;

Print(pwork,n);

deletepwork;〃释放申请的内存空间

return0;

)

voidSortByAge(Worker*p,intn)

(

〃冒泡排序每一趟都可以排出最小或最大的值，我都快用腻了

intcount=0;

for(inti=0;i<n-l&&count<=3;++i)

(

for(intj=n-l;j>ij)

(

if(((p+j)->age)<((p+j-l)->age))

Swap(p+j,p+j-1);〃两个职工交换位置

)

++count;〃计数

)

)

voidSwap(Worker*p,Worker*q)

(

charbuf[30];

inttmp;

〃交换姓名

strcpy(buf,p->name);

strcpy(p->name,q->name);

strcpy(q->name,buf);

〃交换职工号

tmp=p->No;

p->No=q->No;

q->No=tmp;

〃交换年龄

p->age+=q-〉age;

q->age=p->age-q->age;

p->age-=q->age;

)

voidPrint(Worker*p,intn)

{

for(inti=0;i<n&&i<3;++i)

cout«(p+i)->No<<z，z/<<(p+i)->name«z/，z«(p+i)->age<<endl;

)

1191:矩阵最大值

时间限制：1Sec内存限制：32MB

提交：51解决：24

题目描述

编写一个程序输入一个5X6的矩阵存储并输出，并且求出每行的最大值和每行的

总和。

要求把每行总和放入每行最大值的位置，如果有多个最大值，取下标值最小的那

一个作为最大值。

最后将结果矩阵输出。

输入

输入的第一行包括两个整数m和n(l<=m,n<=100),分别代表矩阵的行和列的维

数。

接下来的m行每行有n个数，代表矩阵的元素。

输出

可能有多组测试数据，对于每组数据，输出按题目要求执行后的矩阵。

样例输入

3311111111133323232323

样例输出

311311311823272823

#include<iostream>

usingnamespacestd;

typedefintElemType;

constintMAX=10;〃设置矩阵的最大行、列数

constintN=2;〃测试的组数

voidProcess(ElemTypematrix[][MAX],introw,intcol);〃对矩阵进行处理

voidPrint(ElemTypematrix[][MAX],introw,intcol);〃打印矩阵值

intmain()

(

for(inti=0;i<N;++i)

(

ElemTypeMatrix[MAX][MAX];

introw,col;

cout<<，zInputtherowandcolofMatrix:z，;

cin>>row>>col;

〃输入矩阵数据

for(inti=0;i<row;++i)

for(intj=0;j<col;++j)

cin»Matrix[i][j];

Process(Matrix,row,col);

cout<<，，\nTheMatrixafterconverting:/z<<endl;

Print(Matrix,row,col);

)

return0;

)

voidProcess(ElemTypematrix[][MAX],introw,intcol)

(

for(inti=0;i<row;++i)

(

intMAX=0;〃MAX标示每行的最大元素位置，默认为第一个

ElemTypesum=0;

for(intj=0;j<col;++j)

(

sum+二matrix[i][j];〃累加求和

if(matrix[i][j]>matrix[i][MAX])MAX=j;

matrix[i][MAX]=sum;〃用sum替换最大值

)

)

voidPrint(ElemTypematrix[][MAX],introw,intcol)

(

for(inti=0;i<row;++i)

(

for(intj=0;j<col;++j)

cout«matrix[i][j]«/?";

cout<<endl;

)

cout«endl;

)

1181:遍历链表

时间限制：1Sec内存限制：32MB

提交:88解决：31

题目描述

建立一个升序链表并遍历输出。

输入

输入的每个案例中第一行包括1个整数：n(l<=n<=1000),接下来的一行包括n

个整数。

输出

可能有多组测试数据，对于每组数据，

将n个整数建立升序链表，之后遍历链表并输出。

样例输入

43579

样例输出

3579

#include<iostream>

usingnamespacestd;

typedefintElemType;

typedefstructNode

(

ElemTypedata;

Node*next;

}Node,*List;

voidSortWhenlnput(List&L,ElemTypet);〃边插入边排序

voidTraverseList(constList&L);〃遍历链表数据

voidRecycling(List&L);〃负责回收内存

intmain()

(

intn;

cout«zzInputN:〃；

cin>>n;

ListL=newNode;

L->next=NULL;

if(L)〃申请内存成功

(

ElemTypedata;

cout<<z，Input，z<<n«zzelementszz<<endl;

for(inti=0;i<n;++i)

{

cin>>data;

SortWhenlnput(L,data);

}

cout<<z，elementsorderedbyascend:，z«endl;

TraverseList(L);

)

else

(

cout<<，，MemoryError!/z<<endl;

exit(EXIT_FAILURE);

return0;

voidSortWhenlnput(List&.L,ElemTypet)

(

Node*p=L-〉next;〃获得L的后续结点指针

Node*q=L;〃获取p的前面一个结点的指针

while(p&&p->data<=t)

(

q=P；〃q指向P

p=p->next;//p后移

)

〃新建结点

Node*s=newNode;

s->data=t;

〃在q的后面插入结点

s->next=q->next;

q->next=s;

)

〃遍历链表数据

voidTraverseList(constList&L)

{

Node*p=L->next;

while(p)

(

cout<<p->data«/?”;

p=p->next;

)

cout«endl;

)

voidRecycling(List&.L)

(

Node*p=L-〉next;〃获取L的后续结点指针

while(p)

(

L->next=p->next;

deletep;〃删除L的所有后续结点

p=L->next;

deleteL;〃删除头结点

L=NULL;//L归为NULL

1195:最长&最短文本

时间限制：1Sec内存限制：32MB

提交：32解决：19

题目描述

输入多行字符串，请按照原文本中的顺序输出其中最短和最长的字符串，如果最

短和最长的字符串不止一个，请全部输出。

输入

输入包括多行字符串，字符串的长度len,(l<=len<=1000)o

输出

按照原文本中的顺序输出其中最短和最长的字符串，如果最短和最长的字符串不

止一个，请全部输出。

样例输入

helloshesorryhe

样例输出

hehellosorry

#include<iostream>

usingnamespacestd;

#defineN1000〃字符串的最大长度

SdefineMAXLINE30〃最多可输入的字符串

intmain()

(

chartxt[MAXLINE][N+l];〃每行存储一个字符串，最后一位用于存储每个字符

串的长度

charminline[MAXLINE+l]={0};〃用于存储最短的字符串在数组中的位置，最

后位存储有效位置的数目

charmaxline[MAXLINE+l]={0};〃用于存储最长字符串在数组中的位置，最后

一位存储有效位置的数目

〃设定输入字符串"EOF”时表示输入结束

cout«"请输入字符串(输入字符串EOF表示输入结束)”《endl;

intcount=0;〃记录输入的有效字符串的数目

for(inti=O;i<MAXLINE;++i)

(

cin»txt[i];

if(!strcmp(txt[i],"EOF"))break;〃输入结束

txt[i][N]=strlen(txt[i]);〃把该字符串的长度放在最后一位

++count;

〃整理出最短和最长的字符串在数组中的位置

intmax=txt[0][N];〃最大和最小长度都初始化为第一个字符串的长度

intmin=txt[0][N];

for(i=0;i<count;++i)

(

〃处理最短的字符串

if(min>txt[i][N])

{

min=txt[i][N];〃更新min

minline[0]=i;〃更新最短字符串的位置

minline[MAXLINE]=1;〃最短字符串的数目修改为1

)

elseif(min==txt[i][N])

{

〃出现多个最短字符串，插入到后面,minline的最后一位也指示了插入的位

置

miniine[miniine[MAXLINE]]=i;

++minline[MAXLINE];〃最短字符串数目加1

)

〃处理最长的字符串

if(max<txt[i][N])

(

max=txt[i][N];//更新max

maxiine[0]=i;〃更新最长字符串的位置

maxiine[MAXLINE]=1;〃最长字符串的数目修改为1

)

elseif(max==txt[i][N])

maxiine[maxiine[MAXLINE]]=i;〃出现多个最长字符串，插入到后面

++maxline[MAXLINE];〃最长字符串数目加1

〃输出最短的和最长的字符串

for(i=0;i<count;++i);

(

cout<〈end"〈〃最短的字符串“<Xendl;

for(intj=0;j<minline[MAXLINE];++j)

cout<<txt[miniine[j]]<<endl;

cout〈〈endl<〈”最长的字符串〃<<endl;

for(j=0;j<maxline[MAXLINE];++j)

cout«txt[maxiine[j]]<<endl;

return0;

题目描述

输入一个四行五列的矩阵，找出每列最大的两个数。

输入

输入第一行包括一个整数n(l<=n<=1000),接下来的四行每行包括五个整数。代

表一个四行五列的矩阵，矩阵元素全部是整数。

输出

可能有多组测试数据，对于每组数据，按照样例输出的格式将每列最大的两个数

输出，如果最大的两个数中的一个数在这一列中有多个相同的值，则行值取行值

小的那一个。

输出时要保留原矩阵的行列顺序，即在原矩阵中行值小的，在输出矩阵中的行值

依然小。

样例输入

112498-1498812987078970

样例输出

12999878988

提示

每个数字后面都要输出一个空格

#include<iostream>

usingnamespacestd;

constintR0W=4;

constintC0L=5;

voidProcess(constintarray[ROW][COL],intdata[2][COL]);〃将处理的结

果放在data中

intmainO

(

intn;

intarray[ROW][COL]；〃存储矩阵信息

intdata[2][C0L]={0};〃存储处理结果

〃输入矩阵的数据

cout«，zInputthenumberofarray(，，«ROW<<，/*，/<<COL<<z，):/z;

cin>>n;

for(inti=0;i<n;++i)

(

for(intj=0;j<ROW;++j)

for(intk=O;k<COL;++k)

cin»array[j][k];

Process(array,data);

cout<<，zTheResult:，z«endl;

for(j=0;j<2;++j)

(

for(intk=O;k<COL;++k)

cout«data[j][k]«z，，z;

cout«endl;

)

)

return0;

)

voidProcess(constintarray[ROW][COL],intdata[2][COL])

(

for(inti=0;i〈COL;++i)〃寻找每一列中的最大的两个数

(

〃初始化为该列的最下面的两个数，并与中上下位置对应

data[0][i]=array[ROW-2][i];

data[l][i]=array[ROW-1][i];

for(intj=ROW-3;j>=0;-j)

(

if(array[j][i]>=data[0][i]||array[j][i]>=data[l][i])

(

if(data[0][i]>=data[l][i])data[l][i]=data[0][i];〃将上面的值往下

挪

data[0][i]=array[j][i];〃较大或者相同但是小标较小的数放在上面

)

)

题目描述

不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连

接起来。

输入

每一行包括两个字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据，

不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连

接起来。

输出连接后的字符串。

样例输入

abcdef

样例输出

abcdef

#include<iostream>

usingnamespacestd;

constintN=3;

typedefstructNode

(

charch;

Node*next;

);

intmain()

(

structNode*head[2]={0};

structNode*tail[2]={0};

for(intj=0;j<N;++j)

(

〃利用链表存储字符串

cout<<，zInputtwostrings:";

charch;

for(inti=0;i<2;++i)

(

do

(

ch=getchar();

}while(ch='')；〃过滤掉每个字符串最前面的所有空格符

while(ch!=，\n&&ch!=，')

(

Node*p=newNode;

if(!p)

(

cout«z/Erroroccuredwhenallocatingmemory!/z<<endl;

exit(0);

p->ch=ch;

p->next=NULL;

if(tail[i])tail[i]->next=p;

elsehead[i]=tai1[i]=p;

tail[i]=p;

ch=getchar();

〃进行字符串连接，将链表的首尾相接即完成

tail[0]->next=head[l];

〃输出连接后的字符串

Node*q=head[0];

while(q)

(

cout«q->ch;

q=q->next;

)

cout<<endl;

〃清空申请的内存空间

q=head[0];

while(q)

(

head[O]=q->next;

deleteq;

q=head[0];

)

head[O]=head[1]=NULL;

tail[O]=tail[l]=NULL;

cout<<endl;

)

return0;

1199:找位置

题目描述

对给定的一个字符串，找出有重复的字符，并给出其位置，如：

输出：a,1；a,4；a,5；a,10,b,2；b,11,1,8；1,12,2,9；2,130

输入

输入包括一个由字母和数字组成的字符串，其长度不超过100o

输出

可能有多组测试数据，对于每组数据，

按照样例输出的格式将字符出现的位置标出。

样例输入

abcaaAB12abl2

样例输出

a:0,a:3,a:4,a:9b:1,b:10c:2A:5B:61:7,1:112:8,2:12

提示

1、下标从o开始。

2、相同的字母在一行表示出其出现过的位置。

#include<iostream>

usingnamespacestd;

constintN=100;

intmain(void)

(

chararray[N][N+l]={0};〃每一行的第一位存储字符，后面的空间存储出现的

位置

charcounter[N]={0};〃记录每个字符出现的次数

charstr[N];〃用于存储输入的字符串

intlen;

do//保证输入的字符串长度不超过100

(

cout<<z，Inputthestring:/z<<endl;

cin»str;

len=strlen(str);

}while(len>100);

chari,j;

for(i=0;i<len;++i)

(

j=0;

while(array[j][0]&&array[j][0]!=str[i])++j;

if(!array[j][0])array[j][0]=str[i];〃如果出现的是新字母就填入数组

的第一位

++counter[_j];〃计时器加1

array[j][counter;〃记录字符出现的位置

}

〃输出信息

for(i=0;array[i][0];++i)

(

for(j=l;j<counter[i];++j)

cout<<array[i][0]«//：//<<int(array[i][j])«';";

cout«array[i][0"<"："<<int(array[i][j])«endl;

}

return0;

题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入

输入第一行包括一个整数n(l<=n<=100)o

接下来的一行包括n个整数。

输出

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并

对二叉排序树进行前序、中序和后序遍历。

每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入

516598

样例输出

165981568958961

提示

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

〃下面的已经足够对付这个机试题目了，等过几天我再写个包含更多功能的二叉

排序树的程序

〃这里面的递归实在太多了，递归固然简单，效率较低啊，不用递归的话，就扩

展数据结构了，线索二叉树不错

#include<iostream>

usingnamespacestd;

SdefineMAX100〃二叉排序数中的元素最大数目

typedefintElemType;

〃定义二叉排序数的结点结构

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

Node(ElemTypeelem)〃结点带参构造函数

(

data=elem;

lchild=NULL;

rchild=NULL;

}Node,*BST;

voidCreateBST(BST&bst,ElemTypeelem);〃动态创建二叉排序数

voidPreOrder(constBST&bst);〃前序遍历二叉树

voidMidOrder(constBST&bst);〃中序遍历二叉树

voidPostOrder(constBST&bst);〃后序遍历二叉树

voidRecycling(BST&bst);〃回收二叉树的内存空间

intmain()

intn;

do

cout«〃InputthenumberofelementsofBinary_Sort_Tree:z/;

cin>>n;

}while(n<l||n>MAX);

〃动态创建二叉排序树

cout«z，Input，，«n<<，,elementsofBinary_Sort_Tree:z/<<endl;

BSTbst=NULL;〃二叉排序树跟结点初始化为NULL

ElemTypeelem;

for(inti=0;i<n;++i)

(

cin>>elem;

CreateBST(bst,elem);

〃先序遍历二叉排序树

cout«z，\nPreOrderBinary_Sort_Tree:z，«endl;

PreOrder(bst);

cout«endl;

〃中序遍历二又排序树

cout«/z\nMidOrderBinary_Sort_Tree:，，«endl;

MidOrder(bst);

cout«endl;

〃后序遍历二叉排序树

cout«z，\nPostOrderBinary_Sort_Tree:z，<<endl;

PostOrder(bst);

cout«endl;

return0;

voidCreateBST(BST&bst,ElemTypeelem)

(

if(bst)

(

if(elem<bst->data)〃向左子树扫瞄

(

if(bst->lchild)CreateBST(bst->lchiId,elem);〃左子树不为空

elsebst->lchild=newNode(elem);

)

elseif(elem>bst->data)〃向右子树扫描

(

if(bst->rchild)CreateBST(bst->rchild,elem);〃右子树不为空

elsebst->rchild=newNode(elem);

)

)

〃二叉排序树的根节点为NULL

elsebst=newNode(elem);〃构造新结点

voidPreOrder(constBST&bst)

(

if(bst)

(

cout<<bst->data«zz

PreOrder(bst->lchiId);

PreOrder(bst->rchiId);

)

)

voidMidOrder(constBST&bst)

{

if(bst)

(

MidOrder(bst->lchiId);

cout<<bst->data«zz〃；

MidOrder(bst->rchiId);

voidPostOrder(constBST&bst)

(

if(bst)

(

PostOrder(bst->lchiId);

PostOrder(bst->rchiId);

cout<<bst->data«，zz，;

)

voidRecycling(BST&bst)

(

〃采取中序方式回收内存空间

if(bst)

(

Recycling(bst->lchild);

Recycling(bst->rchild);

deletebst;〃释放根节点的内存空间

)

题目描述

N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。(要求采用

非递归)

输入

输入包括一个整数N,(l<=N<90)。

输出

可能有多组测试数据，对于每组数据，

输出当楼梯阶数是N时的上楼方式个数。

样例输入

4

样例输出

5

〃这题倒是不涉及到数据结构方面的东西,关键是分析问题

//走两阶是一步，走一阶也是一步，前者和后者又不同

//所以只要在所有的步数中选择出那儿步是可以一次走两阶的就所求的走法

//走两阶的步数i在0-N/2之间,进行排列再求和就可以了

//测试了一下,输入n=68时,我的机器就罢工了,郁闷!

#include<iostream>

usingnamespacestd;

intCombine(intn,intm);//求排列结果

〃这是题目不允许的递归，递归关系倒是简单得很

intOtherWay(intn);

intmainO

(

intn;〃阶梯的级数

cout«zzInputthenumberofstairs:z，;

cin>>n;

intsum=0;〃总的走法

inttwo=n/2;〃每次走两阶的最大步数

//每多个一步走了两阶，那么所走的步数相对上一次就少1了

for(inti=0;i<=two;++i)sum十二Combine(n-i,i);

cout«zz\nThenumberofways://<<sum«endl;

〃递归方式

cout<</zTheothersolutionnotallowed:/z<<0therWay(n)<<endl;

return0;

intCombine(intn,intm)〃求排列结果

(

〃按照排列组合的公式求解就可以搞定

if(n<=0)return0;

if(!m)return1;

intp=l;

for(inti=n;i!=n-m;--i)p*=i;

intq=l;

for(intj=l;j!=m+l;++j)q*=j;

returnp/q;

〃这是题目不允许的递归，递归关系倒是简单得很

intOtherWay(intn)

{

if(!n)return0;

elseif(n==l)return1;

elseif(n==2)return2;

elsereturnOtherWay(n-l)+0therWay(n-2);

)

84:二叉树遍历

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉

树（以指针方式存储）。

例如如下的先序遍历字符串：

ABC##DE#G##F###

其中表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉

树进行中序遍历，输出遍历结果。

输入

输入包括1行字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据，

输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。

每个输出结果占一行。

样例输入

abc##de#g##f###

样例输出

cbegdfa

〃这个题目让我机试时写出来时间肯定不够啊

//关键是当时在解决查找插入点时遇到了回溯问题

//一时没想到引入栈，又没找到个递归的规律，浪费了不少时间

//做过一次就好了，以后遇到递归我就果断引入栈

//写完看了下，栈和二叉树封装成类挺合适的

#include<iostream>

usingnamespacestd;

constintMAX_LEN=100;//字符串的最大长度

typedefcharElemType;

〃二叉树的结点结构

typedefstructNode

(

ElemTypedata;

Node*lchild;

Node*rchild;

charflag;〃标示该结点的孩子结点数目

〃结点的构造函数

Node(ElemTypeelem)

(

data=elem;

lchild=NULL;

rchild=NULL;

flag=0;〃不带任何结点

}Node,*BiTree;

〃由于在查找插入点的过程中有回溯问题，只好引入栈了

typedefstructStack

(

chartop;〃指向栈顶

Node*container[MAX_LEN/2];〃最多也就MAX_LEN/2个节点

Stack()〃默认构造函薮

(

top=0;

)；

〃添加栈的相关操作

//节点入栈

voidPush(Node*&p)

(

container[top++]=p;

}

〃获取栈顶元素

Node*GetTop()

(

if(top>0)returncontainer[top-1];

returnNULL;

)

〃弹出所有不能再添加子节点的节点，直到遇到了可添加子节点的节点

//那么也就保证了栈顶元素始终是可添加子节点的

voidPop()

(

Node*p=GetTop();

while(top>0&&p->flag>=2)

(

—top;

p=GetTop();

}Stack;

Stackstack;〃全局的栈辅助查找插入点

〃检查输入的字符串是否满足构造二叉树的条件

boolCheckString(ElemTypestr[]);

//创建二叉树

voidCreateBiTree(BiTree&bt,ElemTypeelem);

〃中序遍历二叉树

voidMidOrder(constBiTree&bt);

〃回收内存空间

voidRecycling(BiTree&bt);

intmainO

(

ElemTypestr[MAX_LEN];

cout«zzInputthestring:zz<<endl;

cin>>str;

if(CheckString(str))〃字符串通过检查

(

BiTreebt=NULL;

intlen=strlen(str);

for(inti=0;i<len;++i)CreateBiTree(bt,strLi]);

cout<<，，\nMidOrdertheBinaryTree:/z«endl;

MidOrder(bt);

cout<<endl;

Recycling(bt);

}

elsecout<<，，Thestringisnotabletoformabinarytree!z，<<endl;

return0;

〃检查输入的字符串是否满足构造二叉树的条件

boolCheckString(ElemTypestr[])

(

〃实际上，如果算上可以构成一颗满二叉树，作为叶子结点的

〃所以，比其余的字符数目多1则满足要求

intlen=strlen(str);

intcount=0;〃为'计数

for(inti=0;i<len;++i)

if(str[i]==，#')++count;

if(count+count-len==l)returntrue;〃测试通过

returnfalse;

〃创建二叉树

voidCreateBiTree(BiTree&bt,ElemTypeelem)

if(!bt&&elem!=，#')

(

bt=newNode(elem);〃创建根节点

stack.Push(bt);〃新节点入栈

}

else

(

stack.PopO;〃弹出所有不能插入子节点的节点

Node*p=stack.GetTop();〃获取插入点

if(p)〃找到了插入点

(

if(elem!='#')

(

Node*q=newNode(elem);

if(p->flag==0)p->lchild=q;

elsep->rchild=q;

stack.Push(q);//新节点入栈

)

++p->flag;

)

)

)

〃中序遍历二叉树

voidMidOrder(constBiTree&bt)

{

if(bt)

(

MidOrder(bt->lchiId);

cout<<bt->data<<z，

MidOrder(bt->rchiId);

)

)

〃回收内存空间

voidRecycling(BiTree&bt)

(

if(bt)

Recycling(bt->lchild);

Recycling(bt->rchiId);

deletebt;〃回收根节点的内存空间

)

)

1107:搬水果

时间限制：1Sec内存限制：32MB

提交：123解决：28

题目描述

在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若

干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并

到一起，消耗的体力等于两堆水果的重量之和。当然经过n-1次合并之后，就

变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。

假定每个水果重量都为1,并且已知水果的种类数和每种水果的数目，你的任务

是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费

值。例如有3种水果，数目依次为1,2,90可以先将1,2堆合并，新堆数

目为3,耗费体力为3o然后将新堆与原先的第三堆合并得到新的堆，耗费体力

为12。所以小明总共耗费体力=3+12=15,可以证明15为最小的体力耗费值。

输入

每组数据输入包括两行,第一行是一个整数n(l<=n<=10000),表示水果的种类

数，如果n等于0表示输入结束，且不用处理。第二行包含n个整数，用空

格分隔，第i个整数(k=ai<=1000)是第i种水果的数目。

输出

对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数

据保证这个值小于2~31。

样例输入

39120

样例输出

15

//先分析问题，运用递归思想解析问题

//1.如果只有一堆水果xl,则不用搬

//2.如果有两堆水果xl和x2,则只需搬一次,且方法唯一

//3.如果有三堆水果xl、x2和x3,则有三种搬运方法：

//3.1若先搬xl和x2,则体力耗费值为Hl=2*(xl+x2)+x3;

//3.2若先搬xl和x3,则体力耗费值为H2=2*(xl+x3)+x2;

//3.3若先搬x2和x3,则体力耗费值为H3=xl+2*(x2+x3);

//3.4很显然,若xl、x2都小于x3,则Hl最小；xl、x3都小于x2时,H2最小;x2、

x3都小于xl时,H3最小；

//3.5也就是和并三者中的较小的两堆可是耗费体力值最小

〃4.如果有四堆水果xl、x2、x3和x4,则必须先合并其中的两堆，然后就成了

三堆水果

//4.1问题就集中在先合并哪两堆呢？

//4.2分析3.5的结论及体力耗费值公式，不难推出：三堆中的较小两堆之

和越小体力耗费值越小

//4.3所以,先合并最小的两堆，然后构成第三堆

//5.依次这样递推，得出结论，每次都合并最小的两堆可是体力耗费值最小

//

//延伸：每次都选择最小的两个数组合，是否让你想到了huffman_Tree?

//实际上，这也就是求带权路径长度WPL的最小值问题

//当然，如果这题要去建立Huffman_Tree去解决问题就太麻烦了，而且

Huffman_Tree也不是那么好构建的

//问题而答案就是Huffman一Tree中所有非终端节点的值的和，我就用结构体数

组解决问题算了

#include<iostream>

usingnamespacestd;

typedefstructNode

(

intdata;〃节点值

boolflag;〃节点值是否可用来合并的标示

Node()

(

flag=false;〃结点的值初始化为不允许合并

data=0;

)

}Node;

#defineMAX100〃最大的水果种类数目及对应的水果数目的最大值

〃处理数据，计算出体力耗费最小值

intProcess(Nodenum[],intn);

〃打印每次搬运后的水果堆的情况

voidPrint(Nodenum[],intn);

〃寻找最小的两个节点的位置,放在la和1b内

voidFindLeast(Nodenum[],int&la,int&lb,intn);

intmain()

(

intn;〃存储水果种类数目

Nodenum[2*MAX-l];〃存储每种水果的数目

do

(

cout<<，，Howmanykindsoffruits:";

cin»n;

cout<<z，Inputthenumberofeverykindoffruit:z，<<endl;

for(inti=0;i<n;++i)

{

cin>>num[i].data;

num[i].flag=true;〃输入数据后允许节点合并

)

intresult=Process(num,n);〃获取体力耗费最小值

cout<<，，Theleastphysicalpowertobeconsumed:，，«result«endK<endl;

}while(n>0&&n<=MAX);

return0;

intProcess(Nodenum[],intn)

(

//最后返回所有非终端节点之和就可以了，非终端节点数目比叶子节点数目小

1

if(n>l)

(

intpos=MAX;//pos标示在p数组放置非终端节点的位置

intla,1b;〃指示最小可用节点的位置

for(inti=0;i〈nT;++i)//处理过程经历n-1次就结束

FindLeast(num,la,lb,n);

numtpos].data=num[la].data+num[lb].data;〃水果堆合并

num[pos].flag=true;//允许节点在下一次合并

num[la].flag=false;//la和lb处节点已经合并就不允许再合并了

num[lb].flag二false;

〃打印合并的节点及结果

cout<<z/Merge:(z，<<num[la].data<<，，+，，«num[lb].data«z/一一>z/<<num[pos].

data<<，z)，，«endl;

++pos;

〃打印合并后的水果堆状态

cout«z?Statusoffruitspile:/z;

Print(num,n);

)

〃计算体力耗费值，也就是所有的非叶子节点的值之和

intsum=0;

for(i=MAX;i<MAX+n-l;++i)

sum+=num[i].data;

returnsum;〃返回体力耗费值

)

elseif(n==l)returnnum[0].data;

return0;

〃打印每次搬运后的水果堆的情况

voidPrint(Nodenum[],intn)

(

cout«zz(〃；

〃打印叶子节点

for(inti=0;i<n;++i)

if(num[i].flag)cout<<num[i].data<<z，,

〃打印由上一次合并后的节点信息

for(intj=MAX;j<MAX+n-l;++j)

if(num[j].flag)cout«num[j].data<<〃,

。。成《〃\了;〃去掉最后一个‘，';

cout«zz)z/<<endl;

)

〃寻找最小的两个节点的位置,放在la和1b内

voidFindLeast(Nodenum[],int&la,int&lb,intn)

la=lb=-l;

〃在未经过合并的水果堆里寻找最小的

for(inti=0;i<MAX+n-l;++i)

(

〃之所以加上这一行，是为了在i=n是将i重定向到以MAX为起始点的位置

〃使得与经过合并的并且可再次用来合并的水果堆里进行比较

i=(i==n)?MAX:i;

if(num[i].flag)

(

if(la==-l)la=i;

elseif(lb==-l)lb=i;

else

(

if.data<num[la].datal|num[i].data<num[lb].data)

(num[la].data>num[lb].data?la:lb)=i;

)

)

题目描述

对于给定的正整数n,计算其十进制形式下所有位置数字之和，并计算其平方的

各位数字之和。

输入

每行输入数据包括一个正整数n(0<n<40000),如果n=0表示输入结束，并不用

计算。

输出

对于每个输入数据，计算其各位数字之和，以及其平方值的数字之和，输出在一

行中，之间用一个空格分隔，但行末不要有空格。

样例输入

41297399990

样例输出

473916223936

#include<iostream>

usingnamespacestd;

SdefineMAX40000

//int类型为4字节，足以保存小于1600000000的数

〃计算data的各位数字之和置于suml内，平方后各位数字之和置于sum2内

voidProcess(intdata,int&suml,int&sum2);

intmain()

(

intn,suml,sum2;

cout<<，zInputn:〃；

cin>>n;

while(n)

(

if(n>MAX)continue;

Process(n,suml,sum2);

cout<<suml<<z，，z«sum2<<endl;

cout<<z，Inputn:〃；

cin»n;

)

return0;

)

〃计算data的各位数字之和置于suml内，平方后各位数字之和置于sum2内

voidProcess(intdata,int&suml,int&sum2)

(

suml=sum2=0;

intsquare=data*data;

while(data)

(

suml+二data;

data/=10;

while(square)

sum2+=square;

square/=10;

题目描述

一个二进制数，将其每一位取反，称之为这个数的反码。下面我们定义一个字符

的反码。如果这是一个小写字符，则它和字符'a'的距离与它的反码和字符'z'

的距离相同；如果是一个大写字符，则它和字符'A'的距离与它的反码和字符

'Z'的距离相同；如果不是上面两种情况，它的反码就是它自身。

举几个例子，'a，的反码是‘z'；'c'的反码是'x'；'旷的反码是‘D'；'『

的反码还是‘1'；'$'的反码还是

一个字符串的反码定义为其所有字符的反码。我们的任务就是计算出给定字符串

的反码。

输入

输入每行都是一个字符串，字符串长度不超过80个字符。如果输入只有！，表

示输入结束，不需要处理

输出

对于输入的每个字符串，输出其反码，每个数据占一行。

样例输入

HelloJLU-CCST-2011!

样例输出

SvoolQ0F-XXHG-2011

#include<iostream>

usingnamespacestd;

constintMAXLEN=80;

voidReverse(char*str);〃对字符串进行反码处理

intmain()

(

charstr[MAX_LEN];

cout<<zzInputastring:";

cin>>str;

while(str[0]!=’!')

(

Reverse(str);

cout<<z，stringreversed:zz;

cout<<str«endl;

cout<<，，Inputastring:";

cin»str;

)

return0;

〃对字符串进行反码处理

voidReverse(char*str)

(

for(chari=0;str[i];++i)

(

if(str[i]>=，a'&&str[i]<=，z')

str[i]=，z'a');

elseif(str[i]>=，AJ&&str[i]<=，Z')

str[i]-Z'-(str[i]~，A?);

题目描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push和pop。Push

一个值会将其压入栈顶，而pop则会将栈顶的值弹出。现在我们就来验证一下

堆栈的使用。

输入

对于每组测试数据，第一行是一个正整数n,0<n<=10000（n=0结束）。而后的n

行，每行的第一个字符可能是'P'或者'0'或者'A'；如果是'P’,后面还会跟

着一个整数，表示把这个数据压入堆栈；如果是'0',表示将栈顶的值pop出

来，如果堆栈中没有元素时，忽略本次操作；如果是'A',表示询问当前栈顶的

值，如果当时栈为空，则输出'E'。堆栈开始为空。

输出

对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A'操作，输

出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E'。当每组测试数

据完成后，输出一个空行。

样例输入

3AP5A4P3P60A0

样例输出

E53

#include<iostream>

usingnamespacestd;

SdefineMAX100〃堆栈的最大容量

〃定义堆栈的数据结构及操作

typedefstructStack

{

int*pdata;

inttop;〃栈顶指示器

Stack()〃默认构造函数

(

top=0;

pdata=newint[MAX];

)

voidPush(intdata)〃入栈操作

*(pdata+top)=data;

++top;

)

intPop()〃出栈操作

(

—top;

return*(pdata+top);

)

intGetTop()〃获取栈顶数据

(

return*(pdata+top-l);

)

boolStackEmpty()〃判定栈是否为空

(

if(!top)returntrue;

returnfalse;

)

"Stack()〃析构函数

(

top=0;

deletepdata;

pdata=NULL;

)

}Stack;

intmainO

(

intn;〃要进行的操作数目

do

cout<<zzInputn:";

cin»n;

charch;

intdata;

for(chari=0;i<n;++i)

(

〃之所以把stack放在这，是保证其作用域在输入的n的范围下有效，以免

下次输入n用的还是上次的栈

Stackstack;

cin>>ch;

switch(ch)

{

case'A':

if(stack.StackEmpty())cout〈〈〃E〃；

elsecout«stack.GetTop()«endl;

cout<</，---Operationisover---zz<<endl;

break;

case'P':

cin>>data;

stack.Push(data);

cout<</，---Operationisover—〃<<endl;

break;

case'O':

if(!stack.StackEmpty())stack.Pop();

cout<<，z---Operationisover---，z<<endl;

break;

default:

一i；〃非法操作时i必须保持不变

cout<<，z--IllegalOpration---/z<<endl;

break;

)

)

}while(n);

return0;

题目描述

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入

每组数据的第一行是两个整数n和m(0<=n<=1000)on表示图的顶点数目，m

表示图中边的数目。如果n为0表示输入结束。随后有m行数据，每行有两

个值X和y(0<x,y<=n),表示顶点x和y相连，顶点的编号从1开始计

算。输入不保证这些边是否重复。

输出

对于每组输入数据，如果所有顶点都是连通的，输出"YES”,否则输出"NO"。

样例输入

4312233232122300

样例输出

NOYES

〃首先，我觉得有必要温习一下图的连通性的相关概念

//I无向图G的连通性：

//若无向图G中的任何两个结点都是可达的，则称G是连通图(connected

graph),

//否则称G是非连通图(unconnectedgraph)或分离图(separatedgraph)

//H有向图G的连通性：

//若将有向图G所有边的方向略去，得无向图G'

//若G'是连通图则成G是连通图或弱连通图(weaklyconnecte