积累(一)

C++的多态——编译时多态与运行时多态。前者指重载（同名函数对应不同的函数体定义）；后者指虚函数（动态绑定）。

struct的成员默认是public，class的成员默认是private。

对于派生类的构造函数，在定义对象时构造函数的执行顺序为？

答：1.基类的构造函数 2.成员对象所在类的构造函数  3.派生类自己的构造函数。

定义一个函数指针，指向的函数有两个int形参并且返回一个函数指针，返回的指针指向一个有一个int形参且返回int的函数。这个函数指针的定义是：int (*(*F)(int, int))(int)；

问：有n个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

答：把A认识B的关系转化为A>B，那么此题可以转化为求一个集合中最小的数字。

People a[n];//n个人

{...}//重载小于号，若A认识B，则A<B为真

int fun(int a[],int n){

  int tmp=0;

  for(int i=1;i<n;i++)

    if(a[i]<a[tmp])

      tmp=i;

  return tmp;

}// time complexity =O(n)

字节对齐

数论-糖果传递

http://blog.csdn.net/chuchus/article/details/21884269

问：A和B晚上无聊就开始数星星。每次只能数K个（20<=k<=30）A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？

答：这本是一道选择题，现给出思路。数星星次序为A\BA\BA...BA。当有（20+30=50）颗星星时，B必应，A任意数x颗，B可数（50-x）颗。所以应有n满足 (n-k)%50==0.（k[20,30]）

问：不定项选择：假定函数rand_k会生成一个[1,k]之间的随机整数，并且每个结果的出现都是等概率的。现有rand_7函数，请问利用这个函数和其他运算与逻辑操作，能实现以下的哪些函数？(a b c d)

a.rand_3         b.rand_21  c.rand_23  d.rand_47

答：首先，可以生成rand_x();//x<=7

也就是说，若有rand_x,可以实现任意的rand_i;    //  i<=x

然后我们分析rand_49的实现。所以，可得答案。

int rand_7();//已有
int rand_x(){//x<=7
    while(1){
	  int t=rand_7();
	  if(t<=x) return t;
    }
}
int rand_49(){
     return 7*(rand_7()-1)+rand_7();
}
/*
给出表达式: x=7*a+b  (a属于[0,6],b属于 [1,7]
[1,49]的任意一个数x都可以唯一的对应于a,b两个参数，所以 rand_49可实现。
*/

问：若一棵二叉树的前序遍历序列与后续遍历序列分别是1,2,3,4 和 4,3,2,1，则该二叉树的中序遍历不会是(C)

A.1234         B.2341              C.3241                    D.4321

答：先序遍历：根、左、右；后序：左、右、根。两次遍历序列完全相反，说明每一个结点都不会同时有左右子树。所以中序遍历中‘1’只能在头或末，四个选项都满足。接下来，234,2只能在头或末，所以C不满足。

先序遍历与后序不能唯一确定一棵二叉树，但可以确定各结点的父子关系。

问：已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无左右孩子的结点个数是（选项略）

答：此题为选择题，可以举特例，易得解。

问：若平衡二叉树的高度为6，且所有非叶结点的平衡因子为1，则该平衡二叉树的结点总数为(20).

答：有函数f(x)=高度为x时叶结点总数。f(2)=2,f(3)=4,配合图形可得规律，f(x)=1+f(x-1)+f(x-2)。则f(4)=7,f(5)=12,f(6)=20。

将两个递增有序的链表合并成一个递减有序链表，仍使用原节点.