25
技术社区[云栖]
积累(一)
积累(一)
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)
字节对齐
数论-糖果传递问：A和B晚上无聊就开始数星星。每次只能数K个（20<=k<=30）A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？
问：不定项选择：假定函数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。
将两个递增有序的链表合并成一个递减有序链表，仍使用原节点.
最后更新：2017-04-03 12:55:46