开发工具:
文件大小: 432kb
下载次数: 0
上传时间: 2014-07-13
详细说明： 基础篇 1、 算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、 算法的时间复杂度指的是什么？如何表示？ 3、 算法的空间复杂度指的是什么？如何表示？ 4、 什么是最坏时间复杂性？什么是最好时间复杂性？ 5、 什么是递归算法？什么是递归函数？ 6、 分治法的设计思想是什么？ 7、 动态规划基本步骤是什么？ 8、 回溯法与分枝限界法之间的相同点是什么？不同之处在哪些方面？ 9、 分枝限界法的基本思想是什么？ 10、 限界函数的功能是什么？ 11、 设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 12、 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。 13、 分别写出求二叉树结点总数及叶子总数的算法。 分治术 14、 有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 15、 利用分治策略，在n个不同元素中找出第k个最小元素。 16、 设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 17、 已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 贪心法 18、 设有n个文件f1，f2，…，fn要求存放在一个磁盘上，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1，p2，…，pn，且 =1。磁头从当前磁道移到被检索信息磁道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道上，1≤i≤n则检索这n个文件的期望时间是 。其中d(i，j)是第i道与第j道之间的径向距离。磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。 19、 设有n个正整数，编写一个算法将他们连接成一排，组成一个最大的多位整数。用贪心法求解本题。 20、 键盘输入一个高精度的正整数N（此整数中没有‘0’），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小（输出应包括所去掉的数字的位置和组成的新的正整数，N不超过240位）。 21、 对于下图给出的有向网，写出用Dijkstra方法求从顶点A到图中其它顶点的最短路径的算法，并写出执行算法过程中顶点的求解次序及从顶点A到各顶点路径的长度。 22、 对于上图给出的有向图，写出最小成本生成树，给出求解算法。 动态规划 23、 求出上图中每对结点间的最短距离的算法，并给出计算结果。 24、 下图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? 25、 已知序列a1，a2，…，an，试设计一算法，从中找出一子序列 ai1 < ai2 < … < aik 使k达到最大，并讨论其复杂性。 26、 设计一个O（n2）时间的算法，找出由n个数组成的序列的最长的单调递增子序列。 27、 旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写算法估计实际行驶在某路线所需的最小费用。 28、 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。 29、 已知如下图，写出用动态规划求最短路径的递推关系式，并写出求从源点A0到终点A3 的最短路径过程。给出求解算法。 6 A1 A2 5 5 2 A0 A3 3 4 4 B1 B2 5 搜索与遍历问题 30、 已知有向图G=，试设计一算法以判断对于任意两点u和v，是否存在一条从u到v的路径，并分析其复杂度。 31、 对于给定的一个二叉树T（如下图） a) 设计一个算法，统计二叉树中结点总数； b) 设计一个算法，求二叉树最大宽度及最大宽度所在深度。 32、 判近亲问题。给定一个家族族谱，为简化问题起见，假设家族中的夫妻关系只表示男性成员。设用线性表存储家族成员，用成员的父指针指向其生父。编写一个在此种族谱表示方式下的算法，判断给定的二个家族成员是否是五代内的近亲。（提示：家族成员的表示方式应与搜索方式相适应。） 33、 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 34、 编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。 35、 编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 回溯法 36、 （组合问题）求出从自然数1，2，…，n中任取r个数的所有组合。 37、 传教士与野人渡河问题。有M个传教士和M个野人准备渡河，船一次最多载2人，任何时刻野人数不能多于传教士数，但允许全部为野人。编写算法给出合理的渡河计划。 38、 某乡有n个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1。试设计一个算法，帮他选择一条最短的路。 39、 设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wi,j是从供应商j处购得的部件i的重量，ci,j是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。 40、 设有n件工作分配给n个人。为第i个人分配工作j所需的费用为ci,j 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。 41、 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=8），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 — 问题无解骑士巡游）。 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
