至今笔试都悲剧的被拒，先发几道笔试中遇到的算法题
1.
给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大.
例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
int max_sub2(int a[], int size)
{
int max = 0;
int temp_sum = 0;
for(int i = 0; i < size; i++)
{
temp_sum += a[i];
if(temp_sum > max)
max = temp_sum;
else if(temp_sum < 0)
temp_sum = 0;
}
return max;
}
2. 任何一个基于"比较"的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。
据严蔚敏数据结构，问题等价于给n个不同的砝码和一台天平要称几次能分辨它们的顺序。含n个记录的序列可能出现的初始状态有n!个，则描述n个记录排序过程的判定树必有n!个叶子节点，若有n个叶子节点，则二叉树的高度至少为log 2 n，（2为底），也即是说必然存在一条长为log 2 n!的路径，求出来n为10,(取上界)
3. 对一个表达式求值时，首先要把表达式转换为后缀表达式，然后在利用栈求值。
1.如果n为偶数，则将它除以2，如果n为奇数，则将它加1或者减1。问对于一个给定的n，怎样才能用最少的步骤将它变到1。
例如 n= 61
n-- 60
n/2 30
n/2 15
n++ 16
n/2 8
n/2 4
n/2 2
n/2 1
参照网上的讨论，这道题的意思其实是看最后两位的二进制数：AB。如果B为偶数，则直接/ 2，如果B为奇数，则看A的值，若A为1，则该值+1，若为0，则该值-1。
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main()
{
int n;
cin>>n;
int count = 0;
while( n > 1)
{
if( n%2 == 0)
n /= 2;
else if( n == 3)
n--;
else
n += (n % 4 - 2);
count++;
}
cout<<"times:"<<count<<endl;
return 0;
}
2.编一个有3个线程的程序，由Main主线程进入，生产者线程产生一个随机的整数。这个整数存在List中，再由消费者线程读取List数据，并显示。
3.列举3种你最喜欢的语言（Java/c++）框架，它们的特点和你喜欢的原因。
4.前缀表达式和后缀表达式的问题。
35,15,+,80,70,-,*,20,/ //后缀表达方式
(((35+15)*(80-70))/20）=25 //中缀表达方式
/,*,+,35,15,-,80,70, 20 //前缀表达方式
人们习惯的运算方式是中缀表达式。而碰到前缀，后缀方式。。迷茫。其实仅仅是一种表达式子的方式而已（不被你习惯的方式），我这里教你一种也许你老师都没跟你讲的简单转换方式。一个中缀式到其他式子的转换方法~~这里我给出一个中缀表达式~ a+b*c-(d+e)
第一步：按照运算符的优先级对所有的运算单位加括号~
式子变成拉：((a+(b*c))-(d+e))
第二步：转换前缀与后缀表达式
前缀：把运算符号移动到对应的括号前面
则变成拉：-( +(a *(bc)) +(de))
把括号去掉：-+a*bc+de 前缀式子出现
后缀：把运算符号移动到对应的括号后面
则变成拉：((a(bc)* )- (de)+ )-
把括号去掉：abc*+de+- 后缀式子出现
发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。
后天晚上会有笔试，我会把最新的发上来~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~2011年的笔试
1前面的选择题记不清了.就上c++的答题吧？
2.不用sizeof，计算int的字节数
3.MAC地址字符串XX：XX：~~~最后改成XX-XX-XX-XX的标准形式
4.色子问题：有一枚筛子，每个面都有一个数字：1~6。很显然，你会倾向于认为这6个面出现的概率是相等的，也就是，你倾向认为：P(x1)=P(x2)=…=P(x6)=1/6其中，P(xi)表示出现数字xi的概率。
假如，我告诉你，这枚筛子与其它筛子不同，似乎，他很容易滚到4或者5这个面，所以这个筛子滚了好多次以后，它出现的平均值是4.5。这个时候，你会怎样分配P(x1)~P(x6)的概率呢？
摘要: 1.你有5瓶药，每个药丸重10克，只有一瓶受到污染的药丸重量发生了变化，每个药丸重9克。给你一个天平，你怎样一次就能测出哪一瓶是受到污染的药呢？—— 1给5个瓶子标上1、2、3、4、5。 2从1号瓶中取1个药丸，2号瓶中取2个药丸，3号瓶中取3个药丸，4号瓶中取4个药丸，5号瓶中取5个药丸。 3把它们全部放在天平上称一下重量。 4现在用1×10＋2×10＋3...
阅读全文
1、智能指针：
智能指针是存储指向动态分配（堆）对象指针的类, 用于生存期控制, 能够确保自动正确的销毁动态分配的对象，防止内存泄露。它的一种通用实现技术是使用引用计数(reference count)。智能指针类将一个计数器与类指向的对象相关联，引用计数跟踪该类有多少个对象共享同一指针。每次创建类的新对象时，初始化指针并将引用计数置为1；当对象作为另一对象的副本而创建时，拷贝构造函数拷贝指针并增加与之相应的引用计数；对一个对象进行赋值时，赋值操作符减少左操作数所指对象的引用计数（如果引用计数为减至0，则删除对象），并增加右操作数所指对象的引用计数；调用析构函数时，构造函数减少引用计数（如果引用计数减至0，则删除基础对象）。
智能指针就是模拟指针动作的类。所有的智能指针都会重载 -> 和 * 操作符。智能指针还有许多其他功能，比较有用的是自动销毁。这主要是利用栈对象的有限作用域以及临时对象（有限作用域实现）析构函数释放内存。当然，智能指针还不止这些，还包括复制时可以修改源对象等。智能指针根据需求不同，设计也不同（写时复制，赋值即释放对象拥有权限，引用计数等，控制权转移等）。auto_ptr 即是一种常见的智能指针。
智能指针通常用类模板实现：
template <class T>
class smpoint
{
public:
smpoint(T * p): _p(p){}
T & operator * (){return *_p;}
T * operator -> (){return _p;}
~smpoint(){delete _p;}
private:
T * _p;
}
2、printf（）可变参数如何实现 ，http://www.vckbase.com/document/viewdoc/?id=1830
int printf(char *fmt, ...)，关键是几个宏的实现
3、标准模板库vector追加数据如何实现。是底层如何实现，不能用现有的东东。
在追加对象前先判断预留的空间是否满足需求，如果不满足则根据分配策略，另分配足够的空间 (一般使用平方增加策略)，复制以前的对象数组，再释放原来的空间，然后把对象追加到尾部。如果任何一个操作环节失败，则至少保留原数组不受影响（异常安全保证策略）。
4、java的垃圾收集机制如何实现为什么？如果是你自己实现垃圾收集机制，如何实现？ 用什么数据结构？
垃圾收集没有统一的实现。《深入Java虚拟机》中提了几种算法，包括引用计数，跟踪收集，拷贝收集（这个挺有趣的），还有重头火车算法。但是这本书有点旧了，新的技术不清楚。
最简单的实现做法，莫过于new的时候纪录，程序exit的时候批量delete……
5.
二叉排序树和哈希表那个查找效率高，实用于pda
质量精良的hash肯定是查找效率最高的。但是pda上，应该是二叉树比较好吧。在内存限制的条件下，hash可能会有变态表现。而有序二叉树的查找算法就比较稳定，空间复杂度n，最坏时间复杂度nlog(n)，而且避免了不同情况下hash函数的设计困难。
6. .net的底层实现机制。
虚拟机
7、过程间通信如何实现。
windows用管道，unix用文件描述符，或者用socket
8、迭代问题，什么问题用迭代，迭代在操作系统中如何实现的 。
迭代算法是用电脑解决问题的一种基本方法。他利用电脑运算速度快、适合做重复性操作的特点，让电脑对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出他的一个新值。
递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
9、如何交换两个变量，不能用中间变量。
int i;
int j;
j = （i + j） - （i = j）；
a = a^b;
b= a^b;
a = b^a;
10、c与c++ static函数的区别？？？
C 语言中 static 关键字作用于函数时起限制函数作用域的作用，其static函数作用域被限制为当前文件中，该函数定义之后部分。
C++ 的全局函数用static 修饰和 C 语言中一个意思 (C++ 标准建议此种情况用匿名名字空间包含该函数来代替static关键字)；但类成员函数如果用static 修饰表示是类的作用域而不是对象作用域，可以直接通过类名来引用。
11、const 函数的作用，如何实现钩子函数。
类的设计者通过将函数声明为 const 以表明它们不修改类对象。
const 函数内不允许修改数据成员 (需要注意的是，虽然在 const 函数内，指针成员变量不允许被修改，但对指针所指向内容的修改是允许的)。
一个 const 类对象只能调用 const 成员函数 (构造和析构函数除外)。
12、两层容错技术怎么实现？
13、写出函数指针，函数返回指针，const指针，指向const的指针，指向const的const指针。
函数指针：函数类型 （*指针变量名）（形参表） --int （*f）（int a）；
--1.说明函数指针变量（int（*f）（int a））；2.要对函数指针变量赋值（f = func）；3.要用（*指针变量）（参数表）；调用函数（（*f）（a，b））
指针函数：类型标识符 *函数名（参数表） int * f（int x， int y）
Const 指针：int *const ptr
指向const的指针：const int *ptr
指向const的const指针：const int *const ptr
14、函数调用如何实现，注意什么问题。
在函数调用的时候，使用栈传递参数，可变参数函数的实现与函数调用的栈结构有关，正常情况下c/c++的函数参数入栈规则为__stdcall, 它是从右到左的，即函数中的最右边的参数最先入栈。对于函数
void fun(int a, int b, int c) { int d; ... }
其栈结构为
0x1ffc-->d
0x2000-->a
0x2004-->b
0x2008-->c
对于任何编译器，每个栈单元的大小都是sizeof(int), 而函数的每个参数都至少要占一个栈单元大小
15、指针和引用的差别
1.指针初始化的时候，可以指向一个地址或者为空，而引用必须初始化为另一个变量;
2.指针是一个变量，占用4个字节，引用是一个别名；指针可以指向NULL，但引用必须与一个已经存在的变量绑定，而且这种绑定不可修改。
3.指针可以被重新赋值与指向另外一个不同的对象，但是引用则总是指向在初始化时被指定的对象，以后不能更改
16
、拷贝构造函数如何实现，什么情况下会用到。
拷贝构造函数的几个用处：
1) 用一个类对象初始化该类的另一个对象的时候：
A a;
A b(a);
A b = a;
2) 把一个类对象赋值给该类的另一个对象的时候：
A b;
b = a;
3) 传参数和返回时：
A f (A a) // 传参和返回都会调用拷贝构造函数
{
// ...
}
实现时要注意的是：
1) 当类中有指针变量成员时，确认是直接拷贝指针变量的值，还是重新分配内存然后递归拷贝构造。
2) 是否有每个对象必须有唯一值的成员变量 (比如账号)。其实 1) 也可以归为 2)。