考研杭电计算机复试面试：专业课

知识点梳理如下： 一、数据结构基础 1. 树的定义与特性 - 树是n（n≥0）个节点的有限集。n=0时称为空树。在非空树中： a) 有且仅有一个特定的称为根的节点。 b) 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个子集又都是一棵树，并且称为根的子树。 2. 二叉树的定义与特性 - 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。 - 二叉树的度为2，表示节点最多有2个子节点。 3. 度为二的树与二叉树的区别 - 度为二的树与二叉树的主要区别在于子树的有序性。度为二的树的子树是无序的，而二叉树中的节点的两个子树是有明确顺序的，区分左子树和右子树。 4. 最小生成树算法 - 普里姆（Prim）算法：从某一顶点开始逐步扩展，每次添加权值最小的边，直至形成最小生成树。 - 克鲁斯卡尔（Kruskal）算法：对所有边按权值从小到大排序，依次选择权值最小的边，确保不会形成环，直至选择n-1条边，形成最小生成树。 5. 排序算法的时间复杂度 - 排序算法的时间复杂度根据算法不同而有所差异，常见的有插入排序、快速排序、堆排序、归并排序等。在面试中，应能快速列举出各种排序算法的时间复杂度。 二、图论基础 1. 图的存储结构 - 邻接矩阵：通过一个二维数组表示图中顶点之间的连接关系。 - 邻接表：每个顶点用链表存储其邻接的其他顶点，节省空间，适用于稀疏图。 - 十字链表：有向图中存储顶点入度和出度。 - 邻接多重表：无向图中便于边的操作。 2. 图的遍历算法 - 图的遍历可以分为深度优先搜索（DFS）和广度优先搜索（BFS）。 - 深度优先搜索使用栈实现，广度优先搜索使用队列实现。 3. 树的遍历 - 树的遍历分为前序遍历、中序遍历、后序遍历和层次遍历。 - 前序遍历先访问根节点，然后递归遍历左子树，最后遍历右子树。 - 中序遍历先遍历左子树，然后访问根节点，最后遍历右子树。 - 后序遍历先递归遍历左子树，然后递归遍历右子树，最后访问根节点。 - 层次遍历按层次从上到下，从左到右顺序访问所有节点。 三、计算机网络基础 1. 互联网的分层结构 - 通常分为应用层、传输层、网络层、数据链路层和物理层。 - 每层都有其特定的功能和协议，如传输层的TCP/UDP协议、网络层的IP协议、数据链路层的以太网协议等。 2. 数据链路层和网络层的协议 - 数据链路层的协议涉及到物理地址（如MAC地址）、帧的结构、流量控制和错误检测等。 - 网络层则涉及到路由选择、分组转发以及IP协议等。 3. HTTP协议 - HTTP（超文本传输协议）是应用层协议，用于从Web服务器传输超文本到本地浏览器的传送协议。 四、操作系统基础 1. 进程与线程 - 进程是系统进行资源分配和调度的一个独立单位。 - 线程是进程中的一个执行单元，是CPU调度和分派的基本单位，一个进程可以有多个线程。 2. 编译过程 - 编译过程分为预处理、编译、汇编和链接四个阶段。 五、编程语言基础 1. Java中的抽象类与接口 - 抽象类用于表示抽象概念，可以包含私有方法或变量，子类继承抽象类时可以选择性地重写方法。 - 接口用于定义一组规范，不能包含私有方法或变量，实现接口的类必须实现接口中所有的方法。 六、硬件知识 1. FPGA、MCU、CPU区别 - FPGA（现场可编程门阵列）是一种可以通过编程来配置的芯片，通常用于实现硬件逻辑。 - MCU（微控制器）是一种集成了CPU、内存、输入输出等模块的集成电路，用于控制其他设备。 - CPU（中央处理器）是计算机的主要组成部分，负责执行指令和处理数据。 以上知识点是根据考研杭电计算机复试面试的内容梳理总结的，每一点都对应了面试中可能遇到的问题，希望能对备考的同学们有所帮助。