数据结构作业_数据结构作业全
数据结构作业由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构作业全”。
1.(1)问题的描述：设计一个程序exp1-1.cpp,输出所有小于等于n(n为一个大于二的正整数)的素数。要求：（1）每行输出10个素数;(2)尽可能采用较优的算法。
(2)解决思想：判断一个整数n是否为素数，只需要用2~n-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。其实可以简化，n不被被2~n-1之间的每一个整数去除，只需被2~根号n之间的每个数去除就可以了。因为如果n能被2~n-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子(3)源代码：
#include #include using namespace std;int main(){ int n,flag;int count=0;cout
cin>>n;if(n
cout
else
for(int i=2;i
{
flag=0;
for(int j=2;j
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)
{
cout
count++;
if(count%10==0)
cout
}
}
cout
} return 0;(4)运行结果截图
(5)心得体会:按照素数定义来判断素数时，可以进行一个较为明显的优化，即只需从2枚举到根n即可。
2.(1)问题的描述：编写一个程序exp1-2.cpp,计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。
(2)解决思想:采用递归的算法，对输入的正整数进行不断的取模运算和取商运算，即可得到该正整数的各位数字之和。时间复杂度为O(1)(3)源代码
exp1-2.cpp
#include using namespace std;int fun(int n){ if(n
return 0;} else
return n%10 + fun(n/10);} int main(){
int n;
cout
cin>>n;
cout
(5)心得体会：当遇到一个复杂问题时，可以从最简单的地方着手，刚开始不知道n是几位数，感觉这个问题有点棘手，心想如果是二位数就好办了，因此脑海中浮现了“递归”的思想，把一个复杂问题转变成简单问题。即把一个正整数n边分解边累加，直到分解完毕。
3.(1)问题的描述：编写一个程序exp1-3.cpp,判断一个字符串是否为“回文”(顺读和倒读都一样的字符串称为“回文”)，并分析算法的时间复杂度。
(2)解决思想：依次将字符串两端的字符进行比较，若都相同，则为回文字符串。时间复杂度为O(n)。(3)源代码：
exp1-3.cpp #include #include using namespace std;#define MAX 1000
int fun(char s[]){ int flag=1;int i,j,n=strlen(s);
for(i=0,j=n-1;i
if(s[i]!=s[j])
{
flag=0;
break;
} return(flag);} int main(){ char s[MAX];cout>s;if(fun(s)==1)
cout
cout
(5)心得体会：如果将这题进行扩展，判断一个正整数是否为回文数，也可以采用类似的算法。将正整数的各位存到数组里，用i从左到右扫描s，用j从右到左扫描s,若s[i]与s[j]不相等，则退出循环，否则继续比较，直到i
