Java程序员面试分类真题12

Java程序员面试分类真题12(总分：100.00，做题时间：120分钟)一、单项选择题(总题数：30，分数：60.00)1.

在主存和CPU之间增加Cache的目的是______。

（分数：2.00）

A.增加内存容量

B.为程序员编程提供方便

C.解决CPU与内存间的速度匹配问题

√

D.提高内存工作的可靠性解析：计算机的存储系统由主存、外存和Cache(缓存)组成。Cache存取速度快、容量小，它存储的内容是主存中经常被访问的程序和数据的剐本。通过Cache可以提高计算机的运行速度，解决CPU与内存之问的速度匹配问题。所以，选项C正确。

对于选项A、选项B和选项D，其描述内容均不是Cache的目的。所以，选项A、选项B和选项D错误。2.

在多级存储体系中，“cache-主存”结构的作用是解决______。

（分数：2.00）

A.主存容量不足

B.辅存与CPU速度不匹配

C.主存与辅存速度不匹配

D.主存与CPU速度不匹配

√解析：3.

对于顺序存储的线性数组，访问结点和增加结点、删除结点的时间复杂度分别为______。

（分数：2.00）

A.A.O(n)，O(n)

B.B.O(n)，O(1)

C.C.O(1)，O(n)

√

D.D.O(1)，O(1)

E.解析：对于线性数组，它支持随机访问，因此，访问结点的时间复杂度为O(1)，增加结点、删除结点的时候需要移动新增结点或待删除结点后面的元素，因此，时间复杂度为O(n)。所以，选项C正确。4.

在有n个结点的顺序表中，算法的时间复杂度是O(1)的操作是______。

（分数：2.00）

A.访问第i个结点(1＜=i＜=n)和求第i个结点的直接前驱(2＜=i＜=n)

√

B.在第i个结点后插入一个新结点(1＜=i＜=n)

C.删除第i个结点(1＜=i＜=n)

D.将n个结点从小到大排序解析：线性表也叫顺序表，在线性表中的数据元素，其关系是一一对应的，即除了第一个数据元素和最后一个数据元素之外，其他数据元素都是首尾相接的。

本题中，对于选项A，线性表是随机存取结构，当对其执行插入和删除操作时，只要不是针对最后一个元素，此时都需要进行元素的搬家，最坏情况下的时间复杂度是O(n)。因此，访问第i个结点(1＜=i＜=n)和求第i个结点的直接前驱(2＜=i＜=n)，其时间复杂度都为O(1)。所以，选项A正确。

对于选项B和选项C，由于插入和删除操作都需要移动元素，此时算法的时间复杂度为O(n)，它与题目要求的O(1)的时间复杂度不相符。所以，选项B与选项C错误。

对于选项D，将n个结点从小到大排序的时间复杂度通常介于O(n)与O(n^2)之间，它与题目要求的O(1)的时间复杂度不相符。所以，选项D错误。5.

二叉树是非线性数据结构，以下关于其存储结构的描述中，正确的是______。

（分数：2.00）

A.它不能用链式存储结构存储

B.它不能用顺序存储结构存储

C.顺序存储结构和链式存储结构都不能使用

D.顺序存储结构和链式存储结构都能存储

√解析：二叉树是非线性数据结构，即每个数据结点至多只有一个前驱，但可以有多个后继，可以使用顺序存储和链式存储两种结构来存储。以下将分别对这两种存储结构进行介绍。

(1)顺序存储结构

二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系。这种结构特别适用于近似满二叉树。这种方法的缺点是可能会有大量空间的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2^k-1个结点存储空间。图1和图2分别给出完全二叉树和非完全二叉树的存储示意图。

图1

完全二叉树的存储方式

图2

非完全二叉树的存储方式

(2)链式存储结构

二叉树的链式存储结构是指用链表来表示一棵二叉树。

每个结点有一个数据域，两个指针域分别指向左孩子和右孩子。其结点结构为：lchicddatarchild

图3给出了一个二叉树的链表存储方式。

图3

链表存储方式

通过上面的分析可知，选项D正确。6.

线性表如果要频繁地执行插入和删除操作，该线性表采取的存储结构应该是______。

（分数：2.00）

A.散列

B.顺序

C.链式

√

D.索引解析：线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素。

链式存储结构又叫链接存储结构，在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻。因此，它没有顺序存储结构所具有的弱点，但也同时失去了顺序表可随机存取的优点。

链式存储结构有以下5个特点：

1)比顺序存储结构的存储密度小(每个结点都由数据域和指针域组成，所以，相同空间内假设全存满，则链式存储比顺序存储所能存储的数据少)。

2)逻辑上相邻的结点物理上不必相邻。

3)插入、删除灵活(不必移动结点，只要改变结点中的指针)。

4)查找结点时链式存储要比顺序存储慢。

5)每个结点由数据域和指针域组成。

链式结构的插入和删除操作只需要修改插入和删除结点以及其前驱结点的指针域即可，而顺序存储结构在插入和删除操作的时候需要执行大量数据的移动操作。由此可以看出，顺序表适合随机访问，不适合插入和删除操作，而链式表适合插入和删除操作，不适合随机访问操作。散列表适合查找运算，索引表在插入和删除的时候还需要修改索引表，由此链式表最适合插入和删除操作。所以，选项C正确。7.

链表要求元素的存储地址______。

（分数：2.00）

A.必须连续

B.部分连续

C.必须不连续

D.连续与否均可

√解析：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。由此可见，可以通过结点的指针域找到下一个结点，存储地址是否连续并不重要。所以，选项A、选项B和选项C错误，选项D正确。

需要注意的是，数组与链表不同，对数组的访问是通过数组的下标来实现的，所以，对于数组而言，存储地址必须是连续的。

所以，本题的答案为D。8.

以链接方式存储的线性表(x1、x2、...、Xn)，访问第i个元素的时间复杂度为______。

（分数：2.00）

A.O(1)

B.O(n)

√

C.O(logn)

D.O(n^2)解析：单链表查找的时候从头结点开始一直找下一个结点，如果要查找的元素在最后，就相当于找了n次，所以，时间复杂度为O(n)。所以，选项B正确。9.

从表中任意一个结点出发可以依次访问到表中其他所有结点的结构是______。

（分数：2.00）

A.线性单链表

B.双向链表

C.循环链表

√

D.线性链表解析：对于选项A，单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。根据定义可知，单链表中中间部分出发只能访问结点的后续结点。因此，选项A错误。

对于选项B，双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。但是从中间结点出发只能访问所有的后继结点，或者只能访问所有的前驱结点。因此，选项B错误。

对于选项C，循环链表是另一种形式的链式存储结构(链表最后一个结点的指针域指向链表的首结点)。它的特点是可以从任意结点出发依次访问所有结点。因此，选项C正确。

对于选项D，线性链表是一个更大的概念，单链表、双向链表都可以看作是一种线性表。因此，选项D错误。

所以，本题的答案为C。10.

以下关于链式存储结构的描述中，错误的是______。

（分数：2.00）

A.查找结点时链式存储比顺序存储快

√

B.每个结点由数据域和指针域组成

C.比顺序存储结构的存储密度小

D.逻辑上不相邻的结点物理上可能相邻解析：链式存储结构又叫链接存储结构，指的是在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻，因此，它没有顺序存储结构所具有的缺点，但同时它也失去了顺序表可随机存取的优点。

具体而言，链式存储结构具有以下几个特点：

1)每个结点都是由数据域和指针域组成的。

2)它比顺序存储结构的存储密度小。由于链式存储结构的每个结点都是由数据域和指针域组成，所以，在相同空间内，顺序存储结构比链式存储结构存储的元素更多。

3)逻辑上相邻的结点物理上不必相邻。

4)插入结点、删除结点灵活，原因在于此时它不必移动结点，只要改变结点中的指针即可。

5)当查找结点时，链式存储要比顺序存储慢。

通过上面的分析可知，选项B与选项C正确，选项A错误。

对于选项D，因为对于链式存储结构，数据的逻辑关系与物理关系没有直接关系，逻辑上相邻的结点在物理上可能相邻也可能不相邻，而逻辑上不相邻的结点在物理上也是有可能相邻也有可能不相邻。所以，选项D正确。

所以，本题的答案为A。11.

如果用数组S[0...n]作为两个栈S1和S2的存储结构，对任何一个栈，只有当S全满时才不能做入栈操作，那么为S1、S2这两个栈分配空间的最佳方案是______。

（分数：2.00）

A.S1的栈底位置为0，S2的栈底位置为n+1

√

B.S1的栈底位置为1，S2的栈底位置为n/2

C.S1的栈底位置为0，S2的栈底位置为n/2

D.S1的栈底位置为1，S2的栈底位置为n+1解析：栈是一个后进先出、先进后出的数据结构，当采用选项A的方案时，两个栈的栈底位置分别设在了存储空间的两端，栈项各自向中间延伸，两个栈的空间就可以相互调节，充分共享所有的存储空间，互补余缺，只有在整个存储空间被占满时，才会发生上溢，这样产生上溢的概率要小得多。所以，选项A正确。

如果采用选项B或者选项C的方案，相当于把数组平均分配给两个栈，各自有独立的存储空间，即使当栈s2为空的时候，栈s1最多能存放的元素个数为n/2。所以，选项B、选项C错误。

对于选项D，s1的栈底位置设置不正确，所以，选项D错误。

所以，本题的答案为A。12.

一个栈的入栈序列是ABCDE，则该栈的出栈序列不可能是______。

（分数：2.00）

A.EDCBA

B.DECBA

C.DCEAB

√

D.ABCDE解析：栈是一个后进先出的数据结构，可以根据这个特点进行分析。

对于选项A，可以把字符A、B、C、D、E按顺序入栈，然后出栈，此时就可以得到选项A中的序列。所以，选项A正确。

对于选项B，由于序列第一个元素为字符D，那么肯定需要先把字符A、B、C、D入栈，然后，字符D出栈得到第一个元素字符D，由于序列的下一个元素为字符E，所以，下一步需要把字符E入栈再出栈，此时就可以得到字符E，接下来栈中的元素依次出栈得到序列CBA。所以，选项B正确。

对于选项C，序列第一个元素为字符D，那么肯定需要先把字符A、B、C、D入栈，然后字符D出栈得到第一个元素字符D，由于第二个元素为字符C，那么下一步字符C出栈得到序列DC，接下来序列为E，那么需要把字符E入栈再出栈得到字符E，此时栈中字符A在栈底，字符B在栈顶，只能得到出栈序列BA，而无法得到序列AB。因此，不可能得到输出序列DCEAB。所以，选项C错误。

对于选项D，字符A、B、C、D、E五个元素每个元素入栈后就马上出栈，此时就可以得到这个序列。所以，选项D正确。

所以，本题的答案为C。13.

如果让元素a、b、c依次进栈，那么出栈次序不可能是______。

（分数：2.00）

A.c，a，b

√

B.b，a，c

C.c，b，a

D.a，c，b解析：14.

往一个栈中顺序push下列元素：ABCDE，其pop可能的序列中，不可能存在的情况是______。

（分数：2.00）

A.BACDE

B.ACDBE

C.AEBCD

√

D.AEDCB解析：15.

如果入栈序列是a1，a3，a5，a2，a4，a6，出栈序列是a5，a4，a2，a6，a3，a1，那么栈的容量最小是______。

（分数：2.00）

A.2

B.3

C.4

√

D.5解析：本题解题的关键是了解栈的后进先出的性质。

通过入栈序列与出栈序列可以模拟一下其具体的出栈与入栈过程，过程如下：

第一步：a1进栈，此时栈中元素为1。

第二步：a3进栈，此时栈中元素为2。

第三步：a5进栈，此时栈中元素为3。

第四步：根据进栈出栈顺序，a5出栈，a2进栈，此时栈中元素为3。

第五步：a4进栈，此时栈中元素为4。

第六步：根据进栈出栈顺序，a4出栈，此时栈中元素为3。

第七步：根据进栈出栈顺序，a2出栈，此时栈中元素为2。

第八步：a6进栈，此时栈中元素为3。

第九步：根据进栈出栈顺序，a6出栈，此时栈中元素为2。

第十步：根据进栈出栈顺序，a3出栈，此时栈中元素为1。

第十一步：根据进栈出栈顺序，a1出栈，此时栈中元素为0。

由以上分析可知，栈中元素最多的时候为4个，所以，栈容量至少为4，选项C正确。16.

采用顺序存储的栈，执行入栈运算，栈顶指针的变化是______。

（分数：2.00）

A.top++

√

B.top--

C.不变

D.(top++)++解析：栈是一种特殊的线性表，在实现的时候可以把顺序表的头看作栈底。栈顶索引top指向栈顶的下一个位置，初始化top=0，每次压栈操作：首先，向索引为top的位置放入入栈的元素，然后，top+1，由此可见，入栈操作栈指针的变化为top++；而对于出栈操作，首先要判断栈是否为空(top=0时栈为空)，如果不为空，则首先执行top-1操作，然后再取出top所在位置的元素，此时指针的变化为--top。所以，选项A正确。17.

在循环队列中，用数组A[0，m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是______。

（分数：2.00）

A.(front-rear+1)%m

B.(rear-front+1)%m

C.(front-rear+m)%m

D.(rear-front+m)%m

√解析：队列是一种线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，进行插入操作的端称为队尾，进行删除操作的端称为队头。

在循环队列中，队头指向的是队首元素的前一个位置，队尾指向队尾元素所在位置。循环队列的front和rear必有一个不指向实质元素，否则，无法判断队列满或空。而且队列头的下标有可能会小于队列尾的下标。所以，当前队列中的元素个数是(rear-froot+m)%m。所以，选项D正确。18.

下列情况中，不能使用栈(stack)来解决问题的是______。

（分数：2.00）

A.将数学表达式转换为后辍形式

B.实现递归算法

C.高级编程语言的过程调用

D.操作系统分配资源(例如CPU)

√解析：栈的性质是先进先出。

对于选项A，后缀表达式指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)，例如，对于表达式(2+1)*3，其后缀表达式为21+3*，通过定义可知，可以通过栈来实现。所以，选项A正确。

对于选项B，根据递归算法的性质可知，可以通过栈来实现。所以，选项B正确。

对于选项C，根据过程调用的性质可知，可以通过栈来实现。所以，选项C正确。

对于选项D，操作系统资源分配有多种分配策略，例如先到先执行，此时就可以使用队列来完成。

所以，选项D不正确。

所以，本题的答案为D。19.

以下关于排序算法的描述中，正确的是______。

（分数：2.00）

A.快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)

B.堆排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)

C.冒泡排序的平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)

√

D.归并排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)解析：各种算法的性能见下表。各种排序算法的性能排序方法最好时间复杂度平均时间复杂度最坏时间复杂度辅助存储稳定性备注简单选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定n小时较好直接插入排序O(n)O(n^2)O(n^2)O(1)稳定大部分已有序时较好冒泡排序O(n)O(n^2)O(n^2)O(1)稳定n小时较好希尔排序O(n)O(nlogn)O(ns)1＜s＜2O(1)不稳定s是所选分组快速排序O(nlogn)O(nlogn)O(n^2)O(logn)不稳定n大时较好堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定n大时较好归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定n大时较好

所以，本题的答案为C。20.

下列排序方法中，属于稳定排序的是______。

（分数：2.00）

A.选择排序

B.希尔排序

C.堆排序

D.归并排序

√解析：所谓稳定排序，指的是一个序列中的相同的元素在排序完毕之后，它们的顺序仍然不会改变。反之，排序算法则是不稳定的。

对于选项A，选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。例如，序列37329，第一遍选择第1个元素3会和第4个元素2交换，那么原序列中两个3的相对前后顺序就被破坏了，所以，选择排序不是一个稳定的排序算法，选项A错误。

对于选项B，希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以，插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于涉及多次插入排序，而一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以，希尔排序是不稳定的，选项B错误。

对于选项C，堆的结构是结点i的孩子为2*i和2*i+1结点，大顶堆要求父结点大于等于其2个子结点，小顶堆要求父结点小于等于其2个子结点。对于一个长为n的序列，堆排序的过程是从第n/2开始和其子结点共3个值选择最大(大顶堆)或者最小(小顶堆)，这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1，n/2-2，…，1这些父结点选择元素时，就会破坏稳定性。有可能第n/2个结点的父结点与它的孩子结点(假设这个结点的值为X)进行了交换，而第n/2-1个结点如果也有一个孩子结点的值为X，但是这个父结点没有与孩子结点进行交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法，选项C错误。

对于选项D，归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不会交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是否受到破坏?没有，合并过程中，可以保证如果两个当前元素相等，则把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序是稳定的排序算法，选项D正确。

所以，本题的答案为D。21.

排序算法的稳定是指关键码相同的记录排序前后相对位置不发生改变，下面排序算法中，______是不稳定的。

（分数：2.00）

A.插入排序

B.冒泡排序

C.快速排序

√

D.归并排序解析：22.

有字符序列(Q，H，C，Y，P，A，M，S，R，D，F，x)，那么新序列(F，H，C，D，P，A，M，Q，R，S，Y，X)是下列______算法一趟扫描结果。

（分数：2.00）

A.堆排序

B.快速排序

√

C.希尔排序

D.冒泡排序解析：对于选项A，堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素(即二叉树的根结点)进行交换后，堆的最后一个元素即为最大记录；接着将前n-1个元素(即不包括最大记录)重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程，直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。

对于选项B，快速排序的原理如下：对于一组给定的记录，首先，通过一趟排序后，将原序列分为两部分，其中前半部分的所有记录均比后半部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

对于选项C，希尔排序的实质是分组插入排序，该方法又称缩小增量排序，基本思想如下：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成)，分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。因此，直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的。

对于选项D，冒泡排序的原理是临近的数字两两进行比较，按照从小到大或者从大到小的顺序进行交换，这样一趟排序后，最大或最小的数字被交换到了最后一位，针对所有的元素重复以上的步骤，每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

所以，本题的答案为B。23.

快速排序算法在序列已经有序的情况下的复杂度为______。

（分数：2.00）

A.O(nlogn)

B.(n^2)

√

C.O(n)

D.O(n^2logn)解析：快速排序是目前被认为最好的一种内部排序方法。快速排序算法处理的最好情况指每次都是将待排序列划分为均匀的两部分，通常认为快速排序在平均情况下的时问复杂度为O(nlogn)。但是，如果初始记录序列按关键字有序或基本有序，那么此时快速排序将蜕化为冒泡排序，其时间复杂度为O(n^2)。

那么对于其他排序算法，当序列已经有序时，又是哪种情况呢?无论原始序列中的元素如何排列，归并排序和堆排序算法的时间复杂度都是O(nlogn)。插入排序是将一个新元素插入已经排列好的序列中。如果在数据已经是升序的情况下，新元素只需插入到序列尾部，这就是插入排序的最好情况，此时，时间复杂度为O(n)。所以，选项B正确。24.

下列排序算法中，对一个list排序的最快方法是______。

（分数：2.00）

A.快速排序

√

B.冒泡排序

C.二分插入排序

D.线性排序解析：对于选项A，需要注意的是，在C++语言中，list采用的是双向列表来存储的，因此，它比较适合用快速排序(快速排序不需要随机的访问元素)。此时的时间复杂度为O(nlogn)。所以，选项A正确。

对于选项B，冒泡排序也是对数据顺序遍历，不需要随机访问，因此，它也适合对list进行排序，但由于算法的时间复杂度为O(n^2)，没有快速排序效率高。所以，选项B不正确。

对于选项C，首先需要弄清楚二分插入排序的基本思想。二分插入排序的基本思想如下：假设列表[0...n]被分成两部分，其中一部分[0...i]为有序序列，另一部分[i+1...n]为无序序列，排序的过程为从无序序列中取一个数d，利用二分查找算法找到d在有序序列中的插入位置并插入。不断重复上述步骤，直到无序序列中的元素全部插入有序序列，就完成了排序。由此可以看出，二分插入排序需要对列表中的元素进行随机访问，因此，它不适合对list进行排序。所以，选项C不正确。

对于选项D，只有当被排序的元素满足某种特定的条件的时候，线性排序算法才能有较好的性能。由于list有非常好的通用性，对任意的数据类型都能排序，因此，线性排序算法不适用对list进行排序。所以，选项D不正确。

所以，本题的答案为A。25.

用某种排序方法对关键字序列(25，84，21，47，15，27，68，35，20)进行排序，序列的变化情况如下所示：

(1)20，15，21，25，47，27，68，35，84

(2)15，20，21，25，35，27，47，68，84

(3)15，20，21，25，27，35，47，68，84

则采用的排序方法是______。

（分数：2.00）

A.选择排序

B.快速排序

√

C.希尔排序

D.归并排序解析：读者要想解答出本题，必须对各种排序算法的原理有着较为深刻的认识。以下将分别对这几种排序算法进行介绍与分析。

对于选项A，选择排序是一种简单直观的排序算法，它的基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个位置的记录进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。

对于选项B，快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理为：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

对于选项C，希尔排序也称为“缩小增量排序”，它的基本原理如下：首先，将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，再对所有元素进行一次直接插入排序。希尔排序也是形成部分有序的序列。

对于选项D，归并排序是利用递归与分治技术将数据序列划分成越来越小的子序列(子序列指的是在原来序列中找出一部分组成的序列)，再对子序列排序，最后再用递归步骤将排好序的子序列合并成为越来越大的有序序列。归并排序会在第一趟结束后，形成若干个部分有序的予序列，并且长度递增，直到最后的一个有序的完整序列。

本题中，很容易发现，第一个序列前4个数都小于等于25，而后5个数都大于25，很显然满足快速排序的方法，而且根据以上对各种排序算法的分析可知，选项B正确。26.

有字符序列{Q，H，C，Y，P，A，M，S，R，D，F，X}，则新序列{F，H，C，D，P，A，M，O，R，S，Y，X}是下列______算法一趟扫描的结果。

（分数：2.00）

A.二路归并排序

B.快速排序

√

C.步长为4的希尔排序

D.冒泡排序解析：27.

初始序列为{1，8，6，2，5，4，7，3}的一组数，采用堆排序的方法进行排序，当建堆(小根堆)完毕时，堆所对应的二叉树的中序遍历序列为______。

（分数：2.00）

A.8，3，2，5，1，6，4，7

√

B.3，2，8，5，1，4，6，7

C.3，8，2，5，1，6，7，4

D.8，2，3，5，1，4，7，6解析：堆是一种特殊的树形数据结构，其每个结点都有一个值，通常提到的堆都是指一棵完全二叉树。

堆排序是树形选择排序，在排序过程中，将R[1...N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

堆一般分为大顶堆和小顶堆两种不同的类型。对于给定n个记录的序列(r(1)，r(2)，…，r(n))，当且仅当满足条件(r(i)＞=r(2i)且r(i)＞=r(2i+1))时称为大顶堆，此时，堆顶元素为最大值。对于给定n个记录的序列(r(1)，r(2)，…，r(n))，当且仅当满足条件(r(i)＜=r(2i)且r(i)＜=r(2i+1))时称为小顶堆，此时，堆顶元素必为最小值。

以小顶堆为例：堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个小顶堆，将堆的最后一个元素与堆顶元素(即二叉树的根结点)进行交换后，堆的最后一个元素即为最小记录；接着将前(n-1)个元素(即不包括最小记录)重新调整为一个小顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最大记录，此时可得到一个有序序列。

堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。

建立小顶堆的方法为：从最后一个非叶子结点开始，找出这个结点、左孩子、右孩子的最小值与这个结点的值交换，由于交换可能会引起孩子结点不满足小顶堆的性质，所以，每次交换之后需要重新对被交换的孩子结点进行调整。对于题目所给的数组构建小顶堆的过程如图所示。

构建小顶堆过程

由此可以得出，树的中序遍历序列为83251647。所以，选项A正确。28.

已知数组序列为{46、36、65、97、76、15、29}，以46为关键字进行一趟快速排序后，结果为______。

（分数：2.00）

A.29、36、15、46、76、97、65

√

B.29、15、36、46、76、97、65

C.29、36、15、46、97、76、65

D.15、29、36、46、97、76、65解析：第一趟排序过程如下：

初始化关键字{46、36、65、97、76、15、29}。

第一次交换后：{29、36、65、97、76、15、46}(从右向左找到小于46的值并交换)。

第二次交换后：{29、36、46、97、76、15、65}(从左向右找到大于46的值并交换)。

第三次交换后：{29、36、15、97、76、46、65}(从右向左找到小于46的值并交换)。

第四次交换后：{29、36、15、46、

76、97、65}(从左向右找到大于46的值并交换)。

所以，选项A正确。29.

以下排序算法中，需要开辟额外的存储空间的是______。

（分数：2.00）

A.选择排序

B.归并排序

√

C.快速排序

D.堆排序解析：30.

下列排序方法中，辅助空间为O(n)的是______。

（分数：2.00）

A.归并排序

√

B.堆排序

C.选择排序

D.希尔排序解析：二、多项选择题(总题数：5，分数：10.00)1.

以下操作中，数组比线性表速度更快的是______。

（分数：2.00）

A.原地逆序

√

B.头部插入

C.返回中间结点

√

D.返回头部结点

E.选择随机结点

√解析：线性结构的基本特征为：

1)集合中必然存在唯一的一个“第一元素”。

2)集合中必然存在唯一的一个“最后元素”。

3)除最后一个元素外，均有唯一的后继。

4)除第一个元素外，均有唯一的前驱。

数组是随机存取的，线性表是逻辑上连续但物理上分开存放的，因此，查询、修改操作数组更快，但插入、删除等操作线性表更快。所以，选项B与选项D错误，选项E正确。

对于选项A，当需要进行原地逆序时，数组比线性表速度更快。对于数组的逆序，具体做法如下：定义两个下标，一个下标i表示数组首元素，一个下标j表示数组尾元素，交换i与j两个位置的元素值，同时执行++i，--i操作，一共需要经过n/2次交换(n表示数组的长度)。而链表的逆序需要修改指针的指向，需要更多的操作。所以，选项A正确。

对于选项C，数组可以通过array[length/2]访问中间结点，链表需要依次查找到中间结点，所以，数组比线性表更快。所以，选项C正确。

所以，本题的答案为ACE。2.

下列数据结构中，同时具有较高的查找和删除性能的是______。

（分数：2.00）

A.有序数组

B.有序链表

C.AVL树

√

D.Hash表

√解析：首先介绍常见的数据结构的操作性能：

1)有序数组：查找的时候可以采用二分查找法，因此，查找的时间复杂度为O(logn)，其中，n表示数组序列的长度。由于数组中的元素在内存中是顺序存放的，因此，删除数组中的一个元素后，数组中后面的元素就需要向前移动。在最坏的情况下，如果删除数组中的第一个元素，那么数组中后面的n-1个元素都需要向前移动，移动操作的次数为n-1，因此，此时的时间复杂度为O(n)。插入操作与删除操作类似，都需要数组中元素的移动，因此，其时间复杂度也为O(n)。

2)有序链表：链表(以单链表为例)的存储特点为：每个结点的地址存储在它的前驱结点的指针域中，对链表的遍历只能从链表的首结点开始遍历，因此，此时查找的时间复杂度为O(n)，其中，n表示链表的长度。对于删除和插入操作，虽然删除和插入操作的时间复杂度都为O(1)(因为不需要结点的移动操作)，但是在删除前首先需要找到待删除结点的地址，这个操作的时间复杂度为O(n)，在插入结点前首先也要找到结点应该被插入的地方，这个操作的时间复杂度也为O(n)，因此，插入与删除的时间复杂度都为O(n)。

3)AVL树(平衡二叉树)：AVL树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。由于树的高度为logn，其中，n表示树中结点的个数，因此，查找的时间复杂度为O(logn)，显然，删除与插入的时间复杂度也为O(logn)。

4)Hash表：Hash表通过Hash值就可以定位到元素的位置，因此，查找、插入与删除的时间复杂度都为O(1)。

5)普通数组：查找的时候只能顺序地遍历数组，在最坏的情况下需要对数组中所有的元素遍历一遍，因此，此时的时间复杂度为O(n)，其中，n表示数组序列的长度。插入的时候只需要把元素插入到数组的最后一个元素的后面即可，因此，时间复杂度为O(1)，删除操作也需要移动这个元素后面的所有的元素，因此，此时的时间复杂度也为O(n)。

6)普通二叉树：在最坏的情况下，有n个结点的树的高度为n，因此，查找、插入与删除的时间复杂度都为O(n)。

从上面的分析可以发现，平衡二叉树的查找和删除的时间复杂度都是O(logn)，Hash表的查找、插入的时间复杂度都是O(1)。因此，这两个数据结构有较好的查找和删除的性能。所以，选项C、选项D正确。3.

一个栈的入栈序列为ABCDE，则不可能的出栈序列为______。

（分数：2.00）

A.ECDBA

√

B.DCEAB

√

C.DECBA

D.ABCDE

E.EDCBA解析：4.

下列排序算法中，时间复杂度不会超过O(nlogn)的是______。

（分数：2.00）

A.快速排序

B.堆排序

√

C.归并排序

√

D.冒泡排序解析：5.

下列描述错误的是______。

（分数：2.00）

A.插入排序算法在某些隋况下时间复杂度为O(n)

B.排序二叉树元素查找的时间复杂度可能为O(n)

C.对于有序列表的排序最快的是快速排序

√

D.在有序列表中通过二分查找的时间复杂度一定是O(nlogn)

√解析：本题中，对于选项A，当数据完全有序时，插入排序的时间复杂度就是O(n)。所以，选项A正确。

对于选项B，当二叉树退化成线性表(只有一叉)出现时，排序二叉树元素查找的复杂度可能为O(n)。所以，选项B正确。

对于选项C，快速排序只对无序、随机序列有优势，针对有序序列，其排序反而没有了优势，在这种情况下，快速排序的效率最低，时间复杂度为O(n2)。所以，选项C错误。

对于选项D，在有序列表中通过二分查找的复杂度是O(logn)，而不是O(nlogn)。所以，选项D错误。

所以，本题的答案为CD。三、论述题(总题数：13，分数：30.00)1.

寻找一条从左上角(arr[0][0])到右下角(arr[m-1][n-1])的路线，使得沿途经过的数组中的整数和最小。

（分数：4.00）__________________________________________________________________________________________

正确答案：(对于这道题，可以从右下角开始倒着来分析：最后一步到达arr[m-1][n-1]只有两条路，即通过arr[m-2][n-1]到达或通过arr[m-1][n-2]到达，假设从arr[0][0]到arr[m-2][n-1]沿途数组最小值为f(m-2,n-1)，到arr[m-1][n-2]沿途数组最小值为f(m-1,n-2)。因此，最后一步选择的路线为min{f(m-2,n-1),f(m-1,n-2)}。同理，选择到arr[m-2][n-1]或arr[m-1][n-2]的路径可以采用同样的方式来确定。

由此可以推广到一般的情况。假设到arr[i-1][j]与arr[i][j-1]的最短路径的和为f(i-1,j)和f(i,j-1)，那么到达arr[i][j]的路径上所有数字和的最小值为f(i,j)=min{f(i-1,j),f(i,j-1))+arr[i][j]。

方法1：递归法

根据这个递归公式可知，可以采用递归的方法来实现，递归的结束条件为遍历到arr[0][0]。在求解的过程中，还需要考虑另外一种特殊情况：遍历到arr[i][j](当i=0或j=0)的时候，只能沿着一条固定的路径倒着往回走直到arr[0][0]。

但是递归算法效率太低，主要因为里面有大量的重复计算过程，比如在计算(i-1,j)与f(j-1,i)的过程中都会去计算f(i-1,j-1)。如果把第一次计算得到的f(i-1,j-1)缓存起来就不需要额外的计算，而这也是典型的动态规划的思路，下面重点介绍动态规划方法。

方法2：动态规划法

动态规划其实也是一种空间换时间的算法，通过缓存计算的中间值，从而减少重复计算的次数，从而提高算法的效率。方法1从arr[m-1][n-1]开始逆向通过递归来求解，采用动态规划要求正向求解，以便利用前面计算出来的结果。

对于本题而言，显然，f(i,0)=arr[0][0]+…+arr[i][0]，f[0,j]=arr[0][0]+…+arr[0][j]。根据递推公式：f(i,j)=min{f(i-1,j),f(i,j-1)}+arr[i][j]。从i=1、j=1开始顺序遍历二维数组，可以在遍历的过程中求出所有的f(i,j)的值，同时，把求出的值保存到另外一个二维数组中以供后续使用。当然，在遍历的过程中可以确定这个最小值对应的路线，在这个算法中，除了求出最小值外顺便还打印出了最小值的路线，实现代码如下：

publicclassTest

{

publicstaticintgetMinPath(int[][]arr){

if(arr==null||arr.length==0)

return0;

introw=arr.length;

inrcol=arr[0].length;

//用来保存计算的中间值

int[][]cache=newint[row][col];

cache[0][0]=arr[0][0];

for(inti=1;i＜col;i++){

cache[0][i]=cache[0][i-1]+arr[0][i];

}

for(intj=1;j＜row;j++){

cache[j][0]=cache[j-1][0]+arr[j][0];

}

//在遍历二维数组的过程中不断把计算结果保存到cache中

for(inti=1;i＜row;i++){

for(intj=1;j＜col;j++){

//可以确定选择的路线为arr[i][j-1]

if(cache[i-1][j]>cache[i][j-1]){

cache[i][j]=cache[i][j-1]+arr[i][j];

System.out.print("["+i+","+(j-1)+"]

");

}

//可以确定选择的路线为arr[i-1][j]

else{

cache[i][j]=cache[i-i][j]+arr[i][j];

System.out.print("["+(i-1)+","+j+"]");

}

}

}

System.out.println("["+(row-1)+","+(col-1)+"]");

returncache[row-1][col-1];

}

publicstaticvoidmain(String[]args){

int[][]arr={{1,4,3},{8,7,5},{2,1,5}};

System.out.print("路径:");

System.out.println("最小值为:"+getMinPath(arr));

}

}

程序的运行结果为：

路径：[0,1][0,2][2,0][2,1][2,2]

最小值为：17

这个方法对二维数组进行了一次遍历，因此，其时间复杂度为O(m*n)。此外由于这个算法同样申请了一个二维数组来保存中间结果，因此，其空间复杂度也为O(m*n)。)解析：2.

实现对一组无序的字母进行从小到大排序(区分大小写)，当两个字母相同时，小写字母放在大写字母前。要求时间复杂度为O(n)。

（分数：2.00）__________________________________________________________________________________________

正确答案：(如果没有时间复杂度的要求，本题可以采用传统的插入排序或快速排序等方法进行排序，但是传统的排序方法在最好的情况下的时间复杂度都为O(nlogn)，显然，不满足题目要求的O(n)时间复杂度。对于对时间复杂度有很高要求的问题，一般可以考虑用空间换时间的方法。鉴于此，对于本题而言，可以采用如下思路：

通常，字母为26个，当区分大小写后，变为26*2=52个，所以，首先申请一个长度为52的int型数组，按照aAbBcC...zZ(小写字母保存在下标为偶数的位置，大写字母保存在下标为奇数的位置)的顺序依次记录各个字母出现的次数，当记录完成以后，就可以遍历这个数组按照各个字母出现的次数来重组排序后的数组，实现代码如下：

publicclassTest{

publicstaticvoidmain(String[]args)

{

char[]src={'R','B','B','b','W','W','B','R','B','w'};

sort(src);

for(inti=0;i＜src.length;i++){

System.out.print(src[i]+"");}

}

privatestaticvoidsort(char[]src)

{

if(src==null)

{

System.out.pIintln("参数不合法");

return;

}

//用于保存52个字符出现的次数，小写字母保存在下标为偶数的位置，大写字母保存在奇

//数的位置

//采用这种保存方法，可以保证在这个数组中小写字母出现在大写字母前面，小的字符出现

//在大的字符前面

int[]charCount=newint[54];

for(inti=0;i＜src.length;i++)

{

//对小写字母出现的次数就行计数

if(src[i]＞'a'&&src[i]＜'z'){charCount[(src[i]-'a')*2]++;}

//对大写字母出现的次数就行计数

elseif(src[i]＜'Z'&&src[i]＞'A')

{charCount[(src[i]-'A')*2+1]++;}

}

//根据各个字符出现的次数按顺序生成排序后的字符数组

intindex=0;

for(inti=0;i＜charCount.length;i++)

{

//这个字符在原始字符数组中存在

if(charCount[i]!=0){

//小写字母

if(i%2==0)

{

for(intj=0;j＜charCount[i];j++){

src[index++]=(char)(i/2+'a');

}

}

//大写字母

else{

for(intj=0;j＜charCount[i];j++){

src[index++]=(char)((i-1)/2+'A');

}

}

}

}

}

}

程序的运行结果为：

bBBBBRRwWW)解析：3.

有N个磁盘，每个磁盘大小为D[i](i=0,…,N-1)，现在要在这N个磁盘上“顺序分配”M个分区，每个分区大小为P[j](j=0，…，M-1)，顺序分配的意思是：分配一个分区P[j]时，如果当前磁盘剩余空间足够，则在当前磁盘分配；如果不够，则尝试下一个磁盘，直到找到一个磁盘D[i+k]可以容纳该分区，分配下一个分区P[j+1]时，则从当前磁盘D[i+k]的剩余空间开始分配，不再使用D[i+k]之前磁盘未分配的空间，如果这M个分区不能在这N个磁盘完全分配，则认为分配失败。请实现函数isallocable判断给定N个磁盘(数组D)和M个分区(数组P)，是否会出现分配失败的情况?举例：磁盘为[120.120.1201]，分区为[60,60,80,20,80]可分配，如果为[60,80,80,20,80]，则分配失败。

（分数：2.00）__________________________________________________________________________________________

正确答案：(本题的主要思路如下：对所有的分区进行遍历，同时用一个变量dIndex记录上次分配磁盘的下标，初始化为0；对于每个分区，从上次分配的磁盘开始继续分配，如果没有足够的空间，则顺序找其他的磁盘，直到找到合适的磁盘为止，进行分配；如果找不到合适的磁盘，则分配失败，实现代码如下：

publicclassTest{

publicstaticvoidmain(String[]args){

int[]d={120,120,120};//磁盘

int[]p={60,60,80,20,80};//分区

if(is_allocable(d,p)){

System.out.println("分配成功");

}else{

System.out.println("分配失败");

}

}

privatestaticbooleanis_allocable(int[]d,int[]p)

{

intdIndex=0;//磁盘分区下标

for(inti=0;i＜p.length;i++){

//找到符合条件的磁盘

while(dIndex＜d.length&&p[i]＞d[dIndex])

dIndex++;

//没有可用的磁盘

if(dIndex＞=d.length)

returnfalse;

//给分区分配磁盘

d[dIndex]-=p[i];

}

returntrue;

}

}

程序的运行结果为：

分配成功)解析：4.

假设有一个中央调度机，有n个相同的任务需要调度到m台服务器上执行，由于每台服务器的配置不一样，因此，服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务需要的时间为t[i]。例如，有2个执行机a与b，执行一个任务分别需要7min和10min，有6个任务待调度。如果平分这6个任务，即a与b各3个任务，则最短需要30min执行完所有。如果a分4个任务，b分2个任务，则最短28min执行完。请设计调度算法，使得所有任务完成所需要的时间最短。输入m台服务器，每台机器处理一个任务的时间为t[i]，完成n个任务，输出n个任务在m台服务器的分布。intestimate_process_time(int[]t,intm,intn)。

（分数：2.00）__________________________________________________________________________________________

正确答案：(本题可以采用贪心法来解决，具体实现思路如下：

申请一个数组来记录每台机器的执行时间，初始化为0。在调度任务的时候，对于每个任务，在选取机器的时候采用如下的贪心策略：对于每台机器，计算机器已经分配任务的执行时间+这个任务需要的时间，选用最短时间的机器进行处理。实现代码如下：

publicclassTest

{

publicstaticvoidmain(String[]args)

{

intt[]={7,10};

intn=6;

intproTime[]=calculate_orocess_time(t,n);

if(proTime==null)

{

System.out.println("分配失败");

return;

}

inttotalTime=proTime[0];

for(inti=0;i＜proTime.length;i++)

{

System.out.println("第"+(i+1)+"台服务器有"+proTime[i]/t[i]

+"个任务,执行总时间为："+proTime[i]);

if(proTime[i]＞totalTime)

totalTime=proTime[i];

}

System.out.println("执行完所有任务所需的时间为"+totalTime);

}

/**

*@paramt

每个服务器处理的时间

*@paramn

任务的个数

*@return各个服务器执行完任务所需的时间

*/

privatestaticint[]calculate_process_time(int[]t,intn)

{

if(t==null||n＜=0)

returnnull;

intm=t.length;

intminlndex;

intminTime;

int[]proTime=newint[m];

for(inti=0;i＜n;i++)

{

minTime=proTime[0]+t[0];//把任务给第j个机器上后这个机器的执行时间

minIndex=0;

//把任务给第minIndex个机器上

for(intj=1;j＜m;j++)

{

//分配到第j台机器上后执行时间更短

if(minTime＞proTime[j]+t[j])

{

minTime=proTime[j]+t[j];

minIndex=j;

}

}

proTime[minIndex]+=t[minIndex];

}

returnproTime;

}

}

程序的运行结果为：

第1台服务器有4个任务，执行总时间为：28

第2台服务器有2个任务，执行总时间为：20

执行完所有任务所需的时间为28)解析：5.

n(1，2，3，…，n)个元素有N!个不同的排列，将这n!个数按字典序排列，并编号0，1，…，n!-1，每个排号为其字典序的值，如n=3时，字典排序为123，132，213，231,312，321，这6个数的字典序分别为0，1，2，3，4，5，现给定n，请输出字典序为k的排列(0＜=k＜n!)。

（分数：2.00）__________________________________________________________________________________________

正确答案：(算法的主要思路为：从当前字符串出发找出下一个排列(下一个排列为大于当前字符串的最小字符串)。

通过引入一个例子来介绍非递归算法的基本思想：假设要对字符串“12345”进行排序。第一个排列一定是“12345”，依此获取下一个排列：“12345”-＞“12354”-＞“12435”-＞“12453”-＞“12534”-＞“12543”-＞“13245”-＞...。从“12543”-＞“13245”可以看出找下一个排列的主要思路如下：

1)从右到左找到两个相邻递增的字符，在本例中，“12543”中从右到左找出第一个相邻递增的子串为“25”，记录这个小的字符的下标为pmin。

2)找出pmin后面的比它大的最小的字符进行交换，在本例中，字符“2”后面的子串中比它大的最小的字符为“3”，因此，交换字符“2”和字符“3”可以得到字符串“13542”。

3)为了保证下一个排列为大于当前字符串的最小字符串，在第2)步完成交换后，需要对pmin后的子串重新组合，使其值最小，只需对pmin后面的字符进行逆序即可(因为此时pmin后面的子串中的字符必定是按照降序排列，逆序后字符就按照升序排列了)，逆序后就能保证当前的组合是新的最小的字符串；在这个例子中，上一步得到的字符串为“13542”，pmin指向字符“3”，对其后面的子串“542”逆序后得到字符串“13245”。

4)依次类推，直到获取到字典序为k的排列为止。

有兴趣的读者可以根据上述思路，自行实现代码。)解析：6.

定义有数组inta[200]={1,2,2,3,...}，数组元素都为正整数，且a[i+1]＞=a[i]，请快速输出a[i]=i的数。

（分数：2.00）__________________________________________________________________________________________

正确答案：(本题中，最简单的方法是对数组进行顺序遍历，判断遍历到的数是否满足条件，这种方法的效率显然是最低的。下面介绍另外一种方法，主要思路如下：如果a[i]＞i，则接下来的a[i]-i-1个数一定不可能满足a[i]=i，此时可以直接遍历下标为i+(arr[i]-i)的元素，从而减少了遍历的次数，实现代码如下：

importjava.util.ArrayList;;

publicclassTest

{

publicstaticArrayList＜Integer＞find(int[]arr)

{

ArrayList＜Integer＞result=newArrayList＜Integer＞();

for(inti=0,j=arr.length-1;i＜=j;)

{

//找到满足条件的数，添加到结果中，继续遍历下一个数

if(arr[i]==i)

result.add(i++);

//当arr[i]＞i时，则接下来的a[i]-i-1个数肯定不满足a[i]=i

elseif(m[i]＞i)

i=i+(arr[i]-i);

//遍历下一个数

else

i++;

}

returnresult;

})解析：7.

定义数组int[n]a={1,2,3,3,4,3,2，...}，数组a中的数均为正整数，当满足a[i]+a[t]=a[x]时，其中，i，t，x均为正数，且小于等于n，求最大的a[x]。

（分数：2.00）__________________________________________________________________________________________

正确答案：(本题的主要思路如下：首先对数组进行排序，然后从后往前遍历数组，对于每遍历到的一个数组元素a[i]，判断从0到a[i-1]个元素中，是否有满足a[j]+a[k]=a[i](j,k＜=i-1)的值。在判断的时候，可以采用如下思路：从前往后遍历子数组a[0...i-1]，对于遍历到的元素a[j]，判断在子数组a[j+1...i-1]中是否存在a[i]-a[j]，如果存在，则说明存在值j和k，使得a[j]+a[k]=a[i]，此时的a[i]就是满足条件的最大值。

有兴趣的读者可以根据上述思路，自行实现代码。)解析：8.

数组和链表有什么区别?

（分数：2.00）__________________________________________________________________________________________

正确答案：(数组是按照数据顺序存储的，其大小固定。而链表中的数据可以随机存储，大小可动态改变。)解析：9.

如何寻找单链表的中间结点?

（分数：2.00）__________________________________________________________________________________________

正确答案：(要寻找到单链表的中间结点，最容易想到的方法是首先求解单链表的长度，记为length，然后遍历length/2的距离即可，但是此种方法需要遍历两次链表，即第一次遍历求解单链表的长度，第二次遍历根据索引获取中间结点。

如果是双向链表，可以首尾并行进行寻找，利用两个指针，一个从头到尾遍历，另一个从尾到头遍历，当两个指针相遇的时候，就找到了中间结点。以此思想为基础，如果是单链表，也可以采用双指针的方式来实现中间结点的快速查找。

具体而言，第一步，定义两个指针，二者同时从链表头开始遍历。第二步，两个指针每次走的步数不一样，其中，快指针一次走2步，慢指针一次走1步。第三步，由于快慢指针每次所走的步数不一样，所以，快指针会先到达链表尾部，而慢指针则恰好到达链表中部。(快指针走到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针，当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点。))解析：10.

编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。但是要保证汉字不被截半个，例如“人ABC”4，应该截为“人AB”，输入“人ABC们DEF”，6，应该输出为“人ABC”而不是“人ABC+们的半个”。

（分数：2.00）__________________________________________________________________________________________

正确答案：(在Java语言中，默认使用的Unicode编码方式，即每个字符占用两个字节，因此，可以用来存储中文。虽然String是由char所组成的，但是它采用了一种更加灵活的方式来存储，即英文占用一个字符，中文占用两个字符。采用这种存储方式的一个重要作用就是可以减少所需的存储空间，提高存储效率。根据这个特点，可以采用如下代码来完成题目的要求：

publicclassTest

{

//判断字符c是否是中文字符，如果是返回true

publicstaticbooleanisChinese(charc)

{

Stringsb=String.valueOf(c);

returnsb.getBytes().length＞1?true:false;

}

publicStringmmcateStr(Stringstr,intlen)

{

if(str==null||str.equals("")||len==0)

return"";

char[]chrArr=str.toCharArray();

StringBuildersb=newStringBuilder("");

intcount=0;//用来记录当前截取字符的长度

for(charcc:chrArr)

{

if(count＜len)

{

if(isChinese(cc))

{

//如果要求截取子串的长度只差一个字符，但是接下来的字符是中文，

//则截取结果子串中不保存这个中文字符

if(count+1==len)

return