2013级DS作业和实验参考答案总汇(1)

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

第一次作业：复习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 第二次实验：顺序表2 9097 第三次实验：单链表 9007 第四次实验：循环链表9008 第五次实验：递归 9039

第六次实验：二叉树的建立及遍历9019 第七次实验：二叉树的结点9054，9056 第八次实验：二叉树的存储转换9049 第九次实验：哈夫曼编码9068

第十次实验：图的邻接表及度9071，9079

第十一次实验：图的存储转换9089，9084，9083 第十二次实验：模拟考试 ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 第一次作业：复习C++9000，9002

9000:矩形面积 Problem Description

声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Input

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

若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 Sample Input 2 2 2 4 4 1 2 3 4

Sample Output

4 4

//9000ANSWER CODE1 #include using namespace std; class rect{ public: rect(int a,int b,int c,int d); ~rect() {} int area(); private: int x1,y1,x2,y2; };

rect::rect(int a,int b,int c,int d){ x1=a;y1=b;x2=c;y2=d;} int rect::area(){return (x2-x1)*(y2-y1);} int main(){

int a,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<<\ else

{ rect r(a,b,c,d); cout<

return 0; }

9002:数组的循环移位

Problem Description

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

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

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

abcdefgh 3

Sample Output

defghabc

//9002ANSWER CODE1 #include using namespace std; #define N 20

void Reverse(char a[],int from,int to) { int i,j;char t;i=from;j=to; while(i

void Converse(char a[],int n,int i) { Reverse(a,0,i-1);Reverse(a,i,n-1);Reverse(a,0,n-1);} int main() { char a[N];int m,n,i;cin>>m; while(m--){ cin>>a>>i; n=strlen(a);i=i%n; Converse(a,n,i); cout<

return 0;

}

第二次作业：顺序表插入和删除操作9003，9004

9003:合并顺序表 Problem Description

假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“not enough”。 Input

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

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

1 3 8 17 3

6 10 15

Sample Output 7

1 3 6 8 10 15 17

//9003ANSWER CODE1 #include using namespace std;

const int MaxSize=20;//有两个由小到大有序的有序顺序表A和B void combine(int A[],int A_len,int B[],int B_len) { if((A_len+B_len)>MaxSize) cout<<\ else { int i=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<

void main(){ int A[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:连续删除

Problem Description

从由小到大有序的顺序表中删除其值在[s, t]之间（含s和t）的所有元素，且不改变顺序表的有序性。如果s>=t则显示“data error”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。 Input

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

对于每组数据，如果s>=t，则直接输出“data error”，否则输出两行信息：第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。

Sample Input 1 8 18 7

1 3 5 10 17 19 25 Sample Output

5

1 3 5 19 25

//9004ANSWER CODE1 #include using namespace std; int main() { int n,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<<\ s_i=0;t_i=len-1; while(A[s_i]t && t_i>=0) t_i--; if(s_i<=t_i) { span=t_i-s_i+1; for(j=s_i;j第三次作业：顺序表查找操作和单链表建立9012，9006

9012:找唯一数 Problem Description

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

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