急求数据结构二叉树的遍历-平衡二叉树课程设计

树结构是一种非线性存储结构,n 个结点组成具有层次关系的有限集合,其中 n >= 0 当 n = 0 时称为空树

存储的是具体一对多的关系的数据元素的集合

  • 有且只有一个根结点,根结点没有父节点

  • 链表可以看成树的从根节点触发到叶子节点一个路径

  • 数据元素(结点)按分支关系组织起来的结构

  • 每个结点最多有两个子树的有序树

叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点

对于一颗二叉树,如果深度 d (d>1) 除了 d 层外所有节点构成满二叉树,且 d 层所有节点从左向右连续紧密排列

  • 叶子结点只可能在最大的两层出现

  • 对任意结点,如果其右子树的最大层次为 L,则其左子树的最大层次为 L 或者 L+1(子树必须向左对齐)

  • 叶子节点(度为 0 的结点)

BFS(广度优先搜索)
DFS(深度优先搜索)

分别可以用递归法和迭代法来实现前、中或后序实现

一颗空树或者左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一个平衡二叉树,同时,平衡二叉树必定是二叉搜索树

1)进程和线程的区别(不能太书面化)(需要从内存角度,或者其他角度描述)

需要用自己理解的方式去回答这个问题,如果你回答了xxx是基本单位,这样子是不行的。技术面试会追问你,需要你用自己的话去理解进程和线程。线程和进程是否是独立的?线程和进程的之间内存空间是否是共享的?进程和进程之间是否是共享的?

2)线程之间是如何调度的

比如说有两个线程:线程A和线程B,线程B要先于线程A运行,或者是线程B运行了多次之后在启动线程A,如何进行调度?

3)非实时操作系统和实时操作系统的区别和选择,以及应用场景。

1)static的作用,函数中变量使用static的作用,它的生命周期会如何。
3)c语言中有哪些宏定义?
5)代码编译的四个过程,预处理的阶段做了哪些事情(深入问条件编译里面做了哪些事情)四个过程都

2)问了队列、栈、链表的概念和特征,队列和栈在项目中的应用场景。什么情况下用栈,什么情况下用队列和链表。

1、简历中有的项目,一定要会,不会的东西不写,写上去的东西保证自己每个细节都懂,也就是确实是自己做的项目,不是捏造的项目。

2、大厂面试注重基础,因为大公司会培养你,只要你基础扎实就行,所以基础很重要,整个面试一个多小时,大部分时间在linux系统、编程能力、数据结构、计算机网络基本概念上。

3、大厂面试喜欢问你对于某个常见的东西自己的理解,因为书上的名词大家都会说,但是你自己理解的

肯定是不一样的。比如富士康的一个面试官问过:你认为OSI七层网络模型和生活中给的什么很像?

岗位:嵌入式软件工程师。面试时间:20分钟

1、简历中写了做过海思音视频项目,所以问了海思项目是怎么学的?(考察自学能力)。

2、问:学海思项目,是因为兴趣,还是为了毕设?

回答:是因为兴趣,因为自己毕设是51单片机。

问:如果一个Linux和51单片机进行通讯,让我怎么设计通讯协议,然后问我怎么进行检验。

回答:可以设计串口,加奇偶校验,并且检查数据包的总字节数。

问:如果字节总个数是对的,但是有些位错了,那应该怎么去检查?
(不该说自己的毕设是51单片机的,因为自己本身不了解51单片机,所以这一块答得一般)后来面试官
知道我对51单片机没怎么学过,是春招后才准备现学现用的,就没有继续问下去了。

回答:学过,但是后面没怎么用,几乎忘光了,比较熟悉和常用的是链表。

4、如何判断一个链表有环?

5、线程和进程的区别?

6、线程和进程间的通讯方式有哪些?

7、访问临界资源时应该怎么办?

8、线程和进程的API,知道哪些?

回答:我把API名字和API的参数是什么都说了,面试官就没继续往下问了

10、对于加班的看法(据说CVTE加班很猛,另外两个是多益和三七)(广州)

11、有没有转管理层的意向?

12、有什么问题想问的?

回答:如果有幸入职贵公司,请问是否会有一些培训制度?

总结:除了一开始的那个怎么设计单片机和Linux通信协议没答好,其他的问题答得还可以,HR挺有耐心挺温柔的,也会在面试时一步步引导。从面试过程可以看出,很多公司,面试官一般都是根据你的简历和你的回答,来决定下一个问题。所以千万不要自己给自己挖坑,简历写的东西,必须要会,自己回答的东西,自己必须要会。所以面试官比较随和的情况下,可以通过自己的回答,把面试官引导到全是自己熟悉的领域。

岗位:嵌入式软件工程师。面试时间:30分钟。
薪资:试用期基本工资7200,转正按情况加(0-1000),算月工资8000,加班有加班费,算上加班费
所应聘部门是基于高通平台,做通信模块的。

2、如何理解交叉编译?
3、OSI七层网络和TCPIP网络模型区别?以及每一层名称。
4、你觉得网络分层协议和生活中什么比较像?(快递业务)
5、什么是上下文切换(我从中断上下文方面讲。然后他问为什么响应中断要保护现场,中断处理流程是
6、你如何理解异步(我从文件IO中的异步非阻塞回答)
7、你是XXXX专业,是不是和嵌入式不太匹配,都是自学的吗?
8、数据结构学的怎么样?
9、计算机操作系统学的怎么样?
10、你熟悉哪些数据结构?
11、如何理解数据结构和算法的关系?
12、你是XXXX专业,是如何学习嵌入式的?(我都是做项目,项目中学习)
13、C语言和其他编程语言有什么关系,处于一个什么地位?(更底层)
14、你如何理解编程语言和日常说话语言的关系?
15、你如何理解指针?(也是一种变量而已,只是存储的内容是地址,所以可以叫指针变量)
16、什么是系统调用?
18、普通调用和系统调用的区别?
19、系统调用用什么函数(ioctl等)?
20、数据结构学的怎么样,学过红黑树吗?讲一讲。
回答:红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每
个节点都遵循下面的规则:
1)每个节点都有红色或黑色
2)树的根始终是黑色的 (黑土地孕育黑树根)
3)没有两个相邻的红色节点(红色节点不能有红色父节点或红色子节点,并没有说不能出现连续的黑色
4)从节点(包括根)到其任何后代NULL节点(叶子结点下方挂的两个空节点,并且认为他们是黑色的)
的每条路径都具有相同数量的黑色节点)
补充:二叉查找树,Binary Search Tree 「BST」,要想了解二叉查找树,我们首先看下二叉查找树有
1)某节点的左子树节点值仅包含小于该节点值

2)某节点的右子树节点值仅包含大于该节点值

3)左右子树每个也必须是二叉查找树

21、讲一讲冯诺依曼和哈佛体系的区别
总结:他特别喜欢问你是如何理解某个东西的,这样的问法比单问你知识点牛多了,就是看你到底有没有对底层原理有理解,然后用通俗的话表达出来。

岗位:嵌入式软件工程师(相机驱动岗)。面试时间:40分钟。
以下问题面试者全部答出,已offer,薪资请去小程序offershow上查。

1、请进行一个简单的自我介绍(2分钟)

2、C语言全局变量可否定义在头文件中?

回答:不能,并且这不是一个好的习惯。

3、全局变量和局部变量是否可以重名?

回答:可以重名。只是作用域不同,局部变量在局部生效。

回答:extern C 的主要作用就是为了能够正确实现C++代码调用其他C语言代码,即在C++代码中嵌入式C语言代码。

5、从代码编译到可执行文件的流程?
回答:一个源程序到一个可执行程序的过程:预编译、编译、汇编、链接。

6、进程和线程的区别?
回答:进程是资源(CPU、内存等)分配的基本单位,线程是CPU调度和分配的基本单位(程序执行的最小单位)。同一时间,如果CPU是单核,只有一个进程在执行,所谓的并发执行,也是顺序执行,只不过由于切换速度太快,你以为这些进程在同步执行而已。多核CPU可以同一时间点有多个进程在执行。

7、手撕代码:写一个双向链表的插入。

8、问简历上面的项目。

9、IIC协议说一下(因为我简历里面写了IIC)

回答:I2C协议有两条信号线,SDA和SCL,分别是数据线和时钟线,同一总线可以挂载多个IIC设备,靠设备地址区分。

10、C++有了解吗,用它做过什么项目没有。

回答:我主要用C语言,C++用的比较少。

12、内存分为哪几个部分

回答:内存分为四区:堆区、栈区、全局区、代码区。

13、二分法查找的原理?

回答:类似于快速排序算法。二分法使用的前提是数组已经是有序序列,原理是折半查找,每次把表分成两半,因为已经排序的,所以只需要和中间数比较就能确定是在哪一半,然后不断分成两半,直到匹配,或者没有数字,表示查找失败。

14、二叉树了解过吗?前序,中序,后序遍历流程说一下。

回答:其实二叉树是很重要的数据结构,更深一点的知识点有平衡二叉树,红黑树,B树,B+树,B-树
等,可以自行了解。这里只问了前中后序遍历,2021秋招百度笔试也考了这道题。

15、内核裁剪说一下。
回答:个人理解,内核裁剪的原因主要是Linux内核本身很庞大,但客户有时候不需要这么多功能,想裁
剪,定制内核,定制功能。

简单的内核的配置有三种方式,在命令行输入:

补充个例子:假如客户需要在手机固件升级的时候,有个指示灯闪烁,该怎么办?这个时候你单纯写应用代码是没用的,因为手机固件升级的时候,系统都没有跑起来,这时候代码只能写在Linux内核的bootloader里,因为bootloader起来了。做嵌入式开发还是要熟悉Linux内核的,没学习的赶紧学习,用到是早晚的事。

回答:这几个函数,做嵌入式岗位必须要会,按照学校老师的话来讲:这道题是这次考试的必考题,15分就放在那里,爱背不背。这道题,浙江大华也考了,mtk也考了,做嵌入式对内存太敏感,必考。strcpy函数会导致内存溢出。strcpy拷贝函数不安全,他不做任何的检查措施,也不判断拷贝大小,不判断目的地址内存是否够用。

strncpy拷贝函数,虽然计算了复制的大小,但是也不安全,没有检查目标的边界。

strcat()函数主要用来将两个char类型连接。例如:

输出 d 为 GoldenView (中间无空格)memcpy拷贝函数,它与strcpy的区别就是memcpy可以拷贝任意类型的数据,strcpy只能拷贝字符串类型。

memcpy 函数用于把资源内存(src所指向的内存区域)拷贝到目标内存(dest所指向的内存区域);
有一个size变量控制拷贝的字节数;

17、栈和队列的区别?

回答:这两种数据结构都很重要,栈是先入后出,队列是先入先出。

18、memcpy函数以什么结尾?

回答:与strcpy相比,memcpy遇到’\0’不结束,而且一定会复制完n个字节,函数原型在上面。

19、你最有成就的项目或者经历是什么?

20、你有什么想问的吗?

岗位:嵌入式软件工程师。
浙江大华嵌入式软件笔试一共37道题,35道选择填空,2道编程,时间60分钟,C语言一半,C++一半。
一面是晚上九点半打电话过来,过程15分钟,可能他们还在加班。二面是现场面,过程20分钟。现场面
流程很快,二面完毕HR面,当天面试完毕。一周内发offer。

回答:我主要介绍过去两年我做的项目和个人的知识框架

2、问了一下我主要用的编程语言,我说C

3、因为他们也做相机类产品,所以我把我实习的项目讲了一遍,包括标定sensor,标定shading、AWB这些相机相关知识。

4、如何防止编译器优化?

那就顺便解释一下关键词static、const、extern的作用(经典)。

5、在C++代码中嵌入C代码,需要做什么?

6、进程与线程,分配资源的最小单位是什么?

7、网络编程中长链接和短链接?

2、比如HTTP是无状态的的短链接,浏览器和服务器每进行一次HTTP操作,就建立一次连接,但任务结 3、因为连接后接收了数据就断开了,所以每次数据接受处理不会有联系。 这也是HTTP协议无状态的原 2、长连接指建立SOCKET连接后不管是否使用都保持连接,但安全性较差。

什么时候用长连接,短连接?

长连接多用于操作频繁,点对点的通讯,而且连接数不能太多情况。每个TCP连接都需要三步握手,这需要时间,如果每个操作都是先连接,再操作的话那么处理速度会降低很多,所以每个操作完后都不断开,次处理时直接发送数据包就OK了,不用建立TCP连接。例如:数据库的连接用长连接, 如果用短连接频繁的通信会造成socket错误,而且频繁的socket 创建也是对资源的浪费。而像WEB网站的http服务一般都用短链接,因为长连接对于服务端来说会耗费一定的资源,而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源,如果用长连接,而且同时有成千上万的用户,如果每个用户都占用一个连接的话,那可想而知吧。所以并发量大,但每个用户无需频繁操作情况下需用短连好。

8、多线程编程中,写线程安全的函数要注意哪些点?

回答:注意的点比较多,这是属于多线程编程的知识点。首先需要注意写的函数是可重入的:CPU运行时收到信号,于是暂停目前正在执行的函数,转到信号处理函数,而这个信号处理函数的执行过程中,又恰恰也会进入到刚刚执行的函数,这样便发生了所谓的重入。此时如果能够正确的运行,而且处理完成后,之前暂停的也能够正确运行,则说明它是可重入的, 反复调用都得到正确的结果。其余的点子请大家自行百度。

回答:assert 不仅仅是个报错函数,事实上,它是个宏,并且作用并非"报错"。assert 宏的原型定义在assert.h 中,其作用是如果它的条件返回错误,则终止程序执行。

assert 的作用是现计算表达式 expression ,如果其值为假(即为0),那么它先向 stderr 打印一条出错信息,然后通过调用 abort 来终止程序运行。

1)在函数开始处检验传入参数的合法性

2)每个assert只检验一个条件,因为同时检验多个条件时,如果断言失败,无法直观的判断是哪个条件失败

3)不能使用改变环境的语句,因为assert只在debug阶段生效,如果这么做,会使用程序在真正运行时遇到问题

4)assert和后面的语句应空一行,以形成逻辑和视觉上的一致感

10、内存四区(堆、栈、全局区、代码区)

11、了解几种排序算法,时间复杂度是多少?
十种常见排序算法可以分为两大类:
非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序

二面是现场面试,大概20分钟左右。

1、对着简历面试,问你简历写的东西。

2、对着你笔试的时候的题目,看你做的情况,随便选一个你做对的或者你做错的让你解释。(所以笔试完一定要搞懂)

3、问进程线程,经典问题。

4、问strcpy拷贝函数安全吗,如果不安全,用什么去替代。

不安全,strcpy函数会导致内存溢出,因为他不做任何的检查措施,也不判断拷贝大小,不判断目的地址内存是否够用。

strncpy拷贝函数,虽然计算了复制的大小,但是也不安全,没有检查目标的边界。

strncpy_s是安全的memcpy拷贝函数,它与strcpy的区别就是memcpy可以拷贝任意类型的数据,strcpy只能拷贝字符串类型。
memcpy 函数用于把资源内存(src所指向的内存区域)拷贝到目标内存(dest所指向的内存区域);有一个size变量控制拷贝的字节数;

5、写一个双向链表的插入删除

6、解释一下动态内存和静态内存

a) 静态内存分配在编译时完成,不占用CPU资源; 动态内存分配在运行时,分配与释放都占用CPU资源。

b) 静态内存在栈(stack)上分配; 动态内存在堆(heap)上分配。

c) 动态内存分配需要指针和引用类型支持,静态不需要。

d) 静态内存分配是按计划分配,由编译器负责; 动态内存分配是按需分配,由程序员负责。

我要回帖

更多关于 数据结构二叉树的遍历 的文章

 

随机推荐