北大屈婉玲算法分析与设计 习题解答6.pdf

《北大屈婉玲算法分析与设计 习题解答6.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Exercise31.给定数轴X上n个不同点的集合{x1,x2,…,xn},其中x1C.ii=1如果要求存入的文件个数达到最多，选用哪种算法设计技术？简述算法设计思想，证明算法的正确性，并估计算法最坏情况下的复杂度.2n3.假设零钱系统的币值是{1,p,p,…,p}，p>1，且每个钱币的重量都等于1.设计一个最坏情况下时间

2、复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少.说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度分析.4.有n个进程p1,p2,…,pn.对于i=1,2,…,n，进程i的开始时间为s[i],截止时间为d[i].可以通过监测程序Test来测试正在运行的进程.Test每次测试的时间很短，可以忽略不计.换句话说，如果Test在时刻t进行测试，那么它将对满足s[i]≤t≤d[i]的所有进程pi同时取得测试数据.假设最早运行的进程的开始时刻是0，问：如何安排测试时刻，使得对每个进程至少测试一次，且Test测试的次数达到最少？说明你的算法的主要设计思想，

3、给出伪码，并分析算法最坏情况下的时间复杂度.5.设字符集S，其中8个字符A,B,C,D,E,F.G.,H的频率是f1,f2,...,f8，且100×fi是第i个Fibannaci数的值，i=1,2,...,8.(1)给出这8个字符的Huffman树和编码.(2)如果有n个字符，其频率恰好是前n个Fibanacci数，那么Huffman树是什么结构，证明你的结论.