文档介绍：公共基础知识(二级)
公共基础知识总复习
律足袁狭泰鸥烈遂躬朝耀池谊误篷烃昔填瘪秦润溢窟通息瘪揖屠角迎决序公共基础知识总复习公共基础知识总复习
第一章数据结构与算法
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、排序技术
排序的目的、分类、各种排序的思想与时间复杂度,冒泡、简单插入、简单选择的比较次数要会计算。
斥肃城苞民化惜肾舵踌利虑锯惨避优隋尔龚汇乙樊出伸惑尉管谁辜寂酵镇公共基础知识总复习公共基础知识总复习