数据结构重要的是理解，面试过程中能说出大体原理即可，不需要硬背。
数据结构栈
队列
链表
数组
字符串
二叉树，AVL树，红黑树，B/B+树，Hash树、Tire树等各种树
一、线性表（重点）
线性表是由N个元素组成的有序序列，也是常见的一种数据结构。重点有两个数组和链表。
1.数组
数组是一种存储单元连续，用来存储固定大小元素的线性表。java中对应的集合实现，比如ArrayList。
2.链表
链表又分单链表和双链表，是在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针连接次序实现的。java中对应的集合实现，比如LinkedList。
二、栈与队列
1.栈
栈是一种运算受限制的线性表，重点掌握其后进先出的特点。表的末端叫栈顶基于操作有push（进栈）和pop（出栈）。Java中stack就是简单的栈实现。
2.队列
也是一种操作受限制的线性表，重点掌握其先进先出的特点。表的前端只允许进行删除操作，表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为对头。Java中很多Queue的实现，消息中间件的队列本质也是基于此的。
三、树（重点）
在非线性结构里面，树是一种非常重要的一种数据结构。基于其本身的结构优势，尤其是查找，应用广泛，其中又以二叉树最为重要。树的话我们这里只重点说一下二叉树。
1.二叉搜索树
二叉搜索树又叫二叉排序树。
性质如下：
（1）若左子树不空，则左子树上所有的节点值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有的值均大于它的根节点的值；
（3）左右子树也分别为二叉排序树；
（4）没有键值相等的结点
2、平衡二叉树
平衡二叉树又叫AVL树。性质如下：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
3、红黑树
红黑树是一种特殊的平衡二叉树，它保证在最坏情况下基本动态集合操作的事件复杂度为O(logn)。
红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
四、图
图是比线性表和树更复杂的数据结构，面试中基本不太会问到，大家有兴建的可以自己去了解下。
算法八大排序以及复杂度分析
二分查找
动态规划，贪心
图算法（深度广度优先，Floyd和Dijkstra）
分治，回溯，分支界限
一：冒泡排序1.算法分析冒泡排序是对于一个数组，从第一个数开始，与下一个数进行比较，大的冒后面，小的冒前面，相邻元素依次比较，完成一次循环，继续下一次循环，直至数组有序。
2.时间复杂度分析由于冒泡排序是两层for循环，所以T=O(n^2)。
3.代码***冒泡排序*/publicclassBubbleSort{publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr;arr=arr[j];arr[j]=tmp;}/***比较相邻元素大小，每次缩减一*
paramarr*/publicstaticvoidbubbleSort(int[]arr){if(arr==null){return;}for(inti=arr.length-1;i0;i--){for(intj=0;ji;j++){if(arr[j]arr[j+1]){swap(arr,j,j+1);}}}}}二：选择排序1.算法分析选择排序是选择数组第一个元素假设为最小元素，与后面的所以元素比较，比其它元素大就交换位置，完成一次循环就从第二个元素开始依次上述过程比较，直至数组有序。
2.时间复杂度分析n^由于选择排序两层for循环，所以T=O(n^2)。
3.代码/***选择排序*/publicclassSelectionSort{publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr;arr=arr[j];arr[j]=tmp;}/***假设第一个值为最小元素，每次循环与后一个元素比较找到最小元素*
paramarr*/publicstaticvoidselectionSort(int[]arr){if(arr==null){return;}for(inti=0;iarr.length-1;i++){intmin=i;for(intj=i+1;jarr.length;j++){min=arr[j]arr[min]?j:min;}swap(arr,i,min);}}}三：插入排序1.算法分析插入排序是从数组第二个元素开始，找前面的数，比较大小，如果前面的数大，就交换位置，然后继续向前比较，。每次从第几个元素开始遍历时都把较小的元素插入到该元素前面，使其前面数组有序，完成一次循环，继续循环下一个元素直至数组有序。
图示：
2.时间复杂度分析由于插入排序两层for循环，T=O(n^2)。
3.代码publicclassInsertionSort{publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr;arr=arr[j];arr[j]=tmp;}publicstaticvoidinsertionSort(int[]arr){if(arr==null){return;}for(inti=1;iarr.length;i++){for(intj=i-1;j=0arr[j]arr[j+1];j--){swap(arr,j,j+1);}}}}四：归并排序1.算法分析
归并排序是利用二分的思想，不断的将数组进行分割为两部分，依次比较每部分的最小元素，将最小的元素放入辅助数组，直到所有元素都插入数组，完成排序。
图示：
2.时间复杂度分析由于归并排序是合并的思想，所有T=O(n*logn)。
3.代码publicclassMergeSort{/***将数组分段排序插入，然后归并排序*
paramarr*paraml*paramm*paramr*/publicstaticvoidmerge(int[]arr,intl,intm,intr){int[]help=newint[r-l+1];inti=0;intp1=l;intp2=m+1;while(p1=mp2=r){help[i++]=arr[p1]=arr[p2]?arr[p1++]:arr[p2++];}while(p1=m){help[i++]=arr[p1++];}while(p2=r){help[i++]=arr[p2++];}for(intj=0;jhelp.length;j++){arr[j+l]=help[j];}}/***递归进行分段归并*paramarr*paraml*paramr*/publicstaticvoidmergeSort(int[]arr,intl,intr){if(l=r){return;}intmid=((r-l)1)+l;mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);merge(arr,l,mid,r);}/***数组归并排序*/publicstaticvoidmergeSort(int[]arr){if(arr==null){return;}mergeSort(arr,0,arr.length-1);}}五：堆排序1.算法分析堆排序的思想是根据二叉树的大根堆和小根堆的概念形成，首先依照数组建立大根堆，之后为了防止某一个元素的变化而引起整个大根堆的变化，建立一个修改二叉树为大根堆的方法，该数组保持大根堆的排序。之后交换大根堆元素，得到有序数组。
图示：
2.时间复杂度分析堆排序建立大根堆的过程，T=O(n*logn)。
3.代码/***堆排序，大根堆，小根堆*/publicclassHeapSort{/***建立大根堆，当孩子结点大于根结点进行交换，没有进行左右孩子结点的比较*
paramarr*paramindex*/publicstaticvoidheapInsert(int[]arr,intindex){while(arr[index]arr[(index-1)/2]){swap(arr,index,(index-1)/2);index=(index-1)/2;}}/***修改数组为大根堆*paramarr*paramindex*paramsize*/publicstaticvoidheapModifiy(int[]arr,intindex,intsize){intleft=2*index+1;while(leftsize){//兄弟之间结点排序intlargest=arr[left+1]arr[left](left+1)size?left+1:left;//孩子结点与根结点进行比较largest=arr[index]arr[largest]?index:largest;if(largest==index){break;}swap(arr,index,largest);index=largest;left=2*index+1;}}/***堆排序*paramarr*/publicstaticvoidheapSort(int[]arr){if(arr==nullarr.length==0){return;}for(inti=0;iarr.length;i++){heapInsert(arr,i);}intsize=arr.length;swap(arr,0,--size);while(size0){heapModifiy(arr,0,size);swap(arr,0,--size);}}publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr;arr=arr[j];arr[j]=tmp;}}六：快速排序1.算法分析
快速排序的基本思想是有荷兰国旗问题的相似，先是随机产生一个范围进行数组的划分，小于区域在左边，等于区域在中间，等于区域在右边，直至数组完成排序。
图示：
2.时间复杂度分析快速排序T=O(n*logn)。
3.代码/***快速排序*/publicclassQuickSort{/***给定范围划分大于区域，等于区域，小于区域排序*
paramarr*paraml*paramr*return*/publicstaticint[]partition(int[]arr,intl,intr){intless=l-1;intmore=r;while(lmore){if(arr[l]arr[r]){swap(arr,++less,l++);}elseif(arr[l]==arr[r]){l++;}else{swap(arr,--more,l);}}swap(arr,more,r);returnnewint[]{less+1,more};}/***产生一个随机范围进行划分排序*paramarr*paraml*paramr*/publicstaticvoidquickSort(int[]arr,intl,intr){if(lr){swap(arr,l+(int)(Math.random()*(r-l+1)),r);int[]partition=partition(arr,l,r);quickSort(arr,l,partition[0]-1);quickSort(arr,partition[1]+1,r);}}/***快速排序*paramarr*/publicstaticvoidquickSort(int[]arr){if(arr==null){return;}quickSort(arr,0,arr.length-1);}publicstaticvoidswap(int[]arr,inti,intj){inttmp=arr;arr=arr[j];arr[j]=tmp;}}面试Java中计算机组成原理知识点计算机系统组成：计算机硬件系统和计算机软件系统
计算机硬件系统：存储器，运算器，控制器，输入设备，输出设备。
计算机软件系统：操作系统，语言处理程序，标准库程序，服务性程序，数据库管理系统，计算机网络软件。
存储器：三级存储结构：高速缓冲存储器（cache），主存储器和外存储器。按存取方式划分为随机存储器（RAM存储器中任何存储单元都能被随机存取），串行访问存储器（SAS存取时间与存储单元的物理位置有关），只读存储器（ROM对内容只能读不能写的存储器）
CPU：控制器（程序计数器，缓存寄存器，指令寄存器，指令译码器，地址寄存器）；运算器（算术逻辑单元，累加寄存器，数据缓冲寄存器和状态标志寄存器）；功能是指令控制，操作控制，时间控制，数据加工。
CPU响应中断的条件：（1）中断源有中断请求（2）CPU允许接受中断请求（3）一般情况下，都要等到一条指令执行完毕后才能响应中断，除非遇到特殊的长指令才允许中途打断它们。
中断处理步骤：（1）关中断（2）保护断点和现场（3）判别中断条件（4）开中断（5）执行中断服务程序（6）退出中断
外围设备：输入设备，输出设备，输入/输出兼容设备，外存设备，过程控制设备（A/D模数转换器、D/A），数据通信及网络设备（调制解调器、网卡）。
系统总线：计算机系统通过总线将CPU、主存储器、I/O设备连接起来，计算机在各部件就可传送地址、数据和控制信息。包含地址线、数据线、控制线，总线通信包含了同步通信和异步通信，常用总线ISA、MCA、PCI、AGP、VESA。
预览时标签不可点收录于话题#个上一篇下一篇