c语言背包问题_背包问题贪心算法_背包问题 贪心算法(6)

∴ T(n)= O(log n) (2分)

2．（15分）请用回溯法设计算法，用四种颜色给地图着色（若在调用了其它算法，也需将该算法写出）。请在每个循环语句和条件判断语句后加注释。

答：（此题解法不唯一）

算法：

boolColor::Ok(int k)

{ for (int j=1; j<k; j++) //检查前k-1个点与当前点（第k点）颜色是否冲突 (2分)

if ((a[k][j]==1)&&(x[j]==x[k]))

//判断第j点与当前点（第k点）颜色是否冲突 (2分)

return false; (1分)

else return true; (1分)

}

void Color::Backtrack(int t)

{ if (t > n) // 判断是否到叶节点 (1分)

{ sum++;

for (int i=1;i<=n; i++) //输出每个点的色号

cout << x[i]<< ’ ’ ;

cout << endl; （2分）

}

else

for (int i=1; i<=4; i++) // 依次检查当前点（第t点）是否可着第i(1≤i≤4)种颜色 (2分)

{ x[t]=i; (1分)

if (Ok(t)) Backtrack(t+1); //若当前点（第t点）可着第i种颜色，则递归调用 (3分)

}

}

3．（10分）请设计一个算法，实现优先队列的出队操作。要求：

（1）指出用什么数据结构实现优先队列；

（2）用C语言描述算法。

答：（此题解法不唯一）

（1）用堆实现优先队列。 （2分）

（2）算法

SIFT(k,i,m)

{temp = k[i];

j=2*i; (1分)

while (j<=m) (1分)

{ if（（j<m）&&（R[j].key<R[j+1].key））j++; (1分)

if （temp.key <R[j].key） (1分)

{ R[i] = R[j];

i=j; j=2*i； （1分）

}

else break; (0.5分)

R[i]=temp; (0.5分)

}

Delete（n）

{ temp = R[1]; R[1]=R[i]; R[i]=temp; (1分)

SIFT(k,1,n-1); （1分）

}

算法导论试题

题型：选择+解答

一，选择

（1） 动态规划的设计思想是a

(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左

（2） 贪心算法的设计思想是b

(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左

（3） 以下哪一个更可能描述实际一个有效的算法d

(a) (b) (c) (d)

（4） 蝶形操作的设计思想是a

(a)分治法 (b)贪心算法 (c)动态规划 (d)回溯

（5） 以下哪一个不是NPC问题

(a)单源最短路径 (b)巡回售货员问题 (c)布尔可满足性问题 (d)大数分解

（6） 以下哪个不是几何研究中的基本操作

(a)+ (b)— (c)× (d)/

（7） 哪个问题不能用贪心算法解决

(a)活动安排 (b)哈夫曼编码 (c)分数背包 (d)0-1背包

（8） 哪个问题不能用动态规划解决c

(a)分数背包 (b)0-1背包 (c)最长简单路径 (d)最短简单路径

（9） 插入排序的最好时间复杂度是a

(a)n (b)n^2 (c)nlgn (d)lgn

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-6.html