第1章 数据结构习题讲解.ppt_第1页
第1章 数据结构习题讲解.ppt_第2页
第1章 数据结构习题讲解.ppt_第3页
第1章 数据结构习题讲解.ppt_第4页
第1章 数据结构习题讲解.ppt_第5页
已阅读5页，还剩7页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、存在问题,书写不规范，存在较多语法错误 符号“.”的应用 输入输出参数 一条语句的结束 符号“ ”的应用 标志算法结束 C+的语法、格式(最好上机调试) 要养成写注释的好习惯 /单行注释 /*多行注释 注意格式*/ 注意程序的可读性,习题 2-1,若S是n个元素的集合，则S的幂集是S的所有可能子集的集合。例如，若S = a,b,c，则Powerset (S) = , a , b , c , a , b , a , c , b , c , a , b , c 请给出一个计算幂集Powerset (S) 的递归算法。 递归算法的思想 递归算法指的是包含递归过程的算法，递归过程指的是调用自身的过程。

2、 算法的有限性要求必须存在递归出口。 递归算法中通过对自身的调用，总能逐步逼近，直到满足递归出口。,习题 2-1,观察幂集的性质,习题 2-1,| P(S) | = | P(S-1) | * 2 | P(S) |=2n P(S) = P(S-a) P(S-a) a /* S的幂集P(S)可以表示为S-a的幂集P(S-a)然后再并上 P(S-a)中任意一个集合并上元素a */,习题 2-1,利用性质 | P(S) |=2n 集合S= a , b , c ,习题 2-1,P(S) = P(S-a) x a |x P(S-a),习题 2-1,算法 POWERSET(s.p) /计算集合s的幂集p P

3、S1 递归出口 IF s= THEN (p. RETURN. ) PS2 递归调用 xanyelement(s). POWERSET(s-x.q). p = q; FOR (yq) p=p(yx) . ,习题 2-3,证明对正整数 n 3，算法BS的元素比较次数 T（n） 5n/3 - 2 数学归纳法证明 证明 n=3 时成立 假设3 n k 时都成立 证明 n= k时也成立,习题 2-3,证明（数学归纳法）： 当n=3时，T（3）=T（2）+T（1）+2=3 （5*3）/3 - 2=3； 命题成立。 假设nk时命题成立，即 T（i） 5i/3 2 i k,习题 2-4,算法 IBS(A,1,n.fmax,fmin) /计算最大最小元 IBS1 初始化 fmin fmax A1. CREATS(S). S (1,n).,IBS2 迭代过程 WHILE (S NULL) （ （l,r） S. IF r-l =0 THEN ( fmax max(fmax, Ar). fmin min(fmin, Ar). ) IF r l =1 THEN (IF Al Ar THEN ( fmax max(fmax, Ar). fmin min(fmin, Al). ) ELSE ( fmax max(fmax,

人人文库> 全部分类> 教育资料 > 考试试卷

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论