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

}

int output[51],stack[51],top=-1; while(cin>>n) { for(i=0;i>output[i]; top=-1;in=0; for(i=0;iin){ for(j=in+1;j<=out;j++) stack[++top]=j; in=out; } if(stack[top]==output[i]) top--; else{cout<<\ } if(i==n && top==-1 ) cout<<\ }

return 0;

9042:判操作序列有效性

Problem Description

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。

Input

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

Output

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

Sample Input

IOIIOIOO IOOIOIIO

Sample Output

1 0

//9042ANSWER CODE1 #include using namespace std; int main() { int n,i,flag; char str[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];} else if(str[i]=='O') { if(top>-1) top--; else{cout<<\ } else{cout<<\ } if(top==-1 && i==n && flag==0){cout<<\ else{if(flag==0) cout<<\} return 0;

9041:判括号匹配

Problem Description

任意输入一个由若干个圆括号、方括号和花括号组成的字符串，设计一个算法判断该串中的括号是否配对。

Input

有多组数据，每组为一个包含3类括号的字符串，串长不超过100。

Output

若该串中的括号匹配输出1，否则输出0。

Sample Input

([{}]) ([{}}) ([{)]}

Sample Output

1 0 0

//9041ANSWER CODE1 #include using namespace std; int main() { int i,len,flag; char str[100],stack[100],top=-1; while(cin>>str) { len=strlen(str);flag=0;top=-1; for(i=0;i

else if((str[i]==')') && (stack[top]=='(') || (str[i]==']') && (stack[top]=='[') || (str[i]=='}') && (stack[top]=='{')){top--;} else{cout<<\ } if(top==-1 && i==len && flag==0){cout<<\ else {if(flag==0)cout<<\ } return 0; }

第六次作业：特殊线性表队列操作9038，9040

9038:循环队列的操作 Problem Description

现有一长度为n的整数序列和一最大容量为m的循环队列（用长为m+1的一维数组实现），要求将该序列中的偶数存入循环队列中；当循环队列满时，将循环队列中的所有元素全部出队，并按存入的先后顺序在同一行内依次输出，即每行输出m个元素，每个元素后输出一个空格。 Input

有多组数据，每组第一行为整数序列的个数n和循环队列的最大容量m（m<=n<=100，0

有多行数据，先输出对应行号，每行输出m个元素，均为偶数，每个元素后输出一个空格。 Sample Input 10 4

9 10 2 7 16 8 12 4 3 1 10 3

9 10 2 7 16 8 12 1 3 4 Sample Output

1:10 2 16 8 1:10 2 16 2:8 12 4

//9038ANSWER CODE1 #include using namespace std; int main() { int i,j,c,l,n,m,A[101],Queue[101],front,rear; while(cin>>n>>m) { for(i=0;i>A[i]; front=rear=0;c=0;l=0; for(i=0;i

}

} }

return 0;

rear=(rear+1)%(m+1); Queue[rear]=A[i]; }

if(c==m) { cout<<++l<<\ for(j=front+1;j<=rear;j++) cout<

9040:火车车厢重排

Problem Description

一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同。这样，在每个车站只需卸掉最后一节车厢。因此，对于给定的任意次序车厢，必须进行重新排列，使其符合要求。车厢重排工作可通过转轨站完成，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式工作，现要求设计算法解决火车车厢重排问题。 Input

有多组数据，每组第一行为车厢节数n和缓冲轨数目k（2<=k<=5，k<=n<=10），第二行为初始给定的车厢编号次序序列。 Output

若给定的车厢编号次序序列可重排，则输出1；否则输出0。 Sample Input 9 3

3 6 9 2 4 7 1 8 5 9 3

3 6 9 2 4 7 5 8 1 Sample Output

1 0

//9040ANSWER CODE1 #include #include

using namespace std; int main(){ int n,k,carNum[11],i,j,rearrange; while(cin>>n>>k) { for(i=0;i>carNum[i]; queue Q[5];rearrange=1;

for(i=0;iQ[j].back()) {Q[j].push(carNum[i]);break;} } if(j==k) {rearrange=0;break;} } cout<

return 0;

}

第七次作业：二叉树的顺序存储9050

9050:顺序存储的前序遍历

Problem Description

给你一个采用顺序存储结构的二叉树，请你设计一个算法求出它的前序遍历。 Input

输入数据有多组，每组的第一行为一个正数n,表示该二叉树的节点个数。

接下来有n个字符，表示各个位置上的元素，当字符为'#'时表示当前节点为空。 Output

输出该二叉树的前序遍历 Sample Input 6

ABCDEF 6

ABC#DE Sample Output

ABDECF ABDCE

//9050ANSWER CODE1 #include using namespace std; int main() { int n,i,top,S[100];char ch[100]; while(cin>>n) { cin>>ch; if(ch[0]=='#') continue; top=-1;i=0; while(top!=-1 || i