1、假设一个客户，他的手机中存放有全中国人民的手机号，他的手机通信录顺序很乱而且里面可能有些重复了，现在客户想让我们设计一个程序，帮他把通讯录整理一下，删除重复手机号，说机上能利用的内存只有10M，但是有无限大的硬盘，请给出设计思路，并评估算法性能。
2、有一组数字，如14,26,5,30,0，-2,108，和一个给定的整数a，是否存在其中一个或几个，它们的和等于a。
请实现方法int findNIntendo（int arr[],int count,int a)，存在返回1，否则返回0.
3、实现反转字符串。
4、以下关于红黑树的恶说法错误的是：
A、红黑树上插入操作的最差情况下的时间复杂度为O（log n)
B、红黑树上任意节点的左右子树高度差绝对不大于1
C、红黑树上删除操作最差情况的时间复杂度为O(log n)
D、红黑树上查找操作最差情况下的时间复杂度为O(log n)
5、unsigned short hash(unsigned short key){
return (key>>4)%256
}
请问hash(16)，hash(256)的值分别是______、______
6、有98个元素的排序好的数组，用二分法查找，最多需要查找几次？
7、下列哪种排序算法和数据结构是不稳定的？
A、插入排序 B、快速排序 C、基数排序 D、（选项忘了）
2、有一组数字，如14,26,5,30,0，-2,108，和一个给定的整数a，是否存在其中一个或几个，它们的和等于a。
请实现方法int findNIntendo（int arr[],int count,int a)，存在返回1，否则返回0.
3、实现反转字符串。
4、以下关于红黑树的恶说法错误的是：
A、红黑树上插入操作的最差情况下的时间复杂度为O（log n)
B、红黑树上任意节点的左右子树高度差绝对不大于1
C、红黑树上删除操作最差情况的时间复杂度为O(log n)
D、红黑树上查找操作最差情况下的时间复杂度为O(log n)
5、unsigned short hash(unsigned short key){
return (key>>4)%256
}
请问hash(16)，hash(256)的值分别是______、______
6、有98个元素的排序好的数组，用二分法查找，最多需要查找几次？
7、下列哪种排序算法和数据结构是不稳定的？
A、插入排序 B、快速排序 C、基数排序 D、（选项忘了）
我的思路是按手机号分别存放到不同的文件当中，比如132的放到一个文件中，133的放到一个文件中。
遍历文件的时候，第一次遍历只读取132的，10M的空间存储132开头的手机号，重复的删除（Set集合就行了），最后剩余的存到132文件中。
然后第二次遍历只读取133的，依次下去。
第二个：我能想到的思路只有双层for循环了。算法就不写了，挺简单的，就是效率上有可能有点低。
第三个:把字符串放到一个List或者map（key和字符成映射）中，遍历list的时候用反转遍历，map就按Key值从大到小读取呗。
第四个：我不知道叫红黑树
后面的先不做了，有空继续做。
import java.util.ArrayList;public class Find{
public static final int MAX = 100;
public static ArrayList<Integer> array = new ArrayList<Integer>(); public static void main(String[] args) {
int arr[] = { 2, 4, 6, 7, 100 };
int flag = findNIntendo(arr, 3, 110);
System.out.println(flag);
} public static int findNIntendo(int arr[], int count, int a) {
int i;
int[] a1 = new int[MAX];
int[] b1 = new int[MAX];
for (i = 1; i < 100; i++)
a1[i - 1] = i;
combine(a1, arr.length, count, b1, count,arr);
for (int j = 0; j < array.size(); j++)
if (array.get(j) == a)
return 1;
return 0;
} public static void combine(int a[], int n, int m, int b[], int M,int[] arr) {
int i, j; for (i = n; i >= m; i--) {
b[m - 1] = i - 1;
if (m > 1)
combine(a, i - 1, m - 1, b, M,arr);
else {
int sum = 0; for (j = M - 1; j >= 0; j--)
sum += arr[a[b[j]]-1];
array.add(sum); }
}
}
}
code=java]
public class Test{
public static void main(String[] args) {
String str="54g34g34";
char[] s;
s=str.toCharArray();
for(int i=s.length-1;i>=0;i--){
System.out.print(s[i]);
}
}
}[[/code]
第四题还是不知道什么叫红黑树
第五题：1,16
hash(16)==>16>>4=1(把16转换为2进制数，然后退4位，就是等于16除以2的4次方)==>1%256余数等于1呗
hash(256)等于16，也即是16除以256余数还是16
第六题：取极端1，那就是分别和49,25,13,7,4,2比较。6次。至于最后一次需不需要和1比较，我不确定，还是回答6次至少证明你知道这个方法。
第七题：快速排序是不稳定的，我也是刚查的，真不起大学时候的数据结构老师。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。4.B、红黑树上任意节点的左右子树高度差绝对不大于1 感觉这个错误，还不确定。
// mobile = 11,person = 1300000000,momery=10M,
double storeByte = 1300000000l * 11;//13亿人需要存储多少空间，11是手机号的字节数
double memery = 10 * 1024 * 1024;//10M换算成字节数
double splitCount = storeByte / memery;//做个小运算，看要读完全部数据到内存要做多少次
1.以10M内存，需要进行计算1364次计算，才能完全处理完这些记录
2.按每次10M处理现在手机号，发现重复的则删除，并记录成一个随机文件A1直到A1364
3.读入A1文件到内存数组，读取A2-A1364文件，将A2到A1364一条记录(readLine)和A1记录比较，将不同结果写入新文件尾部考虑不周地方，欢迎批评
先HASH把号码划分成可以放入内存中操作的N分，存入N个文件中，再对每个文件进行操作。第二题：
这个明显的是个经典的0-1背包问题。
以下是动态规划实现
int findNIntendoHelp(int arr[],int count,int left,stdext::hash_map<int,int> M,int c){
if(M.find(left)!=M.end()){
return M[left];
}
if(left==0){
M[left]=1;
return 1;
}
if(c>=count){
M[left]=0;
return 0;
}
if((findNIntendoHelp(arr,count,left-arr[c],M,++c)|findNIntendoHelp(arr,count,left,M,++c))==1){
M[left]=1;
return 1;
}else{
M[left]=0;
return 0;
}
}
int findNIntendo(int arr[],int count,int a){
stdext::hash_map<int,int> M;
int c=0;
int left=a;
return findNIntendoHelp(arr,count,left,M,c);
}第三题：
void inversestr(char* str){
int r=strlen(str)-1;
int l=0;char temp;
while(r>l){
temp=str[r];
str[r--]=str[l];
str[l++]=temp;
}
}第四题：
B第五题：
1 16第六题
7次。第七题：
快排第八题：
看不清第九题：
A第十题
B
int start = 130 0000 0000 //可以赋值到线程target
while(start++<131 0000 0000){
//文件读取 选出收个和start相同的号码的记录。
}
考虑10M内存，以及程序的线程池、线程等资源消耗，综合控制线程数。
第二题：看到某算法书上说此类问题可以递归解决。应该和背包问题一样吧。
一点浅见，欢迎指正。
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;/**
* @author Administrator
*/
public class CompomentTest { /**
* @param array 要组合的源数组
* @param n 以每n个元素作为一个组合
* @param sum 组合内所有元素的和
* @return 组合后的集合
*/
public static List<int[]> combination(int[] array , int n ,int sum){
List<int[]> combinations = new ArrayList<int[]>();
if(n <= 0 && n > array.length)
return null ; LinkedList<Integer> tmp = new LinkedList<Integer>();
for(int i = 0; i < array.length ;i++){
if(i < n)
tmp.add(1);
else
tmp.add(0);
}
boolean flag = true ;
List<LinkedList<Integer>> indexgraph = new ArrayList<LinkedList<Integer>>();
indexgraph.add(tmp);
//得到所有元素的排列
do{
//寻找到第一个 1 0
int last = tmp.get(0);
int targetIndex = 1 ; for (; targetIndex < tmp.size() ; targetIndex++) {
int current = tmp.get(targetIndex) ;
if( current == 0 && last == 1)
break ;
last = current;
} if(targetIndex == tmp.size()) //已经排列完所有
{
flag = false;
}
if(flag){
LinkedList<Integer> graph = new LinkedList<Integer>() ;
for (int i = 0; i < targetIndex -1 ; i++) { //保存targetIndex之前的部分
int l = tmp.get(i);
if(l == 1)
graph.addFirst(l);
else
graph.addLast(l);
}
graph.add(0);
graph.add(1);
for (int i = targetIndex + 1; i < tmp.size(); i++) {
graph.add(tmp.get(i));
}
indexgraph.add(graph);
tmp = graph ;
}
}while(flag); //从array中取出相对应的元素
for (LinkedList<Integer> queue : indexgraph) {
int[] t = new int[n];
int index = 0 ;
for (int i = 0; i < queue.size(); i++) {
int k = queue.get(i);
if(k == 1){
t[index++] = array[i];
}
}
combinations.add(t);
}
//取除所有元素之和不等于给定值的组合
Iterator<int[]> it = combinations.iterator();
while(it.hasNext()){
int[] t = it.next();
int s = 0 ;
for (int i : t) {
s+= i ;
}
if(s != sum){
it.remove();
}
}
return combinations ;
}
public static void main(String[] args) {
List<int[]> result = combination(new int[]{0,1,2,3,4,5,8} , 3 , 10);
for (int[] is : result) {
System.out.println(Arrays.toString(is));
}
}}运行结果：
[2, 3, 5]
[1, 4, 5]
[0, 2, 8]
时间复杂度为O(nlogn)、空间复杂度为O(1)
第二题 ：该问题其实是一个子集和问题，即NP完全问题
第三题 ：定义两个指示器，一个指在最左边，向右移动，一个指在最右边，向左移动，两个指示器同时移动，直接相等。
void invert_point(char *str)
{
int i,j;
i=0;
j=strlen(str)-1;
while(i<j)
{
*(str+i)=*(str+i)^*(str+j);
*(str+j)=*(str+i)^*(str+j);
*(str+i)=*(str+i)^*(str+j);
i++;
j--;
}
}
第四题：不知道
第五题：hash(16)，hash(256)的值分别是__1____、___16___
如果short为一个字节，则hash(256)为0；如果short为两个字节，则hash(256)为16。
第六题：7(2的7次方约等于98)
第七题:B