作业 1 第 1 章绪论
作业题目:(蓝色字体部分可以不做,供学有余力、有兴趣的同学探索)
一、 你能结合自己的编程实践,谈一下数据结构和算法之间的关系吗?
二、 简单排序算法
1、 编程实现(直接) 冒泡排序算法、(直接)选择排序算法和(直接)插入排
序算法,分析其时间和空间复杂度。
2、 编写(直接) 冒泡排序、(直接)选择排序算和(直接)插入排序的递归算
法,分析其时间和空间复杂度。
3、 你能用实验的方法验证上述算法时间复杂度的分析结论吗?
三、 汉诺塔问题
1、 编程实现汉诺塔问题的递归算法,并分析的时间和空间复杂度。
2、 你能将汉诺塔的递归算法改写成非递归算法吗?并分析期时间和空间复
杂度。
3、 你能通过实验来比较汉诺塔问题的递归和非递归算的时间效率吗?
四、 角谷猜想(冰雹猜想)
对于任何正整数 n,若是偶数,则除以 2;若是奇数,则乘以 3 加上 1。这
样得到一个新的整数,如果继续进行上述处理,则最后得到的数一定是 1 吗?
1、 编写程序对 100 以内的整数进行测试验证,并找出其中最长的序列。
2、 你能给角谷问题一个肯定或否定的回答吗?
五、 交通管制问题
1、 你能编程实现交通管制问题的贪心算法,对任意交叉路口的交通管制?
2、 你能证明该贪心算法的正确性吗?
3、 能根据实际的交通流量等信息,优化该贪心算法吗?
作业说明:
1.上传内容:(1)源程序文件本身;( 2)测试数据和结果数据;( 3)文字、图
表等手写部分可以采用截图方式贴在 word 文件中
2.上传格式:(1)打包为 rar 或 zip 文件;(2)命名规则:学号-姓名-作业编号,
如 120L020539 张岩-作业 1.rar
3.上传方法和网址:用 Google 或 Firefox 浏览器;网址:10.160.3.21:8080
4.上传截止时间:2021 年 09 月 26 日(第 3 周星期日)23:59:59 之前
评论0