一、一个无向连通图G中存在一个具有最小边权的边e。证明：G的最小生成树一定包含边e。
二、某石油公司计划建造一条由东向西的主输油管道，该管道要穿过一个有n口油井的油田，从每个油井都要有一条输油管道沿最短路径（或南或北）与主管道相连，如果给定n口油井的位置,即它们的x坐标（或东或西）和y坐标（南北向），应如何确定主管道的最有位置,即使各油井到主管道之间的输油管道长度总和最小的位置.证明可规定时间内确定主管道的最优位置。要求设计一个分治算法解决这个问题。
（1）描述你的算法。
（2）写出你的算法。（伪代码？）
三、使用最长公共子序列算法LCS解决A=（忘记了），B=（忘记了），要求给出解决过程，最长公共子序列的长度以及一个最长公共子序列。
四、最长递增子序列长度
leetcode-最长上升子序列
（1）给出对应的动态规划方程。
（2）写出对应算法。
（3）分析该算法的时间复杂度。
五、给定n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数，对于给定的n位正整数a和正整数k，设计一个贪心算法找出剩下数字组成的新数最小的删数方案。
六、给一个连通图G，要求设计一个回溯算法求出其中的一条哈密顿回路。
（1）写出算法。（伪代码？）
（2）用你写出的算法，试给出下述邻接矩阵（一个4x4的有向完全图矩阵，无自环）的解决过程。
版权声明：本文为weixin_43960822原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。