408考研—数据结构概念知识点思维导图—所有章节_408数据结构考研知识点资源-CSDN文库

版权申诉

5星 · 超过95%的资源 185 浏览量 2022-06-29 23:02:44 上传评论收藏 575KB PDF 举报

资源推荐

资源详情

资源评论

!数据结构概念

!绪论

!数据

!基本单位 !数据元素

!最⼩单位 !数据项

!数据结构

!（D，R）

!D是数据元素的集合

!R是D关系上的集合

!结构

!逻辑结构

!线性结构

!⾮线性结构

!存储结构（物理结构）

!顺序存储

!链接存储

!索引存储

!散列存储

!三要素

!逻辑结构

!存储结构

!数据的运算

!抽象数据类型ADT

!数据对象

!数据关系

!操作集合

!算法

!性质

!输⼊性

!输出性

!有穷性

!确定性

!可⾏性

!定义：解决问题的步骤序列

!程序结构设计 !层次结构设计⽅法

!⾃顶向下

!⾃底向上

!线性表

!顺序表 !在第i个位置插⼊是指前插

!链表

!栈、队列

!栈

!队列

!顺序队列 !荣政中需要牺牲⼀个存储单元

!循环队列

!需要牺牲⼀个存储单元

!是为了解决“假溢出”⽽不是溢出

!头指针front指向队头元素的前⼀个位置

!尾指针rear指向当前队尾元素的位置

!串和数组

!串的存储结构

!顺序存储

!链式存储

!索引存储

!串的模式匹配(m是⼦串，n是主串)

!朴素的模式匹配（Brute-Force）

!时间复杂度

!最坏情况O(m*n)

!最好情况O(m+n)

!若主串⻓为n，⼦串⻓为m，最坏次数为m*(n-

!m+1)

!KMP算法

!模式串的next[j]求法

!查看模式串的最⼤前缀，前两个为01，后⾯的等

!于最⼤前缀数+1

!时间复杂度O(m+n)

!学会KMP模式匹配的过程

!先写出模式串的next数组

!让模式串跟⽬标串⽐较，⽐较到第⼏个位置下次

!就把串移动到next数组对应的位置

!稀疏矩阵

!压缩存储⽅式

!三元组 !表示⽅式

!线性表

!顺序存储

!⼗字链表

!稀疏矩阵转置算法的执⾏时间⼤于⾮压缩存储的

!矩阵转置算法的执⾏时间

!杂碎

!串的特殊性体现在数据元素是⼀个字符

!⼀个任意串就是其⾃身的⼦串

!所谓压缩存储，是指对多个值相同的元素只分配

!⼀个空间，对零元素不分配空间

!树

!⼆叉树

!完全⼆叉树

!⾼度为[_log2n_] + 1 或者[-log2n+1-]（向上取

!整）

!性质

!⼆叉树的结点是有序的

!n个结点中有n+1个指针域为空

!树所有结点度数加⼀等于结点总数

!⼆叉排序树

!⼆叉排序树的删除⽤中序的前驱或后继代替

!平均查找⻓度ASL

!ASL成功 !查找结点的次数/结点总数

!ASL失败 !查找结点失败的次数/失败查找次数 !注：失败查找次数=结点总数+1

!⽣成树 !是极⼩连通⼦图

!遍历 !时间复杂度O(n)

!做题技巧 !度为2的树就是⼀个⼆叉树（

❌

）

!树和森林的遍历

!树

!先根遍历 !对应⼆叉树前序遍历

!后根遍历 !对应⼆叉树中序遍历

!森林

!先序遍历 !对应⼆叉树前序遍历

!中序遍历 !对应⼆叉树中序遍历

!图

!基本概念

!有向图⽤<,>来表示

!⽆向图⽤(,)来表示

!连通分量是极⼤连通⼦图

!⽣成树是极⼩连通⼦图

!存储⽅法

!邻接表

!顶点表

!边表

!邻接矩阵

!最⼩⽣成树

!Prim !时间复杂度O(n^2) 与边数⽆关

!Kruskal !时间复杂度O(eloge) 与边数有关/与顶点数⽆关

!拓扑排序

!时间复杂度O(n+e)

!拓扑排序和深度优先遍历可以判断图中是否存在

!回路

!BFS/DFS !时间复杂度⻅⼩班Word！

!关键路径

!源点到汇点的具有最⼤路径⻓度的路径

!l(i)=e(i)的活动定义为关键活动

!求法

先求ve，⽅法：从前往后找最⻓

再求vl，⽅法：从后往前找最短

求e，⽅法：出边对应节点序号对应的ve值

求l，⽅法：⼊边对应节点序号对应的vl值

!减去边的权值

写出l-e

!散列存储

!索引结构

!索引表 !每⼀项叫做索引项 !形式：（关键字，地址）

!数据表 !是否按关键字顺序排列

!索引顺序结构

!索引⾮顺序结构

!线性索引 !数据表记录是否有序

!稠密索引（⽆序） !⼀个索引项对应数据表中⼀个对象

!稀疏索引（有序） !⼀组记录对应⼀个索引项

!常⽤的查找⽅式 !分块查找（⼜叫索引顺序查找） !块间有序，块内不⼀定有序

!倒排表 !设定次关键字

!散列

!散列表（哈希表）

!定义：散列法存储的线性表

!装填因⼦ !表中结点个数n/散列表空间⼤⼩m

!冲突 !发⽣冲突的两个关键字称为同义词

!平均查找⻓度是装填因⼦的函数

!散列函数

!构造

!数字选择法 !关键字的位数⽐散列表的地址位数多

!平⽅取中法

!直接数字选择困难，先平⽅扩⼤差别后再取其中

!⼏位

!折叠法 !关键字位数过多时折叠结果相加为散列地址

!除留余数法 !模数p⼀般取⼩于等于散列表⻓度的最⼤素数

!基数转换法 !把原数看作另⼀进制的数然后转回原进制

!随机数法 !关键字⻓度不相等时

!解决冲突

!开放地址法

!线性探查法

!模数取值和除留余数法⼀样

!平均查找⻓度

!ASL成功 !⽐较成功次数/关键字个数 !⽐较成功次数就是表中的查找次数之和

!ASL失败 !关键字失败次数/p

!关键字失败次数是贯穿全表（模数以内），将所

!有结点都⽐较，空的也为⼀次，总共⽐较p次！

!⻓度⼤于模数部分的查找失败⻓度不计！ !详⻅12/14年期末题

!⼆次探查法

!随机探查法

!拉链法 !平均查找⻓度

!ASL成功 !⽐较成功次数/关键字个数 !⽐较成功次数要看结点的深度，深度是⼏就加⼏

!ASL失败 !关键字⽐较次数/p

!（关键字⽐较只看拉链所连结点个数，是多少就

!加多少，空结点就是0）

!缩⼩规模算法

!分治与递归

!递归算法 !应⽤

!排列问题

!整数划分问题

!分治算法

!⼦问题独⽴

!应⽤

!⼆分搜索技术

!mid=向上取整[(low+high)/2]

!关键字⽐较最多次数=向下取整(log2n+1)<其中n

!为表中元素个数>

!归并排序 !⼆路归并排序

!时间复杂度O(nlog2n)

!辅助数组空间复杂度O(n)

!快速排序

!栈的最⼤深度为[_log2n_]+1

!栈的空间复杂度O(n)

!辅助空间O(nlogn)

!时间复杂度

!最好O(nlog2n)

!最坏O(n^2)

!掌握两者过程，⼿动模拟

!动态规划

!性质

!最优⼦结构

!⼦问题重叠

!基于性质和动态规划算法的变形 !备忘录⽅法 !⾃顶向下

!经分解得到的⼦问题不⼀定互相独⽴

!⾃底向上

!应⽤

!矩阵连乘

!图像压缩

!最优⼆叉搜索树

!0-1背包问题 !指要么全部放⼊要么不放，不可部分装⼊

!贪⼼算法

!最优⼦结构

!贪⼼选择

!应⽤

!找零钱问题

!背包问题 !可以不放，也可以全部放和部分放

!哈夫曼编码

!单源最短路径

!补充

!概念

!逻辑结构是指元素之间的逻辑关系（少了逻辑俩

!字就错-17年选择1）

!树

!⼀棵树转化为⼆叉树后其形态唯⼀（09年选择

!7）

!图

!关键路径是事件结点⽹络中从源点到汇点的最⻓

!路径

!AOE⽹是⼀种带权的⽆环连通图

!当AOV⽹中存在有向环时⽆法得到该⽹的拓扑结

!构

!索引和散列

!散列存储的基本思想是根据关键字来决定存储地

!址

!排序

!在待排序⽂件基本有序的前提下，直接插⼊排序

!效率⾼（10年选择13）

!平均时间性能为O(nlogn)且空间性能最好的是堆

!排序（10年选择15）

!归并排序在⼀趟结束后不⼀定能选出⼀个元素放

!在其最终位置上（09年选择15）

!冒泡排序最少⽐较n-1次

!树可以为空树，但图不可以为空图

(强)连通图

!n个结点的⽆向图最少需要n-1条边

!n个结点的有向图最少需要n条边

!当⼀个问题的所有⼦问题都⾄少需要求解⼀次

!时，动态规划算法好于备忘录算法

!散列查找法必须解决两个问题

!散列函数设计

!解决冲突

!树有序的判断题

!⼆叉树是每个结点的度不超过2的有序树的特殊

!情况（

❌

）

!⼆叉树中每个结点的两棵⼦树是有序的（

!bingo）

!索引结构的检索分两步

检索索引表

检索数据表

ADT中没有数据类型！

!边权值不相同的带权⽆向图的最⼩⽣成树是唯⼀

!的

!贪⼼选择性质是指所求问题的整体最优解可以通

!过⼀系列（局部最优解）的选择来实现

!当⼦问题空间中的部分⼦问题可以不必求解时，

!备忘录算法优于动态规划算法

!算法的时间复杂度取决于问题的规模和待处理数

!据的初态

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

评论收藏

内容反馈

版权申诉

wyuj2008

2022-08-04

资源内容总结的很到位，内容详实，很受用，学到了~

睡在树上的鱼-_-

粉丝: 3
资源: 9

408考研— 数据结构概念知识点思维导图—所有章节

最新资源

408考研— 数据结构概念知识点思维导图—所有章节

最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理.emmx.zip

408考研数据结构思维导图

408计算机学科专业基础综合--数据结构各章节思维导图.zip

考研408思维导图：计算机网络、数据结构、操作系统、计算机组成原理

最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理.emmx

考研408 数据结构 计算机组成原理 操作系统 计算机网络 考研思维导图

《数据结构》考研复习思维导图

数据结构思维导图-排序.pdf

数据结构思维导图--图.xmind

【超详细】数据结构与操作系统思维导图（王道考研）.rar

408计算机考研—Crypto-密码学，知识概念思维导图

数据结构思维导图.pdf

最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研),附带经典5层结构的中英对照和框架简介.emmx

《数据结构》考研复习思维图.zip

【考研必备】数据结构-思维导图.pdf

数据结构思维导图--查找.xmind

计算机网络思维导图.pdf

数据结构思维导图--查找.pdf

数据结构思维导图-排序.xmind

操作系统思维导图.pdf

组成原理思维导图.pdf

思维导图数据机构--图.pdf

专业课思维导图.zip

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

编译器（gcc、g++）

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

Qt5.9 C++开发指南.pdf 及示例源码

最新资源

最值得收藏的数据结构全部知识点思维导图整理(王道考研), 附带经典题型整理.emmx.zip

最值得收藏的数据结构全部知识点思维导图整理(王道考研), 附带经典题型整理.emmx

考研408 数据结构计算机组成原理操作系统计算机网络考研思维导图

最值得收藏的计算机网络全部知识点思维导图整理(王道考研),附带经典5层结构的中英对照和框架简介.emmx