第1页 / 共84页
第2页 / 共84页
第3页 / 共84页
第4页 / 共84页
第5页 / 共84页
第6页 / 共84页
第7页 / 共84页
第8页 / 共84页
算法设计与分析课后习题答案（李春保）.pdf
1.1 第 1 章─概论
1.1.1 练习题
1. 下列关于算法的说法中正确的有（ ）。
Ⅰ.求解某一类问题的算法是唯一的
Ⅱ.算法必须在有限步操作之后停止
Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊
Ⅳ.算法执行后一定产生确定的结果
A. 1 个
2. T(n)表示当输入规模为 n 时的算法效率，以下算法效率最优的是（ ）。
A.T(n)= T(n-1)+1，T(1)=1
C.T(n)= T(n/2)+1，T(1)=1
3. 什么是算法？算法有哪些特征？
4. 判断一个大于 2 的正整数 n 是否为素数的方法有多种，给出两种算法，说明其中
B.T(n)= 2n2
D.T(n)=3nlog2n
D.4 个
C.3 个
B.2 个
一种算法更好的理由。
5. 证明以下关系成立：
（1）10n2-2n=(n2)
（2）2n+1=(2n)
6. 证明 O(f(n))+O(g(n))=O(max{f(n)，g(n)}) 。
7. 有一个含 n（n>2）个整数的数组 a，判断其中是否存在出现次数超过所有元素一
半的元素。
8. 一个字符串采用 string 对象存储，设计一个算法判断该字符串是否为回文。
9. 有一个整数序列，设计一个算法判断其中是否存在两个元素和恰好等于给定的整
数 k。
10. 有两个整数序列，每个整数序列中所有元素均不相同。设计一个算法求它们的公
共元素，要求不使用 STL 的集合算法。
11.
正整数 n（n>1）可以写成质数的乘积形式，称为整数的质因数分解。例如，
12=2*2*3，18=2*3*3，11=11。设计一个算法求 n 这样分解后各个质因数出现的次数，采
用 vector 向量存放结果。
12. 有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个
数。如序列 4、1、2、3 的相差最小的元素对的个数是 3，其元素对是（1，2），（2，3），
（3，4）。
13. 有一个 map容器，其中已经存放了较多元素。设计一个算法求出其
中重复的 value 并且返回重复 value 的个数。
14. 重新做第 10 题，采用 map 容器存放最终结果。
15. 假设有一个含 n（n>1）个元素的 stack栈容器 st，设计一个算法出栈从栈顶
到栈底的第 k（1≤k≤n）个元素，其他栈元素不变。
算法设计
1.1.2 练习题参考答案
1. 答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一
类问题的算法不一定是唯一的。答案为 C。
2. 答：选项 A 的时间复杂度为 O(n)。选项 B 的时间复杂度为 O(n2)。选项 C 的时间
复杂度为 O(log2n)。选项 D 的时间复杂度为 O(nlog2n)。答案为 C。
3. 答：算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输
入性和输出性 5 个重要特征。
//方法 1
for (int i=2;i
#include
bool isPrime1(int n)
{
}
bool isPrime2(int n)
{
}
void main()
{
}
方法 1 的时间复杂度为 O(n)，方法 2 的时间复杂度为 ，所以方法 2 更好。
5. 答：（1）当 n 足够大时，(10n2-2n)/( n2)=10，所以 10n2-2n=(n2)。
（2）2n+1=2*2n=(2n)。
6. 证明：对于任意 f1(n)∈O(f(n)) ，存在正常数 c1 和正常数 n1，使得对所有 n≥n1，
for (int i=2;i<=(int)sqrt(n);i++)
return true;
int n=5;
printf("%d,%d\n",isPrime1(n),isPrime2(n));
if (n%i==0)
return false;
n
有 f1(n)≤c1f(n) 。
类似地，对于任意 g1(n)∈O(g(n)) ，存在正常数 c2 和自然数 n2，使得对所有 n≥n2，
有 g1(n)≤c2g(n) 。
令 c3=max{c1，c2}，n3=max{n1，n2}，h(n)= max{f(n)，g(n)} 。
则对所有的 n≥n3，有：
f1(n) +g1(n)≤c1f(n) + c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))
≤c32max{f(n)，g(n)}=2c3h(n)=O(max{f(n)，g(n)})。
7. 解：先将 a 中元素递增排序，再求出现次数最多的次数 maxnum，最后判断是否满
足条件。对应的程序如下：
#include
#include
using namespace std;
2
第 1 章 概论
//递增排序
//出现次数最多的次数
e=a[i];
num=1;
num++;
if (num>maxnum)
{
maxnum=num;
x=e;
}
if (a[i]==e)
{
}
else
{
}
sort(a,a+n);
int maxnum=0;
int num=1;
int e=a[0];
for (int i=1;in/2)
else
bool solve(int a[],int n,int &x)
{
}
void main()
{
}
上述程序的执行结果如图 1.1 所示。
int a[]={2,2,2,4,5,6,2};
int n=sizeof(a)/sizeof(a[0]);
int x;
if (solve(a,n,x))
else
return true;
return false;
printf("出现次数超过所有元素一半的元素为%d\n",x);
printf("不存在出现次数超过所有元素一半的元素\n");
图 1.1 程序执行结果
8. 解：采用前后字符判断方法，对应的程序如下：
#include
#include
using namespace std;
bool solve(string str)
{
int i=0,j=str.length()-1;
while (i
算法设计
i++; j--;
}
return true;
}
void main()
{
}
上述程序的执行结果如图 1.2 所示。
cout << "求解结果" << endl;
string str="abcd";
cout << " " << str << (solve(str)?"是回文":"不是回文") << endl;
string str1="abba";
cout << " " << str1 << (solve(str1)?"是回文":"不是回文") << endl;
图 1.2 程序执行结果
//递增排序
i++;
j--;
//区间中存在两个或者以上元素
if (a[i]+a[j]==k)
return true;
else if (a[i]+a[j]
#include
using namespace std;
bool solve(int a[],int n,int k)
{
}
void main()
{
int a[]={1,2,4,5,3};
int n=sizeof(a)/sizeof(a[0]);
printf("求解结果\n");
int k=9,i,j;
if (solve(a,n,k,i,j))
else
int k1=10;
if (solve(a,n,k1,i,j))
printf(" 存在: %d+%d=%d\n",a[i],a[j],k1);
printf(" 存在: %d+%d=%d\n",a[i],a[j],k);
printf(" 不存在两个元素和为%d\n",k);
4
第 1 章 概论
printf(" 不存在两个元素和为%d\n",k1);
else
}
上述程序的执行结果如图 1.3 所示。
图 1.3 程序执行结果
10. 解：采用集合 set存储整数序列，集合中元素默认是递增排序的，再采用二
路归并算法求它们的交集。对应的程序如下：
++it2;
//输出集合的元素
++it1;
s3.insert(*it1);
++it1; ++it2;
if (*it1==*it2)
{
}
else if (*it1<*it2)
else
set::iterator it1,it2;
it1=s1.begin(); it2=s2.begin();
while (it1!=s1.end() && it2!=s2.end())
{
}
#include
#include
using namespace std;
void solve(set s1,set s2,set &s3) //求交集 s3
{
}
void dispset(set s)
{
}
void main()
{
int a[]={3,2,4,8};
int n=sizeof(a)/sizeof(a[0]);
set s1(a,a+n);
int b[]={1,2,4,5,3};
int m=sizeof(b)/sizeof(b[0]);
set s2(b,b+m);
set s3;
solve(s1,s2,s3);
printf("求解结果\n");
printf(" s1: "); dispset(s1);
set::iterator it;
for (it=s.begin();it!=s.end();++it)
printf("\n");
printf("%d ",*it);
5
算法设计
printf(" s2: "); dispset(s2);
printf(" s3: "); dispset(s3);
}
上述程序的执行结果如图 1.4 所示。
图 1.4 程序执行结果
11. 解：对于正整数 n，从 i=2 开始查找其质因数，ic 记录质因数 i 出现的次数，当找
到这样质因数后，将（i，ic）作为一个元素插入到 vector 容器 v 中。最后输出 v。对应的
算法如下：
int p;
int pc;
//vector 向量元素类型
//质因数
//质因数出现次数
#include
#include
using namespace std;
struct NodeType
{
};
void solve(int n,vector &v) //求 n 的质因数分解
{
}
void disp(vector &v)
{
}
int i=2;
int ic=0;
NodeType e;
do
{
} while (n>1 || ic!=0);
vector::iterator it;
for (it=v.begin();it!=v.end();++it)
ic++;
n=n/i;
if (n%i==0)
{
}
else
{
}
if (ic>0)
{
}
ic=0;
i++;
e.p=i;
e.pc=ic;
v.push_back(e);
printf(" 质因数%d 出现%d 次\n",it->p,it->pc);
//输出 v
6
第 1 章 概论
vector v;
int n=100;
printf("n=%d\n",n);
solve(n,v);
disp(v);
void main()
{
}
上述程序的执行结果如图 1.5 所示。
图 1.5 程序执行结果
12. 解：先递增排序，再求相邻元素差，比较求最小元素差，累计最小元素差的个
//求 myv 中相差最小的元素对的个数
//递增排序
sort(myv.begin(),myv.end());
int ans=1;
int mindif=myv[1]-myv[0];
for (int i=2;i
#include
#include
using namespace std;
int solve(vector &myv)
{
}
void main()
{
}
上述程序的执行结果如图 1.6 所示。
ans++;
ans=1;
mindif=myv[i]-myv[i-1];
if (myv[i]-myv[i-1] myv(a,a+n);
cout << "相差最小的元素对的个数: " << solve(myv) << endl;
7
算法设计
图 1.6 程序执行结果
13. 解：对于 map容器 mymap，设计另外一个 map容器 tmap，
将前者的 value 作为后者的关键字。遍历 mymap，累计 tmap 中相同关键字的次数。一个
参考程序及其输出结果如下：
#include
#include
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
