算法设计与分析试题2011秋

          试 题 专 用 纸                                课程名称：计算机算法设计与分析

                                                            任课教师： 陈玉福

———————————————————————————————————————————————

   姓名                          学号                         成绩                     

一．回答下列问题： (每小题5分)

1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？

2.阐述动态规划算法与贪心算法的区别，它们都有那些优势和劣势？

3.阐述回溯算法与分枝限界算法的共同点和不同点，提高算法效率的关键是什么？

4.在对算法进行复杂性分析时，强调渐进复杂性的意义是什么？

二．（20分）试用Prim算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后次序；写出算法的基本步骤。

三． （20分）用LC－分枝限界算法求解0/1背包问题： ，物品重量和价值分别是：

                    和   

1.画出由算法生成的状态空间树，并标明各节点的优先级的值；

2.给出各节点被选作当前扩展节点的先后次序；

3.给出最优解。

四．（20分）已知一组数满足，且被搜索的对象的概

率分布是：

                                                            共 2 页        第 1 页

其中表示被搜索对象在区间内的概率，表示被搜索对象为的概率， 

使用动态规划算法求该搜索问题的最优二叉搜索树。  

    五．(20分) 假定已知“无向图的Hamilton回路”问题是NPC问题，证明“旅行商判定问题”也是NPC问题。                                       

                                                            共 2 页       第 2 页