二、填空
41、算法是由若干条指令组成的有穷序列,且要满足输入、输出、______和有限性。
答案：确定性
42、实现循环赛日程表利用的算法是______。
答案：递归算法
43、解0-1背包问题不需要排序的算法为______。
答案：动态规划算法
解析：解决0-1背包可以使用
44、贪心算法求解最小生成树问题的时间复杂度为O(______)。
答案：O(n*2^n)
45、回溯法搜索解空间树时，常用的两种剪枝函数为______和限界函数。
答案：分支函数
46、使用分支限界法搜索问题的解，通常采用广度优先和______优先的方法。
答案：深度
47、以下是二分搜索算法函数主要内容，请补齐代码。
int m; while (r >= 1){ m = ________; if (x == a[m]) _______; if (未作答) r = m-1; else l =______； } printf("%d不在数组中,最接近的元素是%d和%d\n",x,r, r+1); return -1; }
答案：
m=(l+r)/2 return m; m+1
解析：分治法二分搜索实现，不多赘述。
三、判断题
48、判断题
操作系统不是一个算法。
答案：√
解析：操作系统因其是死循环执行指令的，不满足算法的有限性。
49、判断题
算法的空间复杂度比时间复杂度更重要，需要优先考虑。
答案：×
解析：优先考虑时间复杂度
50、判断题
对正整数6进行整数划分的方法有12种。
答案：×
解析：对正整数6进行整数划分的方法有11种。
51、判断题
棋盘覆盖问题，可以使用分治法求解。
答案：√
解析：边长2^n的正方形棋盘完全覆盖所用的“L”型方块个数为（4的n次方-1）/3个
52、判断题
合并排序算法的时间复杂度比选择排序要高。
答案：×
解析：合并排序
53、判断题
凸多边形最优三角剖分问题是典型的动态规划算法求解问题。
答案：√
54、判断题
电路布线问题需要使用分支限界法求解。
答案：电路布线问题
55、判断题
活动安排问题的策略是每次都选和之前己选活动相容且结束时间最早的活动。
答案：√
56、判断题
贪心算法求解最单源最短路径问题可以使用Dijkstra算法。
答案：√
57、判断题
使用回溯法可以解决的问题，其解要满足多米诺性质，而分支限界法解决的问题，不需要满足这个性质。
答案：×
解析：在结点<x1,x2,…,xk>处P(x1,x2,…,xk)为真，即向量<x1,x2,…,xk>满足某个性质，则有：P(x1,x2,…,xk+1)-> P(x1,x2,…,xk)，0<k<n，称之为多米诺性质。
58、判断题
最大团问题可以使用回溯法或分支限界法求解。
答案：√
59、判断题
当n=4, m=3时，连续邮资问题的解为{1,4,6,7}，最大连续区间可以到21。
答案：×
解析：连续邮资问题的解为{1，4，7，8}。
60、判断题
回溯法求解0-1背包问题的时间复杂度为O(n*log n)。
答案：×
解析：回溯法解0-1背包的时间复杂度为O(2^n)。
61、判断题
根据重排原理,尽量选择根节点分支最多的树进行扩展求解。
答案：×
解析：重排原理：对于许多问题而言，在搜索试探时选取x[i]的值顺序是任意的。在其它条件相当的前提下，让可取值最少的x[i]优先。
62、判断题
用分支限界法求解单源最短路径问题问题活结点队列采用极小堆，求旅行售货员问题则为极大堆。
答案：×
解析：旅行售货员问题的活结点队列也是极小堆。
四、代码题
63、请补齐最优服务次序问题代码，假设n=10个顾客需要的服务时间已经按照递增的顺序存放在数组y中。
int main(int argc,char *argvI{ int i,n; double t; int x[]={56,12,1,99,1000,234,33,55,99,812]: int y[]={1,12,33,55,56,99,99,234,812,100o} ;int wait[10] ; n=10; …… return 0; }
答案：
for(i=0;i<n;i++) wait[i]=x[i]+x[i-1]; for(i=0;i<n;i++) t+=x[i]; t/=n;
64、请构建汉诺塔问题的hanoi函数。
int main(int argc,char *argv[]){ int n, a, b, c; printf("请输入要移动的盘子个数\n"); scanf ("%d",&n); printf(”请输入三个柱子的编号\n"); scanf("%d%d%d" , &a, &b,&c); printf("具体操作步骤为\n"): hanoi(n, a, b, c); return 0; } void Hanoi…
答案：
void Hanoi(int n,int a,int b,int c){ if(n>0){ hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,c,b,a); } }
五、主观题
65、快速排序
快速排序的基本思想是什么?
n个数进行快速排序的算法最差时间为多少?
现有未排序数据[49][38][65][97][76][13] [27]，写出经过快速排序每个步骤后这些元素的具体位置顺序(从小到大)
答案：
分解->递归求解->合并。
O(2^n)。
66、使用回溯法解旅行售货员问题（如图）,请写出所有的解空间（起点为1不写，且无需回到起点），并画出解空间树，计算最优值和最优解（包含起点1的回路)。
67、用分支限界法求0-1背包问题，应如何选择装入背包的物品，使得装入背包中物品的总价值最大？
其中件数n=4，容量C=10，重量w=(4,7,5,3)，价值v=(40,42,25, 12)(已排序)，使用优先队列式方法，写明什么作为优先扩展的依据，罗列结点扩展的顺序，画出扩展到叶节点的图，并求出最优解。
68、用动态规划求解最长公共子序列问题:
(1)给出计算最优值的递归方程
(2)给定两个序列X={B,C,D,A}，Y={A,B,C,B}，画图求出其最长公共子序列，要写出具体过程
