治白癜风 https://m.39.net/pf/a_4687762.html数据运算
查找
1）顺序查找
将待查的元素从头到尾与表中元素进行比较，如果存在，则返回成功；否则，查找失败。此方法效率不高。顺序查找平均查找长度：（n+1）/2。
2）折半查找
二分查找的前提是元素有序（一般是升序），基本思想是拿中间元素A[m]与要查找的元素x进行比较，如果相等，则已经找到，如果A[m]比x大，那么要找的元素一定在A[m]前边（左边），如果A[m]比x小，那么要找的元素一定在A[m]后边（右边）。每进行一次查找，数组规模减半。反复将子数组规模减半，直到发现要查找的元素，或者当前子数组为空。
3）哈希查找
设关键序列为“47,34,13,12,52,38,33,27,3”哈希表长为11，哈希函数为Hash（key）=keymod11，则Hash（47）=47MOD11=3，Hash（34）=34MOD11=1，Hash（13）=13MOD11=2，Hash（12）=12MOD11=1，Hash（52）=52MOD11=8，Hash（38）=38MOD11=5，Hash（33）=33MOD11=0，Hash（27）=27MOD11=5，Hash（3）=3MOD11=3。对于产生的冲突，哈希函数可以采用线性探测法解决冲突，如下所示：
排序
1）直接插入排序
在插入第i个记录时，R1，R2，...Ri-1均已排好序，这时将第i个记录依次与Ri-1，...R2，R1进行比较，找到合适位置插入，插入位置及其后的记录依次向后移动。
例如：
结果：
直接插入排序最好情况下的时间复杂度为O(n)。最坏情况下的时间复杂度为O(n2)。
2）冒泡排序
通过相邻元素（i与i-1）之间的比较和交换，将排序码较小的元素逐渐从底层移向顶层。整个过程像水底的气泡逐渐向上冒由此而得名。冒泡排序时间复杂度为O(n2)。
例如：
3）简单选择排序
一趟从待排序的数据元素中选出最小的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。简单选择排序时间复杂度为O(n2)。
例如：
第一趟，最小值30与第一个元素交换：
第二趟，最小值45与第二个元素交换：
第三趟，最小值55与第三个元素交换：
4）希尔排序
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。希尔排序时间复杂度为O(n1.3)。
先取一个小于n的整数d1，作为第一个增量，把文件的全部记录分成d1个组，即将所有距离为d1倍数序号的记录放在同一个组中，在组内进行直接插入排序；然后取第二个增量d2＜d1，重复上述步骤，依次类推，直到所取的增量di=1,即将所有记录放在同一组进行直接插入排序。例如：
5）快速排序
快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。
对于n个元素的序列，当且仅当满足下列关系时称其为堆，其中,2i和2i+1需不大于n。
（1）Ki≤K2i且Ki≤K2i+1
或
（2）Ki≥K2i且Ki≥K2i+1，其中（1）称为小顶堆（2）称为大顶堆。
堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（建立初始）
6）堆排序
对于n个元素的序列，当且仅当满足下列关系时称其为堆，其中,2i和2i+1需不大于n。
（1）Ki≤K2i且Ki≤K2i+1或Ki≥K2i且Ki≥K2i+1，其中（1）称为小顶堆（2）称为大顶堆。堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（建立初始堆），之后输出堆顶最大关键字（对于大顶堆而言），然后将剩余的关键字再调整成新堆，从而得到次大关键字，如此反复，直到全部关键字排成有序序列为止。堆排序（以大顶堆为例）的建立过程与调整新堆的过程如下所示。堆排序的时间复杂度为O(nlogn)。
7）归并排序
归并排序过程分为三步：
（1）分解。将n个元素分层各含n/2个元素的子序列。
（2）求解。用归并排序对两个子序列递归地排序。
（3）合并。合并两个已经排好序的子序列以得到排序结果。例如：
第一次排序结果：[][]
第二次排序结果：[]
归并排序时间复杂度为O(nlog2n)。
操作系统知识
操作系统（OperatingSystem，简称OS）是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行，其重要性关系到软件基础产业，关系到国家信息化战略，不管是PC时代，移动互联网时代，还是在软件驱动软件定义大行其道的当下，得OS者得天下，失OS者失天下。
OS概述
1、OS两大作用
1）通过资源管理以提高计算机系统的效率
2）改善人机界面向用户提供友好的工作环境
2、OS特征：并发性、共享性、虚拟性、不确定性
3、OS功能：进程管理、文件管理、存储管理、设备管理、作业管理
4、OS分类：批处理、分时、实时、网络（集中、C/S、对等）、分布式、微型、嵌入式
进程管理
1、前趋图
2、进程间通信：同步与互斥、信号量、PV操作
3、进程的状态：三态模型、五态模型
4、进程调度
1）三级调度
2）调度算法：先来先服务、时间片轮转（固定、可变）、优先级调度、多级反馈调度
3）进程优先级确定
5、死锁
1）必要条件：互斥、请求保持、不可剥夺、环路
2）处理：预防、避免（银行家算法）、检测、解除
存储管理
1、存储结构
1）寄存器--cache--主存--外存
2）虚拟
