文档介绍：公共基础知识(二级)
公共基础知识总复习
主讲人:杨亦
库文档分享
第一章数据结构与算法
1、算法
基本特征、时间复杂度(会计算简单算法的)、空间复杂度
2、基本概念
数据结构的研究内容、目的、定义、逻辑结构与存储结构
库文档分享
3、线性结构几个特例(线性表、栈、队列)的特征与操作比较:
顺序表不需要指针、栈和队列都有两个指针、指向位置的区别、满与空的判别
4、顺序存储和链式存储的区别、操作的异同,各有什么优缺点,注意同样存在链栈、链队,头指针与头结点的区别。
库文档分享
链表的头指针与头结点图
头指针:指向第一个结点;
头结点:链表中为方便运算而设置的结点。
a2
a1
an
^
…
Head
5
10
2
70
地址:
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。
元素地址
1
2
3
4
5
6
7
8
9
值
5
16
23
35
42
58
67
79
81
第一次
第二次
第三次
Low=1
High=9
Mid=5
High=4
Mid=2
Low=3
Mid=3
Mid=[(Low+High)/2]
库文档分享
7、排序技术
排序的目的、分类、各种排序的思想与时间复杂度,冒泡、简单插入、简单选择的比较次数要会计算。
库文档分享