自我介绍的时间
三分钟自我介绍
如果面试官没有特别强调,那么自我介绍的时间3分钟最合适。你可以根据自我介绍的四部分内容,这样分配时间:第一分钟主要介绍自己的姓名、年龄、学历、专业特长、实践经历等;第二分钟主要介绍个人业绩,应届毕业生可着重介绍相关的在校活动和社会实践的成果;第三分钟可谈谈对应聘职位的理想和对本行业的看法。
通常情况下,每分钟180到200字之间的语速是比较合适的。这样的语速可以让对方感到舒服,同时也能更加有效地传递信息,增加面试官对你的印象分。
一分钟自我介绍
有时候,面试官会规定自我介绍的时间,你应该怎样应对呢? 面试官规定的自我介绍时间缩短,如“做一个1分钟的自我介绍”。遇到这种情况,你可以精选事先准备的3分钟自我介绍内容,突出“做成过什么”,展现你与应聘职位相关的能力。
百度实习生电面
1、模拟扑克牌发牌,例如1-54代表每张牌,保证每个数字都出现一次,但是顺序随机
答:把54张牌存到大小为54的数组中,首先产生1-54中的一个随机数,取以该随机数为下标的牌发出来,并用最后一张牌(第54张)占据该位置,然后产生1-53中的以随机数,取以该随机数为下标的牌发出来,并用最后一张牌(第52张)占据该位置;以此类推,直到发完所有牌。
2. 有36匹马,1个跑道,每个跑道跑6匹,没有秒表,要比多少次能比出前3名,答案是8次,自己摸索。。。
答:每组单独跑 决出每组的第一名啊 然后每组的第一名在决出123 这样一共是7次吧
最后就是 第一名那组的23名 和第2名那组的12 还有第三名那匹马 一起比
决出2 3名
就这样啊
3. 用百度搜索的时候,想除去那些网址不同,但是网页内容相同的地址,怎么做?怎么判断网页内容相同?
答:判断网页内容是否相同的方法,可用于搜索引擎技术领域,过滤网页内容相同的查询结果。根据计算网页标题的相似度和网页正文内容的相似度,根据网页的标题和正文内容的相似度来判断其是否为相同内容。如果二者的相似度达到一定阀值,那么就判定为相同内容的网页,否则就判定为不同内容的网页。
4. 怎么找出一个链表的中间节点?
答: 用两个指针从链表头结点开始,一个指针以步长为2向后遍历,另一个以步长为1向后遍历,当步长为2的指针遍历到尾节点时,步长为1的指针刚好指向链表的中间节点
5. 怎么判断一个链表是否又环?环的长度?环的的起点?链表长度?
答:1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。
2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。
3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。假设单链表的总长度为L,头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为x,环的长度为r,慢指针总共走了s步,则快指针走了2s步。另外,快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离),得到以下关系:
s = a + x;
2s = a + nr + x;
=>a + x = nr;
=>a = nr - x;
由上式可知:若在头结点和相遇结点分别设一指针,同步(单步)前进,则最后一定相遇在环入口结点,
4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度
6、说几个常用的Linux命令.
答:pwd cd ls clear cat tail grep chmod cp mv rm mkdir echo tar
7. 一张1米*1米的桌子,有很多直径为10cm的圆形纸片,最少用多少张纸片覆盖桌?
答:
8. 进程间的死锁是怎么产生的?怎么破除?
答:产生死锁的原因主要是:
(1) 因为系统资源不足。
(2) 进程运行推进的顺序不合适。
(3) 资源分配不当等。
产生死锁的四个必要条件:
(1)互斥条件:一个资源每次只能被一个进程使用。
(2)请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3)不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。
(4)循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
9. Sizeof(数组名)的结果是什么?sring 字符串和char*字符串的区别?
答:Sizeof(数组名)的结果是数组所占内存的大小,如果是作为形参传递,则数组名退化为指针,再使用sizeof就变成求指针(地址)占内存大小。
Char是c++的内置类型char
String是C++标准库中定义的类,c中没有
如果是的话,它两的区别有:
char数组仅仅是存储字符串用的,c库中有一系列操作字符串的函数
String是类,它包含一个可变长度的char数组,封装了常用的字符串操作函数
string 和 vector、list一样,都是标准库类型。 string 类型支持长度可变的字符串,C++ 标准库将负责管理与存储字符相关的内存,以及提供各种有用的操作。
10、题目:输入两个整数n和m,从数列1,2,3...n中随意取几个数,使其和等于m,要求列出所有的组合。
[cpp
#include <iostream>
#include <list>
using namespace std;
list<int> list1;
void find_factor(int sum,int n)
{
//递归出口
if(n<=0||sum<=0)
return;
//输出找到的数
if(sum==n)
{
list1.reverse();
for(list<int>::iterator iter=list1.begin();iter!=list1.end();iter++)
cout<<*iter<<"+";
cout<<n<<endl;
list1.reverse();
}
list1.push_front(n);
find_factor(sum-n,n-1);//n放在里面
list1.pop_front();
find_factor(sum,n-1);//n不放在里面
}
由于八个皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8],数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化,接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字,因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上,也就是数组的两个下标i和j,是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。
11、动态链接库,有什么作用?
答:DLL文件 DLL是Dynamic Link Library的缩写,意为动态链接库。DLL是一个包含可由多个应用程序同时使用的代码和数据(函数和资源)的库。许多应用程序并不是一个完整的可执行文件,它们被分割成一些相对独立的动态链接库,即DLL文件,放置于系统中。当我们执行某一个程序时,相应的DLL文件就会被调用。一个应用程序可有多个DLL文件,一个DLL文件也可能被几个应用程序所共用,这样的DLL文件被称为共享DLL文件。
有助于促进代码重用和内存的有效使用。
程序可以实现模块化,由相对独立的组件组成。
可以更为容易地将更新应用于各个模块,而不会影响该程序的其他部分。
静态库本身就包含了实际执行代码、符号表等等,而对于导入库而言,其实际的执行代码位于动态库中,导入库只包含了地址符号表等,确保程序找到对应函数的一些基本地址信息。
12 、为什么析构函数应该设为虚函数
目的就是delete基类指针的时候把派生类的析构函数也调用了,防止内存泄露,因为常有通过基类指针或引用操作子类对象的情况 此时若不使用虚构造函数会造成对象销毁时子类的析构过程不被正确调用
13、多核、多处理器环境下多线程同步技巧——旋锁以及Lock-Free方法
我们这里大部分人应该已经熟悉了在单核单处理器的环境下对多线程进行同步的方法。
传统的方法有:Mutex(互斥体)、Semaphore(信号量)、Event(事件)、MailBox(邮箱)、Message(消息)等。
这些方法都有个共同的特性——即在使用这些方法的前、后会分别加上关中断、开中断操作(或是任务调度的禁止、开启)。
而在多核情况下单单开关中断是不起作用的。因为当一个线程在核心0中运行时,它无法一直去关心核心1中的线程运行状态,它甚至不知道核心1到底在运行哪个线程。
因此需要通过另一种方法来解决线程同步问题。
这里比较早的方法是通过原子操作做成旋锁进行同步。
什么是原子操作?
原子操作是指当对一个指定的存储单元进行这样的操作时,该操作不会被任何事件打断;另一方面,当对一个指定的存储单元进行这样的时,其它外部的访问都无法对该存储单元进行访问,直到该操作完成。
14、数据挖掘中常用分类算法
15、i++ 相比 ++i 哪个更高效?为什么?
++i的效率高些,++i在运算过程中不产生临时对象,返回的就是i,是个左值,类似++i=1这样的表达式是合法的,而i++在运算的过程中会产生临时对象,返回的是零时对象的值,是个右值,像i++=1这样的表达式是非法的
16、浅谈你对面向对象编程的认识
面向对象编程强调抽象、封装、继承、多态
抽象:我们在定义一个抽象类的时候,实际上就是把一类事物共有的属性和行为提取出来,形成一个物理模型(模版),这种研究问题的方法称为抽象。你可以这样来想,抽象就是一个类的最基础的东西,比方说人,他的抽象类可能就是都从母体出来,有皮肤。但具体到你是黑人,白人,还得黑人类,白人类来说明 。
封装:就是将类的属性包装起来,不让外界轻易的知道他的内部实现。只提供给你对外的接口让你来调用。好处可以增强模块的独立性。如设置属性或方法的访问权限(private、protected、public、默认)。
继承:就是从父类把它的有用的东西拿过来自己用,不用在自己去实现了,像母亲会把双眼皮传给女儿,不用她自己去割了 。
多态:“一个接口,多个方法”一个对象变量可以指向多种实际类型的现象。一个人,在不同场合下,有不同的身份,不同的状态。比如在家里,你是父母的孩子;在学校,你就是学生;在公司,你就是老板的职员。再比如在接口总定义一个run()方法,是什么在跑,汽车还是马?通过不同类的实现来表示相似的逻辑。
顺便说一下重载和重写(覆盖)的区别:
重载:相同的方法名(函数名),不同的实现机制(通过传入不同个数或类型的参数)。重载是在同一个类中的两个或两个以上的方法,拥有相同的方法名(返回值可以不同),但是参数却不相同,方法体也不相同,最常见的重载的例子就是类的构造函数。当程序运行过程中自己去判断到底该调用谁。比方说打人,那么多人,当你打起群架来,该打谁就打谁,事前你也不知道。
重写:从父类继承而来的方法不能满足需要的情况下,可以将此方法的逻辑在子类中重新实现。重写是子类的方法覆盖父类的方法,要求返回值、方法名和参数都相同。重写方法的访问修饰符一定要大于被重写方法的访问修饰符(public>protected>default>private)。我们最常用的就是重写toString()方法了。
调用
重载方法:
参数类型决定选择哪个重载版本(根据声明的参数类型),这发生在编译时。被调用的实际方法仍是发生在运行时期的虚拟方法调用。但是编译器已经知道所调用的方法的签名。因此,在运行时期,参数匹配已经明确,只是还不知道该方法所在的实际类。
重写方法:
对象类型(即:堆上实际实例的类型决定调用选择哪个方法,这发生在运行时期)
17、解释下面ptr含义和不同
double* ptr = &value;
//ptr是一个指向double类型的指针,ptr的值可以改变,ptr所指向的value的值也可以改变
const double* ptr = &value
//ptr是一个指向const double类型的指针,ptr的值可以改变,ptr所指向的value的值不可以改变
double* const ptr=&value
//ptr是一个指向double类型的指针,ptr的值不可以改变,ptr所指向的value的值可以改变
const double* const ptr=&value
//ptr是一个指向const double类型的指针,ptr的值不可以改变,ptr所指向的value的值也不可以改变
2、去掉const属性,例: const double value = 0.0f; double* ptr = NULL;怎么才能让ptr指向value?
强制类型转换,去掉const属性,如ptr = <const_cast double *>(&value);
18、宏的问题(MTK一道笔试题)
#define call(x,y) x##y
int x=10,y=5,xy=30;
求x+y+call(x,y)
其实x##y就是xy,所以这个题答案应该是:45
19、如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear,求这个队列中从队列头到队列尾的元素个数(包含队列头、队列尾)。
该队列只有一个队列头指针front,不设队列尾指针rear,而改置计数器count用以记录队列中结点的个数。
20、线程和进程区别和联系。什么是“线程安全”?(2012.5.6百度实习)
(1)如果说,在操作系统中引入进程的目的,是为了使多个程序能并发执行,以提高资源利用率和系统吞吐量。那么,在操作系统中再引入线程,则是为了减少程序在并发执行时所付出的空间开销,使OS具有更好的并发性。进程是作为拥有系统资源的基本单位,同时也是一个可独立调度和分派的基本单位(线程也是)。通常进程包含多个线程并为它们提供资源
(2)线程安全:如果你的代码所在的进程中有多个线程在同时运行,而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是一样的,而且其他的变量的值也和预期的是一样的,就是线程安全的。或者说:一个类或者程序所提供的接口对于线程来说是原子操作或者多个线程之间的切换不会导致该接口的执行结果存在二义性,也就是说我们不用考虑同步的问题。
21、题目:一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。
解法二:同样使用hash_map和链表
(1)将每一个字母对应一个质数,然后让对应的质数相乘,将得到的值进行hash,这样兄弟单词的值就是一样的了,并且不同单词的质数相乘积肯定不同。
(2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的质数相乘积,value为链表的起始地址。
(3)对于用户输入的单词进行计算,然后查找hash,将链表遍历输出就得到所有兄弟单词。
这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。
如果是海量词典的话,可以用B+树。。。。。
22、malloc/free与new/delete的区别与联系
相同点:
(1)都是申请内存,释放内存,free和delete可以释放NULL指针;
(2)都必须配对使用,这里的配对使用,可不能理解为一个new/malloc就对应一个delete/free,而是指在作用域内,new/malloc所申请的内存,必须被有效释放,否则将会导致内存泄露。
new/delete的功能完全覆盖了malloc/free,为什么C++还保留malloc/free呢?因为C++程序经常要调用C函数,而C程序只能用malloc/free管理动态内存。如果用free释放“new创建的动态对象”,那么该对象因无法执行析构函数而可能导致程序出错。如果用delete释放“malloc申请的动态内存”,理论上讲程序不会出错,但是该程序的可读性很差。
不同点:
(1)操作对象有所不同。
malloc与free是C++/C 语言的标准库函数,new/delete 是C++的运算符。对于非内部数据类的对象而言,光用maloc/free 无法满足动态对象的要求。对象在创建的同时要自动执行构造函数, 对象消亡之前要自动执行析构函数。由于malloc/free 是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函数和析构函数的任务强加malloc/free。
(2)用法上也有所不同。
1、malloc 返回值的类型是void *,所以在调用malloc 时要显式地进行类型转换,将void * 转换成所需要的指针类型。
2、 malloc 函数本身并不识别要申请的内存是什么类型,它只关心内存的总字节数。
new/delete 的使用要点:
运算符new 使用起来要比函数malloc 简单得多,
这是因为new 内置了sizeof、类型转换和类型安全检查功能。对于非内部数据类型的对象而言,new 在创建动态对象的同时完成了初始化工作。如果对象有多个构造函数,那么new 的语句也可以有多种形式。
如果用new 创建对象数组,那么只能使用对象的无参数构造函数。
Obj *objects = new Obj[100]; // 创建100 个动态对象
在用delete 释放对象数组时,留意不要丢了符号‘[]’。
再谈二者区别:
1、new自动计算需要分配的空间,而malloc需要手工计算字节数
2、new是类型安全的,而malloc不是,比如:
int* p = new float[2]; // 编译时指出错误
int* p = malloc(2*sizeof(float)); // 编译时无法指出错误
new operator 由两步构成,分别是 operator new 和 construct
3、operator new对应于malloc,但operator new可以重载,可以自定义内存分配策略,甚至不做内存分配,甚至分配到非内存设备上。而malloc无能为力。
4、new将调用constructor,而malloc不能;delete将调用destructor,而free不能。
5、malloc/free要库文件支持,new/delete则不要。
由于内部数据类型的“对象”没有构造与析构的过程,对它们而言malloc/free和new/delete是等价的。
23、数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。要求空间复杂度为O(1)。
思路:由于要求空间复杂度为O(1),故不能使用归并排序
1、遍历0~mid -1,将其与a[mid]相比较,若 a[mid] < a[i]; 则将其交换,进入2
2、循环遍历a[mid~length],如果1中交换后a[mid] > a[mid+1] 则进行交换,进行插入排序,将a[mid]插入到正确位置
24、static在C和C++中的用法和区别
static主要有三个作用:
(1)局部静态变量
(2)外部静态变量/函数
(3)静态数据成员/成员函数
前两种C和C++都有,第三种仅在C++中有,
在C/C++中, 局部变量按照存储形式可分为三种auto, static, register。其中register不常用到,下面主要说说auto和static的区别。
register变量叫做“寄存器变量”
1. 存储空间分配和生存周期不同
auto类型局部变量就是普通的局部变量(不加修饰的局部变量默认为该类型)。该类型局部变量存储在栈上,在动态存储区,生命周期仅限于定义它的函数,函数结束,它就自动释放。static类型局部变量存储在静态存储区,在程序整个运行期间都不释放。两者之间的作用域相同,但生存期不同。
2. static局部变量在所处模块在初次运行时进行初始化工作,且只操作一次(只出始化一次)。
3. 对于局部静态变量,如果不赋初值,编译期会自动赋初值0或空字符,而auto类型的初值是不确定的。(对于C++中的class对象例外,class的对象实例如果不初始化,则会自动调用默认构造函数,不管是否是static类型)
特点: static局部变量的”记忆性”与生存期的”全局性”
二、外部静态变量/函数
在C中 static有了第二种含义:用来表示不能被其它文件访问的全局变量和函数。但为了限制全局变量/函数的作用域, 函数或变量前加static使得函数成为静态函数。但此处“static”的含义不是指存储方式,而是指对函数的作用域仅局限于本文件(所以又称内部函 数)。注意此时, 对于外部(全局)变量, 不论是否有static限制, 它的存储区域都是在静态存储区,生存期都是全局的. 此时的static只是起作用域限制作用, 限定作用域在本模块(文件)内部.
使用内部函数的好处是:不同的人编写不同的函数时,不用担心自己定义的函数,是否会与其它文件中的函数同名。
三、静态数据成员/成员函数(C++特有)
C+ +重用了这个关键字,并赋予它与前面不同的第三种含义:表示属于一个类而不是属于此类的任何特定对象的变量和函数. 这是与普通成员函数的最大区别,
也是其应用所在, 比如在对某一个类的对象进行计数时, 计数生成多少个类的实例,
就可以用到静态数据成员. 在这里面, static既不是限定作用域的, 也不是扩展生存期的作用, 而是指示变量/函数在此类中的唯一性. 这也是”属于一个类而不是属于此类的任何特定对象的变量和函数”的含义. 因为它是对整个类来说是唯一的,因此不可能属于某一个实例对象的. (针对静态数据成员而言, 成员函数不管是否是static, 在内存中只有一个副本, 普通成员函数调用时, 需要传入this指针, static成员函数调用时, 没有this指针. )
原文链接:http://blog.csdn.net/skyereeee/article/details/8000512
虚成员函数函数不可能是static成员函数,?virtual函数一定要通过对象来调用,即有隐藏的this指针,而static没有this指针。
25、C/C++中const关键字
为什么使用const?采用符号常量写出的代码更容易维护,意味着“只读”。
取代了C中的宏定义,声明时必须进行初始化(!c++类中则不然,使用初始化列表初始化)
const修饰函数传入参数,通常修饰指针参数和引用参数:函数将不能修改由这个参数所指的对象。
void Fun( const A *in); //修饰指针型传入参数
void Fun(const A &in); //修饰引用型传入参数
修饰函数返回值
可以阻止用户修改返回值。返回值也要相应的付给一个常量或常指针。
const修饰成员函数(c++特性)
const对象只能访问const成员函数,而非const对象可以访问任意的成员函数,包括const成员函数;
const对象的成员是不能修改的,而通过指针维护的对象确实可以修改的;
const成员函数不可以修改对象的数据,不管对象是否具有const性质。编译时以是否修改成员数据为依据进行检查。
引用就是另一个变量的别名,它本身就是一个常量。也就是说不能再让一个引用成为另外一个变量的别名, 如果我们不希望函数的调用者改变参数的值。最可靠的方法应该是使用引用。
void func(const int& i) {
i = 100; // 错误!不能通过i去改变它所代表的内存区域。
}
在C++中,为了防止类的数据成员被非法访问,在一个函数的签名后面加上关键字const后该函数就成了常量函数。对于常量函数,最关键的不同是编译器不允许其修改类的数据成员。常量对象只能调用常量函数,通过常量对象调用非常量函数时将会产生语法错误。C++也允许我们在数据成员的定义前面加上mutable,以允许该成员可以在常量函数中被修改。
当存在同名同参数和返回值的常量函数和非常量函数时,常量对象调用常量成员;非常量对象调用非常量的成员。
const常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查,而对后者只进行字符替换,没有类型安全检查,并且在字符替换时可能会产生意料不到的错误(边际效应)
const数据成员只在某个对象生存期内是常量,而对于整个类而言却是可变的。所以不能在类声明中初始化const数据成员,因为类的对象未被创建时,编译器不知道const 数据成员的值是什么。const数据成员的初始化只能在类的构造函数的初始化表中进行。要想建立在整个类中都恒定的常量,应该用类中的枚举常量来实现。枚举常量不会占用对象的存储空间,他们在编译时被全部求值。
const 在c和c++中的区别
1. C++中的const正常情况下是看成编译期的常量,编译器并不为const分配空间,只是在编译的时候将期值保存在名字表中,并在适当的时候折合在代码中.
在C中,const是一个不能被改变的普通变量,既然是变量,就要占用存储空间,所以编译器不知道编译时的值.而且,数组定义时的下标必须为常量.
2.在c++ 中const 对象默认为文件的局部变量。变量只存在于那个文件中,不能被其他文件访问。通过指定 const 变更为 extern,就可以在整个程序中访问 const 对象
3. C++中,是否为const分配空间要看具体情况.如果加上关键字extern或者取const变量地址,则编译器就要为const分配存储空间.
4. C++中定义常量的时候不再采用define,因为define只做简单的宏替换,并不提供类型检查.
26、Epoll,Poll,Select模型比较
先说Select:
1.Socket数量限制:该模式可操作的Socket数由FD_SETSIZE决定,内核默认32*32=1024.
2.操作限制:通过遍历FD_SETSIZE个Socket来完成调度,不管哪个Socket是活跃的,都遍历一遍.
后说Poll:
1.Socket数量几乎无限制:该模式下的Socket对应的fd列表由一个数组来保存,大小不限(默认4k).
2.操作限制:同Select.
再说:Epoll:
1.Socket数量无限制:同Poll
2.操作无限制:基于内核提供的反射模式,有活跃Socket时,内核访问该Socket的callback,不需要遍历轮询.
27、深拷贝,浅拷贝的区别
当出现类的等号赋值时,会调用拷贝函数在未定义显示拷贝构造函数的情况下,系统会调用默认的拷贝函数——即浅拷贝,它能够完成成员的一一复制。当数据成员中没有指针时,浅拷贝是可行的。
但当数据成员中有指针时,如果采用简单的浅拷贝,则两类中的两个指针将指向同一个地址,当对象快结束时,会调用两次析构函数,而导致指针悬挂现象。
所以,这时,必须采用深拷贝。深拷贝与浅拷贝的区别就在于深拷贝会在堆内存中另外申请空间来储存数据,从而也就解决了指针悬挂的问题。
简而言之,当数据成员中有指针时,必须要用深拷贝。
28、常用数据类型对应字节数
可用如sizeof(char),sizeof(char*)等得出
32位编译器:
char :1个字节
char*(即指针变量): 4个字节(32位的寻址空间是2^32, 即32个bit,也就是4个字节。同理64位编译器)
short int : 2个字节
int: 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 4个字节
long long: 8个字节
unsigned long: 4个字节
64位编译器:
char :1个字节
char*(即指针变量): 8个字节
short int : 2个字节
int: 4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 8个字节
long long: 8个字节
unsigned long: 8个字节
29、多态的实现原理及多态的内存分布
关于虚函数的背景知识
- 用virtual关键字申明的函数叫做虚函数,虚函数肯定是类的成员函数。
- 存在虚函数的类都有一个一维的虚函数表叫做虚表。类的对象有一个指向虚表开始的虚指针。虚表是和类对应的,虚表指针是和对象对应的。
- 多态性是一个接口多种实现,是面向对象的核心。分为类的多态性和函数的多态性。
- 多态用虚函数来实现,结合动态绑定。
- 纯虚函数是虚函数再加上= 0。并且该函数只有声明,没有实现。
- 抽象类是指包括至少一个纯虚函数的类。
在构造函数中进行虚表的创建和虚表指针的初始化。
对于虚函数调用来说,每一个对象内部都有一个虚表指针,该虚表指针被初始化为本类的虚表。所以在程序中,不管你的对象类型如何转换,但该对象内部的虚表指针是固定的,所以呢,才能实现动态的对象函数调用,这就是C++多态性实现的原理。
总结(基类有虚函数):
- 每一个类都有虚表。
- 虚表可以继承,如果子类没有重写虚函数,那么子类虚表中仍然会有该函数的地址,只不过这个地址指向的是基类的虚函数实现。如果基类有3个虚函数,那么基类的虚表中就有三项(虚函数地址),派生类也会有虚表,至少有三项,如果重写了相应的虚函数,那么虚表中的地址就会改变,指向自身的虚函数实现。如果派生类有自己的虚函数,那么虚表中就会添加该项。
- 派生类的虚表中虚函数地址的排列顺序和基类的虚表中虚函数地址排列顺序相同。
如何快速排序?
有向图中最短路径怎么算?(Dijkstra算法)
以下题目来自:http://www.51nod.com/question/index.html#!questionId=700
1、 将一个排好序的数组,转变成一颗平衡二叉树(尽量平衡)
这个用中位数递归处理就可以了。先用中位数做根。然后递归,分别用两段的中间元素做左右孩子,这样建成的二叉树一定是平衡二叉树了,并且树高是最低的。
2、 给出n个会议的起始时间和结束时间,如何快速计算是会议是否和其他会议有冲突?
这个问题先按照起始时间排个序,然后O(n)遍历一下就好了,遍历过程中记录结束时间的最大值,如果当前开始时间早于结束时间的最大值,就是有冲突。
3、题目如下:
数据库1中存放着a类数据,数据库2中存放着以天为单位划分的表30张(比如table_20110909,table_20110910,table_20110911),总共是一个月的数据。表1中的a类数据中有一个字段userid来唯一判别用户身份,表2中的30张表(每张表结构相同)也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据库2中出现过?
答:select count(*) from 数据库1.a类数据
where exists (select 1 from 数据库2.table_20110909 where userid = 数据库1.a类数据.userid)
or exists (select 1 from 数据库2.table_20110910 where userid = 数据库1.a类数据.userid)
or exists (select 1 from 数据库2.table_20110911 where userid = 数据库1.a类数据.userid)
3、 有一箱苹果,3个一包还剩2个,5个一包还剩3个,7个一包还剩2个,求N个满足以上条件的苹果个数。
答: if(i%3==2&&i%5==3&&i%7==2) 可推出 苹果数为: 21n+2
4、两个骰子,两个人轮流投,直到点数和大于6就停止,最终投的那个人获胜。问先投那个人获胜概率?
先算出2个骰子扔一次大于6的概率,两个的组合数为6*6 = 36,<=6的排列包括:
(1 1)(1 2)(1 3)(1 4)(1 5) | (2 1)(2 2)(2 3)(2 4).....
共5 + 4 + 3 + 2 + 1 = 15种,因而第每一次投超过6的概率为(36 - 15)/36 = 7/12,
不大于6的概率为5/12
因此获胜概率 = 7/12 + (5/12 * 5/12) * 7/12 + (5/12*5/12 *5/12 *5/12) * 7/12 + ......,相当于求一个首项为1,公比为25/144的等比数列的和,最后再乘7/12。
25/144 等比数列求和 = 1/(1 - 25/144) = 144/119,乘以7/12 = 12/17。
4、 给定一个凸四边形,如何判断一个点在这个平面上(四边形内)。
将该点和该凸四边形的四个顶点连起来,相邻2个四边形顶点和该点构成三角形,共4个,判断4个三角形之和的面积与四边形的面积关系即可。如果点在内部或这边上,则三角形面积之和等于四边形面积,否则大于
5、 长度为1的线段,随机在其上选择两点,将线段分为三段,问这3个字段能组成一个三角形的概率
不满足条件有三种情况:
1. a, b<1/2
2. a, b>1/2
3. a<1/2, b>1/2, b-a>1/2
1. 1/4概率
2. 1/4概率
3. 1/4概率
所以组成三角形的概率是1/4
用空间几何的角度来看的话,就是看 平面 x+y+z=1 (x,y,z>=0) 被三个平面 x+y>=z, x+z>=y, z+y>=x 所截部分的面积比,很容易看出来面积比就是 1/4
6、 马路口,30分钟内看到汽车的概率是95%,那么在10分钟内看不到汽车的概率是?
答: 在一定时间段内到达车辆的个数应该用泊松分布来近似吧?
如果用泊松分布的话,有
e^(λ30)λ^0/0! = 1- 95%,即 e^(λ30) = 5%
所以10分钟看不到车的概率是 e^(λ10)λ^0/0!=(5%)^(1/3)
7、 一个贼每次上楼梯1或者2,一个27层的楼梯需要多少种方法,记住贼不能经过5,8,13层,否则会被抓住。
还是可以用斐波那契来推算,f(n) = f(n-1) + f(n-2),只是f(5) f(8) f(13) = 0。
8、 有20个数组,每个数组里面有500个数组,降序排列,每个数字是32位的unit,求出这10000个数字中最大的500个。
为了方便讨论,先设计几个变量。n表示所有元素的数量,n=100000。m表示数组的数量,m=20,k选择最大的元素数量,k=500。
建个m的堆,搞多路归并,复杂度log(m)*k
9、100个任务,100个工人每人可做一项任务,每个任务每个人做的的费用为t[100][100],求一个分配任务的方案使得总费用最少。
解题过程:
每行减去其最小成本(即每行最小数):
10、你现在有一个文件,文件中顺序存有N个记录,R1,R2,...,RN,这些记录不是有序的,但是你知道一个整数M,这些记录满足R1<R2<...<RM以及RM+1<RM+2<...RN.
1,设计一个算法或编写一个程序,将文件中的记录排序为R1'<R2',<…<,RN',算法或程序读取文件的次数为O(N),不限内存使用,
2,设计一个算法或编写一个程序,将文件中的记录排序为R1'<R2'<...<RN',算法或程序读写文件的次数为O(N),空间复杂度为O(1),(亦即,你使用的内存大小和M,N均无关。)
1 将前M条读入内存中,然后从M+1条开始,进行归并,将结果写入新的文件。
2 将前M条记录写入到另一个临时文件,然后对两个文件进行归并。
11、设计一个大数乘法
void GetDigits(int *a,char *s);
void multiply(int *a,int *b,int *c);
//把输入的字符串,按位存放到数组
GetDigits(a,s1);
GetDigits(b,s2);
multiply(a,b,c);
//找到最高位
j=N*2-1;
while(c[j]==0)
j--;
printf("\n %s * %s=",s1,s2);//打印结果
for(i=j;i>=0;i--)
printf("%d",c[i]);
/*把字符串形式的数字按位存放到数组*/
void GetDigits(int *a, char *s)
{
int i;
char digit;
int len=strlen(s);
for(i=0;i<N;i++)
*(a+i)=0;
for(i=0;i<len;i++)
{
digit=*(s+i);
*(a+len-1-i) = digit - '0';
}
}
/*把a*b的结果存储到数组c中,按位表示*/
void multiply(int *a,int *b,int *c)
{
int i,j;
//先把结果数组设置为0
for(i=0;i<N*2;i++)
*(c+i)=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
*(c+i+j)+=*(a+i) * *(b+j);
// 处理进位
for(i=0;i<N*2-1;i++)
{
*(c+i+1)+=*(c+i)/10; //进位累加到高位
*(c+i)=*(c+i)%10; //该位的最后结果
}
}