《数据结构》第六章 递归 习题.doc

《《数据结构》第六章 递归 习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第六章递归习题基本概念题：6-1什么叫递归？6-2适宜于用递归算法求解的问题的充分必要条件是什么？什么叫递归出口？6-3阶乘问题的循环结构算法和递归结构算法哪个的时间效率好，为什么？6-4非递归函数调用时系统要保存哪些信息？递归函数调用时系统要保存哪些信息？系统怎样保存递归函数调用时的信息？6-5什么叫运行时栈？什么叫运行时栈中的活动记录？6-6叙述递归算法的执行过程。复杂概念题：6-7推导求解n阶汉诺塔问题要执行的移动操作（即算法中printf()函数的调用）次数。6-8我们讨论过的折半查找函数设计如下：intBSearch(elemtypea[],elemty

2、pex,intlow,inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;if(x==a[mid])returnmid;if(x

3、,2,3,......,n的n个数累加的递推定义式；（2）编写求1,2,3,......,n的n个数累加的递归算法，假设n个数存放在数组a中。6-10要求：（1）写出求1,2,3,......,n的n个数连乘的递推定义式；（2）编写求1,2,3,......,n的n个数连乘的递归算法，假设n个数存放在数组a中。6-11设a是有n个整数类型数据元素的数组，试编写求a中最大值的递归算法。6-12设计输出如下形式数值的算法。122333......nnn...n要求：（1）把算法设计成递归结构的算法；（2）画出上述递归算法的调用执行过程；（3）把算法设计成循环结构。*6-13背包问

4、题。设有一个背包可以放入物品的重量为s，现有n件物品，重量分别为w[0],w[1],...,[n-1]。问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s。如果存在一种符合上述要求的选择，则称此背包问题有解；否则称此背包问题无解。试用分而治之的算法设计方法设计求解背包问题的函数。提示：此背包问题的递推定义如下（其中True表示有解，False表示无解）：上机实习题：6-14折半查找问题。折半查找问题的描述见6.1节，折半查找问题的递归算法见例6-2。要求：（1）设计折半查找问题的循环结构算法；（2）设计一个查找成功的例子和一个查找不成功的例子，并设计测

5、试主程序；*（3）设计一个包含10000个数据元素的查找成功的例子，然后分别调用循环结构的查找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。*6-15八皇后问题。设在初始状态下在国际象棋棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行，…，第8行上布放棋子。在每一行中共有8个可选择位置，但在任一个时刻棋盘的合法布局都必须满足3个限制条件：1）任意两个棋子不得放在同一行上；2）任意两个棋子不得放在同一列上；3）任意两个棋子不得放在同一正斜线和反斜线上。（1）试用回溯法的算法设计方法编写一个函数，求解并输出此问题的一个合法布局；（2）试用

6、回溯法的算法设计方法编写一个函数，求解并输出此问题的所有合法布局。提示：在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线方向和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。