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

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 #includeiostream 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; cinn; while(n--) { cinabcd; if(a0||b0||c0||d0||a=c||b=d) coutdata errorendl; else { rect r(a,b,c,d); coutr.area()endl;} } return 0; } 9002:数组的循环移位 ?Problem Description 对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。 ?Input 输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。 ?Output 循环左移后的字符型数组内容。 ?Sample Input 1 abcdefgh 3 ?Sample Output defghabc //9002ANSWER CODE1 #includeiostream using namespace std; #define N 20 void Reverse(char a[],int from,int to) { int i,j;char t;i=from;j=to; while(ij) {t=a[i];a[i]=a[j];a[j]=t;i++;j--;} } void Converse(