笔试面试

Posted on Edited on Views: Valine:

2018面试，笔试

数据结构

二叉树

等差数列和：https://zh.wikipedia.org/wiki/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97#%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97%E7%9A%84%E5%92%8C

二叉树的遍历

三种遍历方式

java语言实现：https://zhuanlan.zhihu.com/p/25632253

(1). 先序遍历

(2). 中序遍历

(3). 后序遍历

三种遍历方式，也就是遍历的顺序不一样。

先序遍历: “根左右”，遍历的顺序: 根节点->左节点->右节点。

中序遍历: “左根右”，遍历的顺序: 左节点->根节点->右节点。

后序遍历: “左右根”，遍历的顺序: 左节点->右节点->根节点。

结果：

先序：1,2,4,8,9,5,3,6,7
中序：8,4,9,2,5,1,6,3,7
后序：8,9,4,5,2,6,7,3,1

由后序跟中序来还原二叉树

过程

后序遍历实例:C B E H G I F D A
中序遍历实例:B C A E D G H F I
中序遍历开始位置,结束位置记做z1,z2,后序的记为h1,h2

  1. 新建一颗空树,左右孩子置空
  2. 拿到后序遍历的最后一个结点,其位置为z2,将该值存入树的数据域
  3. 在中序遍历的序列中以遍历的方式找到后序遍历的最后一个结点的位置,记为i
  4. 如果i!=z1,说明以该结点为根结点的树有左子树,以递归的方式,调用当前函数恢复左子树
  5. 如果i!=z2,说明以该结点为根结点的树有右子树,以递归的方式调用当前函数恢复右子树
  6. 返回树的根结点值

c语言实现：https://zhuanlan.zhihu.com/p/50185675

八种排序

https://zhuanlan.zhihu.com/p/26065419

八种排序的关系

直接插入排序

（1）基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void insertSort(int[] a) {
        int i, j, temp;

        for (i = 1; i < a.length; i++) {
            temp = a[i]; // 把当前待比较项付给中间量
            for (j = i; j > 0 && temp < a[j - 1]; j--) {
                // 如果待比较项小 
                a[j] = a[j - 1]; // 向后移
                // 直到找到没有比比较项大的就退出当前循环
            }
            a[j] = temp;// 49
        }
        for (i = 0; i < a.length; i++) {
            System.out.print(a[i] + "\t");
        }

    }

直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法。

简单选择排序

（1）基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；

然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

快速排序

（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

操作系统

https://zhuanlan.zhihu.com/p/23755202

（一）请分别简单说一说进程和线程以及它们的区别。

  • 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。
  • 线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。
  • 一个进程可以有多个线程，多个线程也可以并发执行

（二）线程同步的方式有哪些？

  • 互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。
  • 信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。
  • 事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

（五）什么是死锁？死锁产生的条件？

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

死锁产生的四个条件（有一个条件不成立，则不会产生死锁）

  • 互斥条件：一个资源一次只能被一个进程使用
  • 请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
  • 不剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
  • 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

（六）进程有哪几种状态？

  • 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源
  • 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
  • 阻塞状态： 进程等待某种条件，在条件满足之前无法执行

七）分页和分段有什么区别？

  • 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
  • 段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定
  • 段向用户提供二维地址空间；页向用户提供的是一维地址空间
  • 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

数据库

https://zhuanlan.zhihu.com/p/23713529?refer=passer

（二）索引是什么？有什么作用以及优缺点？

索引是对数据库表中一或多个列的值进行排序的结构，是帮助MySQL高效获取数据的数据结构

你也可以这样理解：索引就是加快检索表中数据的方法。数据库的索引类似于书籍的索引。在书籍中，索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息。在数据库中，索引也允许数据库程序迅速地找到表中的数据，而不必扫描整个数据库。

MySQL数据库几个基本的索引类型：普通索引、唯一索引、主键索引、全文索引

  • 索引加快数据库的检索速度
  • 索引降低了插入、删除、修改等维护任务的速度
  • 唯一索引可以确保每一行数据的唯一性
  • 通过使用索引，可以在查询的过程中使用优化隐藏器，提高系统的性能
  • 索引需要占物理和数据空间

如果你对索引还不太熟悉，建议阅读：漫谈数据库索引

（六）简单说一说drop、delete与truncate的区别

SQL中的drop、delete、truncate都表示删除，但是三者有一些差别

  • delete和truncate只删除表的数据不删除表的结构
  • 速度,一般来说: drop> truncate >delete
  • delete语句是dml,这个操作会放到rollback segement中,事务提交之后才生效;
    如果有相应的trigger,执行的时候将被触发. truncate,drop是ddl, 操作立即生效,原数据不放到rollback segment中,不能回滚. 操作不触发trigger.

（七）drop、delete与truncate分别在什么场景之下使用？

  • 不再需要一张表的时候，用drop
  • 想删除部分数据行时候，用delete，并且带上where子句
  • 保留表而删除所有数据的时候用truncate

（八） 超键、候选键、主键、外键分别是什么？

超键：在关系中能唯一标识元组的属性集称为关系模式的超键。一个属性可以为作为一个超键，多个属性组合在一起也可以作为一个超键。超键包含候选键和主键。

候选键：是最小超键，即没有冗余元素的超键。

主键：数据库表中对储存数据对象予以唯一和完整标识的数据列或属性的组合。一个数据列只能有一个主键，且主键的取值不能缺失，即不能为空值（Null）。

外键：在一个表中存在的另一个表的主键称此表的外键。

（十）说一说三个范式。

第一范式（1NF）：数据库表中的字段都是单一属性的，不可再分。这个单一属性由基本类型构成，包括整型、实数、字符型、逻辑型、日期型等。

第二范式（2NF）：数据库表中不存在非关键字段对任一候选关键字段的部分函数依赖（部分函数依赖指的是存在组合关键字中的某些字段决定非关键字段的情况），也即所有非关键字段都完全依赖于任意一组候选关键字。

第三范式（3NF）：在第二范式的基础上，数据表中如果不存在非关键字段对任一候选关键字段的传递函数依赖则符合第三范式。所谓传递函数依赖，指的是如 果存在”A → B → C”的决定关系，则C传递函数依赖于A。因此，满足第三范式的数据库表应该不存在如下依赖关系： 关键字段 → 非关键字段 x → 非关键字段y

如果你对三个还不太了解，建议阅读：解释一下关系数据库的第一第二第三范式？

UML

依赖，关联，聚合，组合，继承，实现

耦合度依次增加

https://zhuanlan.zhihu.com/p/24576502

1. 依赖 (Dependency) 虚线+箭头

A依赖了B，A使用了B

体现：

类A使用到了类B：如A中某个函数的参数！

通过函数里局部变量

通过静态变量发生依赖

2. 关联 (Association) 实线+箭头

关联关系的定义为：对于两个相对独立的对象，当一个对象的实例与另一个对象的一些特定实例存在固定的对应关系时，这两个对象之间为关联关系。

它体现的两个类中一种强依赖关系，比如我和我的朋友，这种关系比依赖更强，不存在依赖关系中的偶然性，关系也不是临时的，一般是长期性的。

关联关系分为单向关联和双向关联：

  1. 在 Java 中，单向关联表现为：类 A 当中使用了 类 B，其中类 B 是作为类 A 的成员变量。
  2. 双向关联表现为: 类 A 当中使用类 B 作为成员变量，同时类 B 中也使用了类 A 作为成员变量。

3.聚合 (Aggregation) 空心菱形，实线，箭头

has -a 的关系

聚合关系是关联关系的一种，耦合度强于关联，他们的代码表现是相同的，仅仅是在语义上有所区别：关联关系的对象间是相互独立的，而聚合关系的对象之间存在着包容关系，他们之间是“整体-个体”的相互关系。

聚合关系中作为成员变量的类一般使用 set 方法赋值。

司机与车，司机有辆车，司机聚合了车，司机知道车，车不知到司机，setCar

司机 空心菱形，实线，箭头 车

4. 组合 (Composition)实心菱形，实线，箭头

contain a

相比于聚合，组合是一种耦合度更强的关联关系。存在组合关系的类表示“整体-部分”的关联关系，“整体”负责“部分”的生命周期，他们之间是共生共死的；并且“部分”单独存在时没有任何意义。

对比与聚合关系，我们可以将前面的例子变为下面的场景：

  1. 车是一辆私家车，是司机财产的一部分，强调的是人财产的部分性，则相同的代码即可表示聚合关系。
  2. 车是司机必须有的财产，要想成为一个司机必须要现有财产，车要是没了，司机也不想活了。而且司机要是不干司机了，这车也就没了。

所以，关联、聚合、组合只能配合语义，结合上下文才能够判断出来，而只给出一段代码让我们判断是关联，聚合，还是组合关系，则是无法判断的。

司机与车，司机有辆车，司机组合了车，司机知道车，车不知到司机

司机 实心菱形，实线，箭头 车

人：脑子，肚子，心胀 人与他们的关系是组合

聚合和组合的区别

这两个比较难理解，重点说一下。聚合和组合的区别在于：聚合关系是“has-a”关系，组合关系是“contains-a”关系；聚合关系表示整体与部分的关系比较弱，而组合比较强；聚合关系中代表部分事物的对象与代表聚合事物的对象的生存期无关，一旦删除了聚合对象不一定就删除了代表部分事物的对象。组合中一旦删除了组合对象，同时也就删除了代表部分事物的对象。

5. 继承 (Generalization) 实线，三角形

继承表示类与类 (或者接口与接口) 之间的父子关系。在 Java 中，用关键字 extends 表示继承关系。

6. 实现 (Implementation)虚线 ，三角形

表示一个类实现一个或多个接口的方法。接口定义好操作的集合，由实现类去完成接口的具体操作, 在 Java 中使用 implements 表示。在 Java 中，如果实现了某个接口，那么就必须实现接口中所有的方法。

比如一个人可以吃饭和学习，那么就可以定义一个人的接口。让具体的人去实现它。

实例

-------------本文结束感谢您的阅读-------------