数据结构习题课ppt.pptx
《数据结构习题课ppt.pptx》由会员分享,可在线阅读,更多相关《数据结构习题课ppt.pptx(36页珍藏版)》请在咨信网上搜索。
1、数据结构习题课第第7 7章作业章作业l l247页:每组得第1题就是必交得,即7-2、7-5、7-18、7-24、7-49l l7-2、7-3、l l7-5、7-8、7-10、l l7-18、l l7-24、7-26、7-30、7-31、7-35、7-36l l7-49、7-507-27-2l若对序列若对序列(7,3,1,8,6,2,4,5)按从小到大排序按从小到大排序,请写出冒泡排序得第一趟结果。请写出冒泡排序得第一趟结果。l参考答案 3,1,7,6,2,4,5,87-37-3l设文件(R1,R2,Rn)以单链表方式表示,指针变量FIRST指向表头结点,且表中得结点结构为:l其中KEY为该结
2、点得关键词域,LINK为链接域。请给出这种线性表得直接插入排序算法,并要求算法得时间复杂度为O(n2),且算法就是稳定得。KEYLINKl算法InsertSort(FIRST、FIRST)/*对单链表直接插入排序,FIRST指向表头结点*/IS1边界 IF(LINK(FIRST)=NULL OR LINK(LINK(FIRST)=NULL)THEN RETRUN、IS2插入排序 q LINK(FIRST)、q0 LINK(q)、WHILE(qNULL)(p LINK(FIRST)、p0 FIRST、WHILE(KEY(p)=KEY(q)AND LINK(p)q)DO (p0p、pLINK(p)
3、、)、IF(KEY(p)KEY(q)THEN(LINK(q0)LINK(q)、LINK(p0)q、LINK(q)p、q LINK(q0)、)、ESLE(q0 q、q LINK(q0)、)、)7-57-5l设计一算法设计一算法,在尽可能少得时间内重排数组在尽可能少得时间内重排数组,使所有取负值得关键词放在所有取非负值使所有取负值得关键词放在所有取非负值得关键词之前得关键词之前,并分析算法得时间复杂度。并分析算法得时间复杂度。l基本思想:以0为基准记录,使用快速排序得一次分划过程即可,时间复杂度为O(n)、算法Part(A,n、A)/*以0为基准元素一次分划*/P1 初始化 i1、jn、P2以0分
4、划 WHILE ij DO (WHILE Ki0 AND i0 AND iRj+1)时才会发生交换,关键词相同得记录不会发生交换,即相同位置不变,因此就是冒泡排序算法就是稳定得。大家有疑问的,可以询问和交流大家有疑问的,可以询问和交流可以互相讨论下,但要小声点可以互相讨论下,但要小声点可以互相讨论下,但要小声点可以互相讨论下,但要小声点7-107-10l类似于冒泡过程(从下到上),与之对应得就是下沉过程(从上到下)。如果排序就是冒泡与下沉得交替过程,证明如果经过一趟冒泡与一次下沉后发现Rj与Rj+1(1jn1)没有交换,则它们已经进入最终排序位置。参考答案参考答案l证明:l如果经过一趟冒泡与一
5、次下沉后发现Rj与Rj+1(1jn1)没有交换,那么有 R1=R2=R3=Xi+1、key)(Xi Xi+1、change 1、)for i 2 to n-1 step 2 /偶交换偶交换 if(Xi、keyXi+1、key)(Xi Xi+1、change 1、)l(1)最好情况下最好情况下,比较一趟、每趟中奇交换偶交换比较一趟、每趟中奇交换偶交换比较次数共比较次数共(n-1)次次,无记录交换、无记录交换、/正序正序l(2)最坏情况下比较最坏情况下比较 (n/2)+1趟趟,总比较次数为总比较次数为(n-1)*(n/2+1)次、每次比较都交换次、每次比较都交换,总交换次数为总交换次数为(n-1)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题 ppt
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。