算法分析与设计题

《算法分析与设计题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析期末综合实验试题清单分治与递归1-1合并排序问题描述：给定n个整数，利用合并排序思想将其调整成单调序列。输入：整数的个数n,以及n个整数输出：从大到小排序的n个整数（或从小到大排序）1-2split快速排序（枢点法）问题描述：给定n个整数，利用枢点法快速排序的思想将其调整成单调序列。输入：整数的个数n,以及n个整数输出：从大到小排序的n个整数（或从小到大排序）1-3平面最近点对问题描述：平面内有若干点，设计一算法在0（nlogn）时间内求出直线距离最近的一对点，并输它们的距离。输入：点对的数目n以及n对点的坐标输出：最近的点对坐标（x,y）以及距

2、离d1-4棋盘覆盖问题问题描述：在一个2kX2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。输入：棋盘的行列数n,棋盘中特殊方格的行列号（x,y）输出：棋盘的覆盖方案1-5求k大（小）元素（基于split枢点法划分）问题描述：有一数列，设计一分治递归算法，以□（nlogn）时间找出其第k大（小）元素。输入：整数的个数n、n个整数以及k值输出：第k大（小）元素值以及其对应的下标i1-6二

3、分检索问题描述：有一单调序列，设计一分治算法检索出元素X。输入：整数的个数n、n个单调增（减）个整数以及需检索的元素值x输出：最近的点对坐标（x,y）以及距离d1-7大整数乘法（10进制）问题描述：有两个10制的大整数（不少于30位），设计一分治算法，以0（nlogn）时间算出其乘积。输入：第一个大整数的位数叭第二个大整数的位数n,以及两个大整数x,y输出：两个大整数的乘积s1-8循环赛比赛安排问题描述：设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次；（3）循坏赛一共进行n-1天。输入：选手的个数n

4、、n个选手的编号输出：每天的赛事安排（共n-l天）1-9整数的划分问题问题描述：将正整数n表示成一系列正整数之和：…+叫其中nk>l,k$l。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数以及划分情况。输入：正整数n输出：n的划分个数以及划分情况1~10主元素问题问题描述：有一个整数数列，数列屮元素出现次数超过一半的元素定义为主元素，设计一分治算法，求出主元素。输入：整数的个数n以及n个整数输出：如果有主元素，输出主元素以及它们所在的位置；如果没有主元素，输出-11-11全排列的生成问题描述：给出一个序列，生成这个序列的全排列输入：整数的个数n

5、以及n个整数输出：生成这n个数的全排列贪婪算法2-1加油站问题问题描述：一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。输入：汽车加满油后可行驶千米数n,加油站个数k。以及两两加油站之间的距离。输出：最少的加油次数m,如果无法到达目的地，则输出“NoSolution”。1-2货币兑换问题问题描述：当前有N种面额的货币，请为M元钱找出最合理的兑换方案（要求找出的货币数目最少）输入：货币面额的种类以及各种货币的面额以及需要兑换的钱数M输出：兑

6、换方案以及用到的货币张数。1-3普通背包问题问题描述：给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品，使得装入背包屮物品的总价值最大？（物体可以分割）输入：物体的件数n,背包的容量C,每件物品的重量和价值输出：背包内物品的总价值以及装载方案。1-4单源最短路径问题问题描述：给定一张有向带权图，求源点到其他各个点的最短距离以及路径。输入：顶点个数n,有向带权图的邻接表数据输出：各个点到源点的最短距离以及最短路径1-5最小生成树（prim）问题描述：给定一张无向带权图，利用pirm算法的思想求能将图的各个顶点全部

7、连通的最短路径和（即最小生成树）输入：无向带权图输出：最小生成树1-6最小生成树（kruskal）问题描述：给定一张无向带权图，利用kruscal算法的思想求能将图的各个顶点全部连通的最短路径和（即最小生成树）输入：无向带权图输出：最小生成树1-7活动安排问题问题描述：设有n个活动的集合E二{1,2,・・•“},其中每个活动都要求使用同一资源，每个活动i都有一个要求使用该资源的起始时间si和一个结朿时间fi,且si

8、si和一个结束时间fi,Hsi