算法设计分析试题.docx
《算法设计分析试题.docx》由会员分享，可在线阅读，更多相关《算法设计分析试题.docx（12页珍藏版）》请在冰点文库上搜索。
算法设计分析试题
算法设计与分析试卷
一、填空题（20分，每空2分）
1.算法是指解决问题的方法和过程，严格意义讲，算法是包含下述性质的指令序列：
算法的性质包括输入、输出、确定性、有限性。
2.算法的复杂性包括时间复杂性（降阶，去系数，去低阶；如3n^2+10n该函数渐近阶表达式为n^2,10log3^n为log3^n）和空间复杂性（最坏空间占用）。
3.直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2.动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题，然后从这些子问题的解得到原问题的解。
5、最优二叉搜索树即是最小平均查找长度的二叉搜索树。
6、一个算法是对特定问题求解的一种描述，它是指令的有限序列。
7、二分搜索过程的算法行为可以用一颗二叉判定树来描述。
8、用贪心法求解背包问题时，为了使收益最大化要选择单位重量收益最大的物品装入背包。
9、使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法。
10、使用回溯法进行状态空间树裁剪分支时一般有两个标准：
约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型。
其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题
11.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法和分支限界法
12.动态规划算法的两个基本要素是最优子结构性质和重叠子问题
13.贪心选择是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
（贪心算法俩要素：
贪心选择性质和最优子结构）
14.回溯法有通用解题法之称，它是一个带有系统性又带有跳跃性的搜索算法。
二、选择题（10分）
1.最长公共子序列利用的算法是B
A、分治法B、动态规划法C、贪心法D、回溯法
2.实现合并排序利用的算法是（A）
A、分治法B、动态规划法C、贪心法D、回溯法
3.分治法的适用条件是（B）所解决的问题一般具有这些特征
A该问题的规模缩小到一定的程度就可以容易地解决
B该问题可以分解为若干个规模较小的相同问题
C利用该问题分解出的子问题的解可以合并为该问题的解
D该问题所分解出的各个子问题是相互独立的。
4.分支限界法在问题的解空间树中按（A）策略从根结点出发搜索解空间树。
A广度优先B.活结点优先C.扩展结点优先D.深度优先
5.分支限界法解旅行售货员问题时（A）活结点表的组织形式是
A、最小堆B、最大堆C、栈D、数组
6.回溯法解旅行售货员问题时的解空间树是（B）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树
7.以深度优先方式系统搜索问题解的算法称为（D）
A、分支界限算法B、概率算法C、贪心算法D、回溯法
三．简答题
1.递归的概念
答：
直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2.递归二要素
答：
边界条件（递归出口），递归方程。
4.二分搜索技术的前提及其基本思想。
二分搜索的前提是n个元素已经按从大到小的顺序排好。
5.分治法的设计思想，分治法所能解决的问题一般具有哪几个特征？
答：
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
基本思想是将一个n的为题分解为k个规模较小的子问题，这些子问题互相间相互独立且与原问题相同。
递归的解这些子问题，然后将各子问题的解合并得到原问题的解。
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
递归与分治应用范例：
二分搜索、期盼覆盖、合并排序、快速排序等。
5.设计动态规划算法的主要思想，基本要素及主要步骤？
请简述。
基本思想：
将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划的基本要素是：
最优子结构和重叠子问题。
（1）找出最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
动态规划设计范例：
矩阵连乘、最长公共子序列、背包问题、最优二叉搜索树等。
6.分治法与动态规划的区别
答：
分治法与动态规划法的相同点是：
将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点是：
适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
而用分治法求解的问题，经分解得到的子问题往往是互相独立的。
7.贪心算法
答：
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
有时得到的局部最优解是整体最优解。
8.贪心算法与动态规划间的区别
动态规划算法与贪心算法都要求问题具有最优子结构性质，这是二者的一个共同点。
下面通过两个经典的组合优化问题谈谈动态规划算法与贪心算法的主要差异。
例一：
０－１背包问题与背包问题。
０－１背包问题：
给定ｎ种物品和一个背包。
物品ｉ的重量是ｗｉ，其价值为ｖｉ，背包的容量为Ｃ。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大？
在选择装入背包的物品时，对每种物品ｉ只有两种选择：
即装入背包或不装入背包。
不能将物品ｉ放入背包多次，也不能只装入部分的物品ｉ。
背包问题：
与０－１背包问题类似，不同的是在选择物品ｉ装入背包时，可选择物品ｉ的一部分，而不一定要全部装入背包，１≤ｉ≤ｎ。
例二：
动态规划算法与贪心算法的主要差异０－１背包问题和背包问题这两类问题都具有最优子结构性质。
虽然它们极为相似，但背包问题可以用贪心算法求解，而０－１背包问题却不能用贪心算法求解。
用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值ｖｉ／ｗｉ，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过Ｃ，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直进行下去，直到背包装满为止
9.什么是最优装载
答：
有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。
最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
四．计算题
1．Hanoi塔问题
2.单源最短路径的求解。
问题的描述：
给定带权有向图（如下图所示）G=（V,E），其中每条边的权是非负实数。
另外，还给定V中的一个顶点，称为源。
现在要计算从源到所有其它各顶点的最短路长度。
这里路的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
解法：
现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。
请将此过程填入下表中。
3.矩阵连乘最优解结构。
P64，P66
4.0-1背包问题。
P93公式。
4.最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
确切地说，若给定序列X=，则另一序列Z＝.X的子序列是指存在一个严格递增的下标序列,使得对于所有j＝1，2,…，k有zj=xij,例如，序列Z＝是序列x＝。
最长公共子序列问题：
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。
用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。
其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。
故此时C[i][j]=0。
其它情况下，由最优子结构性质可建立递归关系如下：
在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。
五．程序设计
1.九九乘法表
#include
voidmain（）
{//正方形输出
inti,j;
for（i=1;i<=9;i++）
{for（j=1;j<=9;j++）
{printf（"%1d*%1d=%-2d",i,j,i*j）;}
printf（"\n"）;
}
printf（"\n"）;
//上三角输出
for（i=1;i<=9;i++）
{for（j=1;j<=i;j++）
printf（""）;
for（j=i;j<=9;j++）
{printf（"%1d*%1d=%-2d",i,j,i*j）;}
}
printf（"\n"）;
//下三角输出
for（i=1;i<=9;i++）
{for（j=1;j<=i;j++）
{printf（"%1d*%1d=%-2d",i,j,i*j）;}
printf（"\n"）;
}
}
2.斐波拉数列
#include
voidmain（）
{inti,n,f1,f2,f3;
f1=1;
f2=1;
printf（"请输入斐波拉数列长度n（n>=3）：
"）;
scanf（"%d",&n）;
printf（"%d%d",f1,f2）;
for（i=3;i<=n;i++）
{f3=f1+f2;
f1=f2;
f2=f3;
printf（"%d",f3）;
}
printf（"\n"）;
}
5.冒泡排序
#include
voidmain（）
//冒泡排序，对相邻两元素排序，每排序一遍，最大数被找出并放到最后一位，在对n-1个数进行排序。
{inti,j,t;
inta[10];
printf（"请输入10个数：
"）;
for（i=0;i<10;i++）
scanf（"%d",&a[i]）;//利用for循环进行一位数组的输入
for（j=0;j<10;j++）
{for（i=0;i<=10-j;i++）
{if（a[i]>a[i+1]）//if语句呀，没花括号会死的，if语句只会执行一个
{t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
}
for（i=0;i<10;i++）
printf（"%d",a[i]）;
}
6.选择排序
//选择排序选择法（按升序来说）：
将第一位和第二位比较，小者放在第一位，再将此时的第一位与第三位比较，仍然是小者放在第一位，如此重复，当第一位和最后一位比较完后第一位上存放的就是最小值了，再用相同的方法对第二位设置，第二位和最后一位比完后第二位上存放的就是次最小值了，然后第三位、第四位...都进行相同的操作，当倒数第二位也被比较完后，升序序列就排好了
#include
voidmain（）
{inti,j,t,a[10];
printf（"pleaseinputtennumbers:
"）;
for（i=0;i<10;i++）
scanf（"%d",&a[i]）;
for（i=0;i<9;i++）
for（j=i+1;j<10;j++）
{if（a[i]{t=a[j];a[j]=a[i];a[i]=t;
}
}
for（i=0;i<10;i++）
printf（"%d",a[i]）;
}
7.合并排序
#include
voidmain（）
{inta[3]={1,3,5},b[5]={2,4,6,8,10},c[8];
inti=0,j=0,k,m,l=0;
while（i<3&&j<5）
{if（a[i]{c[l]=a[i];
i++;l++;
}
else
{c[l]=b[j];j++;l++;
}
if（i>2）
{for（m=l;m<8&&j<5;m++,j++）
c[m]=b[j];
}
}
for（k=0;k<8;k++）printf（"%d",c[k]）;
}
8.二分搜索
#include
#defineN10
main（）
{intk,i;
inttable[N]={0,2,4,6,8,10,12,14,16,18};
intmid,left=0,right=N-1;
intfind=0;
printf（"inputyournumber:
"）;
scanf（"%d",&k）;
while（!
find&&left{
mid=（left+right）/2;
if（k==table[mid]）
find=1;
elseif（kright=mid-1;
elseleft=mid+1;
}
if（find==1）
printf（"%dintable[%d]\n",k,mid）;
else
printf（"can'tfindthenumber%d.\n",k）;
}
9.矩阵相乘
#include
voidmain（）
{
inta[1][2]={4,5},b[2][3]={4,5,8,7,2,4},c[1][3];
inti,j,k,s;
s=0;
for（i=0;i<1;i++）
for（j=0;j<3;j++）
for（k=0;k<2;k++）
{s+=a[i][k]*b[k][j];
c[i][j]=s;
}
for（i=0;i<1;i++）
{for（j=0;j<3;j++）
printf（"%d",c[i][j]）;
}
printf（"\n"）;
}
升级会员 