




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据分析与算法设计:习题课1第一次作业+第二次作业+第三次作业信电学院王梁昊副研究员(645840)浙江大学玉泉校区信电楼505室第一次作业习题1.2
第1题习题1.3
第4题习题1.3
第5题习题2.1
第10题习题2.2
第5题习题2.5
第8题习题1.2
第1题习题1.3
第4题1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文,在解答问题的同时,开创了数学的一个新的分支——图论与几何拓扑,也由此展开了数学史上的新历程。连通图可以一笔画的充要条件是:奇点的数目不是0个就是2个要想一笔画成,必须中间点均是偶点,也就是有来路必有另一条去路,奇点只可能在两端,因此任何图能一笔画成,奇点要么没有要么在两端习题1.3
第5题习题2.1
第10题习题2.2
第5题习题2.5
第8题没有必要特意使用一个数组来存储数列中前面的元素:为了完成该任务,只需要存储两个元素就足够了第二次作业习题3.1
第12题b习题4.1
第8题习题4.1
第12题a&b
(希尔排序)习题5.2
第4题习题5.2
第9题习题3.1
第12题b习题4.1
第8题哨兵限位器习题4.1
第12题a&b
(希尔排序)希尔排序希尔排序是1959年由D.L.Shell提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序基本思想先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。希尔排序操作方法选择一个增量序列d1,d2,…,dm,其中dki>dkj,dm=1;按增量序列个数m,对序列进行m趟排序;每趟排序,根据对应的增量dk,将待排序列分割成若干子序列,分别对各子表进行直接插入排序。仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。38例:关键字序列T=(49,38,65,97,76,13,27,49*,55,04),请写出希尔排序的具体实现过程。0
1
2
3
4
5
6
7
8
9
104938659776132749*5504第2趟(dk=3)第3趟(dk=1)491338276549*97557604135527044949*76132704497697132749*55044938659776130449*38274955659776041327*3849*4955657697算法分析:开始时dk的值较大,子序列中的对象较少,排序速度较快;随着排序进展,dk值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数对象已基本有序,所以排序速度仍然很快。可以看出,49*排序后出现在49的前面,故希尔算法是不稳定的。r[i]初态:第1趟(dk=5)希尔排序示例希尔排序分析时间效率希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1外没有公因子,且最后一个增量因子必须为1。空间效率:O(1)稳定性:不稳定习题5.2
第4题习题5.2
第9题荷兰国旗呈长方形,长宽比为3∶2。自上而
下由红、白、蓝三个平行相等的横长方形相
连而成。蓝色表示国家面临海洋,象征人民
的幸福;白色象征自由、平等、民主。还代
表人民纯朴的性格特征;红色代表革命胜利。在位(原地)算法课本P16第三次作业习题3.2
第6题习题4.4
第8题习题4.5
第6题(参考§2.2.6)习题5.5
第7题习题7.2
第2题习题
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学数字化教学的实践及研究
- 云公开课展示活动方案
- 云南打卡活动方案
- 云鲸公司年会策划方案
- 互联网公司剪彩活动方案
- 互联网汽车大屏活动方案
- 五一以后活动方案
- 五一减肥活动方案
- 五一卤肉馆活动方案
- 福建水利电力职业技术学院《摄影作品研究》2023-2024学年第二学期期末试卷
- 《基督教概论》课件
- 虚拟现实技术导论 习题答案或解题思路 梁晓辉
- 计算机应用技术专业调研报告(高职)
- 2024NEA水性气硅涂膏隔热保温墙体构造
- 山西省太原市(2024年-2025年小学四年级语文)部编版期末考试((上下)学期)试卷及答案
- BPC10完整版本.0技术培训V1.0
- 2024年新高考II卷高考历史试卷(真题+答案)
- 2024年黑龙江医疗卫生事业单位招聘(药学)备考试题库(含答案)
- 2024年新高考1卷数学真题试卷及答案
- 湖北省武汉市洪山区2023-2024学年七年级下学期期末考试语文试卷
- 施工现场水电费协议
评论
0/150
提交评论