＝8xx，
当x
>40时，y＝[40×8＋（x－40）×10]×（1－10%）＝9x－72，∴y＝
此函数为分段函数，故用条件结构表达，条件为x>40，程序框图为：
8、相传古代印度国王舍罕要褒赏他聪明能干的宰相达依尔（国际象棋的发明者），问他需要什么，达依尔说：
“国王只要在国际象棋的棋盘第一格子上放一粒麦子，第二个格子上放两粒，第三个格子上放四粒，以后按此比例每一格加一倍，一直放到第64格（国际象棋8×8＝64格），我就感恩不尽，其他什么也不要了．”国王想：
“这有多少，还不容易！
”让人扛来一袋小麦，但不到一会儿就全用没了，再扛来一袋很快又没有了，结果全印度的粮食用完还不够，国王很奇怪．一个国际象棋棋盘能放多少粒小麦，试用程序框图表示其算法．
[分
析] 根据题目可知：
第一个格放1粒＝20，第二个格放2粒＝21，第三个格放4粒＝22，第
四个格放8粒＝23，…，第六十四格放263粒．
则此题就转化为求1＋21＋22＋23＋24＋…＋263的和的问题．我们可引入一个累加变量S，一个计数变量i，累加64次
就能算出一共有多少粒小麦．
[解析] 一个国际象棋棋盘一共能放1＋21＋22＋23＋24＋…＋263粒小麦．程序框图如图所示．
9、
（1）用辗转相除
法求840与1764的最大公约数．
（2）用更相减损术求459与357的最大公约数．
[解析]
（1）1746＝
840×2＋84840＝84×10＋0所以840与1764的最大公约数为84.
（2）459－
357＝102357－102＝255255－102＝153153－102＝51102－51＝51
所以459与357的最大公约数为51.
10、用秦九韶算法求多项式f（x）＝x6－5x5＋6x4＋x2x＋2当x＝－2时的值．
[解析] ∵f（x）＝x6－5x5＋6x4＋0·x3＋x2x＋2＝（（（（（x－5）x＋6）x＋0）x＋1）x＋0.3）x＋2
∴当x＝－2时，v0＝1v1＝－2－5＝－7v2＝－7×（－2）＋6＝20v3＝20×（－2）＋0＝－40
v4＝－40×（－2）＋1＝81v5v6＝－161.7×（
∴f（－2）＝325.4.
11、有甲、乙、丙三种溶液分别重147g,343g,133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，则每瓶最多装多少溶液？
[解析] 每个小瓶的溶液的质量应是三种溶液质量147,343,133的公约数，最大质量即是其最大公约数．
先求147与343的最大公约数：
343－147＝196，196－147＝49，147－49＝98.98－49＝49.
所以147与343的最大公约数是49.
再求49与133的最大公约数：
133－49＝84，84－39＝35，49－35＝14，35－14＝21，21－14＝7，
14－7＝7，所以49与133的最大公约数为7，所以147,343,133的最大公约数为7.即每瓶最多装7g溶液．
12、已知175（8）＝120＋r，求正整数r.
[解析] ∵175（8）＝1×82＋7×8
1＋5×80＝12
5，∴125＝120＋r.∴r＝5，即所求正整数r为5.
13、已知44（k）＝36，把67（k）转化为十进制数．
[解析] 由题意得36＝4×k1＋4×k0，则k＝8.故67（k）＝67（8）＝6×81＋7×80＝55.
14、把八进制数2011（8）化为五进制数．
[分析]
→
→
[解析] 2011（8）＝2×83＋0×82＋1×81＋1×80＝1024＋0＋8＋1＝1033.
∴2011（8）＝13113（5）．
[点评] 把一个非十进制数转化为另一个非十进制数，通常是把这个数先转化为十进制数，然后把十进制数再转化为另一个非十进制数．
15、若10y1
（2）＝x02（3），求数字x，y的值及与此两数等值的十进制数．
[分析] 由二进制及三进制可知，y∈{0,1}，x∈{1,2}，将二进制数和三进制数都转化为十进制数，再由两数相等
及x、y的取值范围可得出x、y的值．
[解析] ∵10y1
（2）＝x02（3），∴1×23＋0×22＋y×2＋1＝x×32＋0×3＋2，将上式整理得9x－2y＝7，
由进位制的性质知，x∈{1,2}，y∈{0,1}，当y＝0时，x＝
（舍），当y＝1时，x＝1.
∴x＝y＝1，已知数为102（3）＝1011
（2），与它们相等的十进制数为1×32＋0×3＋2＝11.
一、填空题（本题10分，每空1分）
1、算法的复杂性是的度量，是评价算法优劣的重要依据。
2、设n为正整数，利用大“O（·）”记号，将下列程序段的执行时间表示为n的函数，则下面程序段的时间复杂度为。
i=1;k=0;
while（i3、计算机的资源最重要的是和资源。
因而，算法的复杂性有和之分。
4、f（n）=6×2n+n2，f（n）的渐进性态f（n）=O（ ）
5、递归是指函数或者通过一些语句调用自身。
6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。
二、选择题（本题20分，每小题2分）
1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者（）。
A.求解目标不同,搜索方式相同B.求解目标不同,搜索方式也不同
C.求解目标相同,搜索方式不同D.求解目标相同,搜索方式也相同
2、回溯法在解空间树T上的搜索方式是（）。
A.深度优先C.最小耗费优先
3、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是（）。
A.回溯法
4、以下关于判定问题难易处理的叙述中正确的是（）。
5、设f（N）,g（N）是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f（N）≤Cg（N）,则称函数f（N）当N充分大时有上界g（N）,记作f（N）=O（g（N））,即f（N）的阶（）g（N）的阶。
A.不高于C.等价于
6、对于含有n个元素的子集树问题,最坏情况下其解空间的叶结点数目为（）。
A.n!
nn+1-1D.2n-1
7、程序可以不满足以下（）特征
A.输入B.输出C.确定性D.有限性
8、以下（）不能在线性时间完成排序
A.计数排序B.基数排序C.堆排序D.桶排序
9、以下（）不一定得到问题的最优解
A.贪心算法B.回溯算法C.分支限界法D.动态规划法
10、以下（）不包括在图灵机结构中
A.控制器B.读写磁头C.计算器D.磁带
三、简答题（本题20分，每小题5分）
1、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：
①每个选手必须与其他n-1名选手比赛各一次；
②每个选手一天至多只能赛一次；
③循环赛要在最短时间内完成。
（1）如果n=2k，循环赛最少需要进行几天；
（2）当n=22=4时，请画出循环赛日程表。
2、简述最优子结构性质。
3、简单描述回溯法基本思想。
4、何谓P、NP问题
四、算法填空（本题30分，每空2分）
1、Dijkstra算法是解单源最短路径问题的贪心算法。
请你阅读下面伪代码并在空白处填上适当的代码。
//G是一个n个结点的有向图，它由成本邻接矩阵w[u,v]表示，D[v]表示结点v到源结点s的最短路径长度，p[v]记录结点v的父结点。
Init-single-source（G,s）
1.foreachvertexv∈V[G]
2.do{d[v]=∞p[v]=NIL}
3.d[s]=0
Relax（u,v,w）
1.if1
2.then{d[v]=d[u]+w[u,v]
p[v]=u
}
dijkstra（G,w,s）
1.2
2.S=Φ
3.Q=V[G]
4.whileQ<>3
dou=min（Q）
S=S∪{u}
foreachvertexv∈adj[u]//所有u的邻接点v
do4
2、某工厂预计明年有N个新建项目，每个项目的投资额w[k]及其投资后的收益v[k]已知。
投资总额为C，问如何选择项目才能使总收益最大。
Invest-Program（）
{for（j=0;j<=C;j++）
5
for（j=w[n];j<=C;j++）
m[n][j]=v[n];
for（i=n-1;i>1;i--）
{intjMax=min（w[i]-1,c）;
for（j=0;j<=jMax;j++）
m[i][j]=6;
for（j=w[i];j<=C;j++）
m[i][j]=max（7）;
}
m[1][c]=m[2][c];
if（8）
m[1][c]=max（m[1][c],m[2][c-w[1]]+v[1]）;
}
3、N后问题
（1）用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。
（2）分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。
for（j=0;jif（9）/*安全检查*/
{A[i][j]=i+1;/*放皇后*/
10；
if（i==N-1）输出结果；
else11；;/*试探下一行*/
12；/*去皇后*/
13；;
}
4、通过键盘输入一个高精度的正整数n（n的有效位数≤240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。
delete（n,s）
{输入s,n;
while（s>0）
{14//从串首开始找
while（15）
i++;
delete（n,i）;//删除串n的第i个字符
s--;
}
while（length（n）>1）&&（n[1]=‘0’）
delete（n,1）;//删去串首可能产生的无用零
输出n;
}
五、请你阐述prim算法的基本思想。
并给出下图的最小生成树（要求画出生成树，分析过程可以省略）（本题10分）
六、算法分析题（本题10分）
数字全排列问题：
任意给出从1到N的N个连续的自然数的各种排列。
如N=3时，共有以下6种排列方式：
123，132，213，231，312，321。
算法描述如下。
画出N=3时递归调用时堆栈变化情况,写出相对应i,j的值。
设数组b的初始值为1，2，3。
perm（intb[],inti）
{intk,j;
if（i==N）
输出；
else
for（j=i;j<=num;j++）
{swap（b[i],b[j]）;
perm（b,i+1）;
swap（b[j],b[i]）;
}
}/*初始调用时i=1;*/
答案：
一、填空题（本题10分，每空1分）
1、算法效率
2、O（n）
3、时间、空间时间复杂度、空间复杂度
4、2n
5、直接间接
6、独立
二、选择题（本题20分，每小题2分）
1-5：
BABCA6-10：
BDCAC
三、简答题（本题20分，每小题5分）
1、
（1）2k-1天（2分）；
（2）当n=22=4时，循环赛日程表（3分）。
1
2
3
4
2
1
4
3
3
4
1
2
4
3
2
1
2、某个问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
3、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。
搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。
在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。
4、P（Polynomial问题）：
也即是多项式复杂程度的问题。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
四、算法填空（本题30分，每空2分）
1、
（1）d[v]>d[u]+w（u,v）
（2）Init-single-source（G,s）
（3）Φ
（4）Relax（u,v,w）
2、（5）m[n][j]=0;
（6）m[i+1][j]
（7）m[i+1][j],m[i+1][j-w[i]]+v[i]
（8）c>=w[1]
3、（9）!
M[j]&&!
L[i+j]&&!
R[i-j+N]
（10）M[j]=L[i+j]=R[i-j+N]=1;
（11）try（i+1,M,L,R,A）
（12）A[i][j]=0
（13）M[j]=L[i+j]=R[i-j+N]=0
4、（14）i=1;
（15）（i五、阐述prim算法的基本思想（本题10分）
（5分）prim算法的基本思想是：
设G=（V,E）是连通带权图，V={1,2,…,n}。
首先置U={1}，然后，只要U是V的真子集，就作如下的贪心选择：
选取满足条件i∈U，j∈V-U，且c[i][j]最小的边，将顶点j添加到U中。
这个过程一直进行到U=V时为止。
在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
（5分）最小生成树如下：
六、算法设计题（本题10分）
perm（intb[],inti）
{intk,j;
if（i==N）
输出b数组各元素值；
else
for（j=i;j<=N;j++）
{swap（b[i],b[j]）;
perm（b,i+1）;
（1）
（2）（3）（4）（5）（6）（7）（8）（9）
swap（b[j],b[i]）;
}
}/*初始调用时i=1;*/
升级会员 