android数据结构面试

① 数据结构面试常见问题

数据结构面试常见问题

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。下面就是我整理的数据结构面试常见问题，一起来看一下吧。

数据结构面试常见问题 篇1

数据结构与算法，这个部分的内容其实是十分的庞大，要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构，每种算法都学习，但是找工作笔试或者面试的燃银坦时候，要在很短的时间内考察一个人这方面的能力，把每种结构和算法都问一遍不太现实。所以，实际的情况是，企业一般考察一些看起来很基本的概念和算法，或者是一些变形，然后让你去实现。搏弯也许看起来简单，但是如果真让你在纸上或者是计算机上快速地完成一个算法，并且设计测试案例，最后跑起来，你就会发现会很难了。这就要求我们要熟悉，并牢固掌握常用的算法，特别是那些看起来貌似简单的算法，正是这些用起来很普遍的算法，才要求我们能很扎实的掌握，在实际工作中提高工作效率。遇到复杂的算法，通过分析和扎实的基本功，应该可以很快地进行开发。

闲话少说，下面进入正题。

一.数据结构部分

1.数组和链表的区别。（很简单，但是很常考，记得要回答全面）

C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用将已分配的空间释放，不会造成内存空间的浪费。

从逻辑结构来看：数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；链表动态地进行存储分配，可以适应数据动态地增减的.情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。

从内存存储来看：（静态)数组从栈中分配空间（用NEW创建的在堆中）, 对于程序员方便快速,但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦.

1.从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低。

2.链表的一些操作，如链表的反转，链表存在环路的判断（快慢指针），双向链表，循环链表相关操作。

3.队列（特殊的如优先级队列），栈的应用。（比如队列用在消息队列，栈用在递归调用中）

4.二叉树的基本操作

二叉树的三种遍历方式（前序，中序，后序）及其递归和非递归实皮桐现，三种遍历方式的主要应用（如后缀表达式等）。相关操作的时间复杂度。

5.字符串相关

整数，浮点数和字符串之间的转换（atoi,atof,itoa）

字符串拷贝注意异常检查，比如空指针，字符串重叠，自赋值，字符串结束符'/0'等。

二.算法部分

1.排序算法：

排序可以算是最基本的，最常用的算法，也是笔试面试中最常被考察到的算法。最基本的冒泡排序，选择排序，插入排序要可以很快的用代码实现，这些主要考察你的实际编码能力。堆排序，归并排序，快排序，这些算法需要熟悉主要的思想，和需要注意的细节地方。需要熟悉常用排序算法的时间和空间复杂度。

各种排序算法的使用范围总结：

（1）当数据规模较小的时候，可以用简单的排序算法如直接插入排序或直接选择排序。

（2）当文件的初态已经基本有序时，可以用直接插入排序或冒泡排序。

（3）当数据规模比较大时，应用速度快的排序算法。可以考虑用快速排序。当记录随机分布的时候，快排的平均时间最短，但可能出现最坏的情况，这时候的时间复杂度是O(n^2)，且递归深度为n,所需的栈空间问O(n)。

（4）堆排序不会出现快排那样的最坏情况，且堆排序所需的辅助空间比快排要少。但这两种算法都不是稳定的，若要求排序时稳定的，可以考虑用归并排序。

（5）归并排序可以用于内排序，也可以用于外排序。在外排序时，通常采用多路归并，并且通过解决长顺串的合并，产生长的初始串，提高主机与外设并行能力等措施，以减少访问外存额次数，提高外排序的效率。

2,查找算法

能够熟练写出或者是上机编码出二分查找的程序。

3.hash算法

4.一些算法设计思想。

贪心算法，分治算法，动态规划算法，随机化算法，回溯算法等。这些可以根据具体的例子程序来复习。

5.STL

STL(Standard Template Library)是一个C++领域中，用模版技术实现的数据结构和算法库，已经包含在了C++标准库中。其中的vecor,list,stack,queue等结构不仅拥有更强大的功能，还有了更高的安全性。除了数据结构外，STL还包含泛化了的迭代器，和运行在迭代器上的各种实用算法。这些对于对性能要求不是太高，但又不希望自己从底层实现算法的应用还是很具有诱惑力的。

数据结构面试常见问题 篇2

1. 什么是数据结构？

数据结构是数据组织（存储）和操作进行检索和访问的方式。它还定义了不同数据集相互关联、建立关系和形成算法的方式。

2. 描述数据结构的类型？

列表：链接到先前或/和后续数据项的相关事物的集合。

数组：所有相同的值的集合。

Records：字段的集合，每个字段都包含来自单一数据类型的数据。

树：在分层框架中组织数据的数据结构。这种形式的数据结构遵循数据项插入、删除和修改的顺序。

表格：数据以行和列的形式保存。这些与记录相当，因为数据的结果或更改反映在整个表中。

3. 什么是线性数据结构？请举例

如果数据结构的所有元素或数据项都按顺序或线性顺序排列，则数据结构是线性的。元素以非分层方式存储，因此除了列表中的第一个和最后一个元素外，每个项目都有后继者和前驱者。数组、堆栈、字符串、队列和链表，都属于线性数据结构。

4. 数据结构有哪些应用？

数值分析、操作系统、人工智能、编译器设计、数据库管理、图形、统计分析和仿真。

5、文件结构和存储结构有什么区别？

区别在于访问的内存区域。存储结构是指计算机系统内存中的数据结构，而文件结构是指辅助存储器中的存储结构。

6、什么是多维数组？

多维数组的意思是指三维或者三维以上的数组。 三维数组具有高、宽、深的概念,或者说行、列、层的概念,即数组嵌套数组达到三维及其以上。是最常见的多维数组,由于其可以用来描述三维空间中的位置或状态而被广泛使用。

7. 什么是链表数据结构？

这是最常见的数据结构面试问题之一，面试官希望你能给出全面的答案。尝试尽可能多地解释，而不是用一句话来完成你的答案！

它是一个线性数据结构或一系列数据对象，其中元素不存储在相邻的内存位置。元素使用指针链接以形成链。每个元素都是一个单独的对象，称为节点。每个节点有两项：数据字段和对下一个节点的引用。链表中的入口点称为头。如果列表为空，则头部为空引用，最后一个节点具有对空的引用。

一个链表是一个动态的数据结构，其中节点的数量是不固定的，这样的例子有扩大和缩小需求的能力。

它适用于以下情况：

我们处理未知数量的对象或不知道列表中有多少项目；

我们需要从列表中进行恒定时间的插入/删除，就像在时间可预测性至关重要的实时计算中一样；

不需要随机访问任何元素；

该算法需要一个数据结构，无论对象在内存中的物理地址如何，都需要在其中存储对象；

我们需要在列表中间插入项目，就像在优先队列中一样；

一些实现是堆栈和队列、图形、名称目录、动态内存分配以及对长整数执行算术运算

8.什么是双向链表？请举例

它是链表的一种复杂类型（双端 LL），其中一个节点有两个链接，一个连接到序列中的下一个节点，另一个连接到前一个节点。这允许在两个方向上遍历数据元素。

举例：

带有下一个和上一个导航按钮的音乐播放列表

具有 BACK-FORWARD 访问页面的浏览器缓存

浏览器上的撤消功能

9. 为什么要做算法分析？

一个问题可以使用多种解决算法以多种方式解决。算法分析提供对算法所需资源的估计，以解决特定的计算问题。还确定了执行所需的时间和空间资源量。

算法的时间复杂度量化了算法运行所花费的时间，作为输入长度的函数。空间复杂度量化了算法占用的空间或内存量，以作为输入长度的函数运行。

② 经典笔试面试知识整理，数据结构与算法(代码演示)

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

输入描述: array： 待查找的二维数组 target：查找的数字

输出描述:

查找到返回true，查找不到返回false

题目描述：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目描述： 输入一个链表，从尾到头打印链表每个节点的值。

输入描述： 输入为链表的表头

输出描述： 输出为需要打印的“新链表”的表头

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1、题目描述：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

2、题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

3、题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

4、题目描述：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

1、题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

2、题目描述：

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作， 队列中的元素为int类型。

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

③ 面试准备之【数据结构】1——图

共有：邻接表，邻接矩阵

有向图独有：十字链表，边集数组  

无向图独有：邻接多重表  

一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：Arc[i][j]=1,若<vi,vj>∈E或<vi,vj>∈E,反之等于0。

可以看出，无向图的邻接矩阵是对称矩阵，要想知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。

在有向图的邻接矩阵中，某个顶点的出（入）度是这个顶点vi在邻接矩阵中第i 行（列）的元素之和；

        我们发现，当图中的边数相对于顶点较少时，邻接矩阵是对存储空间的极大浪费。我们可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。回忆树结构的孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。

邻接表的创建过程如下：

1）  图中顶点用一个一维数组存储，当然也可以用单链表来存储，不过用数组可以较容易的读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2）  图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为以vi为弧尾的出边表。

从图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息。

firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。

边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指

向边表中下一个结点的指针，比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2.

如果想知道某个顶点的度，就去查找这个顶点的边表中结点的各数。

若要判断顶点vi和vj是否存在边，只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了。

若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。

有向图的邻接表中顶点vi的边表是指以vi 为弧尾 的弧来存储的，这样很容易就可以得到每个顶点的出度。

有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立

一个链接为vi为弧头的表。如下图所示：

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道。反之，逆邻接表解决了入度

却不了解出度的情况。有没有可能把邻接表和逆邻接表结合起来呢？

答案是肯定的，就是把它们整合在一起。这种存储有向图的方法是：十字链表（Orthogonal List）.

我们重新定义顶点表结点结构为：   

|    data    |     firstin   |    firstout    |

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义的 边表 结点结构如下表：

|    tailvex    |    headvex    |    headlink    |    taillink    |

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点（弧头）相同的

下一条边，taillink是指出边表指针域，指向起点（弧尾）相同的下一条边。如果是带权值的网，还可以再增加一个weight域来存储权值。

如下图表示的十字链表：

顶点表依然是存入一个一维数组{v0,v1,v2,v3},以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以v0边表结点的headvex=3,

而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所以headlink和taillink都是空。

这里虚线箭头的含义，其实就是逆邻接表的表示。对于v0来说，它有两条入边，分别来自顶点v1和v2。因此v0的firstin指向顶点v1的边表

结点中headvex为0的结点，虚线（1），接着由入边结点的headlink指向下一个入边顶点v2，虚线（2）。

对于顶点v1,它有一个入边顶点v2，2个出边顶点v0和v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，虚线（3）.

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得

顶点的出度和入度。除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表是相同的，因此很好的应用在有向图中。

十字链表主要是针对有向图的存储结构进行了优化，那么对于无向图的邻接表，有没有问题呢？如果我们在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作。如下图，若要删除(v0,v2)这条边，需要对邻接表结构中右边表的两个结点进行删除，显然这是比较繁琐的。

因此，我们也仿照十字链表的方式，对边表结点的结构进行一些改造，重新定义的边表结点结构如下表：

|    ivex    |     ilink    |     jvex    |     jlink    |

其中ivex和jvex是指某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。

这就是邻接多重表结构。如上图有4个顶点和5条边，先将边表结点画出来。由于是无向图，所以ivex，jvex正反过来都可以，为了绘图

方便，都将ivex值设置的与一旁的顶点下标相同。

下面开始连线，首先连线的（1）（2）（3）（4）是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同。接着，由于顶点v0的(v0,v1)边的

邻边有(v0,v3)和(v0,v2)。因此（5）（6）的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex（ivex）一定要与它本身

的jvex（ivex）的值相同。同理，连线（7）就是指（v1,v0）这条边，它是相当于顶点v1指向（v1,v2）边后的下一条。v2有三条边依附，所以（3）之后就有

了（8）（9）。连线（10）就是顶点v3在连线（4）之后的下一条边。左图一共有5条边，所以右图有10条连线，完全符合预期。

邻接多重表与邻接表的差别， 仅仅是在于同一条边在邻接表中用两个边表结点表示，而在邻接多重表中只有一个结点 。这样对边的操作就方便

多了，若要删除左图的(v0,v2)这条边，只需要将右图的（6）（9）的链接指向改为^即可。

---- 边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

如上图所示，边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次

进行处理的操作，而不适合对顶点相关的操作

路径长度：路径上各活动持续时间的总和（即路径上所有权之和）。

完成工程的最短时间：从工程开始点（源点）到完成点（汇点）的最长路径称为完成工程的最短时间。

关键路径：路径长度最长的路径称为关键路径。

二分图是一类特殊的图，又称为双分图、二部图、偶图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。可以将 U 和 V 当做一个着色：U 中所有顶点为蓝色，V 中所有顶点着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分图无法被二着色

完全二分图 是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。欧拉证明了如下定理： 一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数。 由此可得如下结论：一个连通图有欧拉迹当它至多有两个度数是奇数的顶点。

AOE网Activity On Edge Network：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

图的存储结构-邻接助阵和邻接表  https://blog.csdn.net/dongyanxia1000/article/details/53582186

图的存储结构-十字链表和邻接多重表 https://blog.csdn.net/dongyanxia1000/article/details/53584496

④ 大厂数据分析面试题，大数据结构化面试

作为程序员，你认为代码只要实现功能就可以了吗？
其实，工作2~3年后，你会陪蠢发现随着工作的深入，工作中遇到的问题会变大，处理的数据量也会变大。
一开始，我可能会耐心加班，等机器处理好了再回家，但最后，处理完这些数据通常是在深夜。
面对这样的问题，其实可以用数据结构解决。 仔细整理开发中遇到的问题，会发现很多工作中的问题，用简单的逻辑就能解决。
举个例子，你很熟悉。 如何实时统计99%的业务接口响应时间？
您可能会首先想到，每次查询时，都会按照从小到大的顺序对所有响应时间进行排序。 如果总共有1200个数据，第1188个数据将有99%的响应时间。
很明显，每次用这种方法查询都要排序，效率非常低。
但是，如果知道“堆”数据结构，两个堆就可以非常有效地解决这个问题。
因此，数据结构是提高我们程序员工作效率的利器！
另外，已经工作了2到3年的你，可能想跳槽进入大工厂。
但是，当你去面试时，你经常会碰到数据结构和算法的主题。
目前，数据结构和算法是许多知名企业面试的必考问题。
国内外各大互联网公司在面试过程中，都多少听说了一些有关数据结构和算法的主题。
而且，规模越大的公司，越重视数据结构和算法。
例如，2019年6月，阿里面试中涉及的数据结构主题：
2019年华为面试涉及的数据结构主题：
目前，许多中小企业的面试问题都涉瞎盯及数据结构知识。
其实，你会发现，即使是大小公司，为了筛选更优秀的人磨乱和才，面试问题的难度也会越来越大。
因此，数据结构是进入大厂的重要门槛。
总之，如果你想提高工作效率，进入更大的公司，数据结构和算法是你必须跨越的一道坎。
从易传传媒、亚信、奥鹏教育、程序员到架构师再到技术经理樊延欣老师，前后六年通过各种工作方式打好数据结构基础，在过程中梳理了许多心得，进行了深入思考。
和樊延欣老师一起，死战数据结构，跳过代码陷阱，尽快完成数据结构通关，有机会升职更好。
扫描堆场上的二维码，点击组，立即抢购
原价69元，限时优惠49元
老师怎么解释这门课？#
老师介绍枯燥抽象的结构规则用详细的方法映射到实际项目中。 然后尽量脱离复杂的数学基础，在许多常见的应用场合映射相关理论，降低学习者的理解门槛，使其零基础也能学习。
同时，该课程至少涵盖了50%常见互联网公司中数据结构方面的面试问题纲领，序列和栈是基础性主题，树是更高级的主题，可以理解和把握，发挥面试信心，更上一层楼
#课程介绍#
#我能得到什么？ #
1、提高编程效率和质量
熟悉数据结构原理，复杂的项目无需为需求实现原理而烦恼。
2、优化能力提升
随着了解的加深，能够发现与工作中数据结构特性相违背的代码，并具有优化修改的能力。
3、提高面试成功率
学习50%以上互联网公司数据结构的面试问题纲领，提高面试合格率。
#使用者群组#
1、开发业务系统2年，有相关项目经验，不断重复制作业务车轮希望提高的程序员。
有2、3~5年开发经验，但基础不牢固，想改变体系结构的程序员。
3、基础扎实，需要大量用例和思考才能巩固基础的优秀毕业生/在校生。
#新课初优惠#
限时49元
(成本69 )。
每百人加价十元
第26节课，平均每课2元，持续一个月，改变报关大厂面试机会
享受七折的折扣

自考/成考有疑问、不知道自考/成考考点内容、不清楚当地自考/成考政策，点击底部咨询官网老师，免费领取复习资料：https://www.87dh.com/xl/

⑤ 面试经典数据结构和算法汇总

如果说数据结构是骨架，那么算法就是灵魂。没了骨架，灵魂没有实体寄托；没了灵魂，骨架也是个空壳。两者相辅相成，缺一不可，在开发中起到了砥柱中流的作用。

现在我对各种数据结构和算法做一总结，对比一下它们的效率

1.数据结构篇
1. 如果让你手写个栈和队列，你还会写吗？
2. 开发了那么多项目，你能自己手写个健壮的链表出来吗？
3. 下次面试若再被问到二叉树，希望你能对答如流！
4. 面试还在被红-黑树虐？看完这篇轻松搞定面试官 ！

2.排序算法篇
1. 几个经典的基础排序算法，你还记得吗？
2. 手把手教你学会希尔排序，很简单！
3. 快速排序算法到底有多快？
4. 五分钟教你学会归并排序
5. 简单说下二叉树排序
6. 学会堆排序只需要几分钟
7. 图，这个玩意儿竟然还可以用来排序！

掌握了这些经典的数据结构和算法，面试啥的基本上没什么问题了，特别是对于那些应届生来说。接下来再总结一下不同数据结构和算法的效率问题，做一下对比，这也是面试官经常问的问题。

数据结构常用操作效率对比：

常用排序算法效率的对比：

关于经典的数据结构和算法，就总结到这，本文建议收藏，利用等公交、各种排队之时提升自己。这世上天才很少，懒蛋却很多，你若对得起时间，时间便对得起你。

⑥ android面试题及答案

android面试题及答案

本文是我精心整理的android面试题及答案，欢迎大家参考。

1. 下列哪些语句关于内存回收的说明是正确的? (b ) A、 程序员必须创建一个线程来释放内存

B、 内存回收程序负责释放无用内存

C、 内存回收程序允许程序员直接释放内存

D、 内存回收程序可以在指定的时间释放内存对象

2. 下面异常是属于Runtime Exception 的是(abcd)(多选) A、ArithmeticException

B、IllegalArgumentException

C、NullPointerException

D、BufferUnderflowException

3. Math.round(11.5)等于多少(). Math.round(-11.5)等于多少(c). c A、11 ,-11 B、11 ,-12 C、12 ,-11 D、12 ,-12

4. 下列程序段的输出结果是：(b )

void complicatedexpression_r(){

int x=20, y=30;

boolean b;

b=x>50&&y>60||x>50&&y<-60||x<-50&&y>60||x<-50&&y<-60;

System.out.println(b);

}

A、true B、false C、1 D、011.activity

5. 对一些资源以及状态的操作保存，最好是保存在生命周期的哪个函数中进行(d) A、onPause() B、onCreate() C、 onResume() D、onStart()

6. Intent传递数据时，下列的数据类型哪些可以被传递(abcd)(多选) A、Serializable B、charsequence C、Parcelable D、Bundle

7. android 中下列属于Intent的作用的是(c) A、实现应用程序间的数据共享

B、是一段长的生命周期，没有用户界面的程序，可以保持应用在后台运行，而不会因为切换页面而消失

C、可以实现界面间的切换，可以包含动作和动作数据，连接四大组件的纽带

D、处理一个应用程序整体性的工作

8. 下列属于SAX解析xml文件的优点的是(b) A、将整个文档树在内存中，便于操作，支持删除，修改，重新排列等多种功能

B、不用事先调入整个文档，占用资源少

C、整个文档调入内存，浪费时间和空间

D、不是长久驻留在内存，数据不是持久的，事件过后，若没有保存数据，数据就会

消失

9. 下面的对自定style的方式正确的是

A、

B、

C、

fill_parent

D、

fill_parent

10. 在android中使用Menu时可能需要重写的方法有(ac)。(多选) A、onCreateOptionsMenu()

B、onCreateMenu()

C、onOptionsItemSelected()

D、onItemSelected()

11. 在SQL Server Management Studio 中运行下列T-SQL语句，其输出值(c)。 SELECT @@IDENTITY

A、 可能为0.1

B、 可能为3

C、 不可能为-100

D、 肯定为0

12. 在SQL Server 2005中运行如下T-SQL语句，假定SALES表中有多行数据，执行查询之 后的结果是(d)。 BEGIN TRANSACTION A

Update SALES Set qty=30 WHERE qty<30

BEGIN TRANSACTION B

Update SALES Set qty=40 WHEREqty<40

Update SALES Set qty=50 WHEREqty<50

Update SALES Set qty=60 WHEREqty<60

COMMITTRANSACTION B

COMMIT TRANSACTION A

A、SALES表中qty列最小值大于等于30

B、SALES表中qty列最小值大于等于40

C、SALES表中qty列的数据全部为50

D、SALES表中qty列最小值大于等于60

13. 在android中使用SQLiteOpenHelper这个辅助类时，可以生成一个数据库，并可以对数据库版本进行管理的方法可以是(ab) A、getWriteableDatabase()

B、getReadableDatabase()

C、getDatabase()

D、getAbleDatabase()

14. android 关于service生命周期的onCreate()和onStart()说法正确的是(ad)(多选题) A、当第一次启动的时候先后调用onCreate()和onStart()方法

B、当第一次启动的时候只会调用onCreate()方法

C、如果service已经启动，将先后调用onCreate()和onStart()方法

D、如果service已经启动，只会执行onStart()方法，不在执行onCreate()方法

15. 下面是属于GLSurFaceView特性的是(abc)(多选) A、管理一个surface，这个surface就是一块特殊的内存，能直接排版到android的视图

view上。

B、管理一个EGL display，它能让opengl把内容渲染到上述的surface上。

C、让渲染器在独立的线程里运作，和UI线程分离。

D、可以直接从内存或者DMA等硬件接口取得图像数据

16. 下面在AndroidManifest.xml文件中注册BroadcastReceiver方式正确的

A、

android:name="android.provider.action.NewBroad"/>

B、

android:name="android.provider.action.NewBroad"/>

C、

android:name="android.provider.action.NewBroad"/>

D、

android:name="android.provider.action.NewBroad"/>

17. 关于ContenValues类说法正确的是(a) A、他和Hashtable比较类似，也是负责存储一些名值对，但是他存储的名值对当中的

名是String类型，而值都是基本类型

B、他和Hashtable比较类似，也是负责存储一些名值对，但是他存储的名值对当中的

名是任意类型，而值都是基本类型

C、他和Hashtable比较类似，也是负责存储一些名值对，但是他存储的名值对当中的

名，可以为空，而值都是String类型

D、他和Hashtable比较类似，也是负责存储一些名值对，但是他存储的名值对当中

的名是String类型，而值也是String类型

18. 我们都知道Hanlder是线程与Activity通信的桥梁,如果线程处理不当，你的机器就会变得越慢，那么线程销毁的方法是(a) A、onDestroy()

B、onClear()

C、onFinish()

D、onStop()

19. 下面退出Activity错误的方法是(c) A、finish()

B、抛异常强制退出

C、System.exit()

D、onStop()

20. 下面属于android的动画分类的有(ab)(多项) A、Tween B、Frame C、Draw D、Animation

21. 下面关于Android dvm的进程和Linux的进程,应用程序的进程说法正确的是(d) A、DVM指dalivk的虚拟机.每一个Android应用程序都在它自己的进程中运行,不一定拥有一个独立的Dalvik虚拟机实例.而每一个DVM都是在Linux中的一个进程,所以说可以认为是同一个概念.

B、DVM指dalivk的虚拟机.每一个Android应用程序都在它自己的进程中运行,不一定拥有一个独立的Dalvik虚拟机实例.而每一个DVM不一定都是在Linux中的一个进程,所以说不是一个概念.

C、DVM指dalivk的虚拟机.每一个Android应用程序都在它自己的进程中运行,都拥有一个独立的Dalvik虚拟机实例.而每一个DVM不一定都是在Linux中的一个进程,所以说不是一个概念.

D、DVM指dalivk的虚拟机.每一个Android应用程序都在它自己的进程中运行,都拥有一个独立的 Dalvik虚拟机实例.而每一个DVM都是在Linux中的一个进程,所以说可以认为是同一个概念.

22. Android项目工程下面的assets目录的作用是什么bA、放置应用到的图片资源。

B、主要放置多媒体等数据文件

C、放置字符串，颜色，数组等常量数据

D、放置一些与UI相应的布局文件，都是xml文件

23. 关于res/raw目录说法正确的是(a)A、 这里的文件是原封不动的存储到设备上不会转换为二进制的格式

B、这里的'文件是原封不动的存储到设备上会转换为二进制的格式

C、 这里的文件最终以二进制的格式存储到指定的包中

D、这里的文件最终不会以二进制的格式存储到指定的包中

24. 下列对android NDK的理解正确的是(abcd )A、 NDK是一系列工具的集合

B、 NDK 提供了一份稳定、功能有限的 API 头文件声明。

C、 使 “java+C” 的开发方式终于转正，成为官方支持的开发方式

D、 NDK 将是 Android 平台支持 C 开发的开端

二.文件存储方式

三.SQLite数据库方式

四.内容提供器(Content provider)方式

二、Android面试填空题

25. android中常用的四个布局是framlayout，linenarlayout，relativelayout和tablelayout。26. android 的四大组件是activiey，service，broadcast和contentprovide。27. java.io包中的objectinputstream和objectoutputstream类主要用于对对象(Object)的读写。28. android 中service的实现方法是：startservice和bindservice。29. activity一般会重载7个方法用来维护其生命周期，除了onCreate(),onStart(),onDestory() 外还有onrestart,onresume,onpause,onstop。30. android的数据存储的方式sharedpreference,文件,SQlite,contentprovider,网络。31. 当启动一个Activity并且新的Activity执行完后需要返回到启动它的Activity来执行 的回调函数是startActivityResult()。32. 请使用命令行的方式创建一个名字为myAvd,sdk版本为2.2,sd卡是在d盘的根目录下,名字为scard.img， 并指定屏幕大小HVGA.____________________________________。33. 程序运行的结果是：_____good and gbc__________。 public classExample{

String str=new String("good");

char[]ch={'a','b','c'};

public static void main(String args[]){

Example ex=new Example();

ex.change(ex.str,ex.ch);

System.out.print(ex.str+" and ");

Sytem.out.print(ex.ch);

}

public void change(String str,char ch[]){

str="test ok";

ch[0]='g';

}

}

34. 在android中，请简述jni的调用过程。(8分)1)安装和下载Cygwin，下载 Android NDK

2)在ndk项目中JNI接口的设计

3)使用C/C++实现本地方法

4)JNI生成动态链接库.so文件

5)将动态链接库复制到java工程，在java工程中调用，运行java工程即可

35. 简述Android应用程序结构是哪些?(7分)Android应用程序结构是：

Linux Kernel(Linux内核)、Libraries(系统运行库或者是c/c++核心库)、Application

Framework(开发框架包)、Applications (核心应用程序)

36. 请继承SQLiteOpenHelper实现：(10分) 1).创建一个版本为1的“diaryOpenHelper.db”的数据库，

2).同时创建一个 “diary” 表(包含一个_id主键并自增长，topic字符型100

长度， content字符型1000长度)

3).在数据库版本变化时请删除diary表，并重新创建出diary表。

publicclass DBHelper extends SQLiteOpenHelper{

public final static String DATABASENAME ="diaryOpenHelper.db";

public final static int DATABASEVERSION =1;

//创建数据库

public DBHelper(Context context,Stringname,CursorFactory factory,int version)

{

super(context, name, factory,version);

}

//创建表等机构性文件

public void onCreate(SQLiteDatabase db)

{

String sql ="create tablediary"+

"("+

"_idinteger primary key autoincrement,"+

"topicvar100),"+

"contentvar1000)"+

")";

db.execSQL(sql);

}

//若数据库版本有更新，则调用此方法

public void onUpgrade(SQLiteDatabasedb,int oldVersion,int newVersion)

{

String sql = " ifexists diary";

db.execSQL(sql);

this.onCreate(db);

}

}

37. 页面上现有ProgressBar控件progressBar，请用书写线程以10秒的的时间完成其进度显示工作。(10分)答案

publicclass ProgressBarStu extends Activity {

private ProgressBar progressBar = null;

protected void onCreate(BundlesavedInstanceState) {

super.onCreate(savedInstanceState);

setContentView(R.layout.progressbar);

//从这到下是关键

progressBar = (ProgressBar)findViewById(R.id.progressBar);

Thread thread = new Thread(newRunnable() {

@Override

public void run() {

int progressBarMax =progressBar.getMax();

try {

while(progressBarMax!=progressBar.getProgress())

{

intstepProgress = progressBarMax/10;

intcurrentprogress = progressBar.getProgress();

progressBar.setProgress(currentprogress+stepProgress);

Thread.sleep(1000);

}

} catch(InterruptedException e) {

// TODO Auto-generatedcatch block

e.printStackTrace();

}

}

});

thread.start();

//关键结束

}

}

38. 请描述下Activity的生命周期。 必调用的三个方法：onCreate() --> onStart() --> onResume()，用AAA表示

(1)父Activity启动子Activity，子Actvity退出，父Activity调用顺序如下

AAA --> onFreeze() --> onPause() --> onStop() --> onRestart()--> onStart(),onResume() …

(2)用户点击Home，Actvity调用顺序如下

AAA --> onFreeze() --> onPause() --> onStop() -- Maybe -->onDestroy() – Maybe

(3)调用finish()， Activity调用顺序如下

AAA --> onPause() --> onStop() --> onDestroy()

(4)在Activity上显示dialog，Activity调用顺序如下

AAA

(5)在父Activity上显示透明的或非全屏的activity，Activity调用顺序如下

AAA --> onFreeze() --> onPause()

(6)设备进入睡眠状态，Activity调用顺序如下

AAA --> onFreeze() --> onPause()

39. 如果后台的Activity由于某原因被系统回收了，如何在被系统回收之前保存当前状态? onSaveInstanceState()

当你的程序中某一个Activity A在运行时，主动或被动地运行另一个新的Activity B，这个时候A会执行onSaveInstanceState()。B完成以后又会来找A，这个时候就有两种情况：一是A被回收，二是A没有被回收，被回收的A就要重新调用onCreate()方法，不同于直接启动的是这回onCreate()里是带上了参数savedInstanceState;而没被收回的就直接执行onResume()，跳过onCreate()了。

40. 如何将一个Activity设置成窗口的样式。 在AndroidManifest.xml 中定义Activity的地方一句话android:theme="@android:style/Theme.Dialog"或android:theme="@android:style/Theme.Translucent"就变成半透明的

41. 如何退出Activity?如何安全退出已调用多个Activity的Application?对于单一Activity的应用来说，退出很简单，直接finish()即可。

当然，也可以用killProcess()和System.exit()这样的方法。

但是，对于多Activity的应用来说，在打开多个Activity后，如果想在最后打开的Activity直接退出，上边的方法都是没有用的，因为上边的方法都是结束一个Activity而已。

当然，网上也有人说可以。

就好像有人问，在应用里如何捕获Home键，有人就会说用keyCode比较KEYCODE_HOME即可，而事实上如果不修改framework，根本不可能做到这一点一样。

所以，最好还是自己亲自试一下。

那么，有没有办法直接退出整个应用呢?

在2.1之前，可以使用ActivityManager的restartPackage方法。

它可以直接结束整个应用。在使用时需要权限android.permission.RESTART_PACKAGES。

注意不要被它的名字迷惑。

可是，在2.2，这个方法失效了。

在2.2添加了一个新的方法，killBackgroundProcesses()，需要权限android.permission.KILL_BACKGROUND_PROCESSES。

可惜的是，它和2.2的restartPackage一样，根本起不到应有的效果。

另外还有一个方法，就是系统自带的应用程序管理里，强制结束程序的方法，forceStopPackage()。

它需要权限android.permission.FORCE_STOP_PACKAGES。

并且需要添加android:sharedUserId="android.uid.system"属性

同样可惜的是，该方法是非公开的，他只能运行在系统进程，第三方程序无法调用。

因为需要在Android.mk中添加LOCAL_CERTIFICATE := platform。

而Android.mk是用于在Android源码下编译程序用的。

从以上可以看出，在2.2，没有办法直接结束一个应用，而只能用自己的办法间接办到。

现提供几个方法，供参考：

1、抛异常强制退出：

该方法通过抛异常，使程序ForceClose。

验证可以，但是，需要解决的问题是，如何使程序结束掉，而不弹出Force Close的窗口。

2、记录打开的Activity：

每打开一个Activity，就记录下来。在需要退出时，关闭每一个Activity即可。

3、发送特定广播：

在需要结束应用时，发送一个特定的广播，每个Activity收到广播后，关闭即可。

4、递归退出

在打开新的Activity时使用startActivityForResult，然后自己加标志，在onActivityResult中处理，递归关闭。

除了第一个，都是想办法把每一个Activity都结束掉，间接达到目的。

但是这样做同样不完美。

你会发现，如果自己的应用程序对每一个Activity都设置了nosensor，在两个Activity结束的间隙，sensor可能有效了。

但至少，我们的目的达到了，而且没有影响用户使用。

为了编程方便，最好定义一个Activity基类，处理这些共通问题。

42. 请介绍下Android中常用的五种布局。FrameLayout(框架布局)，LinearLayout (线性布局)，AbsoluteLayout(绝对布局)，RelativeLayout(相对布局)，TableLayout(表格布局)