程序员数学经典题

A. 面试最常考的 100 道算法题分类整理

大家好，我是 “负雪明早冲烛” ，一位用 7 年写槐毁了 1000 篇 LeetCode 算法题题解的程序员。欢迎关注。

粉丝常说： LeetCode 算法题太多了，准备面试该刷哪些题目 ？

我之前根据 LeetCode 上面的点赞量分享过： LeetCode 上最经典的 100 道算法题 。

这 100 道题目都属于经典题目了，面试也常考，不过我还是不放心呢，毕竟 经典题 ≠ 面试题 呀！

但如果想知道面试常考的 100 道算法题的话，需要至少整理 1000 篇面经吧？这个工作量可不小啊！

还好，网上有个开源项目，帮我们做了这件事情，这个项目就是 CodeTop ！

这是网站的界面（地址： https://codetop.cc/home ），展示的就是每个面试题目出现的频度情况，甚至区分了公司和岗位：

这是开源项目的 GitHub 主页，已经 11.5k star ⭐️ 了：

这个项目中的题目来源是牛客网的面经、网友投票等，而且持续更新中，所以还是比较可靠的。

我对这个项目做了陆明歼整理，分类整理出来面试常考的 100 道算法题。

在整理之后，我对结果还是有点 惊讶 的！因为一些常见的数据结构与算法，竟然没有在常考面试中出现过！

比如前缀和、前缀树、并查集、图，这些都没有出现……

最常考面试题还是很基本的链表、二叉树、动态规划等等，是不是符合你的认知呢？

强烈建议大家在面试前把这 100 道题目搞懂！

作为宠粉达人，我提供了 3 种方式查看这 100 道题目：

没有任何套路，直接分享给大家！

在线查看地址： https://www.mubucm.com/doc/7jiBYKCKqet

在线查看地址： https://leetcode-cn.com/problem-list/q3iOID0B/

所有题目的地址如下：

前序遍历

中序遍历

层序遍历

视图

如果你觉得对你有帮助的话，求赞、求分享、求收藏。你的每一点鼓励都是对我的最大帮助！

B. C/C++经典面试题

C/C++经典面试题

面试题 1：变量的声明和定义有什么区别

为变量分配地址和存储空间的称为定义，不分配地址的称为声明。一个变量可以在多个地方声明，

但是只在一个地方定义。加入 extern修饰的是变量的声明，说明此变量将在文件以外或在文件后面部分

定义。

说明：很多时候一个变量，只是声明不分配内存空间，直到具体使用时才初始化，分配内存空间，

如外部变量。

面试题 2：写出 bool 、int、 float、指针变量与“零值”比较的 if 语句

bool型数据：

if( flag )

{

A;

}

else

{

B;

}

int型数据：

if( 0 != flag )

{

A;

}

else

{

B;

}

指针型数：

if( NULL == flag )

{

A;

}

else

{

B;

}

float型数据：

if ( ( flag >= NORM ) && ( flag <= NORM ) )

{

A;

2

}

注意：应特别注意在 int、指针型变量和“零值”比较的时候，把“零值”放在左边，这样当把“==”

误写成“=”时，编译器可以报错，否则这种逻辑错误不容易发现，并且可能导致很严重的后果。

面试题 3：sizeof 和strlen的区别

sizeof和 strlen 有以下区别：

 sizeof是一个操作符，strlen是库函数。

 sizeof的参数可以是数据的类型，也可以是变量，而 strlen只能以结尾为‘‘的字符串作参数。

 编译器在编译时就计算出了 sizeof 的结果。而 strlen 函数必须在运行时才能计算出来。并且 sizeof

计算的是数据类型占内存的大小，而 strlen计算的是字符串实际的长度。

 数组做sizeof的参数不退化，传递给strlen就退化为指针了。

注意：有些是操作符看起来像是函数，而有些函数名看起来又像操作符，这类容易混淆的名称一定

要加以区分，否则遇到数组名这类特殊数据类型作参数时就很容易出错。最容易混淆为函数的操作符就

是 sizeof。

面试题 4：C 语言的关键字 static 和 C++ 的关键字 static 有什么区别

在C 中static 用来修饰局部静态变量和外部静态变量、函数。而 C++中除了上述功能外，还用来定

义类的成员变量和函数。即静态成员和静态成员函数。

注意：编程时 static的记忆性，和全局性的特点可以让在不同时期调用的函数进行通信，传递信息，

而 C++的静态成员则可以在多个对象实例间进行通信，传递信息。

面试题 5：C中的 malloc 和C++中的 new有什么区别

malloc和 new有以下不同：

(1)new、 是操作符，可以重载，只能在 C++中使用。

(2)malloc、free是函数，可以覆盖，C、C++中都可以使用。

(3)new 可以调用对象的构造函数，对应的 调用相应的析构函数。

(4)malloc仅仅分配内存，free 仅仅回收内存，并不执行构造和析构函数

(5)new、 返回的是某种数据类型指针，malloc、free 返回的是void指针。

注意：malloc申请的内存空间要用 free释放，而 new申请的内存空间要用 释放，不要混用。

因为两者实现的机理不同。

面试题 6：写一个“标准”宏 MIN

#define min(a,b)((a)<=(b)?(a):(b))

注意：在调用时一定要注意这个宏定义的副作用，如下调用：

((++*p)<=(x)?(++*p):(x)。

p指针就自加了两次，违背了 MIN的本意。

面试题 7：一个指针可以是 volatile 吗

可以，因为指针和普通变量一样，有时也有变化程序的不可控性。常见例：子中断服务子程序修改

一个指向一个 buffer的指针时，必须用 volatile来修饰这个指针。

说明：指针是一种普通的变量，从访问上没有什么不同于其他变量的特性。其保存的数值是个整型

数据，和整型变量不同的是，这个整型数据指向的是一段内存地址。

面试题 8：a 和&a 有什么区别

请写出以下代码的打印结果，主要目的是考察 a和&a的区别。

#include

void main( void )

{

int a[5]={1,2,3,4,5};

int *ptr=(int *)(&a+1);

printf(“%d,%d”,*(a+1),*(ptr-1));

return;

}

输出结果：2，5。

注意：数组名 a可以作数组的首地址，而&a是数组的指针。思考，将原式的 int *ptr=(int *)(&a+1);

改为 int *ptr=(int *)(a+1);时输出结果将是什么呢?

面试题 9：简述 C、C++程序编译的.内存分配情况

C、C++中内存分配方式可以分为三种：

(1)从静态存储区域分配：

内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在。速度快、不容易出错，

因为有系统会善后。例如全局变量，static变量等。

(2)在栈上分配：

在执行函数时，函数内局部变量的存储单元都在栈上创建，函数执行结束时这些存储单元自动被释

放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

(3)从堆上分配：

即动态内存分配。程序在运行的时候用 malloc 或 new 申请任意大小的内存，程序员自己负责在何

时用free 或 释放内存。动态内存的生存期由程序员决定，使用非常灵活。如果在堆上分配了空间，

就有责任回收它，否则运行的程序会出现内存泄漏，另外频繁地分配和释放不同大小的堆空间将会产生

堆内碎块。

一个C、C++程序编译时内存分为 5大存储区：堆区、栈区、全局区、文字常量区、程序代码区。

4

面试题 10：简述 strcpy、sprintf 与 memcpy的区别

三者主要有以下不同之处：

(1)操作对象不同，strcpy的两个操作对象均为字符串，sprintf的操作源对象可以是多种数据类型，

目的操作对象是字符串， memcpy 的两个对象就是两个任意可操作的内存地址，并不限于何种数据类型。

(2)执行效率不同，memcpy最高，strcpy次之，sprintf的效率最低。

(3)实现功能不同，strcpy主要实现字符串变量间的拷贝，sprintf 主要实现其他数据类型格式到字

符串的转化，memcpy主要是内存块间的拷贝。

说明：strcpy、sprintf 与memcpy都可以实现拷贝的功能，但是针对的对象不同，根据实际需求，来

选择合适的函数实现拷贝功能。

C. c++经典面试题及答案

1. C++的类和C里面的struct有什么区别?

struct成员默认访问权限为public，而class成员默认访问权限为private

2. 析构函数和虚函数的用法和作用

析构函数是在对象生存期结束时自动调用的函数，用来释放在构造函数分配的内存。

虚函数是指被关键字virtual说明的函数，作用是使用C++语言的多态特性

3. 全局变量和局部变量有什么区别?是怎么实现的?操作系统和编译器是怎么知道的?

1) 全局变量的作用用这个程序块,而局部变量作用于当前函数

2) 前者在内存中分配在全局数据区,后者分配在栈区

3) 生命周期不同：全局变量随主程序创建和创建，随主程序销毁而销毁，局部变量在局部函数内部，甚至局部循环体等内部存在，退出就不存在

4) 使用方式不同：通过声明后全局变量程序的各个部分都可以用到，局部变量只能在局部使用

4. 有N个大小不等的自然数(1–N)，请将它们由小到大排序.要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。

void sort(int e[], int n)

{

int i;

int t;

for (i=1; i {

t = e[e[i]];

e[e[i]] = e[i];

e[i] = t;

}

}

5. 堆与栈的去区别

A. 申请方式不同

Stack由系统自动分配，而heap需要程序员自己申请，并指明大小。

B. 申请后系统的响应不同

Stack：只要栈的剩余空间大于申请空间，系统就为程序提供内存，否则将抛出栈溢出异常

Heap：当系统收到程序申请时，先遍历操作系统中记录空闲内存地址的链表，寻找第一个大于所申请空间的堆结点，然后将该结点从空间结点链表中删 除，并将该结点的空间分配给程序。另外，大多数系统还会在这块内存空间中的首地址处记录本次分配的大小，以便于delete语句正确释放空间。而且，由于 找到的堆结点的大小不一定正好等于申请的大小，系统会自动将多余的那部分重新放入空闲链表。

C. 申请大小限制的不同

Stack：在windows下，栈的大小是2M(也可能是1M它是一个编译时就确定的常数)，如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。

Heap：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

D. 申请效率的比较：

栈由系统自动分配，速度较快。但程序员是无法控制的。

堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。

E. 堆和栈中的存储内容

栈：在函数调用时，第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址，然后是函数的各个参数，在大多数的C编译器 中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开 始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。

堆：一般是在堆的.头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

6. 含参数的宏与函数的优缺点

宏： 优点：在预处理阶段完成，不占用编译时间，同时，省去了函数调用的开销，运行效率高

缺点：不进行类型检查，多次宏替换会导致代码体积变大，而且由于宏本质上是字符串替换，故可能会由于一些参数的副作用导致得出错误的结果。

函数： 优点：没有带参数宏可能导致的副作用，进行类型检查，计算的正确性更有保证。

缺点：函数调用需要参数、返回地址等的入栈、出栈开销，效率没有带参数宏高

PS：宏与内联函数的区别

内联函数和宏都是在程序出现的地方展开，内联函数不是通过函数调用实现的，是在调用该函数的程序处将它展开(在编译期间完成的);宏同样是;

不同的是：内联函数可以在编译期间完成诸如类型检测，语句是否正确等编译功能;宏就不具有这样的功能，而且宏展开的时间和内联函数也是不同的(在运行期间展开)

7. Windows程序的入口是哪里?写出Windows消息机制的流程

Windows程序的入口是WinMain()函数。

Windows应用程序消息处理机制：

A. 操作系统接收应用程序的窗口消息，将消息投递到该应用程序的消息队列中

B. 应用程序在消息循环中调用GetMessage函数从消息队列中取出一条一条的消息，取出消息后，应用程序可以对消息进行一些预处理。

C. 应用程序调用DispatchMessage，将消息回传给操作系统。

D. 系统利用WNDCLASS结构体的lpfnWndProc成员保存的窗口过程函数的指针调用窗口过程，对消息进行处理。

8. 如何定义和实现一个类的成员函数为回调函数

A.什么是回调函数?

简而言之，回调函数就是被调用者回头调用调用者的函数。

使用回调函数实际上就是在调用某个函数(通常是API函数)时，将自己的一个函数(这个函数为回调函数)的地址作为参数传递给那个被调用函数。而该被调用函数在需要的时候，利用传递的地址调用回调函数。

回调函数，就是由你自己写的，你需要调用另外一个函数，而这个函数的其中一个参数，就是你的这个回调函数名。这样，系统在必要的时候，就会调用你写的回调函数，这样你就可以在回调函数里完成你要做的事。

B.如何定义和实现一个类的成员函数为回调函数

要定义和实现一个类的成员函数为回调函数需要做三件事：

a.声明;

b.定义;

c.设置触发条件，就是在你的函数中把你的回调函数名作为一个参数，以便系统调用

如：

一、声明回调函数类型

typedef void (*FunPtr)(void);

二、定义回调函数

class A

{

public:

A();

static void callBackFun(void) //回调函数，必须声明为static

{

cout<<"callBackFun"<

}

virtual ~A();

};

三、设置触发条件

void Funtype(FunPtr p)

{

p();

}

void main(void)

{

Funtype(A::callBackFun);

}

C. 回调函数与API函数

回调和API非常接近，他们的共性都是跨层调用的函数。但区别是API是低层提供给高层的调用，一般这个函数对高层都是已知的;而回调正好相反， 他是高层提供给底层的调用，对于低层他是未知的，必须由高层进行安装，这个安装函数其实就是一个低层提供的API，安装后低层不知道这个回调的名字，但它 通过一个函数指针来保存这个回调函数，在需要调用时，只需引用这个函数指针和相关的参数指针。

其实：回调就是该函数写在高层，低层通过一个函数指针保存这个函数，在某个事件的触发下，低层通过该函数指针调用高层那个函数。