C++数据结构上机作业DS作业和实验参考答案总汇.docx

资源描述

C++数据结构上机作业DS作业和实验参考答案总汇.docx

《C++数据结构上机作业DS作业和实验参考答案总汇.docx》由会员分享，可在线阅读，更多相关《C++数据结构上机作业DS作业和实验参考答案总汇.docx（112页珍藏版）》请在冰点文库上搜索。

C++数据结构上机作业DS作业和实验参考答案总汇.docx

C++数据结构上机作业DS作业和实验参考答案总汇

2013级DS作业和实验参考答案总汇目录20141217

第一次作业：

复习C++9000，9002

第二次作业：

顺序表插入和删除操作9003，9004

第三次作业：

顺序表查找操作和单链表建立9012，9006

第四次作业：

单链表操作9014，9016，9017

第五次作业：

特殊线性表栈操作9045，9042，9041

第六次作业：

特殊线性表队列操作9038，9040

第七次作业：

二叉树的顺序存储9050

第八次作业：

复制二叉树9063

第九次作业：

二叉树的高度宽度9057，9067

第十次作业：

图的邻接矩阵及遍历9070，9072，9087

第十一次作业：

图的生成树9076，9077，9088

第十二次作业：

图的最短路径9092，9091，9085

！

第一次实验：

顺序表9010，9005

第二次实验：

顺序表29097

第三次实验：

单链表9007

第四次实验：

循环链表9008

第五次实验：

递归9039

第六次实验：

二叉树的建立及遍历9019

第七次实验：

二叉树的结点9054，9056

第八次实验：

二叉树的存储转换9049

第九次实验：

哈夫曼编码9068

第十次实验：

图的邻接表及度9071，9079

第十一次实验：

图的存储转换9089，9084，9083

第十二次实验：

模拟考试

！

第一次作业：

复习C++9000，9002

9000:

矩形面积

ProblemDescription

声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。

若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。

Input

输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。

Output

若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。

SampleInput

SampleOutput

//9000ANSWERCODE1

#include

usingnamespacestd;

classrect{

public:

rect（inta,intb,intc,intd）;

~rect（）{}

intarea（）;

private:

intx1,y1,x2,y2;

};

rect:

rect（inta,intb,intc,intd）{x1=a;y1=b;x2=c;y2=d;}

intrect:

area（）{return（x2-x1）*（y2-y1）;}

intmain（）{

inta,b,c,d,n;

cin>>n;

while（n--）

{

cin>>a>>b>>c>>d;

if（a<0||b<0||c<0||d<0||a>=c||b>=d）

cout<<"dataerror"<

else

{rectr（a,b,c,d）;

cout<

}

return0;

}

9002:

数组的循环移位

ProblemDescription

对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。

Input

输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。

Output

循环左移后的字符型数组内容。

SampleInput

abcdefgh

SampleOutput

defghabc

//9002ANSWERCODE1

#include

usingnamespacestd;

#defineN20

voidReverse（chara[],intfrom,intto）

{

inti,j;chart;i=from;j=to;

while（i

{t=a[i];a[i]=a[j];a[j]=t;i++;j--;}

}

voidConverse（chara[],intn,inti）

{Reverse（a,0,i-1）;Reverse（a,i,n-1）;Reverse（a,0,n-1）;}

intmain（）

{

chara[N];intm,n,i;cin>>m;

while（m--）{

cin>>a>>i;

n=strlen（a）;i=i%n;

Converse（a,n,i）;

cout<

}

return0;

}

第二次作业：

顺序表插入和删除操作9003，9004

9003:

合并顺序表

ProblemDescription

假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。

若合并后的顺序表表长超过总容量20，则输出“notenough”。

Input

第一行为一个数字n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。

Output

若合并成功，输出两行信息，第一行表示合并后A表的表长，第二行表示合并后A表的数据元素，元素之间用一个空格分隔；若合并后的顺序表表长超过总容量20，则输出“notenough”。

SampleInput

13817

61015

SampleOutput

1368101517

//9003ANSWERCODE1

#include

usingnamespacestd;

constintMaxSize=20;//有两个由小到大有序的有序顺序表A和B

voidcombine（intA[],intA_len,intB[],intB_len）

{

if（（A_len+B_len）>MaxSize）cout<<"notenough\n";

else

{

inti=0,j=0,k=0;

for（i=0;i

{

while（B[i]>A[j]）//找到B[i]在A表中的插入位置j

{j++;}

for（k=A_len-1;k>=j;k--）//把j（包括j）后的元素往后挪一个位置，空出j来。

{A[k+1]=A[k];}

A[j]=B[i];//把B[i]插入A表中的位置j

A_len++;//A表长度加1

}

cout<

for（i=0;i<（A_len-1）;i++）cout<

cout<

}

voidmain（）{

intA[MaxSize],B[MaxSize],A_len,B_len,n,i;

cin>>n;

while（n--）{

cin>>A_len;

for（i=0;i>A[i];}

cin>>B_len;

for（i=0;i>B[i];}

combine（A,A_len,B,B_len）;

}

9004:

连续删除

ProblemDescription

从由小到大有序的顺序表中删除其值在[s,t]之间（含s和t）的所有元素，且不改变顺序表的有序性。

如果s>=t则显示“dataerror”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。

Input

输入的第一行为一个数字n，表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个数字s和t，第二行为顺序表的表长len（0

Output

对于每组数据，如果s>=t，则直接输出“dataerror”，否则输出两行信息：

第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。

SampleInput

818

13510171925

SampleOutput

1351925

//9004ANSWERCODE1

#include

usingnamespacestd;

intmain（）

{

intn,s,t,len,A[21],i,s_i,t_i,j,span;

cin>>n;

while（n--）{

cin>>s>>t>>len;

for（i=0;i>A[i];

if（s>=t||len<=0||len>20）

{cout<<"dataerror"<

s_i=0;t_i=len-1;

while（A[s_i]

while（A[t_i]>t&&t_i>=0）t_i--;

if（s_i<=t_i）

{

span=t_i-s_i+1;

for（j=s_i;j

len-=span;

}

if（len!

=0）

{

cout<

for（i=0;i

cout<

}

return0;

}

第三次作业：

顺序表查找操作和单链表建立9012，9006

9012:

找唯一数

ProblemDescription

在一个表长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。

请找出这个仅出现一次的元素。

Input

有多组数据，每组第一行表示表长n（1<=n<=11111）；第二行表示顺序表的各元素。

Output

输出这个唯一数。

SampleInput

22131

2113-123

SampleOutput

-1

//9012ANSWERCODE1

#include

usingnamespacestd;

intmain（）

{

intn,i,j,A[11112],B[11112];

while（cin>>n）

{

if（n>=1&&n<=11111）

{

for（i=0;i>A[i];

for（i=0;i

{for（j=i+1;j

{if（A[i]==A[j]）{B[i]=0;B[j]=0;break;}}

}

for（i=0;i

{if（B[i]==1）cout<

}

return0;

}

9006:

单链表的建立和遍历

ProblemDescription

输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。

Input

输入数据有多组，每组数据占两行；每组第一行为一个数字N（N<=50）；第二行有N个整数。

Output

输出这组整数，数字之间用一个空格分隔。

SampleInput

1232457854

SampleOutput

1232457854

//9006ANSWERCODE1

#include

usingnamespacestd;

structNode{intdata;Node*next;};

intmain（）

{

intN,i,A[51];

Node*head=newNode,*p,*tail;

while（cin>>N）

{

if（N>0）

{

for（i=0;i>A[i];

tail=head;

for（i=0;i

{

p=newNode;p->data=A[i];

tail->next=p;tail=p;

}

tail->next=NULL;p=head->next;

for（i=0;i

{cout<data<<"";p=p->next;}

cout<data<

}

return0;

}

第四次作业：

单链表操作9014，9016，9017

9014:

删最小值

ProblemDescription

设有一单链表，现要求删除其最小值（假设最小值唯一）。

若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。

Input

有多组数据，每组第一行为单链表的元素个数n（0<=n<100）；第二行为单链表的各个元素。

Output

若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。

SampleInput

426-319145

24167

SampleOutput

-3

//9014ANSWERCODE1

#include

usingnamespacestd;

structNode{intdata;Node*next;};

intmain（）

{

inti,n,data[100],min;

Node*first,*p,*q,*s,*tail;

while（cin>>n）

{

if（n==0）{cout<<"notexist\n";continue;}

for（i=0;i>data[i];

first=newNode;first->next=NULL;tail=first;

for（i=0;i

{s=newNode;s->data=data[i];tail->next=s;tail=s;}

tail->next=NULL;

p=first;min=first->next->data;

while（p->next）

{q=p;p=p->next;

if（p->datadata;

}

p=first->next;q=first;

while（p）

{if（p->data==min）break;

else{q=p;p=p->next;}}

if（p&&q）{q->next=p->next;deletep;cout<

else{cout<<"notexist\n";}

}

return0;

}

9016:

查找倒数第k个结点

ProblemDescription

有一单链L，请输出该单链表中倒数第k个结点的值。

若该结点不存在，则输出“notfind”。

Input

有多组数据，每组第一行为单链表元素个数n和k值（00）；第二行为单链表的各元素。

Output

输出该单链表中倒数第k个结点的值。

若该结点不存在，则输出“notfind”。

SampleInput

12345

SampleOutput

//9016ANSWERCODE1

#include

usingnamespacestd;

structNode{intdate;Node*next;};

intmain（）

{

intn,k,i,c,data[100];Node*first,*r,*p,*s;

while（cin>>n>>k）

{

for（i=0;i>data[i];

first=newNode;r=first;

for（i=0;i

{s=newNode;s->date=data[i];

r->next=s;r=s;

}

r->next=NULL;

//倒数第k个就是正数第n-k+1个。

if（k<=n&&k>=1）

{

p=first->next;c=1;

while（p&&c<（n-k+1））{p=p->next;c++;}

if（p&&c==（n-k+1））{cout<date<

}

elsecout<<"notfind"<

}

return0;

}

9017:

统计选票

ProblemDescription

设有m个候选人n张选票，每张选票选且只选一人，候选人编号依次为1，2，3，...，m。

现将这n张选票存于一单链表中，要求统计并输出每个候选人的得票结果。

Input

有多组数据，每组第一行为候选人总数m和选票总数n（m>0，0

Output

输出每个候选人的得票结果，数字之间用一个空格隔开。

SampleInput

131221

33433211

SampleOutput

321

21410

//9017ANSWERCODE1

#include

usingnamespacestd;

intmain（）

{

intvotes[100],n,i,m,c;

while（cin>>m>>n）

{

for（i=1;i<=m;i++）votes[i]=0;

for（i=0;i

{cin>>c;

votes[c]++;}

for（i=1;i

cout<

}

return0;

}

第五次作业：

特殊线性表栈操作9045，9042，9041

9045:

判栈输出序列的有效性

ProblemDescription

设一个栈的输入序列为1,2,3,...,n-1,n。

请编写一个算法，判断一个序列p1,p2,p3,...,pn是否是一个有效的栈输出序列。

若有效输出1，无效输出0。

Input

有多组数据，每组第一行为序列长度n（n<=50），第二行为一个由1~n值组成的长度为n且值无重复的序列。

Output

栈输出序列有效输出1，无效输出0。

SampleInput

123

312

SampleOutput

//9045ANSWERCODE1

#include

usingnamespacestd;

intmain（）

{

intn,i,j,in,out;//in输入序列指针，out输出序列指针

intoutput[51],stack[51],top=-1;

while（cin>>n）{

for（i=0;i>output[i];

top=-1;in=0;

for（i=0;i

out=output[i];

if（out>in）{

for（j=in+1;j<=out;j++）stack[++top]=j;

in=out;

}

if（stack[top]==output[i]）top--;

else{cout<<"0\n";break;}

}

if（i==n&&top==-1）cout<<"1\n";

}

return0;

}

9042:

判操作序列有效性

ProblemDescription

假设以I和O分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。

请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。

Input

有多组数据，每组为由I和O组成的序列，序列长度不超过50。

Output

操作序列有效输出1，无效输出0。

SampleInput

IOIIOIOO

IOOIOIIO

SampleOutput

//9042ANSWERCODE1

#include

usingnamespacestd;

intmain（）

{

intn,i,flag;

charstr[51],stack[51],top=-1;

while（cin>>str）

{

n=strlen（str）;top=-1;flag=0;

for（i=0;i

{

if（str[i]=='I'）{stack[++top]=str[i];}

elseif（str[i]=='O'）

{

if（top>-1）top--;

else{cout<<"0\n";flag=1;break;}

}

else{cout<<"0\n";flag=1;break;}

}

if（top==-1&&i==n&&flag==0）{cout<<"1\n";}

else{if（flag==0）cout<<"0\

展开阅读全文