您的位置: 首页  >  文章  >  C++面试要点（Part 2）

C++面试要点（Part 2）

分类: 文章 • 2024-04-30 17:27:28

C++面试要点（Part 2）

下面题目都是面试经常问到的，答案可能比较简略，大家想了解详细的实现要再进行搜索，大神的博客写得都很清楚。这次再更新30题！！！

1.图论基本算法

a.广度优先搜索

C++面试要点（Part 2）

b.深度优先搜索

  • 访问搜索到的未被访问的邻接点；

  • 将此顶点标记为已访问节点；

  • 搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

栈实现

C++面试要点（Part 2）

递归实现

C++面试要点（Part 2）

c.Dijkstra算法

  • 采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

  • 然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

  • 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

  • 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

d.有权无向图最小生成树算法

Prim算法的步骤包括：

  • 将一个图分为两部分，一部分归为点集U，一部分归为点集V，U的初始集合为{V1}，V的初始集合为{ALL-V1}。
  • 针对U开始找U中各节点的所有关联的边的权值最小的那个，然后将关联的节点Vi加入到U中，并且从V中删除（注意不能形成环）。
  • 递归执行步骤2，直到V中的集合为空。
  • U中所有节点构成的树就是最小生成树。

Kruskal算法的步骤包括：

  • 对所有权值进行从小到大排序（这里对边排序时还需要记录边的索引，这样以边的权值排完序后只改变了权值的索引位置）

  • 然后每次选取最小的权值，如果和已有点集构成环则跳过，否则加到该点集中。最终有所有的点集构成的树就是最佳的。

2.sizeof一个空类是多大？为什么？编译器为什么这么做？

1个字节，任何一个实例在内存中都有一个独一无二的地址，为了达到这个目的，编译器往往会给一个空类隐含的加一个字节，这样空类在实例化后在内存得到了独一无二的地址。

3.在这个类中添加一个virtual函数后再sizeof，这时是多大？为什么？

4个字节，有virtual函数，就会对应一个指向虚函数表的vptr指针，指针的大小在32位系统中是4个字节.

4.inline关键字是做什么用的？inline关键字在什么情况下会展开失败？

内联函数。inline类似于将代码直接替换，但是又不是。省去了调用函数的开销。增快了代码的执行效率。代码长度过大，会导致展开失败

5.虚拟内存

操作系统在管理内存时，每个进程都有一个独立的进程地址空间，进程地址空间的地址为虚拟地址，对于32位操作系统，该虚拟地址空间为2^32=4GB

6.STL容器

  • 无序容器在管理上组织为一组桶，通过哈希函数将元素映射到桶，每个桶存放0个或多个元素，相同哈希值存放在同一个桶，效率取决于桶的数量和哈希函数的质量。

  • 关联容器map, set函数insert erase find count lower_bound，upper_bound，equal_range,

Map下标操作，遍历通常迭代器

  • 迭代器使算法不依赖于容器，但依赖于元素操作

7.C风格字符串函数

strlen()，strcpy()，strcat()，strcmp()

8.操作系统页面置换算法

最佳置换算法，先入先出置换算法，最近最久未被使用，时钟置换算法。

9.C++从源代码到可执行文件经过了哪些过程

  • 预处理 宏替换，条件编译，#include，删除注释，添加行号和文件标识

  • 编译 词法分析，语法分析，语义分析及优化后生成相应的汇编代码文件

  • 汇编 将汇编代码转变成机器可执行代码

  • 链接 地址和空间分配(Address and Storage Allocation)、符号决议(Symbol Resolution)和重定位(Relocation)

10.什么是库？

库是写好的现有的，成熟的，可以复用的代码。

现实中每个程序都要依赖很多基础的底层库 ，本质上来说库是一种可执行代码的二进制形式，可以被操作系统载入内存执行。库有两种：静态库（.a、.lib）和动态库（.so、.dll）

11.静态链接与动态链接

因为在链接阶段，会将汇编生成的目标文件.o与引用到的库一起链接打包到可执行文件中。因此对应的链接方式称为静态链接。

  • 静态库对函数库的链接是放在编译时期完成的。

  • 程序在运行时与函数库再无瓜葛，移植方便。

  • 浪费空间和资源，因为所有相关的目标文件与牵涉到的函数库被链接合成一个可执行文件。

  • 静态库对程序的更新、部署和发布也会带来麻烦

动态库在程序编译时并不会被连接到目标代码中，而是在程序运行是才被载入

  • 不同的应用程序如果调用相同的库，那么在内存里只需要有一份该共享库的实例

  • 只需要更新动态库即可，增量更新

  • 使用动态链接库的应用程序不是自完备的，它依赖DLL模块，速度比静态链接慢

12.ISO网络模型有几层？每层是什么？分别作用？

ISO国际标准化组织。

OSI七层开放式系统互联模型。

  • 应用层 :网络与用户接口，完成网络用户的应用需求

  • 表示层 :改变数据表示方式，数据压缩和加密

  • 会话层 :建立，管理，终止应用程序的会话

  • 运输层 :为上层协议提供端对端可靠，透明的数据传输服务

  • 网络层 :通过路由选择算法决定数据包如何在节点间传输

  • 数据链路层 :解决两个相邻节点的通信问题

  • 物理层: 利用传输介质为数据链路层提供物理连接

13.什么是控制反转？

控制反转就是应用本身不负责依赖对象的创建和维护，而是交给外部容器来负责。

14.引用与指针的区别

  • 引用是对象的别名，指针是对象，值存储的是数据的地址

  • 引用必须初始化，指针不必初始化

  • 存在指向空值的指针，不存在指向空值的引用

  • 引用一旦初始化完成，不允许再绑定其他对象，指针可以改变值

  • 指针作为形参传递值，引用作为形参传递引用

  • 存在const指针，但不存在const引用

  • 存在指针的数组，不存在引用的数组

15.内存对齐原因

平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据，硬件原因：经过内存对齐之后，CPU的内存访问速度大大提升。

16.内存重叠

内存重叠：拷贝的目的地址在源地址范围内

函数strcpy和函数memcpy都没有对内存重叠做处理的

memmove函数对内存重叠做了处理，不重叠时正向拷贝，重叠时反向拷贝

17.各种排序方法

  • 希尔排序通过增量对数据分组，对组内元素进行插排，不断减小增量，直到增量为1
  • 插入排序将数据分为有序区和无序区。每次从无序区取出一个元素，放入有序区插排 O（n） O（n^2）
  • 冒泡排序比较相邻元素反序则交换，有序区不断增大 O（n） O（n^2）
  • 快速排序取一个值作为轴，小的放左边，大的放右边，递归该过程 O（nlog2n） O（n^2）
  • 堆排序构造大根堆，将堆顶元素取走，剩余元素再整理成堆，直至有序 O（nlog2n） O（nlog2n）
  • 归并排序首先将一个序列分二，二分为四，然后对若干序列两两归并 O（nlog2n） O（nlog2n）

18.栈帧

栈帧也叫过程活动记录，是编译器用来实现过程/函数调用的一种数据结构

  • 寄存器ebp（base pointer ）可称为“帧指针”或“基址指针”
  • 寄存器esp（stack pointer）可称为“ 栈指针”。
  • ebp 在未受改变之前始终指向栈底，所以ebp的用途是在堆栈中寻址用的。
  • esp是会随着数据的入栈和出栈移动的， esp始终指向栈顶。

栈是向下生长的，所谓向下生长是指从内存高地址->低地址的路径延伸

任何时候，这一对指针指向的是同一个函数的栈帧结构

Main函数调用其他函数之前会将ebp和esp压入栈保护起来，等被调用函数执行完再出栈

19.死锁

死锁定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程占有资源的事件，那仫该组进程就是死锁的.

产生死锁的必要条件

  • 互斥条件，进程对资源独立占有
  • 不可抢占
  • 请求和保持 请求资源的同时保持当前资源
  • 循环等待条件

死锁预防

  • 破坏不可抢占，请求资源不能获得时释放占有的资源

  • 破坏请求与保持，每个进程在开始时就申请所需全部资源

死锁避免

  • 系统对进程的资源请求进行检查，分配后是否可能出现死锁。
    • 安全状态指如果对其中每一个进程Pi(i >=1 && i <= n)他以后尚需要的资源不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量之和，系统处于安全状态则不会发生死锁。
    • 不安全状态可能死锁也可能不死锁

20.银行家算法

  • 可利用资源矩阵Available[i][j]

  • 最大需求矩阵Max[i][j]

  • 分配矩阵Allocation[i][j]

  • 需求矩阵Need[i][j] = Max - Allocation

(1).如果Request[i] <= Need[i][j]转下步，否则它所需要的资源数已超过它所需要的最大值

(2).如果Request[i] <= Available[i][j]转下步，否则尚无足够资源，进程需等待

(3).系统试分配给进程p,并修改Available,Allocation和Need

​ Available[j] -= Request[j]

​ Allocation[i][j] += Request[j]

​ Need[i][j] -= Request[j]

(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态.若安全，才正式分配；否则恢复原来的分配状态，让该进程等待

检查算法描述：

向量Free[ j ]表示系统可分配给各进程的Rj类资源数目，初始与当前Available等值

向量Finish[ i ]表示进程Pi在此次检查中是否被满足，初始均为false 当有足有资源可分配给进程时，

Finish[ i ]=true, Pi完成并释放资源(Free[ j ]+=Allocation[ i ][ j ])

  1. 从进程队列中找一个能满足下述条件的进程Pi

  • Finish[ i ]==false,表示资源未分配给Pi进程

  • Need[ i ][ j ]<Free[ j ],表示资源足够分配给Pi进程

  1. 当Pi获得资源后，认为Pi完成，释放资源

Free[ j ]+=Allocation[ i ][ j ];

Finish[ i ]=true;

goto Step 1）；

21.ARP协议工作原理

每台主机都会在自己的ARP缓冲区中建立一个 ARP列表，以表示IP地址和MAC地址的对应关系。当源主机需要将一个数据包要发送到目的主机时，会首先检查自己 ARP列表中是否存在该 IP地址对应的MAC地址，如果有，就直接将数据包发送到这个MAC地址；如果没有，就向本地网段发起一个ARP请求的广播包，查询此目的主机对应的MAC地址。

此ARP请求数据包里包括源主机的IP地址、硬件地址、以及目的主机的IP地址。网络中所有的主机收到这个ARP请求后，会检查数据包中的目的IP是否和自己的IP地址一致。如果不相同就忽略此数据包；如果相同，该主机首先将发送端的MAC地址和IP地址添加到自己的ARP列表中，如果ARP表中已经存在该IP的信息，则将其覆盖，然后给源主机发送一个 ARP响应数据包，告诉对方自己是它需要查找的MAC地址；

源主机收到这个ARP响应数据包后，将得到的目的主机的IP地址和MAC地址添加到自己的ARP列表中，并利用此信息开始数据的传输。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。

22.常见的路由选择协议，以及它们的区别

常见的路由选择协议有：RIP协议、OSPF协议。

  • RIP协议：底层是贝尔曼福特算法，它选择路由的度量标准（metric)是跳数，最大跳数是15跳，如果大于15跳，它就会丢弃数据包。

  • OSPF协议：底层是迪杰斯特拉算法，是链路状态路由选择协议，它选择路由的度量标准是带宽，延迟。

23.TCP与UDP的区别

UDP是面向无连接的，不可靠的数据报服务；

TCP是面向连接的，可靠的字节流服务。

TCP对应的协议和UDP对应的协议

TCP：HTTP，FTP，Telnet，SMTP，POP3

UDP：DNS

24.HTTP协议包括哪些请求？

GET：请求读取由URL所标志的信息。

POST：给服务器添加信息（如注释）。

PUT：在给定的URL下存储一个文档。

DELETE：删除给定的URL所标志的资源。

HEAD:获取头部信息

25.网络协议解释

  • NAT协议：网络地址转换(NAT,Network AddressTranslation)属接入广域网(WAN)技术
  • DHCP协议：动态主机设置协议（Dynamic Host ConfigurationProtocol, DHCP）
  • DNS协议：DNS 是域名系统 (Domain Name System) 的缩写，是因特网的一项核心服务，它作为可以将域名和IP地址相互映射的一个分布式数据库

26. 交换机

交换机属于数据链路层，mac对应端口，自学习，路由属于网络层，路由表IP对应端口

27.虚继承

虚继承底层实现原理与编译器相关，一般通过虚基类指针和虚基类表实现，每个虚继承的子类都有一个虚基类指针（占用一个指针的存储空间，4字节）和虚基类表（不占用类对象的存储空间）（需要强调的是，虚基类依旧会在子类里面存在拷贝，只是仅仅最多存在一份而已，并不是不在子类里面了）；当虚继承的子类被当做父类继承时，虚基类指针也会被继承。

实际上，vbptr指的是虚基类表指针（virtual base table pointer），该指针指向了一个虚基类表（virtual table），虚表中记录了虚基类与本类的偏移地址；通过偏移地址，这样就找到了虚基类成员，而虚继承也不用像普通多继承那样维持着公共基类（虚基类）的两份同样的拷贝，节省了存储空间。

28.STL提供六大组件

STL提供六大组件，彼此可以组合套用

  • 容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。

  • 算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。

  • 迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。

  • 仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator()的class或class template。一般的函数指针也可视为狭义的仿函数。

  • 适配器（adapters）：一种用来修饰容器、仿函数、迭代器接口的东西。

  • 配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

29. STL容器实现

vector采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围

vector采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端。

以原来大小的的两倍另外分配一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。

stack默认以deque为底层容器。

queue默认以deque为底层容器。

priority queue的底层机制, heap默认建立的是大堆。

Map和Set底层基于红黑树实现，无序容器基于哈希表。

STL的中心思想是：将数据容器和算法分隔开，彼此独立设计，最后再用黏合剂将它们撮合在一起。黏合剂就是迭代器

30.内存管理

  • 在内存管理中，内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。
  • 外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块
  • 固定分区存在内部碎片，可变式分区分配会存在外部碎片；
  • 页式虚拟存储系统存在内部碎片；段式虚拟存储系统，存在外部碎片

内存为程序分配空间有四种分配方式：

  • 连续分配方式

  • 基本分页存储管理方式

  • 基本分段存储管理方式

  • 段页式存储管理方式

  • 连续分配: 固定分区分配方式，动态分配方式，寻表。

  • 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)

  • 在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，系统又为每个进程建立了一张页面映像表，简称页表。两次访问内存，

  • 在分段系统中，段却是信息的逻辑单位，分段有段表。

  • 段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页

  • 地址结构由段号、段内页号和页内地址三部分所组成。

相关推荐