【14】C++岗位求职面试八股文系列文章(语言基础)
第一篇:语言基础
第二篇:设计模式
第三篇:数据库
第四篇:计算机网络
第五篇:操作系统
第六篇:LInux
第七篇:数据结构
第八篇:智力题
[261]函数模板、类模板
使用函数模板有两种方式:自动类型推导、显示指定类型使用类模板有一种方式:显示指定类型
类模板与函数模板区别主要有两点:
- 类模板没有自动类型推导的使用方式,只有显示推导类型
- 类模板在模板参数列表中可以有默认参数
[262]简述GDB常见的调试命令,什么是条件断点,多进程下如何调试
GDB调试:gdb调试的是可执行文件,在gcc编译时加入 -g ,告诉gcc在编译时加入调试信息,这样gdb才能调试这个被编译的文件 gcc -g tesst.c -o test
Gcc操作:预处理-E 编译-S 汇编-c 链接-l 生成目标代码-o预处理:宏替换、头文件展开、注释去掉Tar.gz结尾的压缩包:tar -zxvf 解压 tar -zxcf压缩
[263]Gdb多进程调试
链接RUN
[264]Gdb多线程调试
[265]coredump,很常见,你遇到过吗?怎么调试这个错误?
coredump是程序由于异常或者bug在运行时异常退出或者终止,在一定的条件下生成的一个叫做core的文件,这个core文件会记录程序在运行时的内存,寄存器状态,内存指针和函数堆栈信息等等。对这个文件进行分析可以定位到程序异常的时候对应的堆栈调用信息。• 使用gdb命令对core文件进行调试
程序崩了会是什么情况,代码量特别大怎么定位和解决分段错误: 访问受保护的内存位置、访问系统中不存在的内存位置、在只读存储器位置上进行写操作、堆栈溢出缓冲区溢出:将数据写入缓冲区时会溢出缓冲区的边界并覆盖相邻的内存位置。内存泄漏:
当程序运行过程中出现Segmentation fault (core dumped)错误时,程序停止运行,并产生core文件。core文件是程序运行状态的内存映象。使用gdb调试core文件,可以帮助我们快速定位程序出现段错误的位置。当然,可执行程序编译时应加上-g编译选项,生成调试信息。想要定位这个问题,可以开启-g调试,然后程序core drump的时候会生成core的文件,可以用gdb去调试这个core定位是这些问题哪一个
sudo sysctl -w kernel.core_pattern=/home/hutu/test/core-%e-%s-%u-%g-%p-%t
Gdb调试:设置:ulimit -c unlimited //core文件生成开关
设置core文件路径:sudo sysctl -w kernel.core_pattern=/home/hutu/test/core-%e-%s-%u-%g-%p-%t
编译:gcc -g test.c
运行:./可执行文件
调试:gdb a.out core文件
gdb运行:run
Bt :breaktrace
[266]静态库优点:.a
速度快,移植方便,消耗资源。更新部署麻烦
[267]动态库优点:.so
[268]易错点
条件变量和信号量不可以实现信号同步,是用来实现生产者消费者模型;只有互斥锁可以实现信号同步
Tcp头部固定部分20字节,可选项40字节,最大60字节
[269]Select poll epoll的原理和各自有缺点
Select:
Poll优点:解决了select的1024限制,可以无数个;解决了fd复用,因为结构体除了有events,还有revents;
[270]红黑数 平衡二叉B树
链接可以在O(log n)时间内做查找,插入和删除,
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:
性质1:每个节点要么是黑色,要么是红色。性质2:根节点是黑色。,叶子结点是黑色(NULL)性质4:每个红色结点的两个子结点一定都是黑色。黑节点子节点可为黑)性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
二叉搜索树 < 红黑数 <二茬平衡树 (二叉平衡树一定有排序树的特点)红黑数具有搜索树特点
由于红黑树也是二叉查找树,它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点,并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值
记住大小顶堆底层并不是红黑数,性质就冲突了,底层是优先队列(优先队列底层是数组实现)
红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色。
旋转操作不会影响旋转结点的父结点,父结点以上的结构还是保持不变的。左旋只影响旋转结点和其右子树的结构,把右子树的结点往左子树挪了。右旋只影响旋转结点和其左子树的结构,把左子树的结点往右子树挪了。
红黑数查找、插入、删除的时间复杂度都是log(n)。插入结点最多只需要2次旋转,删除一个结点最多只需要3次旋转操作。任何不平衡都会在3次旋转之内解决。插入节点颜色为红色
链接情况1:将红色直接变为黑色情况2:将Z的父节点、祖父节点、叔节点进行变色情况3:旋转z的祖父节点,将原来父节点和祖父节点变色情况4:红黑数删除节点:
- 删除红色节点不影响黑高,所以只讨论删除黑色节点。 2被删除后替代被删除节点位置的节点是x,w是它的兄弟节点 3.【w是黑色,子节点都是黑色】由于删除操作让x路径上黑高-1,所以将w变为红色,以保持A以下的局部黑高平衡。但整体仍然可能黑高不平衡,所以将A节点作为对象继续迭代到修复算法中。直到迭代对象变为根节点或者红色。 4.【w是黑色,右子节点为红色】把w变为与父节点A同色,把父节点A和红色的右子节点B变为黑色,最后左旋A。 5.【w是黑色,左子节点为红色】交换w和他左子节点c的颜色,右旋w。这时候x的兄弟节点w‘变成了c,c的右子节点为原来的w,是红色,情况变为2。 6.【w是红色】(注意这里w的子节点必然都是黑色)将w与A的颜色对掉,左旋A,此时x的兄弟节点变为w原来的黑色左子节点。同上。
[271]红黑树和平衡二叉树区别如下
1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。2、平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。
[272]二叉平衡树插入节点:复杂度logn 具有二叉搜索树的特点
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子,平衡树只可能是 -1,0 或 1链接
调整不平衡树的基本方法就是旋转。 下面我们归纳一下平衡旋转的4情况:1.RR型,左旋
2LL型,右旋
3LR型 左右旋
4RL型 右左旋
[273]大小顶堆
利用完全二叉树的结构来维护的一维数组,按照堆的特点可以把堆分为大顶堆和小顶堆大顶堆:每个结点的值都大于或等于其左右孩子结点的值小顶堆:每个结点的值都小于或等于其左右孩子结点的值
链接划分有序区和无序区的排序:插入。希尔。选择,堆,冒泡,内排序:排序操作在内存中完成外排序:数据太大放在磁盘,排序通过磁盘和内存数据传输
[274]介绍一下几种典型的锁
读写锁• 多个读者可以同时进行读• 写者必须互斥(只允许一个写者写,也不能读者写者同时进行)• 写者优先于读者(一旦有写者,则后续读者必须等待,唤醒时优先考虑写者)
互斥锁一次只能一个线程拥有互斥锁,其他线程只有等待互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒,而操作系统负责线程调度,为了实现锁的状态发生改变时唤醒阻塞的线程或者进程,需要把锁交给操作系统管理,所以互斥锁在加锁操作时涉及上下文的切换。互斥锁实际的效率还是可以让人接受的,加锁的时间大概100ns左右,而实际上互斥锁的一种可能的实现是先自旋一段时间,当自旋的时间超过阀值之后再将线程投入睡眠中,因此在并发运算中使用互斥锁(每次占用锁的时间很短)的效果可能不亚于使用自旋锁
条件变量互斥锁一个明显的缺点是他只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足,他常和互斥锁一起使用,以免出现竞态条件。当条件不满足时,线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量,他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制,条件变量则是同步机制。
自旋锁如果进线程无法取得锁,进线程不会立刻放弃CPU时间片,而是一直循环尝试获取锁,直到获取为止。如果别的线程长时期占有锁那么自旋就是在浪费CPU做无用功,但是自旋锁一般应用于加锁时间很短的场景,这个时候效率比较高。
[275]delete和delete[]区别?
• delete只会调用一次析构函数。• delete[]会调用数组中每个元素的析构函数
[276]为什么不能把所有的函数写成内联函数?
内联函数以代码复杂为代价,它以省去函数调用的开销来提高执行效率。所以一方面如果内联函数体内代码执行时间相比函数调用开销较大,则没有太大的意义;另一方面每一处内联函数的调用都要复制代码,消耗更多的内存空间,因此以下情况不宜使用内联函数:• 函数体内的代码比较长,将导致内存消耗代价• 函数体内有循环,函数执行时间要比函数调用开销
[277]为什么C++没有垃圾回收机制?这点跟Java不太一样
• 实现一个垃圾回收器会带来额外的空间和时间开销。你需要开辟一定的空间保存指针的引用计数和对他们进行标记mark。然后需要单独开辟一个线程在空闲的时候进行free操作。• 垃圾回收会使得C++不适合进行很多底层的操作
[278]为什么用红黑树实现map、set?
map, set底层都提供了排序功能,红黑树形式存储的键值是有序的。同时红黑树可以在O(log n)时间内做插入,查找和删除。
[279].为什么使用红黑树而不是二叉搜索树?
二叉搜索树并不一定是一颗平衡树,红黑数是自平衡的二叉搜索树。如果插入的值是有序的,那么构造出来的二叉树将是一个链表,它的时间复杂度将达到O(n)。而使用红黑树,可以通过对每个节点标色的方式,每次更新数据后进行平衡,保证查找效率。
[280]调⽤empty⽽不是检查size()是否为0
empty()对所有的标准容器都是常数时间操作,⽽size()对于list耗费的是线性时间。
[续]C++岗位求职面试八股文第十五篇
更多关于算法题解、软件开发面经、机器学习算法面经、各企业面试问题记录,关注Fintech砖,持续更新中。https://www.nowcoder.com/users/873777317
企业面试记录专栏https://www.nowcoder.com/creation/manager/columnDetail/0YBWnm
机器学习面经专栏https://www.nowcoder.com/creation/manager/columnDetail/j8nNy0
软件开发面经专栏https://www.nowcoder.com/creation/manager/columnDetail/0aXKaM
更多校园招聘常见面试问题(开发、算法、编程题目)参见CSDN博客:http://t.csdn.cn/V4qbH
欢迎关注、收藏、点赞后进行问题咨询及秋招建议!
#晒一晒我的offer##牛客在线求职答疑中心##牛客解忧铺##软件开发薪资爆料##如何判断面试是否凉了#包含C++、操作系统、数据库、计算机组成、计算机网络、设计模式、操作系统、牛客网服务器项目、综合智力题等