笔试题集

(Updated: )

数据结构与算法

a,b,c,d,e 对应出现的频率为4，6，11，13，15；以下符合哈夫曼编码的选项是？（B）

A.a=000、b=01、c=001、d=10、e=11
B.a=000、b=001、c=01、d=10、e=11
C.a=010、b=001、c=01、d=11、e=10
D.a=000、b=10、c=001、d=11、e=01

二叉树的三种遍历方式

1
2
3
4
5
    G
   / \
  E   C
 / \ / \
D  A H  S
  1. 先序遍历：GEDACHS。
  2. 中序遍历：DEAGHCS。
  3. 后序遍历：DAEHSCG。

2019! 的末尾有多少个零？（403+80+16+3=502）

与十进制数28.5625相等的四进制数是(130.21)。（整数部分除4取余，小数部分乘4取整数部分）

贪心算法的特点

  • 求解速度快。
  • 时间复杂度低。
  • 需要证明求解问题的解是最优解。

Java基础

位运算

  1. 与运算（&）：两个位都为1时，结果才为1。
  2. 或运算（|）：两个位都为0时，结果才为0。
  3. 异或运算（^）：两个位相同为0，相异为1。

Java只支持单继承，实现多重继承三种方式：

  1. 直接实现多个接口。
  2. 扩展一个类然后实现一个或多个接口。
  3. 通过内部类去继承其他类。

并发性是指若干事件在同一时间间隔发生。

X=+0111001,Y=+1001101,求[X-Y]补=

1
2
3
4
5
6
[X] = 00111001 [Y] = 01001101
[X-Y]补 = [X]补 + [-Y]补
[-Y]补 = Y各位取反+1 = 10110011
[X]补    00111001
[-Y]补 + 10110011
得       11101100

Java事务三种类型：JDBC事务、JTA（Java Transaction API）事务、容器事务。
JDBC 事务是用 Connection 对象控制的。JDBC Connection 接口（ java.sql.Connection ）提供了两种事务模式：自动提交和手工提交。 java.sql.Connection 提供了以下控制事务的方法：容器事务主要是J2EE应用服务器提供的，容器事务大多是基于JTA完成，这是一个基于JNDI的，相当复杂的API实现。

Java常用处理流

缓冲流、转换流、数据流。

某递归算法的递归关系式为T( n ) = 2*T(n/2) + O( n )，那么它所对应的时间复杂度为

n * log n

散列函数构造方法

  1. 直接定址法：H(key) = a*key + b
  2. 除留余数法：H(key) = key % p(p为不大于散列表表长，但最接近或等于表长的质数p)
  3. 数字分析法：选取r进制数数码分布较为均匀的若干位作为散列地址
  4. 平方取中法：取关键字的平方值的中间几位作为散列地址
  5. 折叠法：将关键字分割成位数相同的几部分，然后取这几部份的叠加和作为散列地址

散列冲突及解决

  1. 开放寻址法
    • 线性探测法。
    • 二次探测：线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。
    • 双重散列：使用一组散列函数，直到找到空闲位置为止。
    • 伪随机数法。
  2. 冲突链表法

计算机网络

常用协议介绍

  • ICMP协议是因特网控制报文协议，用于在IP主机、路由器之间传递控制消息。
  • HTTP协议是超文本传输协议，是一个属于应用层的面向对象的协议。
  • DHCP协议是动态主机配置协议，用于为主机分配IP地址。
  • NAT协议网络地址转换，是一种将私有（保留）地址转化为合法IP地址的转换技术。
  • ARP协议是地址解析协议，能够从IP地址得到MAC地址。
  • DNS协议是域名系统，提供的服务是域名到IP地址的解析。

UDP协议报头的内容中没有序号。

网络层：路由器，进行分组转发。
数据链路层：网卡、网桥，交换机。
物理层：网线，集线器，中继器，调制解调器。

邮件服务需要两种不同的协议。一种是用户代理向邮件服务器发送邮件或在邮件服务器之间发送邮件，如STMP协议；另外一种是用于用户代理从邮件服务器读取邮件，如邮局协议POP3。

SMTP：发件人用户代理 —-发送邮件—> 发送方邮件服务器；发送方邮件服务器 —-发送邮件—> 接收方邮件服务器。
POP3/IMAP：接受方邮件服务器—-读取邮件—> 收件人用户代理。

冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中， CPU 区分它们的依据是（指令周期的不同阶段）

变量a是一个64位有符号的整数，初始值用16进制表示为：0x7FFFFFFFFFFFFFFF;变量b是一个64位有符号的整数，初始值用16进制表示为：0x8000000000000000。则a+b的结果用10进制表示为多少？（-1）

局域网不跨网段，不需要IP地址，只需要MAC地址就可以了。

Cookie的描述

  • 子域名可以访问根域名的Cookie，根域名不可以访问子域名的Cookie
  • 浏览器禁用Cookie时可以用URL重写与服务端保持状态
  • Cookie有大小限制
  • Cookie中保存的是字符串

五类ip地址

  • A类网络：1.0.0.0-127.255.255.255，最大主机数为16777214台。（2^24-2）。
  • B类网络：128.0.0.0-191.255.255.255，最大主机数为65534台。（2^16-2）。
  • C类网络：192.0.0.0-223.255.255.255，最大主机数为254台。（2^8-2）。
  • D类网络：224.0.0.0-239.255.255.255，不分网络地址和主机地址。
  • E类网络：240.0.0.0-255.255.255.255，不分网络地址和主机地址。

OSI参考模型

  • 物理层：RJ45、CLOCK、IEEE802.3（中继器，集线器，网关）
  • 数据链路：PPP、FR、HDLC、VLAN、MAC（网桥，交换机）
  • 网络层：IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP、（路由器）
  • 传输层：TCP、UDP、SPX
  • 会话层：NFS、SQL、NETBIOS、RPC
  • 表示层：JPEG、MPEG、ASII
  • 应用层：FTP、DNS、Telnet、SMTP、HTTP、WWW、NFS

internet的基本服务功能

  • ftp：文件传输协议
  • telnet：远程登录
  • mail：发邮箱指令
  • open：打开文件

默认端口号

  • FTP：21用于连接，20用于传输数据
  • SSH：22
  • Telnet：23
  • DNS：53，区域传送使用TCP，域名解析使用UDP
  • Http：80
  • Https：443
  • MySQL：3306
  • Redis：6379

基于TCP的有：Telnet，HTTP，HTTPS，SMTP，POP3，FTP。
基于UDP的有：NFS，TFTP，SNMP，DHCP，NTP，BOOTP。

对称加密算法主要有：DES、3DES、AES等，非对称加密算法主要有RSA、DSA等，散列算法主要有SHA-1、MD5等。

网络协议三要素：语法，语义，同步。

光盘＜U盘＜硬盘＜内存＜高速缓存＜CPU。

IP数据报分片发生在路由器，重组发生在目的主机。

操作系统

某台计算机连接了8个相同的设备，有N个进程在竞争使用，每个进程最多会同时占用3个设备，请问当N大于等于多少时，系统可能发生死锁？（4）

1
2
死锁问题：设备m=3，进程p，资源r=8；
solution：p*(m-1)+1>r；p=4；

计算机从用户态切换至内核态：系统调用、异常、外围设备中断。

虚拟内存的容量只受(计算机地址位数)的限制。

若处理器有32位地址，则它的虚拟地址空间为(4G)。

进程中的几种通信方式

  • 管道：管道是一种半双工的通信方式，数据只能单向流动。而且只能在具有血缘关系（父子进程之间）的的进程间使用。
  • 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。
  • 消息队列：消息队列是由消息组成的链表，存放在内核中，并由消息队列标识符标识。
  • 信号：信号是有一种比较复杂的通信方式，用于通知接收进程某一事件已经发生。
  • 共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。
  • 套接字：即Socket，是一种通信机制，凭借这种机制，客户/服务器系统的开发工作既可以在本地单机上进行，也可以跨网络进行。

设计模式

单例模式

  • 优点：减少内存开支、减少系统调用、避免资源的多重占用。
  • 比较：懒汉式存在线程安全问题，属于延迟加载，在需要时才创建对象，不安全；饿汉式是安全的。

单例模式特点：

  • 单例类只能有一个实例。
  • 单例类必须自己创建自己的唯一实例。
  • 单例类必须给所有其他对象提供这一实例。

桥接模式特点：将抽象部分与它实现部分分离，使他们都可以独立变化，抽象类和子类实现自己的对象。

组合模式特点：将对象组合成树形结构以表示‘部分-整体’的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。

外观模式特点：为子系统中一组接口提供一个一致的界面，此模式定义了一个高层接口。

备忘录模式：适用于恢复某个类的先前状态，有点类似于快照这类型功能。

原型模式：通过new产生一个对象需要非常繁琐的数据准备或访问权限，则可以使用原型模式。就是java中的克隆技术，以某个对象为原型，复制出新的对象。显然，新的对象具备原型对象的特点。

状态模式：当一个对象，它具有很多种状态的，需要进行繁琐复杂的逻辑处理时，我们可以利用状态模式，将对象的各种状态进行类的封装，用于避免if else过于繁琐的情况。

命令模式：是一种数据驱动的设计模式，它属于行为型模式。请求以命令的形式包裹在对象中，并传给调用对象。调用对象寻找可以处理该命令的合适的对象，并把该命令传给相应的对象，该对象执行命令。

Linux命令

如果想列出当前目录以及子目录下所有扩展名为”.txt”的文件，那么可以使用以下哪个命令？（find . -name “*.txt”）

uname：用于显示系统信息。

  • -r：显示操作系统的发行编号。
  • -n：显示在网络上的主机名称。

find：查找文件或目录。

grep：在文件中查找字符串，语法：grep 字符串 文件名。

kill：用来删除执行中的程序或工作。

ctrl+c：是终止一个前台进程，是终止当前在终端窗口中运行的命令或脚本。

ctrl+z：是将任务中止（暂停的意思）。

halt：用来关闭正在运行的Linux操作系统

编译原理

  • 词法分析器：分析单词的构成（class, const , static）。
  • 语法分析器：一个句子的构成（单词组合）。
  • 语义分析器：判断程序的结构。

排序算法

选择排序：每次从数组中选出一个最小数（最大数）放到数组最前面，存放在序列的起始位置，直到全部待排序的数据元素排完。
希尔排序：设置增量分割数组，逐步进行直接插入排序，增量逐趟减少，并最后使得整个数组基本有序，再对整体进行直接插入排序。
插入排序：构建有序序列，未排序数据依次从已排序数据按从后往前比较，插入到合适的位置。
归并排序：把序列分成两个长度为n/2的子序列，对这两个子序列分别归并排序（循环将两个数组的第一个值比较，并弹出第一个值，直到数组长度都不存在），将两个排序好的子序列合并成一个最终的排序序列。

一趟结束后能够确定一个元素的最终位置的排序方法有：简单选择排序、快速排序、冒泡排序、堆排序。

堆排序中自底向上构建堆的时间复杂度是O(n）。
堆排序中自上而下调整堆的时间为O(nlogn)。

ElasticSearch

什么是倒排索引（反向索引）

以诗句内容中的一些关键字作为索引，来找到诗句。

搜索引擎三大过程

爬取内容、进行分词、建立反向索引。

ElasticSearch介绍

其实很早以前，业界有一个叫做Lucene的库，用它就可以方便地建立倒排索引。但是Lucene还是一个库，必须要懂一点搜索引擎原理的人才能用的好，所以后来又有人基于lucene进行封装，写出了ElasticSearch。ElasticSearch将对搜索引擎的操作都封装成了restful的api，通过http请求就能对其进行操作。同时，它还考虑了海量数据，实现了分布式，是一个可以存储海量数据的分布式搜索引擎。

Elasticsearch基本概念

要了解ElasticSearch，首先要了解里面的几个专有名称，索引（数据库）、类型（表）、文档（行）、字段（列）。ElasticSearch中的索引是存放数据的地方，可以理解为mysql中的一个数据库。类型是用来定义数据结构的，可以认为是mysql中的一张表。文档就是最终的数据，可以认为一个文档就是一条记录。

一个数据怎么存储到elasticsearch

  • 比如一首诗，有诗题、作者、朝代、字数、诗内容等字段，那么首先，我们可以建立一个名叫 Poems 的索引，然后创建一个名叫 Poem 的类型，类型是通过 Mapping 来定义每个字段的类型。
  • 比如诗题、作者、朝代都是 Keyword 类型，诗内容是 Text 类型，而字数是 Integer 类型，最后就是把数据组织成 Json 格式存放进去了。
  • keyword 类型是不会分词的，直接根据字符串内容建立反向索引，Text 类型在存入 Elasticsearch 的时候，会先分词，然后根据分词后的内容建立反向索引。
  • 使用 curl -XPUT http://ip:port/poems ，就能建立一个名为 Poems 的索引，其他操作也是类似的。

搜索引擎总结

  • 反向索引又叫倒排索引，是根据文章内容中的关键字建立索引。
  • 搜索引擎原理就是建立反向索引。
  • ElasticSearch 在 Lucene 的基础上进行封装，实现了分布式搜索引擎。
  • ElasticSearch 中的索引、类型和文档的概念比较重要，类似于 MySQL 中的数据库、表和行。
  • ElasticSearch 也是 Master-slave 架构，也实现了数据的分片和备份。
  • ElasticSearch 一个典型应用就是 ELK 日志分析系统。

其它

搜索引擎对文章分词之后，根据关键字建立倒排索引。

参考

ActiveMQ

浅谈ActiveMQ与使用（博客园）

什么是消息中间件

实现的就是在两个系统或两个客户端之间进行消息传送。

什么是ActiveMQ

ActiveMQ是一种开源的基于JMS（Java Message Servie）规范的一种消息中间件的实现，ActiveMQ的设计目标是提供标准的，面向消息的，能够跨越多语言和多系统的应用集成消息通信中间件。

什么时候需要用ActiveMQ

系统业务的解耦，异步消息的推送，增加系统并发量，提高用户体验。

ActiveMQ的两种消息传递类型

  • 点对点传输，即一个生产者对应一个消费者，生产者向broke推送数据，数据存储在broke的一个队列中，当消费者接受该条队列里的数据。
  • 基于发布/订阅模式的传输，即根据订阅话题来接收相应数据，一个生产者可向多个消费者推送数据，与MQTT协议的实现是类似的。
  • 区别：点对点传输消费者可以接收到在连接之前生产者所推送的数据，而基于发布/订阅模式的传输方式消费者只能接收到连接之后生产者推送的数据。

MySQL

以下关于sql查询语句执行顺序描述正确的是：

from->where->group by→having→select→order by

count(distinct column_name) 函数返回指定列的不同值的数目。
count(column_name) 函数返回指定列的值的数目（NULL 不计入）。

在数据库系统中，视图可以提供数据的安全性。

在数据库系统中，产生不一致的根本原因是：数据冗余，并发控制不当，各种故障、错误。

limit分页查询

1
2
select * from student limit 2,3; # 跳过2行记录,查询3行
select * from student limit 2 offset 3; # 查询2行,跳过3行记录

SQL语言

  • 数据定义语言(DDL)，例如：CREATE、DROP、ALTER等语句。
  • 数据操作语言(DML)，例如：INSERT（插入）、UPDATE（修改）、DELETE（删除）语句。
  • 数据查询语言(DQL)，例如：SELECT语句。（一般不会单独归于一类，因为只有一个语句）。
  • 数据控制语言(DCL)，例如：GRANT、REVOKE、DENY等语句。

Oracle

Oracle数据库的逻辑结构

数据库 > 表空间 > 段（segment）> 区（extent）> 块（block）> 文件（file）

数学思想

n-1边的和大于最长边，就能组成封闭多边形。

给定字符串求字符串的子串个数

假设字符串str=”abcdef”；求子串可以看成将该字符串分割成不同的字符串，需要两个分隔符即可实现。a|bc|def 设字符串长度为n，第一个分隔符有n+1种放法，第二个有n种放法。由于两个分隔符互换位置结果相同，所以需要折半，再加上空串所以个数为：n(n+1)/2+1。

完全二叉树叶子结点数 (n+1)/2 (n为奇数) n/2 (n为偶数)。

从m个数中选n个数,有多少种组合：m! / n! * (m - n)!

Java虚拟机

JAVA的类加载期负责整个生命周期内的class的初始化和加载工作，就虚拟机的规范来说，以下代码会输出什么结果？

Java 中静态代码块初始化问题测试