JAVA面试题（精）.doc

JAVA 面试题集( 基础篇) 什么是数据结构? 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。常用数据结构概念数组(Array) 在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在 C 语言中, 数组属于构造数据类型。一个数组可以分解为多个数组元素, 这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同, 数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。栈(Stack) 是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据, 先进入的数据被压入栈底, 最后的数据在栈顶, 需要读数据的时候从栈顶开始弹出数据( 最后一个数据被第一个读出来)。队列(Queue) 一种特殊的线性表, 它只允许在表的前端( front ) 进行删除操作, 而在表的后端( rear ) 进行插入操作。进行插入操作的端称为队尾, 进行删除操作的端称为队头。队列中没有元素时,称为空队列。链表(Linked List) 是一种物理存储单元上非连续、非顺序的存储结构, 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点( 链表中每一个元素称为结点) 组成, 结点可以在运行时动态生成。每个结点包括两个部分: 一个是存储数据元素的数据域, 另一个是存储下一个结点地址的指针域。树(Tree) 是包含 n( n>0 ) 个结点的有穷集合 K, 且在 K 中定义了一个关系 N,N 满足以下条件: (1) 有且仅有一个结点 k0, 他对于关系 N 来说没有前驱,称 K0 为树的根结点。简称为根( root )。(2)除 K0外,k 中的每个结点, 对于关系 N 来说有且仅有一个前驱。(3) K 中各结点,对关系 N 来说可以有 m 个后继( m>=0 )。图(Graph) 图是由结点的有穷集合 V 和边的集合 E 组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点, 边是顶点的有序偶对, 若两个顶点之间存在一条边, 就表示这两个顶点具有相邻关系。堆(Heap) 在计算机科学中, 堆是一种特殊的树形数据结构, 每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大) ,且根结点的两个子树也是一个堆。散列表(Hash) 若结构中存在关键字和 K 相等的记录, 则必定在 f(K) 的存储位置上。由此, 不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数(Hash function) , 按这个思想建立的表为散列表。常见排序算法: 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。排序算法: 大多数排序算法都给出了每一步的状态, 以方便初学者更容易理解, 通俗易懂, 部分难以理解的排序算法则给出了大量的图示, 也算是一个特色吧经典排序算法- 快速排序 Quick sort 经典排序算法- 插入排序 Insertion sort 经典排序算法- 归并排序 Merge sort 经典排序算法- 冒泡排序 Bubble sort 经典排序算法- 选择排序 Selection sort 经典排序算法- 希尔排序 Shell sort 经典排序算法- 堆排序 Heap sort 序经典排序算法- 奇偶排序 Odd-even sort 经典排序算法- 计数排序 Counting sort 什么是二叉树,相应的算法? 在计算机科学中, 树是一种重要的非线性数据结构, 直观地看, 它是数据元素( 在树中称为结点)按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”( left subtree )和“右子树”( right subtree ) 。二叉树常被用于实现二叉查找树和二叉堆。结点和右结点。简介在计算机科学中, 二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”( left subtree )和“右子树”( right subtree ) 。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树( 不存在度大于 2 的结点) ,二叉树的子树有左右之分, 次序不能颠倒。二叉树的第 i 层至多有 2 的i -1 次方个结点; 深度为 k 的二叉树至多有 2^(k) -1 个结点;对任何一棵二叉树 T ,如果其终端结点数( 即叶子结点数) 为n0 ,度为2 的结点数为 n2 ,则 n0=n2+1 。编辑本段辨析尽管二叉树与树有许多相似之处,但二叉树不是树的特