数据结构_(严蔚敏C语言版)_学习、复习提纲
16页1、期末复习第一章绪论复习数据:计算机处理的信息总称 数据项:最小单位数据元素:最基本单位/概念4数据对象:元素集合数据结构:相互之间存在一种或 多种特定关系的数据元素集合。数据结构逻辑结构概念:数据元素之间的关系线性结构:一对一非线性结构树:一对多图:多对多存储结构顺序存储结构 链表存储结构 索引。散列。数据运算算法描述:指令的有限有序序列有穷性 确定性 可行性 输入 输出时间复杂度空间复杂度1、计算机算法必须具备输入、输出、可行性、确定性、有穷性5个特性。2、算法分析的两个主要方面是空间复杂度和时间复杂度。3、数据元素是数据的基本单位。4、数据项是数据的最小单位。5、数据结构是带结构的数据元素的集合。6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。第二章线性表复习前趋后继线性表基本特点一顺序存储结构基本运算-随机存取插、删效率低插入删除一个指针域+一个数据域多占空间查找费时插、删效率高无法查找前趋结点链表存储结构双向链表特点:单链表+前趋指针域I运算插入删除循环 链表特点:单链表的尾结点指针 指向附加头结点。运算:联接、一个指向后继结点的指针1、在双链表中,每个结点有两个指针
2、域,包括一个指向前驱结点的指针2、线性表采用顺序存储,必须占用一片连续的存储单元3、线性表采用链式存储,便于进行插入和删除操作4、线性表采用顺序存储和链式存储优缺点比较。5、简单算法第三章栈和队列复习栈的概念:在一端操作的线性表栈的特点:先进后出 LIFO存储结构栈初始化运算算法t 进栈push出栈pop队列概念:在两端操作的线性表队列特点:先进先出FIFO顺序队列循环队列假溢出 队空:front=rear上 队满:front=(rear+1)%MAXSIZE链队列队空:rear基本运算【初始化判空进队出队I取队首元素1、栈和队列的异同点。2、栈和队列的基本运算3、出栈和出队4、 基本运算第四章串复习定义:由n(1)个字符组成的有限序列S=ClC2c3 Cn”串长度、空白串、空串。紧缩格式顺序串J 非紧缩格式I以字节为单位的存储格式(C语言用数组或指针表示)余小申单字符链表串链表串I多字符链表串串变量的存储映像:串名、串值对应关系表S strlen(s)串长度strcat(s1,s2)联接基本运算 0)个元素的有限序列概念:长度、深度、原子、子表表头:Head(A尸a 1表尾:Tail
3、(A)=(a2,a3,an)表结点 tag=11 hptp存储结构(链表)原子结点tag=0 hptp第六章树复习定义:双亲、树深、递归定义,不为空孩子、叶子、兄弟、祖先 结点的度、有序树、无序树(二叉树定义:树中结点的度W 2有序树可为空树(n=0)1 .第i层至多有2i-1个结点。2 .数深为k的二叉树,至多有2k-1 个结点。3 .no=n2+14 .n个结点的二叉树树深为 Log2n/2+15 .双亲结点为i,做孩子结点的编 号为2i,有孩子2i+1。顺序:满、完全二叉树链表:二叉、三叉链表二叉树存储方式二叉树的遍历先根遍历序列 已知先根、中根序列 中根遍历序列卜画树;已知后根、中I后根遍历序列根序列画树;线索二叉树先根线索T 中根线索I后根线索下 线索树的画法树、森林树、森林与二叉树的相互转换树、森林的遍历树的应用二叉排序树左中右小中大哈夫曼树,哈夫曼树的画法 t编码:左0右11、三个结点可以组成 2种不同形态的树。2、一个稀疏矩阵 Am*n采用三元组形式表示,若完成了其的转置运算要经过哪几步:矩阵的行、列数值互换 、矩阵元素所在行列值互换、元素在矩阵中排列的位置)重新排列
4、3、若二叉树中每一层结点的个数都达到了最大,则称为一棵满二叉树。4、树最适合用来表示现有元素之间具有分支层次关系的数据5、哈夫曼树是带权路径长度最小的二叉树。6、以下那些项为用十字链表表示的稀疏矩阵元素结点信息元素所在行和列、元素的值 、指向该元素所在行的下一个元素的指针、指向该元素所在列的下一个元素的指针。7、一个广义表可以为其它广义表所共享。8、广义表可以是一个多层次的结构。9、压缩存储的三角矩阵和对称矩阵的存储空间相同。10、广义表中的元素类型可以不相同。11、两个稀疏矩阵的和仍为稀疏矩阵。12、二叉树的先序遍历序列中,任意一个结点均处在其孩子结点的前面。13、对于一棵具有n个节点的树,该树中所有节点的度数之和为n-1 o14、树和森林的遍历中有中序遍历。15、二叉树用链式存储时,空链域数多于非空链域数。16、由森林转换成二叉树,其根节点的右子树总是空的。17、哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。18、当一棵具有n个叶子结点的二叉树的 WPL直为最小时,称其树为 Huffman树,且其二叉树的形状必是唯一的。x19、某二叉树的先序遍历序列和中序遍历序列相
《数据结构_(严蔚敏C语言版)_学习、复习提纲》由会员大米分享,可在线阅读,更多相关《数据结构_(严蔚敏C语言版)_学习、复习提纲》请在金锄头文库上搜索。
关于三爱活动的倡议书
旅游安全生产联检工作总结总结
推荐-幼儿园专用表格大全
高考常考重难点命题规律探究(四)大气运动
绿色施工方案(专项方案)
汽车齿轮配件生产项目可行性研究报告模板备案审批
我的学习榜样满分精品作文摘选3篇
2023年度校本培训工作计划书
18颐和园自主学习任务单
年产200万套不锈钢日用品餐具申请报告可行性研究报告
2022年公司管理者的个人年度工作总结
高三数学每天一练半小时:第80练 高考大题突破练——概率 Word版含答案
棚室土壤磷超标咋办
2023年国家网络安全宣传周心得体会范本集锦四篇(全文完整)
2006年郑州金水区招教考试真题试卷
工商管理专业本科生实习汇报
企业设备工作总结(三篇).doc
如何提高小学数学练习的科学性和针对性
环保行业个人工作总结(4篇).doc
激光加工设备项目资金申请报告写作模板
2023-12-08 5页
2022-12-24 3页
2022-12-04 6页
2023-10-28 6页
2022-11-01 11页
2023-10-22 8页
2022-10-25 8页
2022-11-07 17页
2023-12-18 3页
2022-12-12 11页