数据结构高分笔记-1

所需积分/C币:50 2018-01-11 14:56:42 47.17MB PDF
收藏 收藏
举报

数据结构高分笔记-1数据结构高分笔记-1数据结构高分笔记-1数据结构高分笔记-1数据结构高分笔记-1数据结构高分笔记-1
木书讨论群:15945769 作者qq:39826407 前言 在计算机统考的四门专业课中,最难拿高分的就是数据结构。但是这门课本身的难度 不是考生最人的璋碍,真正的障碍在于考生不能独自把握复习的方向和考试范闱。也许有同 学要问了,我们不是有大纲吗?照着大纲去复与不就可以了吗?表面上看是这样,但是当你 真正开始复习的时候你就会发现,其实大纲只给了考生一个大致范围,有很多地方是模糊的, 这些模糊的地方就可能是你要纠结的地方。比如大纲里对于栈和队列的考查中有这么一条: “栈和队列的应用”。这个知识点就说的很模糊,因为只要涉及到栈和队列的地方,都是其 应用的范畴,这吋考生该怎么办呢?于是把所有的希望寄托于参考书,希望参考书能帮助我 们理解大纲的意图。下边我们就米说说参考书吧。参考书分两种,一是课本,二是与课本配 套的辅导书。对于课本,考生用的最多的就是严版的《数据结构》,这里我也推荐大家把这 夲书选作考硏辅导教材。因为这夲书的内容非常丰富,如果能把这本书中考纲要求的章节理 解透彻了,参加考研没有任何问题。但是这个过程是漫长的,除非本科阶段就学的非常好。 计算机统考后,专业课四门加上公共课三门,一共是七门。绝大数考生复习的时间一般也就 六个月,而数据结构的复习需要占用多少时间,我不算大家也清楚。要在这么短的时间内掌 握严版数据结构上考纲要求的知识点,基本上是不可能的,这就需要一本辅导书来依照大纲 从课本中总结出考纲要求的知识点,才能使得考生在短时间内达到研究生考试的要求。市面 上的参考书有两种,一种是四合一的辅导书,比如大家熟悉的复旦版的,山东人民出版社出 版的等等。另一种是分册的,比如网上流行的《1800题》以及其第二版,此书题目巨多, 并且有很多老式的考研题,有些算法设计题的答案是 Pascal语言与的。这木书中的题目 般考生全做基本上是不可能的,挑着做又会把时间浪费在选题上。不可否认,这本书确实是 本非常好的题库,但是考生直接拿来用做考研辅导书去不太合适。还有一本书叫《数据结 构习题与解析》,作者是李春葆,上边总结了一些考研所需知识点,但是这本书同样出自统 考以前,也不完全适应新大纳的要求。直到复试后,第一次见到周伟与的计算机閃络高分笔 记样稿,经过半天的硏读,发现这个就是我想要的,如果这种写作风格用在数据结构我相信 一定是最畅销的书籍。辅导书就应该站在学生的角度去写,特别像数据结构这门比较难深入 的课。所以我决定加入周伟的队伍一起来完成一本真正意义站在学生角度去写的数据结构辅 导书。去史好的帮助考生在最短的时冋内去掌握这一门课。这也是我与这木辅导书最主要的 动机 接下来我详细讲解一下这本辅导书书的写作过程,请看下图 木书讨论群:15945769 作者qq:39826407 ●精选1800题中 且并辅以最詳 用通俗的语 数据结构 总结出严办和李 鼋芮知袁 笔记 1800题 数据结构 习与解析 佔莖妻延鬈结 数据结构 李春葆版 严蔚敏版 《数据结构高分笔记》的由来 图中所涉及的书都是大家很熟悉的吧。当年这些书我都买了,花了很大心思 才从中找出在考研战场上真正有用的东西。比如《1800题》,里边有好题,有废题,我当 时多么渴望有人能在我复习之前就帮我从中去掉重复的题目,选出大纲要求的题目,并能把 解答写的更通俗易葷点,可是当时没有人这么做,。而我们所做的工作就是从这1800题中 选出了大纲要求的题目,并且修正了部分解答,使其更容易理解,我想这也是你们很想要的 吧。其次是严版的《数据结构》写的过于严谨,语言表述过于专业,对于基础稍差的同学米 说读起来十分费力,要很长时间才能适应这本书的写作风格。我当时就是在这本书中痛苦的 挣扎了很久,看第三遍的时候才真正的可以说适应了,何苦这样呢?如果当时有一本辅导书 帮我扣那些复杂程序的执行过程,拗∏的专业术语,令人头大的符号,翻译成容易理解的语 言,我就可以节省很多时间,可惜当时也没有。而我们所做的就是根据自己复习的经验,以 及对这本书的理解,把其中考试不需要的内容删掉,把需要的内容绎过改造变成一般学牛容 易接受的形式。对于李版的《习题与解析》我也徹了类似的处理。并且,我在本书中穿插讲 解了些考纲中没有明文规定但是很多算法题目中大量用到得算法设计课程中的思想,来帮 助大家提高解算法设计题的能力,比如搜索(打印图中两节点之间的所有路径),分治法( 分法排序、求树的深度等等)等算法思想。因此我相信这本书会给你的考研复习带来很大的 帮助。 木书讨论群:15945769 作者qq:39826407 本书特点: (1)精心挑选出适合考研的习题,并配上通俗易懂的答案供你自测和练习。 9,B4 本题考查B-树的定义及插入操作。 π阶B-树根结点至少有两棵子树:并且这两颗子 个分豆,即m/2个子树,因此①不对。 每个结点中关键字的个数比分支数少1,m阶B 此至多有皿-1个关键宇,②正确。 D树是平衡的多路查找树,叶子结点均在同一层 发生结点分裂的时候不一定会使树长高。比如向 变成图(h)牛的R-树,使得第二层右端的一个绊点分 (2)总结出考研必备知识点,并且帮你把其中过于专业过于严谨的表述翻译成通俗易 懂的语言。 2算法的时间复杂度与空间复杂度分析 1考研中的算法时间复杂度杂谈 于这部分,要牢记住一句话:将算法中基本操作的执行次数作为算 门所讨论的时间复杂度,不是执行完一段程序的总时间,而是其十基 于一个算法进行时间复杂度分析的要点,无非是明确算法中哪些操 出基本操作所重复执行的次数。在考试中算法题目里你总能找到 莫,比如要处理的数组元素的个数为n,而基本操作所执行的次数 (3)针对于近年数据结构大题的出题风格(比如算法设计题日中的三段式题目:1.表 述算法思想。2.写出算法描述。3.计算算法的时间和空间复杂度),设计了独特的真题仿 造部分,让你在复习的过程中逐渐养成适合解决考研类型题日的习惯。 真题仿造 1.设计一算法,使得在尽可能少的时间内重排数组,将所有 取非负值的关键字之前,假设关键字存储在R[1…n]中。请分析 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处 (3)分析本题的时间复杂度和空间复杂度。 听我说了这么多之后,很多学生现在想问,我只看你这本书够个够?还需要自己准备其 他书吗?对于这个问题,我用下图来回答。 木书讨论群:15945769 作者qq:39826407 30% 100 95% 数据结构严版 高分笔记 数据结构》 考研所需 所能达到所能达到 水平 的水平 的水平 从图中可以看到,如果你只看本书,你能达到考研要求水平的95%左右,为什么是这样 因为今年大纲还没有公布,所以我不敢保证我的书涵盖大纲所有内容。但是数据结构中的经 典内容本书已经全部包括,再加上对统考这两年大纲氾围的解读,估计今年大纲变化不会太 人,毕竟数据结构是一门经典科目,因此考硏对这一门科的考察范闱较为稳定。从图中同样 可以看出,掌握了严版《数据结构》你可以至少掌握比考试范围多出30%的内容,但是这需 要花很多时间,并个可行。因此在这里我建议大家先看本书,把重要知识点先拿到手,然后 把严版数据结构当做字典来用,等正式大纲出来之后进行查缺补漏,这是一种较为高效的复 习方法。这本书不仅涵盖了考纲绝大部分内容,更重要的是它会帮助你坦解大纲,理解出题 人的思路,这样你就会白哪一类的题日有可能考,哪一类的题日不会考,慢慢的,你复习的 方向感会越米越明确,效率会越米越高 本书作者 木书讨论群:15945769 作者qq:39826407 第一章绪论. 1.1针对考研数据结构的代码书写规范以及C&C++语言基础 1 1.1.1考研综合应用题中算法设计部分的代码书写规范. 1.2考研中的C&C++语言基础杂谈.. 1.2算法的时间复杂度与空间复杂度分析基础 12 1.2.1考研中的算法时间复杂度杂谈. 12 1.2.2例题选讲 12 1.2.3考研中的算法空间复杂度分析 14 1.3数据结构和算法的基本概念.. ,,,,14 1.3.1数据结构的基本概念 .....14 1.3.2算法的基本概念.. ,,.15 习题心选. ..16 习题心讲 18 第二章线性表 ,21 2.1线性表的基本概念与实现 21 2.2线性表的基本操作 ...26 2.2.1线性表的定义 26 2.2.2顺序表的算法操作 28 2.2.3单链表的算法操作 .31 2.2.4双链表的算法操作 35 2.2.5循环链表的算法操作 37 ▲真题仿造 37 真题仿造答案与讲解. 38 习题心选...,,,,, 3 习题心讲 ,,43 第三章栈、队列和数组 54 3.1栈和队列的基本概念 54 3.1.1栈的基本概念 54 3.1.2队列的基本概念. 54 3.2栈和队列的存储结构算法与应用.. 55 3.2.1本章所涉及的数据结构定义 55 3.2.2顺序栈的基本算法操作 56 3.2.3链栈的基本算法操作. ·· ,.58 3.2.4栈的应用 59 3.2.5顺序队的算法操作 63 3.2.6链队的算法操作,,,,,,,,,,,,,, 65 3.3特殊矩阵的压缩存储.. 67 ▲真题仿造. 69 真题仿造答案与讲解 69 习题心选. .,,,72 习题心讲 7 第四章树和二叉树 .85 4.1树的基本概念 85 木书讨论群:15945769 作者qq:39826407 4.1.1树的定义 ,,,,.85 4.1.2树的基本术语 85 4.1.3树的存储结构 .,,,.86 4.2二叉树, ,.87 4.2.1二叉树的定义 ,,,87 4.2.2二叉树的主要性质 88 4.2.3二叉树的存储结构 89 4.2.3二叉树的遍历算法 90 4.2.4线索二叉树的基本概念和构造 98 3树和森林 101 4.3.1孩子兄弟存储结构 101 4.3.2森林与二叉树的转换 102 4.3.3树和森林的遍历 102 4.4树与二叉树的应用 104 4.4.1二叉排序树与平衡二叉树 104 4.4.2哈夫曼树和哈夫曼编码. ,104 ▲真题仿造 107 真题仿造答案与解析: 107 习题心选 108 习题心讲 113 第五章图 127 5.1图的基本概念 127 5.2图的存储结构.. .128 5.2.1邻接矩阵 ,128 5.2.2邻接表. ,130 5.3图的遍历算法操作 131 5.3.1深度优先搜索遍历(DFs).......,. ,,,131 5.3.2广度优先搜索遍历(BFS) .132 5.3.3例题选讲 134 5.4最小(代价)生成树., 136 5.4.1普里姆算法和克鲁斯卡尔算法 .136 5.4.2例题选讲 140 5.5最短路径 141 5.5.1迪杰斯特拉算法 141 5.5.2弗洛伊德算法 .148 .6拓扑排序.. ...150 5.6.1Ao恻 150 5.6.2拓扑排序... .,,150 5.6.3例题选讲 152 5.7关键路径 153 5.7.1AOE网 153 5.7.2关键路径 153 ▲真题仿造 156 真题仿造答案解析: .157 木书讨论群:15945769 作者qq:39826407 习题心选 159 习题心讲 ..164 第六章内部排序 175 6.1排序的基本概念. 177 6.1.1排序 ...177 6.1.2稳定性 178 6.1.3排序算法的分类 ,178 6.2插入类排序 179 6.2.1直接插入排序 179 6.2.2折半插入排序 180 6.3交换类排序 183 6.3.1起泡排序 183 6.3.2快速排序 84 6.4选择类排序 186 6.4.1简单选择排序 186 6.4.2堆排序 187 6.5二路归并排序 190 6.6基数排序 191 排序知识点小结 195 ▲真题仿造 196 真题仿造答案与解析 196 习题心选 .....197 习题心讲. 201 第七章查找 ,210 7.1查找的基本概念、顺序查找法、折半查找法 ,,210 7.1.1查找的基本概念 ,210 7.1.2顺序查找法 211 7.1.2折半查找法 212 7.2叉排序树、平衡二叉树 214 7.2.1二叉排序树.. 214 7.2.2平衡二叉树... ..217 7.3B-树及其基本操作、B+树的基本概念. 221 7.3.1B-树的基本概念., ,221 7.3.2B-树的基本操作 222 4散列(Hash)表 ,228 7.4.1散列(Hash)表的概念... 228 7.4.2散列(Hash)表的建立方法以及冲突解决方法 228 7.4.3散列(Hash)表的性能分析 .,,,232 ▲真题仿造.. 233 貞题仿造答案与解析: 234 习题心选. 236 习题心讲. 240 2010年计算机考研试题. ,251 2009年计算机考研试题 256 数据结构高分笔记勘误表(高分笔记讨论在天勤论坛:ww.csbiji.com) 虽然本书已经过团队多次勘误,但是小错误依然难以避免,所以特发此表,给您带来的不便我们深表歉意。 (1)p1.最下面 28)P91,例题1.a-(b+-(/e)改为a-(b+)*(a/e) 改为 (29)p251.缺图 Ⅹ0rX1·,,x。-1} (2)p9.12题讲解部分:结合区.1.3改为结合.3.可 (3)p44.11题答案改为B (4)p132中间:说明:对应于图的先序遍厉代码”改为 对应于困的深度优先搜索遍历代码… 第4题图 第8题图 图的先序遍厉则是要访问多个分支,"改为"图的深度优先搜索 (30)9252.第10题A.递归次数于初始数据的排列次数无关 遍历则是要访问多个分支。n 改为递归次数写初始数据的排列次无关 (5)p225.最下边图(c)删除[5后的结果改为删除图后的结果 (31)p136.中间普利姆算法过程标号(3)中:候选边长分别为 6)p226.中间图7.7不太清晰,清晰图如下: 5,3回2,3改为5,3,2,3,即将4去掉。 b g 32)P37真题仿造第1题,后n个元素递增有序,改为后n个元素 无 s-□-s--:ss- (33)P149.中间①pata01]做为回ath「[0 Pah3①改为园athO后边:从顶点3到顶点1|改为从 等于n/2-1等m24-1等于m(d2 于n/2-1 等于-1 顶点3到顶点习③ath[2]1为pat[21(0,后边:指向 1)初始状本 1)删除关健字a 2)结点合并后 顶点的边改为指向点0的边。并将下边F1oa算法中的都改 图7.7删除关键字a后的结点合并过程(a<b<c) 成< (7)252将图1题改为上题,将生2题改为园题 (34)p126.下方,将if(top!=-1) 鍪个放入 (XprXp-1l, ,Xn-1x0,X1.∴X2-1}改为 hile top!=-1&p!=NULL}{..,}内,位置在其内层whi1e循 环下方 (8)p11.中间 typedef STATUS bo改为 (35)P22.1+树结点结构图改为国树结点结构图。另外图74 typedef bool STATU,另一个 typedef的该法类似 上面倒数第6行(1≤≤叫做改为(0≤≤n (9)p11.下部最后一段中 typedef回 LEMTYPE int改成 (36)P114.第9题讲解部分:C,D,F,G,工可改为D,,E,且,工,了 typedef int ELEMTYPE (37)p27.图2.9上面倒数2、3行,将这两行注释的位置调换, (10)919最下边应tn)=n+ Kellog2n (38)p224.标号8)第二行中的两个15改成13 改为fn)-(1× n+clog2n (39)p46.20题说明的倒数第三行改为q>ata=temp; (1)134第二个说明,國改为面 (40)p141图5.12顶点3至4的权值将4改为园 (12)181.62改为62. (41)p131.图5.5中4,5两图中将边(,C)变细D,C)变粗 15)23选2某队列允许在其两端进行入队操作,但934图改为 (13)p227.732改为7.3国 (42)168.29题答案改为 14)P17最下边的 mergesort(函数中,在 mergesort(i;m,; 一句上边加上m=(+j)/2 许在一端进行出队操作,则… 改为:2.某队列允许在其两端进行入队操作,但仅允许在一端进行 出队操作,匿元素按照a、b、cd依次入此队则…(16)p253 1} (2 第2题讲解:将无论哪种入队序列改为无论哪种入队方式 (17)P96.中间层次遍历代码部分: (43}p166.15题答案为D,对应的解析改为第一和最后一个序列是 程序第7行f!=NUL)改为if(p!=NT) 满足条件 程序第19行皿ear]=p改为 uprear1=q=21ef 1)p229Hash表地址6上关键字改为 程序笫24行eear=p改为 ue [rear >right (45)p101.图4.12下边标号(1)同一层结点用线中起来改为将 (1B)g9:1id城为线索,rh1域为链钳改为1c:id域为同一结点的各孩子结点用线串起来 链指钮, rchild域为索 (19)p108.程序算一句 (46)p212.折半賽找的第六行,mid=(low+high)/2 ];⊥nt (47)p222.B-树查找的第9行应该是k[i]<key<k[i+1 改为: char ancestor( char tree[,iti,intj (48)p67第一个[0.n*(n+1)/2]改为a0.n*{n+1)/2-1 (20)p115.16题,因此分支结点改为因此区分支结点 (49)p68第一行.-改为 (21)p143.第三行dist[4]-=gdst(1]+g[1](4]=11 (50)p133.①BFS算法中在whi1e循环上加上 改为dist[4]=∞ist[1]+g[1][4]=11 visit(v); ViSIt[]=1;两句 ②将j= que [front];后的 Visit(j);visi[i=1;两句删掉 因比本算法的时间复杂度为m改为:因此本算法的时间复杂度③在下边语句中的reax-(reax+1)%Mx;-句上边加上 为 (23}p161.33题C选项 Visit(p- >ad-vex); vlslt[p-> adver]=1;两句 1,2,3,4,56,7改为1,2,3,4,5,,回 (51)p123最下边 int top=-1;改为int[op=; p199.28题A选项:两对括号中间的②6改成 28。 第25题题干:对n个数据进行排序 (52)p186.中间,将快速排序的空间复杂度改为c(1og2n) 改为对n个数据进行瑶排序 53)p132.DFS算法中将i语句的一对大括号去掉。P158.页的 (25)p202.11题答案为A,解析正确,答案标错。 DFS做同样的修改 (26)p238.26题A.21B.28改为.21,B.28/园 (54)排序那一章将快速排序的空间复杂度改为o(1og2n) 对应的26题答案解析查找失败的平均查找长度改为②1/7 (55)p244.25题解析第四个图最后一个关键字35应画在右分支 (27)p239.30题D.15国55,35改为D.15,园习,55,35 56)p247.第2题计算表长/n=15改为/a=15

...展开详情
试读 127P 数据结构高分笔记-1
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
数据结构高分笔记-1 50积分/C币 立即下载
1/127
数据结构高分笔记-1第1页
数据结构高分笔记-1第2页
数据结构高分笔记-1第3页
数据结构高分笔记-1第4页
数据结构高分笔记-1第5页
数据结构高分笔记-1第6页
数据结构高分笔记-1第7页
数据结构高分笔记-1第8页
数据结构高分笔记-1第9页
数据结构高分笔记-1第10页
数据结构高分笔记-1第11页
数据结构高分笔记-1第12页
数据结构高分笔记-1第13页
数据结构高分笔记-1第14页
数据结构高分笔记-1第15页
数据结构高分笔记-1第16页
数据结构高分笔记-1第17页
数据结构高分笔记-1第18页
数据结构高分笔记-1第19页
数据结构高分笔记-1第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >