湖南省二级新增知识点..ppt

公共基础知识(二级)公共基础知识总复****主讲人:高艳霞第一章数据结构与算法1、算法基本特征、时间复杂度(会计算简单算法的)、空间复杂度2、基本概念数据结构的研究内容、目的、定义、逻辑结构与存储结构3、线性结构几个特例(线性表、栈、队列)的特征与操作比较:顺序表不需要指针、栈和队列都有两个指针、指向位置的区别、满与空的判别4、顺序存储和链式存储的区别、操作的异同,各有什么优缺点,注意同样存在链栈、链队,头指针与头结点的区别。链表的头指针与头结点图头指针:指向第一个结点;头结点:链表中为方便运算而设置的结点。a2a1an^…Head510270地址:5头结点头指针总结:顺序表的优缺点顺序表的优点:1)无需为表示结点间的逻辑关系而增加额外的存储空间。2)可以方便地随机存取表中的任一结点。顺序表的缺点:1)插入和删除运算不方便。须移动大量结点,效率较低。2)存取空间要预先分配,动态扩充和分配都不方便。总结:链表的优缺点链表的优点:1)插入和删除很方便。2)不需要实现估计“容量”,扩充和动态分配空间很容易。链表的缺点:1)为表示结点间的逻辑关系需要增加额外的空间。2)不能实现随机访问。5、树与二叉树1)根、叶子、度、深度的概念2)二叉树的五条性质:总个数、叶子数、高度的计算。完全二叉树中,由总结点个数求叶子与非叶子结点的简单做法。3)三种遍历方法:由其中两种求另一种遍历的序列一定要知道。6、查找技术顺序查找适合于任何线性表,最坏情况需要比较n次二分查找只适应于顺序存储的有序表,二分查找的结束直到查找成功或子表长度为0才停止,要会计算它的次数;最坏情况需要比较log2n二分查找举例设有有序表(5,16,23,42,58,67,79,81)使用二分法查找元素23。元素地址123456789值51623354258677981第一次第二次第三次Low=1High=9Mid=5High=4Mid=2Low=3Mid=3Mid=[(Low+High)/2]7、排序技术排序的目的、分类、各种排序的思想与时间复杂度,冒泡、简单插入、简单选择的比较次数要会计算。