算法设计与分析(试卷小抄)

学院:计算机学院专业:班级:学号:姓名:装订线广东工业大学考试试卷(A)课程名称:算法设计与分析试卷满分100分考试时间:2008年6月6日(第15周星期五)题号一二三四五六七八总分评卷得分评卷签名复核得分复核签名一、简答题(每小题5分,共15分)1、简述什么是在位的算法?不需要额外的空间,个别空间除外,那么这个算法就叫做在位的算法。2、举出一个反例,说明包含负权重的加权连通图,Dijkstra算法可能会无效。3、解释什么是算法空权衡理论中的输入增强技术?对问题的部分或全部输入进行预处理,然后对获得的额外信息进行存储。二、(8分)考虑如下算法:Mindist(A[0..n-1])dist←∞fori←0ton-1doforj←0ton-1doifi≠jand│A[i]-A[j]│maxmax←A[i]Returnmax-min(1)说明该算法的功能,(2)该算法的基本操作是什么?(3)计算该算法的效率类型。四、(12分)给出某算法所做的基本操作次数的递推关系如下x(n)=x(n/2)+n,其中n>1,x(1)=1试对于n=2k的情形求解该关系,并指出该算法的效率类型。五、(14分)对下面的通讯数据构造哈夫曼编码,并对文本100010111001010进行解码。字符ABCD@出现频率0.10.20.150.40.15六、(15分)对于输入关键字K的序列{30,20,56,75,31,19}和散列函数h(K)=Kmod11,(1)构造它们的开散列表,(2)求在开散列表中成功查找的平均键值的比较次数。七、(12分)堆排序算法体现了变治的技术,对关键字列表{1,8,6,5,3,7,4}:(1)用自底向上算法为列表构造一个堆(大顶堆);(2)指出在最坏情况下堆构造阶段的算法效率和整个堆排序算法的算法效率。1865374>1875364>8175364>8571364八、(10分)合并排序算法体现了分治的技术,其中合并过程将有序数组A、B合并为有序数组C。(1)结合实例A={1,3,4,9,13,34}、B={2,5,16,22}说明合并排序的步骤;(2)说明合并排序算法在最坏情况下的时间效率。

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供参考,付费前请自行鉴别。
3、如文档内容存在侵犯商业秘密、侵犯著作权等,请点击“举报”。

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

客服邮箱:

biganzikefu@outlook.com

所有的文档都被视为“模板”,用于写作参考,下载前须认真查看,确认无误后再购买;

文档大部份都是可以预览的,笔杆子文库无法对文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;

文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为依据;

如果您还有什么不清楚的或需要我们协助,可以联系客服邮箱:

biganzikefu@outlook.com

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

笔杆子文秘
机构认证
内容提供者

为您提供优质文档,供您参考!

确认删除?