前言

首先什么是性能：在同一个手机里面，同样功能的app，哪个跑的快，哪个不卡，哪个就性能高。我们这篇文章就是解决学习那些性能慢的问题：

1）我们要找到性能低的地方，并且把这些地方解决掉，这个就是性能优化；

2）我们要让自己具备一开始写的代码，它运行起来就是高性能的，所以这个就是设计思想和代码质量优化。一个app的性能好不好我们需要从两个层面努力。

第一个层面：从写代码的时候就需要注意，让自己的代码是高性能高可用的代码，这个过程是书写高性能代码；

第二个层面：对已经成型的代码通过工具检查代码的问题，通过检查到的问题来指导我们进行代码的删改，这个过程被称为调优。如何写出高性能的代码呢？那就需要我们具备深厚的代码功底，这就是代码的基础。

今天我们讲的就是里面的一个重要分支，数据结构！希望对大家有帮助，由于篇幅问题，所以题目只能放一些代表性的，需要完整版的（有答案解析）以及关于性能优化这方面的Android高级工程师学习资料的 私信我 【学习】 即可免费领取 全部系统学习资料！

学习知识导图一、单项选择题

(1)一个算法应该是（ ）

A) 程序

B) 问题求解步骤的描述

C) 要满足五个基本属性

D) A和C

(2)算法指的是（ ）。

A) 计算机程序

B) 解决问题的计算方法

C) 排序算法

D) 解决问题的有限运算序列。

(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

A) 存储结构 B) 逻辑结构 C) 算法 D)操作

(4)从逻辑上可以把数据结构分为（ ）两大类。

A) 动态结构、静态结构

B) 顺序结构、链式结构

C) 线性结构、非线性结构

D) 初等结构、构造型结构

(5)下列叙述中正确的是( )。　　

A）一个逻辑数据结构只能有一种存储结构　　

B）数据的逻辑结构属于线性结构，存储结构属于非线性结构　　

C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

(6)数据的基本单位是（　　　）

A) 数据项 B) 数据类型 C) 数据元素 D) 数据变量

(7)下列程序的时间复杂度为（　　　）i=0；s=0；while（s<n）{ i++；s=s+i；}

A) O（） B) O（） C) O（n） D) O（n2）

(8)下列程序段的渐进时间复杂度为（ ）。for( int i=1;i<=n;i++)for( int j=1;j<= m; j++)A[i][j] = ij ;

A）O(m2) B）O(n2) C）O(mn) D）(m+n)

(9)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）。

A）O(n） B) O(nlogn) C) O(n3) D) O(n2)

(10)在下面的程序段中，对x的赋值语句的频度为（ ）。for ( i=1; i>=n ; i++)for ( j=1; j>=n ; j++)x:=x+1;

A) O(2n) B)O(n) C) O(n2) D) O(log2n)

(11)程序段 for ( i:=n-1; i<=1; i–）for ( j:=1; j>=i ; j++)if (a[j]>a[j+1] ){ t=a[j]; a[j]= a[j+1]; a[j+1]= t; }其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）。

A) O(n） B) O(nlogn) C) O(n3) D) O(n2)

(12) 设有一个递归算法如下：int fact(int n){ /* 大于等于0 /

if ( n<=0 ) return 1 ;

else return nfact (n-1) ;}则计算fact(n)需要调用该函数的次数为（ ）。

A) n B) n+1 C) n+2 D) n-1

(13)下述程序段中语句①的频度是（　　　）。s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)s+=j;A) B) C) D)

(14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（　　　）。

A)单链表

B)仅有头指针的单循环链表

C)双链表

D)仅有尾指针的单循环链表

(1)求循环链表中当前结点的后继和前驱的时间复杂度分别是（　　）。

A) O(n)和O(1) B) O(1)和O(1) C) O(1)和O(n) D) O(n)和O(n)

(15)求单链表中当前结点的后继和前驱的时间复杂度分别是（　　）。

A) O（n）和O（1）

B) O（1）和O（1）

C) O（1）和O（n）

D) O(n)和O（n）

(16)非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（　　）。

A) rear->next= =head

B) rear->next->next= =head

C) head->next= =rear

D) head->next->next= =rear

(17)从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　　）。

A)n-i

B)n-i+1

C)n-i-1

D)i

(18)已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（　　）。

A)1

B)2

C)3

D)4

(19)假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（　　）。

A) R[3][3][3]

B) R[3][3][4]

C) R[4][3][5]

D) R[4][3][4]

(20)设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（　　）。

A) 13

B) 35

C) 17

D) 36

(21)线性表采用链式存储时，节点的存储的地址（ ）。

A) 必须是不连续的

B) 连续与否均可

C) 必须是连续的

D) 和头节点的存储地址相连续

(22)用链表表示线性表的优点是（ ）。

A) 便于随机存取

B) 花费的存储空间比顺序表少

C) 数据元素的物理顺序与逻辑顺序相同

D) 便于插入与删除

(23)链表不具有的特点是（ ） 。

A) 插入、删除不需要移动元素

B) 可随机访问任一元素

C) 不必事先估计存储空间

D) 所需空间与线性长度成正比

(24)在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )。

A) n-i+1 　　　 B) i　　 C) i+1 　　　　 D) n-i

(25)采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（ ）。

A) n　　　 B) n/2　　 C) (n-1)/2 　　　　 D) (n+1)/2

二、填空题

(1)数据结构是一门研究非数值计算的程序设计问题中计算机的 （ ） 以及它们之间的 （ ）和运算等的学科。

(2)数据结构被形式地定义为（D, R），其中D是 —— 的有限集合，R是D上的 —— 有限集合。

(3)数据结构包括数据的 —— 、数据的 —— 和数据的 —— 这三个方面的内容。

(4)数据结构按逻辑结构可分为两大类，它们分别是 —— 和 —— 。

(5)线性结构中元素之间存在一对一关系，树形结构中元素之间存在——关系，图形结构中元素之间存在——关系。

(6)在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点—— 后续结点，其余每个结点有且只有1个后续结点。

(7)在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 —— 个前驱结点；叶子结点没有 —— 结点，其余每个结点的后续结点数可以任意多个 。

(8)在图形结构中，每个结点的前驱结点数和后续结点数可以 —— 。

(9)数据的存储结构可用四种基本的存储方法表示，它们分别是——— —— —— ——

(10)数据的运算最常用的有5种，它们分别是—— —— —— —— ——

(11)一个算法的效率可分为 —— —— —— ——

(12)对于给定的n个元素,可以构造出的逻辑结构有 四种。

(13)顺序映象的特点是借助元素在存储器中的 来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的 表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定 而算法的实现依赖于采用的 存储结构。

(14)数据类型是一组___________的值集合以及定义在这个值集合上的一组操作的总称。

(15)数据对象是___________的数据元素的集合，是数据的一个子集。

(16)如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 型运算。

(17)算法的 特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。

(18)算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的 做出估计，从中得到算法执行时间的信息。

(19)T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率 ——，称作算法的渐进时间复杂度，简称时间复杂度。

(20)若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为 ——，辅助空间为o（1）

(21)在带有头结点的单链表中L中，第一个元素结点的指针是 ——————

(22)在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= ——————

(23)设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: ——————————

(24)对于栈操作数据的原则是 ——。(25)设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。

简答题

1.怎么理解数据结构？

2.什么是斐波那契数列？

3.迭代和递归的特点，并比较优缺点

4.了解哪些查找算法，时间复杂度都是多少？

5.了解哪些排序算法，并比较一下，以及适用场景

6.快排的基本思路是什么？最差的时间复杂度是多少？如何优化？

7.AVL树插入或删除一个节点的过程是怎样的？

8.什么是红黑树？

9.100盏灯问题

10.老鼠和毒药问题，加个条件，必须要求第二天出结果

11.海量数据问题

12.（手写算法）二分查找

13.（手写算法）反转链表

14.（手写算法）用两个栈实现队列

15.（手写算法）多线程轮流打印问题

16.（手写算法）如何判断一个链有环/两条链交叉

17.（手写算法）快速从一组无序数中找到第k大的数/前k个大的数

18.（手写算法）最长（不）重复子串

私信我 【学习】 即可免费领取 全部Android高级工程师系统学习资料！