数据结构和算法|集29

2012门考试提出了以下问题。

1） 给出了捕捉n个圆盘的河内塔问题最优时间的递推关系 （A） T（n）=2T（n-2）+2 （B） T（n）=2T（n-1）+n （C） T（n）=2T（n/2）+1 （D） T（n）=2T（n-1）+1

答复（D）

以下是解决问题的步骤 河内大厦 问题反复出现。

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.To move n discs from peg A to peg C:    move n-1 discs from A to B. This leaves disc n alone on peg A    move disc n from A to C    move n?1 discs from B to C so they sit on disc n

上述递推解的时间复杂度的递推函数T（n）可以写成如下。

T（n）=2T（n-1）+1

2）考虑下图所示的有向图。顶点S和T之间有多条最短路径。Dijkstra将报告哪一条？s最短路径算法？假设在任何迭代中，只有在发现到顶点v的较短路径时，才会更新到顶点v的最短路径。

（A） SDT （B） SBDT （C） 萨克特 （D） 小囊

答复（D）

3） 假设容量（n–1）元素的循环队列由n个元素组成的数组实现。假设插入和删除操作分别使用REAR和FRONT作为数组索引变量执行。最初，后=前=0。检测队列已满和队列已空的条件如下 （A） 满：（后+1）模块n==前，空：后==前 （B） 满：（后+1）模n==前，空：（前+1）模n==后 （C） 满：后==前，空：（后+1）模块n==前 （D） 满：（前+1）模块n==后，空：后==前

答复（A） 看见 这 详细信息。

请看 门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。