【23考研】计算机408数据结构代码题强化阶段划重点(王道书) |
您所在的位置:网站首页 › 分块矩阵题目怎么做的 › 【23考研】计算机408数据结构代码题强化阶段划重点(王道书) |
视频链接:【23考研】10分钟带你整理408数据结构强化阶段代码题复习重点 本篇只适合考408的同学,请自主命题的同学自觉右上角×掉 因为王道书为了照顾自主命题的同学,所以很多算法也给出了代码实现,实际上对于考408的同学,很多代码是不需要掌握的,毕竟408的代码题没有像自主命题有些挖的那么深,那么难。 2.线性表P12 2.2线性表的顺序表示P14 2.2.1顺序表的定义P14对于顺序表,一般情况下不需要使用结构体包起来,直接使用数组就行 传参时只需传一个数组名,一个数组中元素个数就行了 void f(int A[],int n){ } 2.2.2顺序表上的基本操作的实现p15增删改查,此处查找指的是顺序查找 2.3线性表的链式表示P28 2.3.1单链表的定义P29单链表的话对应的结构体就需要掌握了 2.3.2单链表上的基本操作的实现P29头插法(可以用于链表逆置),尾插法,单链表的遍历,插入结点,删除结点。 2.3.3双链表P33今年大概率考链表,对于链表大家要引起重视,最好双链表也掌握下,也是有概率考的。 2.3.4循环链表P34学有余力的最好也掌握下 2.3.5静态链表P35学有余力的最好也掌握下 如果考双链表、循环链表、静态链表那么不会考大家链表的建立,大家主要是注意对链表的遍历、插入结点、删除结点这些操作 3.栈、队列和数组P64 3.1栈P64 3.2 队列P77实现不要求掌握,408历史上只在2014年使用层序遍历的时候用到了队列,其实那题不需要层序遍历也能做。 如果遇到需要使用栈和队列的情况的话,只需使用标准库就行了(比如C++中的STL),一般来讲是用不到的。 只有在题目要求你实现栈和队列的情况,你才需要手写实现,这样的情况一般不考 4.串P110这里所有的代码都不要求掌握 5.树与二叉树P125 5.2二叉树的概念P129 5.2.2 二叉树的存储结构P131顺序存储结构+链式存储结构 5.3二叉树的遍历和线索二叉树P139 5.3.1二叉树的遍历P139先序遍历P139 中序遍历P140 后序遍历P140 非递归实现P141(不做要求) 层次遍历P142 (不做要求,三种遍历方式足够了) 5.3.2线索二叉树P143代码全部不做要求 5.5树与二叉树的应用P181 5.5.2并查集P183并查集代码不要求(此处有争议) 6.图P192 6.2 图的存储及基本操作P199 6.2.1邻接矩阵法P199 6.2.2邻接表法P20121年图刚考过,最近再考概率不大 6.3图的遍历P211最多最多就掌握深搜(dfs)就行了,其实我们树那边遍历不论是先序还是中序还是后序其实都是一个深搜的过程。 6.4图的应用P222代码全部不做要求 7.查找P256 7.2顺序查找和折半查找P257 7.2.1顺序查找P257 7.2.2折半查找P259根据自己情况选择性掌握,考普通的二分概率不大,20年考的那题是变形的二分(需要类似于C++中的lower_bound,upper_bound那样的操作),但是那题用二分也不是最优解。 7.3树型查找代码不要求 8.排序p320408算法题排序模板 去年我在代码库中把我以前写的一些排序算法翻了出来,今年后期我还会重新做一下 重点大家只需掌握快速排序就行了 不会写的话也把那段代码背下来,排序没啥好变化的,就一个排序能变出啥呢? 用快排比用冒泡排序、选择排序那些要多2-3分。 快排的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn),空间复杂度是 O ( l o g n ) O(logn) O(logn) |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |