1. 在计算机中，算法是指什么？

答案：解题方案的准确而完整的描述。

2. 在下列选项中，哪个不是一个算法一般应该具有的基本特征？

说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。

3. 算法一般都可以用哪几种控制结构组合而成？

答案：顺序、选择、循环。

4. 算法的时间复杂度是指？

答案：算法执行过程中所需要的基本运算次数。

5. 算法的空间复杂度是指？

答案：执行过程中所需要的存储空间。

6. 算法分析的目的是？

答案：分析算法的效率以求改进。

7. 下列叙述正确的是（C）

A．算法的执行效率与数据的存储结构无关

B．算法的空间复杂度是指算法程序中指令（或语句）的条数

C．算法的有穷性是指算法必须能在执行有限个步骤之后终止

D．算法的时间复杂度是指执行算法程序所需要的时间

8. 数据结构作为计算机的一门学科，主要研究什么？

答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。

9. 数据结构中与所使用的计算机无关的是数据的（C）

A．存储结构B．物理结构

C．逻辑结构D．物理和存储结构

10. 下列叙述中，错误的是（B）

A．数据的存储结构与数据处理的效率密切相关

B．数据的存储结构与数据处理的效率无关

C．数据的存储结构在计算机中所占的空间不一定是连续的

D．一种数据的逻辑结构可以有多种存储结构

11. 数据的存储结构是指什么？

答案：数据的逻辑结构在计算机中的表示。

12. 数据的逻辑结构是指？

答案：反映数据元素之间逻辑关系的数据结构。

13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？

答案：线性结构和非线性结构。

14. 下列数据结构具有记忆功能的是（C）

15. 下列数据结构中，按先进后出原则组织数据的是（B）

一、数组求和     给定一个含有n个元素的整型数组a，求a中所有元素的和。可能您会觉得很简单，是的，的确简单，但是为什么还要说呢，原因是这道题要求用递归法，只用一行代码。

1. 如果数组元素个数为0，那么和为0。

2. 如果数组元素个数为n，那么先求出前n - 1个元素之和，再加上a[n - 1]即可

二、求数组中的最大值与最小值
给定一个含有n个元素的整型数组a，找出其中的最大值和最小值 分析： 常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。

三、求数组的最大值与次大值
给定一个含有n个元素的整型数组，求其最大值和次大值

分析：思想和上一题类似，同样是用分治法，先求出左边的最大值leftmax和次大值leftsecond，再求出右边的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情况考虑

注意： 这种方法无法处理最大元素有多个的情况，比如3,5,7,7将返回7，7而不是7,5。

// 找出数组的最大值和次大值，a是待查找的数组，left和right是查找区间，max和second存放结果
 

 四、求数组中出现次数超过一半的元素  给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。据说是百度的一道题
 


 

 分析：设置一个当前值和当前值的计数器，初始化当前值为数组首元素，计数器值为1，然后从第二个元素开始遍历整个数组，对于每个被遍历到的值a[i]
 


 

 


 

 2 如果a[i] != currentValue， 则计数器值减1，如果计数器值小于0，则更新当前值为a[i]，并将计数器值重置为1
 


 

// 找出数组中出现次数超过一半的元素
 

 另一个方法是先对数组排序，然后取中间元素即可，因为如果某个元素的个数超过一半，那么数组排序后该元素必定占据数组的中间位置。 五、求数组中元素最短的距离
给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小 分析：先对数组排序，然后遍历一次即可
 


// 求数组中元素的最短距离
 

 六、求两个有序数组中的共同元素
 


 

 给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如
 


 

 


 

 


 

 


 

 分析：充分利用数组有序的性质，用两个指针i和j分别指向a和b，比较a[i]和b[j]，根据比较结果移动指针，则有如下三种情况
 


 

 


 

 


 

 


 

 重复以上过程直到i或j到达数组末尾。



 

// 找出两个数组的共同元素
 

 这到题还有其他的解法，比如对于a中任意一个元素，在b中对其进行Binary Search，因为a中有n个元素，而在b中进行Binary Search需要logn。所以找出全部相同元素的时间复杂度是O(nlogn)。
 


 

 

 七、找到数组中的唯一元素
给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数 分析：求出整个数组的和，再减去1-1000的和。
代码：略。
 
 

 八、找出现奇数次的元素
 给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。 分析：因为对于任意一个数k，有k ^ k = 0，k ^ 0 = k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。
代码：略。
九、求数组中满足给定和的数对
给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)
分析：两个指针i和j分别指向数组的首尾，然后从两端同时向中间遍历，直到两个指针交叉。
 

// 找出满足给定和的数对
 

 十、最大和子段
给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14. 编程珠玑上的经典题目，不多说了。
 


 

 十一、最大子段积
给定一个整型数足a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84 分析：与最大子段和类似，注意处理负数的情况
 


 

// 子数组的最大乘积
 

 十二、数组循环移位
将一个含有n个元素的数组向右循环移动k位，要求时间复杂度是O(n)，且只能使用两个额外的变量，这是在微软的编程之美上看到的一道题
 


 

 分析：比如数组 1 2 3 4循环右移1位 将变成 4 1 2 3， 观察可知1 2 3 的顺序在移位前后没有改变，只是和4的位置交换了一下，所以等同于1 2 3 4 先划分为两部分1 2 3 | 4，然后将1 2 3逆序，再将4 逆序 得到 3 2 1 4，最后整体逆序 得到 4 1 2 3
 


// 将含有n个元素的数组buffer右移k位
 

 十三、字符串逆序
给定一个含有n个元素的字符数组a，将其原地逆序。
 分析：可能您觉得这不是关于数组的，而是关于字符串的。是的。但是别忘了题目要求的是原地逆序，也就是不允许额外分配空间，那么参数肯定是字符数组形式，因为字符串是不能被修改的（这里只C/C++中的字符串常量），所以，和数组有关了吧，只不过不是整型数组，而是字符数组。用两个指针分别指向字符数组的首位，交换其对应的字符，然后两个指针分别向数组中央移动，直到交叉。
 


 

 


 

 给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子
 


 

 


 

 


 

 


 

 


 

 2 3 4, 2 3 5, 2 4 5
3 4 5
分析：典型的排列组合问题，首选回溯法，为了简化问题，我们将a中n个元素值分别设置为1-n
 


 

// n选m的所有组合
 

 


 

 给定含有n个元素的两个有序（非降序）整型数组a和b。合并两个数组中的元素到整型数组c，要求去除重复元素并保持c有序（非降序）。例子如下
 


 

 


 

 


 

 

 分析：利用合并排序的思想，两个指针i,j和k分别指向数组a和b，然后比较两个指针对应元素的大小，有以下三种情况
 


 

 


 

 


 

 


 

 重复以上过程，直到i或者j到达数组末尾，然后将剩下的元素直接copy到数组c中即可
代码：略。
十六、重排问题



 

 给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
 


 

 1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
 


 

 2. 不能使用额外存储空间
 


 

 


 

 


 

 


 

 分析：此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果a[k]为0，则将a[i]赋值给a[k]，a[k]赋值为0。实际上i是非0元素的下标，而k是0元素的下标
 


 

 十七、求出绝对值最小的元素
给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 -5, -3, -1, 2, 8 则返回1。
 


 

 分析：由于给定序列是有序的，而这又是搜索问题，所以首先想到二分搜索法，只不过这个二分法比普通的二分法稍微麻烦点，可以分为下面几种情况
 


 

• 如果给定的序列中所有的数都是正数，那么数组的第一个元素即是结果。
• 如果给定的序列中所有的数都是负数，那么数组的最后一个元素即是结果。
• 如果给定的序列中既有正数又有负数，那么绝对值得最小值一定出现在正数和负数的连接处。

 

 为什么？因为对于负数序列来说，右侧的数字比左侧的数字绝对值小，如上面的-5, -3, -1, 而对于整整数来说，左边的数字绝对值小，比如上面的2, 8，将这个思想用于二分搜索，可先判断中间元素和两侧元素的符号，然后根据符号决定搜索区间，逐步缩小搜索区间，直到只剩下两个元素。

 

// 找出一个非递减序整数序列中绝对值最小的数