WatchStor.com — 领先的中文存储网络媒体 | 51CTO旗下网站

新闻资讯 > 存储网络 > 正文
预习篇之动态存储管理、查找、排序
作者: lxy 2018-07-30 17:12 【DataStructureLearning】

 动态存储管理

新用户请求分配内存:一,系统继续从地址的空闲中分配地址,直到无法分配,才回收不在使用的空闲块。二,运行结束,就把它所占的内存释放成空闲块。

分配策略:首次拟合发,最佳拟合法(适用最广),最差拟合法。

查找

(面试笔试重点:

笔试选择题、简答题都有,要会画查找的哈希表、会计算平均查找时间;

面试编程:折半查找;

面试经常考:可能因为我研究生的方向是与数据查询有关的,经常被问到解决哈希冲突的方法,问的细了,还问各个的优缺点,一般何时用)

基本术语:文件,记录、字段(数据的最小单位)、关键字、主关键字、次关键字

静态查找表:查询某个特定的元素是否在表中;检索某个特定的元素的各种属性。查找方法为顺序查找、折半查找、索引顺序表查找

动态查找表:若在查找的同时对表做修改运算(如插入和删除)

二叉排序树,有序表,和折半查找类似;中序遍历此树得到有序序列

平衡二叉树,二叉排序树中每个结点的左、右子树的高度至多相差1。

B树:多路平衡查找树,一种组织和维护外存文件系统非常有效的数据结构。B-树的查找过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。B+树是B-树的一种变形,应用更普遍。

平均查找长度ASL:确定数据元素在表中的位置,需和给定值进行比较的关键字个数的期望值。

哈希表:

别名:散列法,杂凑法或关键字地址计算法等,称为哈希表或散列表。

基本思想,p=H(key),H称为哈希函数,是从关键字空间到存储地址空间的一种映射。

构造方法:直接定地址法、数字分析法、平方取中法、折叠法、除留余数法、伪随机数法

处理冲突的方法:开放地址法(线性探测再散列,二次探测再散列,随机探测在散列)、在hash法、建立公共溢出区、链地址法

排序

(面试笔试重点,重中之重呀!!!!!:

笔试选择题:一般偏概念,要熟练各个排序算法的步骤、时间复杂度、空间复杂度、稳定性、会算移动次数等;

面试经常考:现场编程,让写过递归与非递归的快排、递归与非递归的归并排序、堆排序,所以这章真的真的很重要)

概念:将一组杂乱无章的数据按一定的规律顺序排列起来,使之按关键字递增(0或递减)有序排列。了解稳定排序的意义

排序时间开销:算法执行中关键字比较次数和记录移动次数来衡量。

内部排序:待排序记录存放在计算机随机存储中进行的排序过程。

外部排序:待排序记录数量大,在排序过程中尚需对外存进行访问的排序过程。

方法分类:

插入排序:将待排序记录按其关键字大小插入到前面已经排好序的子表中的适当位置,知道全部插入完全为止。包括:直接插入排序、折半插入排序、2-路插入排序、表插入排序、希尔排序(缩小增量排序,多趟)。主要应用“比较”和“移动”。

交换排序:通过不断比较相邻元素大小,进行交换来实现排序。冒泡排序、快排。

选择排序:每一趟都选出一个最大或最小的元素,并放在合适的位置。有简单选择排序、树形选择排序、堆排序。

归并排序:将2个或两个以上的有序表合成一个新的有序表。

基数排序:通过“分配”和“收集”过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。包括多关键字排序,链式基数排序,

各个排序算法比较:


标签:存储网络 

LecVideo