搜档网
当前位置:搜档网 › 计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)

计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)

计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)
计算机算法分析与设计(第四版)习题算法分析部分详解(实验1)

//算法实验1.1~1.5;任选一道实验、写实验报告,当堂1分;实验报告4分

//算法实现题1-1 统计数字问题

#include

#include

using namespace std;

int main()

{

int count[10];

int i,j,k,L;

int n,len,m;

while(scanf("%d",&n)!=EOF)

{

m=n;

L=ceil(log10(n+1));

for(i=0;i<10;i++)

count[i]=0;

for(j=0;j

{

len=ceil(log10(m+1));

k=m/pow(10.0,len-1); //从高位到低位取各个位数的值

for(i=0;i<10;i++) //小K*len的数数值0-9出现的次数

count[i]+=k*(len-1)*pow(10.0,len-2);//K*n*f(n-1)

for(i=0;i

count[i]+=pow(10.0,len-1); //在高位小于数值K的数出现的次数count[k]+=m-k*pow(10.0,len-1)+1; //在高位数值K的数出现的次数

m=m-k*pow(10.0,len-1);//去掉已计算的高位

}

for(i=0;i

count[0]-=pow(10.0,i);//分别考虑0在高位的情况有到少种for(i=0;i<10;i++)

printf("%d\n",count[i]);

}

return 0;

}

//算法实现题1-2 字典序问题

#include

#include

unsigned long dp[27][11], sum[17], ans; //本代码实现,字符串长度不超过10,可解

char str[11];

void main()

{

int i, j,k,len,start;

memset(dp, 0, sizeof(dp)); //为数组分配空间,并初始化为0

memset(sum, 0, sizeof(sum));

for(i = 1; i < 27; i++) dp[i][1] = 1;

for(j = 2; j <= 10; j++)

{

for(i = 27 - j; i >= 1; i--)//dp[i][j]以第i个字母开头的长度为j的单词个数

{

dp[i][j] += dp[i+1][j];

dp[i][j] += dp[i+1][j-1];

}

}

for(i = 1; i <= 10; i++) //长度为i是的总个数

{

for(j = 1; j <= 26; j++)

{

sum[i] += dp[j][i];

}

}

scanf("%s", str);

len=strlen(str);

for(i=1;i

start=1;

for(j=len;j>=1;j--)

{

for(i=start,k=1;k<=str[len-j]-('a'+start-1);k++,i++) //考虑打头为1~i-1长度为j的字符串个数

ans+=dp[i][j];

start=str[len-j]-'a'+2; //打头字符在字典序中下一个字符位置

}

for (i = 0; i < len - 1; i++)

{

if (str[i] >= str[i + 1]) ans = -1;

}

printf("%u\n", ans + 1); }

算法实现题1-3 最多约数问题

方法一:

#include

using namespace std;

bool *back;

int a,b;

int max=0,maxn;

void main(){

cin>>a>>b;

if (a>b) {

cout<<"a<=b:error"<

return;

}

back =new bool[b+1];

for(int i=a;i<=b;i++){

int count=0;

for(int j=0;j<=b;j++) back[j]=false;

for(int k=1;k<=(i/2+1);k++){

if (i%k==0) {

back[k]=true;

back[i/k]=true;

}

}

for(j=0;j<=i;j++) if (back[j]) {

count++;

}

if (count>max) {

max=count;

maxn=i;

}

}

cout<

}

方法二:

#include

using namespace std;

#define max Max

const long MAXP = 100000;

long prim[MAXP];

long max, numb, PCOUNT; //max存放最多约数个数,numb存放约数个数最多的数void primes(); //用筛选法产生质数存于prim数组中

void search(long from, long tot, long num, long low, long up);

int main()

{

primes();

long l, u;

cin >> l >> u;

if ((l == 1) && (u == 1))

{

max = 1;

numb = 1;

}

else

{

max = 2;

numb = l;

search(1, 1, 1, l, u);

}

cout << max << endl << numb << endl;

system("pause");

return 0;

}

void primes()

{

bool get[MAXP+1];

long i;

for (i = 2; i <= MAXP; i++)

get[i] = true;

for (i = 2; i <= MAXP; i++)

if (get[i])

{

long j = i + i;

while (j <= MAXP)

{

get[j] = false;

j += i;

}

}

long ii, j;

for (ii = 2, j = 0; ii <= MAXP; ii++)

if (get[ii]) prim[++j] = ii;

PCOUNT = j;

}

// 区间[low,up]上,tot为当前约数最多个数,num为约数个数最多的数,//from表示现在是第几个质数。

void search(long from, long tot, long num, long low, long up)

{

if (num >= 1)

if ( (tot > max) || ((tot == max) && (num < numb)) )

{

max = tot;

numb = num;

}

if ((low == up) && (low > num)) search(from, tot*2, num*low, 1, 1);

for (long i = from; i <=PCOUNT; i++)

{

if (prim[i] > up) return;

else

{

long j = prim[i], x = low - 1, y = up, n = num, t = tot, m = 1;

while (true)

{

m++;

t += tot;

x /= j;

y /= j;

if (x == y) break;

n *= j;

search(i+1, t, n, x+1, y);

}

m = 1 << m;

if (tot < max / m) return;

}

}

}

//算法实现题1-4 金币列阵问题

#include

#include

using namespace std;

const int size = 100;

int k,n,m,ccount,best;

int b0[size+1][size+1],b1[size+1][size+1],b[size+1][size+1]; bool found;

void print()

{

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= m; j++)

cout << b1[i][j] << " ";

cout << endl;

}

}

void trans1(int x) //行翻转

{

for(int i = 1; i <= m; i++)

b1[x][i] = b1[x][i]^1;

ccount++;

}

void trans2(int x, int y) //列交换

{

for(int i = 1; i <= n; i++)

swap(b1[i][x],b1[i][y]);

if (x != y) ccount++;

}

bool same(int x, int y)

{

for(int i = 1; i <= n; i++)

if (b0[i][x] != b1[i][y])

return false;

return true;

}

void acpy(int a[size+1][size+1], int b[size+1][size+1])

{

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

a[i][j] = b[i][j];

}

void answer()

{

int x,y,j,p;

cin >> k;

for(int i = 1; i <= k; i++)

{

cin >> n >> m;//n行m列

//原状态b0

for( x = 1; x <= n; x++)

for( y = 1; y <= m; y++)

cin >> b0[x][y];

//目标状态b1

for( x = 1; x <= n; x++)

for(int y = 1; y <= m; y++)

cin >> b1[x][y];

acpy(b,b1);//b1复制到b

best = m + n + 1;

for( j = 1; j <= m; j++)

{

acpy(b1,b);

ccount = 0;

trans2(1,j); //列变换

int p;

for( p = 1; p <= n; p++)

if (b0[p][1] != b1[p][1])

trans1(p); //行变换

for(p = 1; p <= m; p++) //找列相等的(b1的q列和b0的p列相等)

{

found = false;

for(int q = p; q <= m; q++)

if (same(p,q))

{

trans2(p,q);

found = true;

break;

}

if (!found) break;

}

if (found && ccount < best)

best = ccount;

}

if (best < m + n + 1)

cout << best << endl;

else

cout << -1 << endl;

}

}

int main() {

answer();

return 0; }

//算法实现题1-5 最大间隙问题

#include

using namespace std;

const int MAX=200001;

double num[MAX];

bool run()

{

int n;

if(scanf("%d",&n)==EOF) return false;//ctrl + z回车退出

int i;

double max=0.0,min=INT_MAX;//大值初始化为最小,小值初始化为最大for(i=0;i

{

scanf("%lf",&num[i]);

if(num[i]>max) max=num[i];

if(num[i]

}

int *cnt=new int[n];

double *low=new double[n];

double *high=new double[n];

for(i=0;i

{

cnt[i]=0;

low[i]=max;

high[i]=min;

}

double ave=(max-min)/(n-1);

for(i=0;i

{

int tmp=(int)((num[i]-min)/ave);

cnt[tmp]++;//增加桶元素

if(num[i]>high[tmp]) high[tmp]=num[i];//修改桶边界

if(num[i]

}

double t=high[0],res=0.0;

for(i=1;i

{

if(cnt[i]>0)//桶中有数字才进行检查,无数字跳过

{

double tmp=low[i]-t;

if(tmp>res) res=tmp;

t=high[i];

}

}

cout<

return true;

}

int main()

{

while(run());

return 0;

}

附:实验(设计)报告参考格式

设计一

多段图问题的动态规划算法与实现

班级学号姓名成绩

一、设计目的

1.掌握有向网的成本邻接矩阵表示法;

2.掌握多段图问题的动态规划递推算法;

3.进一步掌握动态规划法的基本思想和算法设计方法;

……

二、设计内容

1.任务描述

1)多段图问题简介

……

2)设计任务简介

设计求解多段图问题的动态规划算法,即设计和实现多段图问题的表示方案、动态规划递推算法,设计对算法或程序的测试方案并完成测试。

2.多段图问题的表示方案

本设计采用成本邻接矩阵表示多段图,针对多段图(可插入图例)描述成本邻接矩阵的规模与元素意义……

3.递推过程的抽象描述

本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解(抽象地)描述递推过程……

4.主要数据类型与变量

typedef NodeNumber int; /* 节点编号 */

typedef CostType int; /* 成本值类型 */

CostType cost[n][n]={…}; /* 成本邻接矩阵, n为顶点数 */

NodeNumber path[k]; /* k段图最短路径上的节点编号数组 */

NodeNumber cur= -1; /* 当前邻接节点 */

(必要时,可对数据类型和变量进一步解释或说明,增加可读性)

5.算法或程序模块

int FindForward(CostType *cost[n], NodeNumber i, NodeNumber cur)

功能: 根据邻接矩阵查找节点i的下一个前向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的前向邻接节点, 第一次调用时其值为-1.

int FindBackward(CostType *cost[n], NodeNumber i, NodeNumber cur)

功能: 根据邻接矩阵查找节点i的下一个后向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的后向邻接节点, 第一次调用时其值为-1.

(必要时,可对算法或程序模块进一步解释或说明,增加可读性)

三、测试

1.方案

描述测试方案、测试模块、测试数据实例(文字数据、图或表等形式)……

2.结果

结合测试数据实例描述测试过程和测试结果,最好给出表示测试过程和结果的抓图,对测试结果进行分析并得出结论。

四、总结与讨论

可针对本设计谈体会、谈改进、谈设想等,展示你的概括、归纳和创新思维能力,看重的不是你的对与错,而是鼓励你的想象和创新思维。

附:程序模块的源代码

算法分析与设计试卷

《算法分析与设计》试卷(A) (时间90分钟满分100分) 一、填空题(30分,每题2分)。 1.最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2.在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3.实现最大子段和利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4..广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5.衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6.Strassen矩阵乘法是利用( A)实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是( A )。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8.用动态规划算法解决最大字段和问题,其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题,最好用( B )算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略( B ) A.递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是( C )。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14.下面是贪心算法的基本要素的是( C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15.回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题(20分,每空1分)。 1.算法由若干条指令组成的又穷序列,且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法,用一个队列来存储结点的表叫活节点表。

计算机组成原理试题及答案

A .(7CD )16 B. ( 7D0)16 C. (7E0)16 D. 3. 下列数中最大的数是 _______ 。 A .(10011001) 2 B. (227) 8 C. (98)16 4. ____ 表示法主要用于表示浮点数中的阶码。 A. 原码 B. 补码 C. 反码 D. 移码 5. 在小型或微型计算机里,普遍采用的字符编码是 A. BCD 码 B. 16 进制 C. 格雷码 6. 下列有关运算器的描述中, ______ 是正确的 A. 只做算术运算,不做逻辑运算 B. C. 能暂时存放运算结果 D. 7. EPROM 是指 ____ 。 A. 读写存储器 B. C. 可编程的只读存储器 D. 8. Intel80486 是 32位微处理器, Pentium 是A.16 B.32 C.48 D.64 9 .设]X ]补=1.XXX 3X 4,当满足 _________ ■寸,X > -1/2 成立。 A. X 1必须为1,X 2X 3X 4至少有一个为1 B. X 1必须为1 , X 2X 3X 4任意 C. X 1必须为0, X 2X 3X 4至少有一个为1 D. X 1必须为0, X 2X 3X 4任意 10. CPU 主要包括 _____ 。 A.控制器 B. 控制器、运算器、cache C.运算器和主存 D.控制器、ALU 和主存 11. 信息只用一条传输线 ,且采用脉冲传输的方式称为 _________ 。 A. 串行传输 B. 并行传输 C. 并串行传输 D. 分时传输 12. 以下四种类型指令中,执行时间最长的是 _________ 。 A. RR 型 B. RS 型 C. SS 型 D. 程序控制指令 13. 下列 _____ 属于应用软件。 A. 操作系统 B. 编译系统 C. 连接程序 D. 文本处理 14. 在主存和CPU 之间增加cache 存储器的目的是 _____ 。 A. 增加内存容量 B. 提高内存可靠性 C.解决CPU 和主存之间的速度匹配问题 D. 增加内存容量,同时加快存取速 度 15. 某单片机的系统程序,不允许用户在执行时改变,则可以选用 ____________ 作为存储芯 片。 A. SRAM B. 闪速存储器 C. cache D. 辅助存储器 16. 设变址寄存器为X ,形式地址为D, (X )表示寄存器X 的内容,这种寻址方式的有 效地址为 ______ 。 A. EA=(X)+D B. EA=(X)+(D) C.EA=((X)+D) D. EA=((X)+(D)) 17. 在指令的地址字段中,直接指出操作数本身的寻址方式,称为 ___________ 。 A. 隐含寻址 B. 立即寻址 C. 寄存器寻址 D. 直接寻址 18. 下述 I/O 控制方式中,主要由程序实现的是 ________ 。 7F0)16 D. ( 152)10 o D. ASC H 码 只做加法 既做算术运算,又做逻辑运算 只读存储器 光擦除可编程的只读存储器 位微处理器。

算法分析与设计实验报告

算法设计与分析 学院:计算机科学与技术 学号:129074106 姓名:张淼淼 2014 11 14

1、 当问题规模100 N 时,快速排序和插入排序各需多少时间?写清机器配置,列出五种 快速排序所需时间(ms) 插入排序所需时间(ms ) 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu :Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics

程序: #include #include #include #include int a[1000000];

int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i=x&&i(j+1)) QuickSort(j+1,high); } void BinaryInsertSort(int length) { int low,high,mid; int i,j,m;//m为保存待插入的元素 for(i=1;i=b[mid]) low=mid+1; else high=mid-1; } for(j=i-1;j>=high+1;j--)//high为插入位置 b[j+1]=b[j];//后移元素,留出插入的空位b[high+1]=m;//将元素插入正确的位置 }

算法设计与分析试卷A及答案

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作; 高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高; 高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高; 把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。 2、 ①不能保证最后求得的解是最佳的;即多半是近似解。(少数问题除外) ②策略容易发现(关键:提取清楚问题中的维度), 而且运用简单,被广泛运用。 ③策略多样,结果也多样。 ④算法实现过程中,通常用到辅助算法:排序 3、解:① 因为:;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知: 1-10n n 2 2+是n ;的渐近表达式。 ② 因为:;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知: 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为:FBGDECA 。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 5x =6x =7x =

计算机组成原理试题及答案

二、填空题 1 字符信息是符号数据,属于处理(非数值)领域的问题,国际上采用的字符系统是七单位的(ASCII)码。P23 2 按IEEE754标准,一个32位浮点数由符号位S(1位)、阶码E(8位)、尾数M(23位)三个域组成。其中阶码E的值等于指数的真值(e)加上一个固定的偏移值(127)。P17 3 双端口存储器和多模块交叉存储器属于并行存储器结构,其中前者采用(空间)并行技术,后者采用(时间)并行技术。P86 4 衡量总线性能的重要指标是(总线带宽),它定义为总线本身所能达到的最高传输速率,单位是(MB/s)。P185 5 在计算机术语中,将ALU控制器和()存储器合在一起称为()。 6 数的真值变成机器码可采用原码表示法,反码表示法,(补码)表示法,(移码)表示法。P19-P21 7 广泛使用的(SRAM)和(DRAM)都是半导体随机读写存储器。前者的速度比后者快,但集成度不如后者高。P67 8 反映主存速度指标的三个术语是存取时间、(存储周期)和(存储器带宽)。P67 9 形成指令地址的方法称为指令寻址,通常是(顺序)寻址,遇到转移指令时(跳跃)寻址。P112 10 CPU从(主存中)取出一条指令并执行这条指令的时间和称为(指令周期)。 11 定点32位字长的字,采用2的补码形式表示时,一个字所能表示

的整数范围是(-2的31次方到2的31次方减1 )。P20 12 IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位,则它能表示的最大规格化正数为(+[1+(1-2 )]×2 )。 13 浮点加、减法运算的步骤是(0操作处理)、(比较阶码大小并完成对阶)、(尾数进行加或减运算)、(结果规格化并进行舍入处理)、(溢出处理)。P54 14 某计算机字长32位,其存储容量为64MB,若按字编址,它的存储系统的地址线至少需要(14)条。64×1024KB=2048KB(寻址范32围)=2048×8(化为字的形式)=214 15一个组相联映射的Cache,有128块,每组4块,主存共有16384块,每块64个字,则主存地址共(20)位,其中主存字块标记应为(9)位,组地址应为(5)位,Cache地址共(13)位。 16 CPU存取出一条指令并执行该指令的时间叫(指令周期),它通常包含若干个(CPU周期),而后者又包含若干个(时钟周期)。P131 17 计算机系统的层次结构从下至上可分为五级,即微程序设计级(或逻辑电路级)、一般机器级、操作系统级、(汇编语言)级、(高级语言)级。P13 18十进制数在计算机内有两种表示形式:(字符串)形式和(压缩的十进制数串)形式。前者主要用在非数值计算的应用领域,后者用于直接完成十进制数的算术运算。P19 19一个定点数由符号位和数值域两部分组成。按小数点位置不同,

计算机算法设计与分析

算法设计与分析 实 验 报 告 班级: 姓名: 学号: (备注:共给出5个参考实验案例,根据学号尾数做对应的实验,即如尾号为1,则模仿案例实验123;尾号2,则模仿案例实验234;尾号3,即345;尾号4,同1.)

目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法:起泡排序、选择排序、插入排序、shell排序,归并排序、快速排序等 (19) 2、实验小结 (18)

P art1:课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2:课程设计撰写的主要规范 1.题目分析:主要阐述学生对题目的分析结果,包括题目描述、 分析得出的有关模型、相关定义及假设; 2.总体设计:系统的基本组成部分,各部分所完成的功能及相互 关系; 3.数据结构设计:主要功能模块所需的数据结构,集中在逻辑设 计上; 4.算法设计:在数据结构基础上,完成算法设计; 5.物理实现:主要有数据结构的物理存储,算法的物理实现,系 统相关的实现。具体在重要结果的截图,测试案例的结果数据,核心算法的实现结果等; 6.结果分析:对第五步的分析,包括定性分析和定量分析,正确 性分析,功能结构分析,复杂性分析等; 7.结论:学生需对自己的课程设计进行总结,给出评价,并写出 设计体会; 8.附录:带有注释的源代码,系统使用说明等; 9.参考文献:列出在撰写过程中所需要用到的参考文献。

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14.广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.背包问题的贪心算法所需的计算时间为( B )。

5.《算法设计与分析》试题库

《算法分析与设计》试题库 (一) 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是(D ) A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上,并 D.动态规划算法

3. 动态规划算法的基本要素为(C) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质

D.预排序与递归调用 4. 算法分析中,记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有:(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题,一般具有的重要性质为:(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先

计算机组成原理练习题-答案

一、填空题 1.对存储器的要求是速度快,_容量大_____,_价位低_____。为了解决这方面的矛盾,计算机采用多级存储体系结构。 2.指令系统是表征一台计算机__性能__的重要因素,它的____格式__和___功能___不仅直接影响到机器的硬件结构而且也影响到系统软件。 3.CPU中至少有如下六类寄存器__指令____寄存器,__程序_计数器,_地址__寄存器,通用寄存器,状态条件寄存器,缓冲寄存器。 4.完成一条指令一般分为取指周期和执行周期,前者完成取指令和分析指令操作,后者完成执行指令操作。 5.常见的数据传送类指令的功能可实现寄存器和寄存器之间,或寄存器和存储器之间的数据传送。 6.微指令格式可分为垂直型和水平型两类,其中垂直型微指令用较长的微程序结构换取较短的微指令结构。 7.对于一条隐含寻址的算术运算指令,其指令字中不明确给出操作数的地址,其中一个操作数通常隐含在累加器中 8.设浮点数阶码为8位(含1位阶符),尾数为24位(含1位数符),则32位二进制补码浮点规格化数对应的十进制真值范围是:最大正数为 2^127(1-2^-23) ,最小正数为 2^-129 ,最大负数为 2^-128(-2^-1-2^-23) ,最小负数为 -2^127 。 9.某小数定点机,字长8位(含1位符号位),当机器数分别采用原码、补码和反码时,其对应的真值范围分别是 -127/128 ~+127/128 -1 ~+127/128 -127/128 ~+127/128 (均用十进制表示)。 10.在DMA方式中,CPU和DMA控制器通常采用三种方法来分时使用主存,它们是停止CPU访问主存、周期挪用和DMA和CPU交替访问主存。 11.设 n = 8 (不包括符号位),则原码一位乘需做 8 次移位和最多 8 次加法,补码Booth算法需做 8 次移位和最多 9 次加法。 12.设浮点数阶码为8位(含1位阶符),尾数为24位(含1位数符),则32位二进制补码浮点规格化数对应的十进制真值范围是:最大正数为,最小正数为,最大负数为,最小负数为。 13.一个总线传输周期包括申请分配阶段、寻址阶段、传输阶段和结束阶段四个阶段。 14.CPU采用同步控制方式时,控制器使用机器周期和节拍组成的多极时序系统。

计算机组成原理典型例题讲解

分析设计计算: 1.CPU结构如图1所示,其中有一个累加寄存器AC,一个状态条件寄存器,各部分之间的连线表示数据通路,箭头表示信息传送方向。 (1)标明图中四个寄存器的名称。 (2)简述指令从主存取到控制器的数据通路。 (3)简述数据在运算器和主存之间进行存/ 取访问的数据通路。 图1 解: (1)a为数据缓冲寄存器DR ,b为指令寄存器IR ,c为主存地址寄存器,d为程序计数器PC。 (2)主存M →缓冲寄存器DR →指令寄存器IR →操作控制器。 (3)存贮器读:M →缓冲寄存器DR →ALU →AC 存贮器写:AC →缓冲寄存器DR →M

2. 某机器中,配有一个ROM芯片,地址空间0000H—3FFFH。现在再用几个16K×8的芯片构成一个32K×8的RAM区域,使其地址空间为8000H—FFFFH。假设此RAM芯片有/CS和/WE信号控制端。CPU地址总线为A15—A0,数据总线为D7—D0,控制信号为R//W,MREQ(存储器请求),当且仅当MREQ 和R//W同时有效时,CPU才能对有存储器进行读(或写)。 (1)满足已知条件的存储器,画出地址码方案。 (2)画出此CPU与上述ROM芯片和RAM芯片的连接图。 解:存储器地址空间分布如图1所示,分三组,每组16K×8位。 由此可得存储器方案要点如下: (1)用两片16K*8 RAM芯片位进行串联连接,构成32K*8的RAM区域。片内地址:A0——A13,片选地址为:A14——A15; (2)译码使用2 :4 译码器; (3)用/MREQ 作为2 :4译码器使能控制端,该信号低电平(有效)时,译码器工作。 (4)CPU的R / /W信号与RAM的/WE端连接,当R // W = 1时存储器执行读操作,当R // W = 0时,存储器执行写操作。如图1 0000 3FFF 8000

《算法分析与设计》实验指导书

《计算机算法设计与分析》实验指导书(第一版)

前言 计算机算法分析与设计是面向设计的,它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习,使学生掌握计算机领域中许多常用的非数值的算法描述:分治法、贪心法、动态规划、回溯法、分枝限界等算法,并掌握算法分析的方法,从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学,即学生应该具备一门高级语言程序设计编程基础,学习基本的数据结构知识,还要求学生掌握较好的数学基础。 开发环境不限,本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告,包含实验问题、基本思想、关键算法流程图、测试数据及运行结果(截图)、调试心得和源程序。 总实验学时为16学时。

目录 预备实验验证算法的方法 (4) 实验目的: (4) 实验课时: (4) 实验原理: (4) 实验题目: (6) 基本题: (6) 提高题: (6) 实验一递归与分治 (7) 实验目的: (7) 实验课时: (7) 实验原理: (7) 实验题目: (7) 基本题: (7) 提高题: (8) 思考问题: (8) 实验二动态规划算法 (9) 实验目的: (9) 实验课时: (9) 实验原理: (9) 实验题目: (9) 基本题: (9) 提高题: (10) 思考问题: (10) 实验三贪心选择算法 (11) 实验目的: (11) 实验课时: (11) 实验原理: (11) 实验题目: (11) 基本题: (11) 提高题: (12) 思考问题: (12) 实验四回溯算法 (13) 实验目的: (13) 实验课时: (13) 实验原理: (13) 实验题目: (14) 基本题: (14) 提高题: (14) 思考问题: (14)

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1.D 2.B 3.C 4.D 5.D 6.D 7.C 8.D 9.B 10.C 11.D 12.B 13.D 14.C 15.C 16.D 17.D 18.D 19.D 20.C 1.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 2.根据执行算法的计算机指令体系结构,算法可以分为()。 A精确算法与近似算法B串行算法语并行算法 C稳定算法与不稳定算法D32位算法与64位算法 3.具有10个节点的完全二叉树的高度是()。 A6B5C3D 2 4.下列函数关系随着输入量增大增加最快的是()。 Alog2n B n2 C 2n D n! 5.下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6.Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7.4个盘子的汉诺塔,至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8.下列序列不是堆的是()。 A 99,85,98,77,80,60,82,40,22,10,66 B 99,98,85,82,80,77,66,60,40,22,10 C 10,22,40,60,66,77,80,82,85,98,99 D 99,85,40,77,80,60,66,98,82,10,22 9.Strassen矩阵乘法的算法复杂度为()。 AΘ(n3)BΘ(n2.807) CΘ(n2) DΘ(n) 10.集合A的幂集是()。 A.A中所有元素的集合 B. A的子集合 C. A 的所有子集合的集合 D. 空集 11.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 12.从排序过程是否完全在内存中显示,排序问题可以分为()。 A稳定排序与不稳定排序B内排序与外排序 C直接排序与间接排序D主排序与辅助排序 13.下列()不是衡量算法的标准。 A时间效率B空间效率 C问题难度D适应能力 14.对于根树,出度为零的节点为()。 A0节点B根节点C叶节点D分支节点 15.对完全二叉树自顶向下,从左向右给节点编号,节点编号为10的父节点编号为()。 A0B2C4D6 16.下列程序段的算法时间的复杂度为()。 for i ←0 to n do for j ←0 to m do

计算机组成原理试题

计算机组成原理试题(A) 教学中心名称考点成绩 专业、班级姓名学号 一、填空题(每空1分,共10分) 1.计算机中的信息可分为两类,它们是信息和信息。 2.第二代电子数字计算机所用的基本器件是。 3.设X=-9/16,[X]补= 。 4.运算器中的核心部件是。 5.浮点表示法中,阶码决定浮点数的,尾数决定浮点数的。 6.CPU中PC的主要功能是。 7.按照信息的传送格式,接口可分为和两大类。 二、选择题(每小题2分,共20分) 1. 某主存储器按字节编址,地址线数目为16,这个存储器的容量为 . A 16K×16位B.32K×8位、C.64K ×8位 2.采用DMA方式传送数据时,每传送一个数据就要占用的时间。 A一个指令周期B.一个存储周期C.一个机器周期 3. Cache是。 A.主存的一部分 B.为扩大存储容量而设置的 C.为提高存储系统的速度而设置的 4.操作控制器的功能是。 A产生操作控制信号,以解释并执行指令 B、产生时序信号C.对指令泽码 5.中断响应时,保存PC并更新PC的内容,主要是为了. A.提高处理机的速度 B.能进入中断处理程字并能正确返回原程序 C.便于编制中断处理程序 6.计算机辅助设计是指。 A.CAD B.CAI C.CAT 7.某机字长32位,内存容量为4MW,若按字节编址,其寻址范围为. A.0~4M B。0~16M C.0~32M 8.在磁盘存储器中,与转速无关的技术指标是。 A.存储密度B.平均等待时间C.数据传输率 9.设指令中的形式地址为以相对寻址时,操作数的有效地址E=. A.(D)B.(PC)+D C.(R)+D

10.计算机中,执行部件接控制部件的命令所作的不可再分的操作称为. A.微命令B.微操作C操作 三.判断改错题(每小题2分,共10分。正确,在括号内打√;错误,则打×并更正) 1.磁盘存储器是一种随机存取存储器。() 2.零地址指令就是没有操作数的指令。() 3.时序发生器是控制器的主要部件之一。() 4.设X=10110110,采奇校验时,其校验位C=1。() 5.中断处理过程中,保存现场必须在中断服务之后进行。() 四.简答题(每小题10分,共40分) 1.CPU由哪些主要部件组成?说明各部件的作用。 2.试述高速缓冲存储器的基本设计思想和特点。 3.主机与外部设备间为什么要设置接口? 4.为什么说取指令是公操作?在取指令阶段,CPU主要完成哪些操作? 五.计算题(共10 分) 1.设X=0.0101,Y=-0.1101,用双符号补码计算X+Y=?和X-Y=?并判断其结果是否溢出。(5分) 2. 设X=8C3E(H),Y=B6DF(H),Z=54D2(H)。求X∧Y⊕Z=? (5分) 七.设计题(10分) 某机字长16 位,主存按字编址,容量为8MW,请用如下RAM芯片为该机设计一个主存。 A A0 07 1.地址线和数据线各有多少根? 2.共用多少这种芯片? 3.画出其组成框图,并正确标出各信号线。

计算机算法设计与分析小论文

计算机算法设计与分析小论文 摘要: 算法是一个系列解决问题的清晰指令,即在有限时间内能够对一定规范的输入,能够得到所需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见一个算法的优劣是通过一定的准则来规定的。通过这学期的对《计算机算法分析设计》这门课程的学习让我们充分的了解到了计算机算法的多样性和复杂性,让我们更加细心和耐心的去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方案都是合理最优的!这时就是需要考虑透过一定的算法来得到自己的最优路线。所以可见算法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。目前我们将进行常见的算法分析设计策略介绍: 1.递归算法 1.1递归算法介绍: 直接或间接的调用自身的算法称为递归算法。或者说就是用自己来定义自己,不断调用自己的某一种状态。 1.2递归算法满足的条件 (1)递归满足2个条件: 1)有反复执行的过程(调用自身) 2)有跳出反复执行过程的条件(递归出口) 1.3递归例子 递归例子:阶乘问题 n! = n * (n-1) * (n-2) * ...* 1(n>0) //阶乘 intresult(int i) { int sum = 0; if (0 == i) return (1); else sum = i * result(i-1); return sum; }

可见一个递归算法都有一个比较特殊的特点,那就是要先处理一些比较特殊的情况再处理递归关系。如上例中如果是0!的话!那么他的阶乘就是1,所以先处理0!这个特殊情况,然后再调用其他的递归关系得到自己想要的阶乘。比如当我们想要求出4!的结果那么我们就需要调用result(3)的结果而result(3)又要调用result(2)的结果!就这样直到得出答案为止。 在我们日常,递归算法的出现可以帮助我们解决很多问题,正因为它的:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。 2.分治算法 2.1分治算法介绍: 一个分治算法把问题实例划分成若干子实例(多数情况是分成两个),并分别递归地解决每个子实例,然后把这些子实例的解组合起来,得到原问题实例的解。 2.2 分治算法的特性 1)规模小,则很容易解决 2)大问题可以分为若干规模小的相同问题 3)利用子问题的解可以合并成该问题的解 2.3分治算法的遇到问题 为了阐明这个方法,考虑这样一问题:在一个整数组A[1...n]中,同时寻找最大值和最小值。下面我们来看一下用分治策略:将数组分割成两半,A[1...n/2]和A[(n/2)+1...n],在每一半中找到最大值和最小值,并返回这两个最小值中的最小值及这两个最大值中的最大值。 过程 Min-Max ⅰ输入 n个整数元素的数组A[1...n]n为2的幂 ⅱ输出 (x,y), A中的最大元素和最小元素

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题: 1.算法重要特性是什么? 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么? 2.分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关? 3. 算法的时间复杂性与问题的规模相关,是问题大小n的函数。 4.算法的渐进时间复杂性的含义? 4.当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同? 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时,不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度: W(n) = max{ T(n,I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和: A(n) =∑P(I)T(n,I) I∈Dn 6.简述二分检索(折半查找)算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i:j] 和x,选取A[(i+j)/2]与x比较, 如果A[(i+j)/2]=x,则返回(i+j)/2,如果A[(i+j)/2]

计算机组成原理练习题答案

一、选择题 1、完整得计算机系统应包括运算器、存储器、控制器。 一个完整得计算系统应该就是:硬件系统与软件系统,硬件系统应该包括运算器,控制器,存储器,输入设备与输出设备,软件系统包括系统软件与应用软件、而您给得答案中B与D就是可以排除得,也就就是不能选,A与C两个中A得可能性最大,答案只能选A、 3、冯、诺依曼计算机工作方式得基本特点就是按地址访问并顺序执行指令. 4、移码表示法主要用于表示浮点数中得阶码。 5、动态RAM得刷新就是以行为单位得。 8、在定点运算器中产生溢出得原因就是运算得结果得超出了机器得表示范围。 10、在指令得地址字段中,直接指出操作数本身得寻址方式,称为立即寻址. 11、目前得计算机,从原理上讲指令与数据都以二进制形式存放. 13、计算机问世至今,新型机器不断推陈出新,不管怎样更新,依然保有“存储程序”得概念,最早提出这种概念得就是冯、诺依曼。 16、在CPU中,跟踪后继指令地址得寄存器就是程序计数器。 20、系统总线中地址总线得作用就是用于选择指定得存储单元或外设。 21、计算机中得主机包含运算器、控制器、存储器。 23、原码一位乘运算,乘积得符号位由两个操作数得符号进行异或运算. 24、对于真值“0”表示形式唯一得机器数就是移码与补码。 25、若[X]补=0、0100110,则[X]反= 0、0100110。--x为正数 26、在CPU中,存放当前执行指令得寄存器就是指令寄存器。 保存当前正在执行得指令得寄存器称为(指令寄存器)。 指示当前正在执行得指令地址得寄存器称为(程序计数器或指令计数器)。 27、下列编码中通常用作字符编码得就是ASCII码。 ASCII ASCII(American Standard CodeforInformationInterchange,美国信息互换标准代码)就是基于拉丁字母得一套电脑编码系统.它主要用于显示现代英语与其她西欧语言。它就是现今最通用得单字节编码系统,并等同于国际标准ISO/IEC646。28、在下列存储器中,半导体存储器可以作为主存储器. 30、在CPU中跟踪指令后继地址得寄存器就是PC。 31、EPROM就是指光擦除可编程得只读存储器。

算法分析与设计实验报告

实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法,并能独立在计算机上实现,同时并能够计算它们的时间复杂度,并用计算机来验证。 二、实验实习设备(环境)及要求(软硬件条件) 计算机eclipse软件,执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤,适当文字+代码+截图说明) 项目:对10 4 6 3 8 2 5 7进行从小到大排序,采用几种排序方法,并统计这几种方法的运行时间,与归并排序比较。 内容及步骤: (1)归并排序:将序列每次分成两组,再进行合并,直到递归完成; 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组

3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序:每次选择一个当前最小的并和当前的相对的第一个元素交换,直到最后 只有一个元素时结束;也可选择当前最大的并与当前的相对的最后一个 元素交换,直到最后只有一个元素时结束。

1、数组长度为n,需要选择n-1次;每次选择完成后,将数组中的最大值与最后一 个元素互换,调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序:从第二个元素开始,每次插入一个到当前有序序列中,使得有序,当 所有的元素插入完毕时,就排好序了; 1、从第二个元素开始,与之前序列比较,插入到合适的位置。

2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序:每次选择一个中间元素,并进行交换,使得中间元素的左边比它小,右 边比它大,然后对左右两边进行递归; 1、选取一个基准位,从右边向左边看,找比基准位小的元素,再从左边向右边看, 找比基准位大的元素,若两者均存在则交换;若两者相遇,则相遇元素与基准位元素交换,然后递归排序左右半数组。

《算法分析与设计》期末考试复习题纲(完整版)

《算法分析与设计》期末复习题 一、选择题 1.算法必须具备输入、输出和( D )等4个特性。 A.可行性和安全性 B.确定性和易读性 C.有穷性和安全性 D.有穷性和确定性 2.算法分析中,记号O表示( B ),记号Ω表示( A ) A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并 完成概算法的时间为t秒。现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题( B )解题方法:3*2^n*64=3*2^x A.n+8 B.n+6 C.n+7 D.n+5 4.设问题规模为N时,某递归算法的时间复杂度记为T(N),已知T(1)=1, T(N)=2T(N/2)+N/2,用O表示的时间复杂度为( C )。 A.O(logN) B.O(N) C.O(NlogN) D.O(N2logN) 5.直接或间接调用自身的算法称为( B )。 A.贪心算法 B.递归算法 C.迭代算法 D.回溯法 6.Fibonacci数列中,第4个和第11个数分别是( D )。 A.5,89 B.3,89 C.5,144 D.3,144 7.在有8个顶点的凸多边形的三角剖分中,恰有( B )。

A.6条弦和7个三角形 B.5条弦和6个三角形 C.6条弦和6个三角形 D.5条弦和5个三角形 8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。 A.重叠子问题 B.最优子结构性质 C.贪心选择性质 D.定义最优解 9.下列哪个问题不用贪心法求解( C )。 A.哈夫曼编码问题 B.单源最短路径问题 C.最大团问题 D.最小生成树问题 10.下列算法中通常以自底向上的方式求解最优解的是( B )。 A.备忘录法 B.动态规划法 C.贪心法 D.回溯法 11.下列算法中不能解决0/1背包问题的是( A )。 A.贪心法 B.动态规划 C.回溯法 D.分支限界法 12.下列哪个问题可以用贪心算法求解( D )。 A.LCS问题 B.批处理作业问题 C.0-1背包问题 D.哈夫曼编码问题 13.用回溯法求解最优装载问题时,若待选物品为m种,则该问题的解空间树的结点 个数为()。 A.m! B.2m+1 C.2m+1-1 D.2m 14.二分搜索算法是利用( A )实现的算法。 A.分治策略 B.动态规划法 C.贪心法 D.回溯法 15.下列不是动态规划算法基本步骤的是( B )。P44 A.找出最优解的性质 B.构造最优解 C.算出最优解(应该是最优值) D.定义最优解

相关主题