二级基础知识数据结构与算法_第1页
二级基础知识数据结构与算法_第2页
二级基础知识数据结构与算法_第3页
二级基础知识数据结构与算法_第4页
二级基础知识数据结构与算法_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

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

文档简介

二级基础知识第一章数据结构与算法全国计算机等级考试1.1算法一、算法的概念解决问题准确而完整的描述。特征：可行性、确定性、有穷性、拥有足够的情报。要素：对数据运算操作（算术、逻辑）通过指令序列程序来实现、算法的控制结构（执行顺序）。算法设计方法：列举法：列举所有可能归纳法：从特殊到一般递推：从条件到结论递归：函数的自调用减半递推：中间分冶回溯:反证二、算法复杂度1、时间复杂度（工作量）平均性态（平均值）；最坏情况（最大值）2、空间复杂度（资源）内存资源1.2数据结构的基本概念研究数据结构——逻辑结构、物理结构、运算的实现1、数据结构数据逻辑结构：数据元素及元素间的关系，B=(D,R)存储结构：内存中的存放形式线性与非线性结构：有且仅有一个根结点；一个前件，一个后件只有一个根结点不是线性结构1.3线性表及其顺序存储结构线性表：连续顺序存储，逻辑结构与存储结构一致。插入运算：插入点起所有元素后移删除运算：删除点后所有元素前移1.4栈和队列1、栈只有一个出入口仅有一个元素宽度的巷道， 先进后出入栈、退栈、读栈顶元素2、队列一个出口一个入口仅有一个元素宽度的巷道，先进先出队列移动，循环标志s0空入队；上溢、退队；下溢1.5线性链表线性表的缺点：插入删除上的复杂性、空间的连续性（预留、不够）结点：元素+指针Head---a1*a2---a2*a3…annull双链表栈与队列的链表实现链表的插入删除改变前后元素的指针指向，可以不改变位置循环链表：增加一个表头结点数据不定,最后一指针指向表头1.6树与二叉树1、树层次结构根结点、叶子结点、子结点、深度（层数）、节点的度（分叉数）了解表达式的树表示2、二叉树分叉数少于等于2（左右子树）,一个根节点是二叉树性质A、k层节点少于2^(k-1)B、m深度的树节点总数为2^m-1C、度为2的比度为0节点多一个d、节点为n，则深度为int(log2N)+13、满二叉树与完全二叉树满二叉树不缺枝完全二叉树：仅缺右子树注意完全二叉树节点编号间关系4、二叉树的存储采用双链表5、二叉树的遍历遍历：不重复访问所有结点前序：根、左、右中序：左、根、右后序：左、右、根注意从上到下均按上述顺序例1.33b左前：abdhiejkcflg；中:hdibjekalfcg后:hidjkeblfgca1.7查找技术1、顺序查找无序表、链表2、二分法查找有序表，最多log2N次1.8排序技术1、交换类排序A、昌泡法排序前后顺序交换改变逆序n(n-1)/2B、快速排序法取一个中点两边与中点比较交换2、插入类排序A、简单插入排序从第一个开始小的插在前n(n-1)/2B、希尔排序法分成若于子序列排序后减少子序列个数。

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论