408复试day1

数据结构

深度优先遍历DFS：
首先访问图中起始顶点v，然后由v出发，访问与v邻接且未被访问的顶点v1，再访问与v1相邻的且未被访问的顶点v2……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它仍有邻接顶点未被访问过，则从该点继续上述搜索过程，直到图中所有顶点均被访问过为止。因此深度优先遍历的策略就是尽可能“深”的搜索一个图，即一条路走到黑。
广度优先遍历BFS:
广度优先遍历类似于二叉树的层次遍历。首先访问顶点v，然后从v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3……然后依次访问w1，w2，w3……的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，访问他们未被访问过的邻接顶点。直到图中所有顶点都被访问过为止，此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有的顶点都被访问为止。
满二叉树：
①高度为H。结点数为2^H-1的二叉树为满二叉树。
②满二叉树一定是完全二叉树
完全二叉树：
①除最后一层外，其余各层的结点数量达到最大值，并且最后一层只能在右侧缺少节点。
②若有度为1的结点，则只能有一个，且该结点只有左孩子而无右孩子。
二叉排序树：
①左子树上所有的关键字均小于根节点，右子树上所有关键字均大于根节点。左子树和右子树又分别为一颗二叉排序树。
②构造二叉排序树时，用两组相同的数据，若数据的排序顺序不同，构造出的二叉排序树也不一样。
③二叉排序树的叶子结点到根节点的路径不一定是有序的。
平衡二叉树：
树中每一个结点的左子树，右子树高度之差的绝对值等于1。

计算机组成原理

冯诺依曼计算机的基本组成：
运算器，存储器，输入单元，输出单元，控制器
其中控制器和运算器共同组成cpu。
冯诺依曼计算机的基本特征：
①计算机由存储器、运算器、输入输出单元，控制器组成，并以运算器为中心连接在一起。
②存储器由一组一维排列、线性编址的存储单元组成，每个存储单元的位数是相等且固定的，存储单元按地址访问。
③程序是由一条一条的指令有序排列而成，而指令由操作码和地址码组成。
④指令和数据均以二进制数表示，并以二进制数的形式进行计算。
⑤程序（指令）与数据是同等地不加区分地存储在一个存储器中。
⑥设置“程序计数器PC”来指示下一条将要执行的指令的地址。每执行完一条指令，程序计数器就自动加1，指向下一条指令的存储单元。
电子计算机的发展经历了那几代，每一代的特征是什么？
第一代电子计算机是电子管计算机，它的特征是采用电子管作为逻辑元件，能够处理的数据类型只有定点数，用机器语言或汇编语言来编制程序。
第二代电子计算机是晶体管计算机，它的特征是采用晶体管代替电子管作为逻辑元件；用磁芯作为主存储器；采用磁带、磁鼓、纸带、卡片穿孔机和阅读机作为输入输出设备。
第三代电子计算机是集成电路计算机，它的特征是采用集成电路代替分立的晶体管元件；半导体存储器逐渐取代磁芯存储器；控制单元设计开始采用微程序控制技术。
第四代电子计算机的特征是采用大规模集成电路、采用半导体存储器作为主存储器。

操作系统

内存管理的主要功能：内存分配、内存保护、地址映射和内存扩充。
①内存分配：内存分配的主要任务是为每道程序分配内存空间，使它们“各得其所”，提高存储器的利用率，减少不可用的内存空间；允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要；
②内存保护：内存保护的主要任务是确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰；决不允许用户程序访问操作系统的程序和数据；也不允许用户程序转移带非共享的其它用户程序中去执行；
③地址映射：为使程序能正确运行，存储器管理必须提供地址映射功能，以将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址，该功能应在硬件支持下完成；
④内存扩充：借助于虚拟存储技术，从逻辑上去扩充内存容量，使用户所感觉到的内存容量大得多，以便于让更多的用户程序并发运行。

计算机网络

TCP/IP的核心思想：是“网络互联”，将使用不同低层次协议的异构网络，在运输层、网络层建立一个统一的虚拟逻辑网络