笔试知识汇总

笔试知识汇总

记录一些笔试常见的计算机领域基础知识。

数据结构

树

二叉树

遍历

二叉树的遍历常常有三种：前序遍历、中序遍历以及后序遍历。

前序遍历顺序：根节点 -> 左孩子节点构成的树 -> 右孩子节点构成的树

中序遍历顺序：左孩子节点构成的树 -> 根节点 -> 右孩子节点构成的树

后序遍历顺序：左孩子节点构成的树 -> 右孩子节点构成的树 -> 根节点

常有题目类型为，已知二叉树的前序与中序遍历结果，求后序遍历结果。如：

• 前序遍历：34627159
• 中序遍历：64273519

求解方法：前序遍历中的分布方式是 (根

左树

右树)，而中序遍历中的分布方式为(左树

根

右树)，由前序遍历中的3在中序遍历的位置可知其左右树状况，其次由4在中序遍历中的位置可知其子树情况，一直向下便可构建出完整的树。

前序顺序与后序顺序同理可确定一棵二叉树，但前序与后序不行，分不清左右节点。

哈夫曼树 Huffman

哈夫曼树Huffman Tree 构造过程：

1. 统计所有元素的出现频次。
2. 选出出现频率最小的两个元素作为左右节点构成一棵二叉树。这两个节点从列表中删除后，将根节点加入到元素列表，其频次为两左右节点频次之和。
3. 循环 2 直至列表中只剩下一个元素，此元素即为哈夫曼树的根节点。
4. 对叶子节点（即各个元素）进行编码。

构造过程的不同各个元素的具体编码可能不同，但每个字符的编码位数可以固定。

字符串匹配

KMP算法

排序

常见排序算法对比：

排序算法	稳定性	时间复杂度	最好情况	最坏情况
冒泡排序	稳定		O(n)	O(n^2)
选择排序	不稳定	O(n^2)	O(n^2)	O(n^2)
快速排序	不稳定	O(n log n)
堆排序
基数排序

排序算法的稳定性定义：待排序序列中相同元素在经过排序后其相对位置是否变化。

堆排序

堆排序和选择排序都拥有 每轮选择未排序区中的一个元素加入排序区的思想。堆是一颗完全二叉树。进行堆排序时，会将排序数组看作为一颗完全二叉树。

• 大根堆：每个节点的值大于左右孩子节点的值。

• 小根堆：每个节点值小于左右孩子节点的值。

堆排序中主要的步骤只有两种：

1. 构建堆：将当前不符合最小堆或是最大堆定义的堆根据固定算法将堆重建。从最后一个非叶子节点开始重建堆直至根节点操作完成。
2. 交换元素：当堆构建完后，堆的第一个元素（或称为二叉堆的根节点）一定为最大的元素。将堆顶元素与非排序区中最后一个元素互换，此举将堆顶元素放置到排序区。此时非排序区组成的堆可能会被破坏，重复第一步。

当非排序区中无元素时，排序完成。举例：[4, 6, 8, 5, 9]

基数排序

基数排序Radix sort 为非比较型的排序算法，排序方法分为 最低位优先(LSD) 与 最高位优先（MSD）两种。

最低位优先(LSD) 从最低位一路向上，在每一位时根据每个数在此位的大小进行排序。

计算机网络

应用层

HTTP

操作系统

进程状态

进程共有 创建、就绪、运行、阻塞与结束五个状态。

图来自 https://baijiahao.baidu.com/s?id=1776735226586475368&wfr=spider&for=pc

同步与互斥

信号量机制

实现多个进程之间对临界资源的访问。

当信号量 K > 0 时，表示还有 K 个资源可用。

当信号量 K < 0 时，表示有

K

个进程在等待资源。

死锁

计算机组成原理

大端与小端

数据库

关键词

Linux系统常用命令

netstat

编程语言

虚函数

虚函数能够被

设计模式