数据分析与算法设计习题课

数据分析与算法设计：习题课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题习题