##数据结构：

   逻辑结构：线性表，树形结构，图形结构，集合

   物理结构：顺序存储，链接存储，散列存储，索引存储。

 

   数组和链表的区别：

       数组是从栈中分配空间的，具有固定的长度，方便读取记录，不易增删；链表是从堆中分配空间的，不定长，方便对数据元素的增删，不易读取。

      

 快速排序：

     选取一个基准元素，通过排序将待排序的元素划分为独立的两个子序列，此时基准元素就处在了最终的位置上，然后对两个子序列按照之前的方法再次划分，直到整个序列有序。

 

 改进：

1. 对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序，一般选8 。
2. 选定一个合适的基准元素，将整个序列尽可能的划分为两个等长的子序列。（利用分治法的特性）

 

  正在上传…重新上传取消

  记忆的方法：

        稳定性：小基插队去吃泡面，并加了鸡蛋

   

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

 

选择排序算法的一般方法：

设待排序元素的个数为n.

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

2）当n较大，内存空间允许，且要求稳定性：归并排序

3）当n较小，可采用直接插入或直接选择排序。

    直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

    直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

5）一般不使用或不直接使用传统的冒泡排序。

6）基数排序
它是一种稳定的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的

 

改进冒泡排序：

1. 设置一个flag，用来记录是否发生过交换，如果没有发送交换，则flag为flase,跳出循环，结束。
2. 利用每一次排序都可以得到一个最大或最小值，所以我们可以在每次遍历中使用两个正反向排序，将大大减少循环次数。

 

邻接矩阵与邻接表优缺点：

邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 n∗n 的矩阵。

而邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。

 

 

算法和程序的区别：程序可以不满足有穷性

 

哈希函数（散列函数）：类似于函数调用一样，给一个字符串作为输入，返回一个哈希码。

哈希表（散列表）：把哈希码映射到表中的一个位置来访问记录，存放记录的数组就叫散列表

直接寻址法：hash（key） = a * key + b；数字分析法；平方取中法；折叠法；随机数法

；除留余数法

解决冲突的方法：

开放寻址法（包括线性探测再散列、二次探测再散列（改善堆积现象）、伪随机探测再散列、双散列法），容易造成堆积现象

链地址法：在原地址新建一个空间，以链表结点的形式插入到该空间。链地址算法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。插入新数据项的时间随装载因子线性增长。

 

补充：{   

 处理冲突;开放定址法，再哈希，链地址法，建立公共溢出区

构建hash函数的方法：

直接定址法，数字分析法，折叠法，平方取中法，除留余数法

使用哈希查找的步骤:先转化；再处理冲突

hash表：通过键值，快速映射到目标地址的数据结构

hash算法：散列算法，将输入的不定长的二进制数转化为输出的定长二进制数。特点：确定性，压缩性，单向性，分散性。

应用于管理数据结构，信息安全（文件校对.数字指纹；数字签名；鉴权协议）MD5，sha1,sha256

散列法:元素特征转变为数组下标的方法，常用除法散列法，平方散列法，斐波那契（Fibonacci）散列法

一致性hash算法：考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来的情况，如何保证当系统的节点数目发生变化的时候，我们的系统仍然能够对外提供良好的服务

}

 

递归算法：

优点：代码简洁、清晰，并且容易验证正确性。

缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

 

循环算法：

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

 

B树和B+树的区别，以一个m阶树为例。

关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。

存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。

分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。

查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

 

补充：{

    B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于

走右结点；

       B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键

字范围的子结点；

       所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

       B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点

中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

       B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率

从1/2提高到2/3；

}

 

迪杰斯特拉（Dijkstra）算法

是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。（针对有向图，不管是求哪一个特定点，时间复杂度都是n2）

按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后，选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。

 

弗洛伊德（Floyd）算法<邻接矩阵求>

是解决任意两点间的最短路径的一种算法（不断更新点对（i，j）在顶点v的辅助下，最短路径。即A[i][j]<A[i][v]+A[v][j]），可以正确处理有向图或负权的最短路径问题。时间复杂度N的3次方

 

普里姆算法的基本思想：

从图中任意取出一个顶点，把他当作一棵树，然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到一棵有两个顶点的树。以此类推，直到所有的顶点被并入为止，此时得到最小生成树。

 

克鲁斯卡尔算法的基本思想：

引入并查集，每次从候选边中找出最小的边，就将该边并入生成树中。

 

 

普里姆和克鲁斯卡尔算法的比较：

普里姆适用于边较多的情况下，克鲁斯卡尔适用于边较少的情况下。

由于克鲁斯卡尔算法只有一次排序花费时间较长，所以该算法的效率高于普里姆。

 

 

 

分治法：

所谓“分而治之” 就是把一个复杂的算法问题按一定的“分解”方法分为等价的规模较小的若干部分，然后逐个解决，分别找出各部分的解，把各部分的解组成整个问题的解。（快速排序和归并排序）

 

动态规划：

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。（从上向下，迭代；从下向上，递归）

前一个问题的求解，给后一个问题的求解带来有用的信息。

（核心:分治思想和解决冗余。特点：重复子问题，有最优子结构，无后效性。优点:运行速度快；缺点：占用空间）

 

贪心算法：

   在对问题求解时，总是做出在当前看来是最好的选择。

选择的贪心策略必须具备无后效性

 

回溯：类似深度优先搜索。

 

分支限定法：类似广度优先搜索

 

 

 

 

 

 

##ThinkPHP

框架有哪些：ZF（大型项目）、易框架，TP

世面上的框架主要是基于MVC和面向对象的思想，都是单一入口，支持ORM机制

TP的目录：

application(开发者编写的代码)

Public(存放cs,js等静态资源信息)

Thinkphp(存放官方信息)

正在上传…重新上传取消

对上图的描述 : 打开入口文件，经过路由，检测url信息和参数信息，再经过安全模块来过滤掉一下敏感信息，再将文件送到控制器，由控制器决定传达给哪一个模块，经行什么行为，产生交互，再由控制器把信息传达给视图。

 

什么是路由：

包含URL模式和路由规则，确定对应控制器下的方法。

什么是ORM：

采用元数据来描述对象和关系映射的细节。

元数据：数据的数据，描述数据的属性。

 

 

 

 

##操作系统：

是什么？控制和管理整个计算机系统的硬件和软件，合理组织调度计算机的工作资源分配

特点？并发性、共享性、虚拟性、异步性

 

发展历程？与硬件紧密关联，无操作系统的计算机系统—单道批处理—多道批处理—分时操作系统—实时操作系统—微型操作系统

 

运行环境？根据cpu上的性质，具体可以分为操作系统内核程序和用户编写外部程序，根据cpu上的操作，具体可以分为两部分，一部分与硬件关联紧密，有时钟管理程序、中断处理程序、设备驱动程序等，另一部分操作频繁，如进程管理程序等。一般总结成时钟管理程序、中断处理程序、原语、系统控制数据结构。这里可以理解用户态和核心态。当用户态向核心态转化的时候，需要发出一条特权指令，如一次中断，用户程序申请系统服务，它的转化不仅仅是状态的更新，而且也是zai的更新

     记：中断是与cpu的指令无关，一般指硬件，异常是与cpu的指令有关。

 

进程：

是什么？系统调度和资源分配的基本单位，包含pcb,程序段和数据段

 

它的状态及转化？运行、阻塞/等待、就绪、新建、终止等。描述过程阻塞可以到就绪状态但不能直接到运行状态。

 

线程？cpu的基本执行单位，轻量型的进程，。由线程id、程序计数器、寄存器集合、和堆栈组成

 

区别：进程是资源分配的基本单位，线程不独立拥有资源，但可以访问隶属进程的资源；进程的创建、撤销和切换都要有资源的分配和回收，开销远大于线程的切换

    

实现方式？用户级线程（给一个函数库）和内核级线程（系统接口），他们之间存在1对1、1对多、多对多等多种模型

 

处理机调度：

是什么？提高资源的利用率

 

调度有哪些？高级调度（任务调度）、中级调度（进程在内存和外存中的调度）、低级调度（进程调度：从队列中，选取进程，分配处理机）

 

不能调度的情况？1、处理中断的过程中；2、进程在操作系统内核临界区；

 

调度的算法：先来先服务、最短优先时间、轮转调度、优先级调度。

临界资源：每次只允许一个进程访问的资源称为临界资源。

 

临界区：访问临界资源的那段代码称为临界区

 

同步：直接制约关系，两个进程在时间上有先后关系。

 

互斥：简介制约关系，当一个进程进入临界区，另一个必须等待。

 

临界区互斥的方法：单标志法、信号量法

 

死锁：

是什么？多个进程竞争资源而造成的一种僵局

 

为什么？资源有限和操作不当

 

条件？请求保持、不可剥夺、循环等待、互斥条件

 

银行家算法？避免死锁方法中允许进程动态地申请资源，但是在分配之前，需要检查安全性

 

内存管理：

涉及的功能：内存的分配与回收、地址转换、内存空间的扩充、存储保护

 

内存保护采用两种方法：①上下限寄存器法；②重定位寄存器和界地址寄存器组合法。

 

多级页表？解决了当逻辑地址空间大时，页表的长度会大大增加的问题。带来了采用多级页表时，一次访盘需要多次访问内存甚至磁盘，会增加一次访问的时间。

 

覆盖是在同一程序或进程中进行的。交换是在不同进程之间进行的。

 

页式存储：把内存空间划分成相同大小且固定的块，具体由系统决定。

 

段式存储：为了考虑到用户的感受，设计出来的逻辑结构，大小不固定，段内连续，段间不连续。

 

 

虚拟存储器：是计算机内存管理的一种技术，它使得应用程序认为自己有连续的可用内存，但是实际上，它通常被分隔成多个物理内存碎片，或者是外存上，在需要是进行数据交换

特性：多次性、对换性、虚拟性

 

需要的硬件支持：1、一定容量的内存和外存 ；2、页表机制；3、中断机构，产生中断；4、地址变换机构

页面置换算法：最佳置换算法、先进先出算法、最近最久未使用算法

 

抖动：页面调动活动，频繁访问的页面数远高于物理页面的数量

 

页面集：时间间隔内，程序要访问的页面集合

 

 

文件：

是什么？以计算机硬件为存储载体在计算机上的信息集合

拓展：文件系统是负责控制和管理文件的软件

 

硬链接：通过索引节点来进行连接。允许多个文件名和路径指向一个索引节点

软链接：符号链接，类似快捷键，包含目标文件的地址。

 

文件保护：为了防止共享文件被未经核准的用户访问或修改，必须通过文件保护来控制用户对文件的存取。

方式：口令保护、加密保护、访问控制

 

文件系统的层次结构：用户调用接口、文件目录系统、存取控制验证、逻辑文件系统与文件信息缓冲区、物理文件系统、辅助分配模块、设备管理程序模块

 

文件分配方式：连续分配、链接分配、索引分配

 

文件存储空间管理：位示图法、组成链接法

 

磁盘调度算法：先来先服务、最短寻找时间、扫描算法、循环扫描。

 

磁盘读写需要：寻道时间、延迟时间和传输时间。寻道时间最耗时

 

IO的四种控制方式：

直接控制方式、中断驱动方式、DMA方式、通道控制方式。

注意从IO设备和CPU两个角度来描述直接控制方式。

 

IO设备的层析结构：

用户应用层、设备独立层、设备驱动层、中断处理层

 

功能：状态跟踪、设备存取、设备分配、设备控制。

 

引入设备独立性的好处：方便用户、提高设备的利用率、提高系统的可适应性和可拓展性

 

##网络：

7层结构：应用层（满足用户需求并确定进程通信的性质）、表示层（解决用户信息的语法问题）、会话层（提供访问验证和会话管理，建立相应的通信机制）、传输层（利用最佳的网络资源，为端对端系统会话层建立通道）、网络层（为要传输的分组选择一条合适的路径，使发送分组能够正确无误地按照给定的目的地址找到目的主机）、数据链路层（负责在2个相邻的结点之间的链路上实现无差错的数据帧传输）、物理层（提供物理连接，保证透明传输）。

 

TCP/IP模型：应用型、传输层、网络层、链路层

 

网络层和传输层的区别：

1、服务对象：传输层提供端到端逻辑通讯，网络层提供主机到主机的逻辑通讯；

2、复用和分用：传输层的复用是发送方不同的应用进程都可使用统一传输层协议传送数据，传输层的分用是接收方的传输层在剥去报文的首部后能够把这些数据正确交付到应用进程。网络层的复用是发送方的不同协议数据都可以封装成IP数据报发出去，分用时指接收方的网络层在剥去首部后把数据交付给相应的协议。

3、传输层差错检测时要检查首部和数据，而网络层只检查IP数据报的首部。

4、传输层可以提供有链接和无连接的两种协议，而网络层只能提供其中之一，不能同时存在两个。

 

 

Udp和IP数据报的区别：

IP数据包是通过路由转发的，而UDP是封装在IP数据报里的，对路由不可见。

 

TCP和网路层虚电路的区别：

TCP对路由不可见，虚电路可见。并且如果采用虚电路，则必须提供连接服务

 

TCP和UDP的区别：

TCP是面向连接、可靠的、字节流传输，仅支持单播，提供拥塞控制和流量控制，头部至少20个字节，用于文件传输。而UDP是不需要建立连接的传输，基于数据报，有单播、多播和广播的功能，头部的开销小，只有8个字节（端口号、数据报的长度），应用于实时传输，如电话会议。

 

3次握手：

   客服端向服务器发出一个请求连接的报文。（包含客户端初始化的序列号）

   服务器收到报文后，同意连接，发出一个应答。（包含服务器初始化的序列号）

   客户端确认回复应答。

 

为什么2次不行？

1. 会陷入一个历史性的重复连接
2. 避免不断同步初始化双方的序列号
3. 减少资源的消耗

 

4次挥手：

   主机A向主机B发送一个请求断开连接的报文。

主机B收到确认，并释放从主机A到主机B的连接。

主机B消息发送完了，给主机A也发出一个请求断开连接的报文。

主机A收到确认，就释放从主机B到主机A的连接

等待2ms,就关闭

 

TCP的序列号：用来解决网络包的乱序问题

      确认应答号：用于解决不丢包的问题

TCP保证了IP层接收网络包无损坏、无间隔、非冗余和按序。

 

 

拥塞控制：属于全局性的，防止过多的数据注入网络，避免过载。有四种算法：慢开始、拥塞避免、快重传、快恢复

流量控制是点对点的，为了抑制发送端发送速率。

 

网络层

功能？异构网络的互连，路由与转发，拥塞控制

 

尽最大努力交付？这点体现出了网络层的优点。只要能交付，可以不考虑数据报是否按序、是否完整、是否有错。

 

 

距离—向量路由算法：定期将更新的路由表发送给与他相邻的结点。路由表包括每条路径的目的地和路径的代价

 

 

常见的路由协议：

RIP协议（根据跳数来选择，最大15跳），OSPF协议（链路状态选择协议）

 

 

IP首部的重要字段：

标识：这个字段是为了让目标主机确定一个新到达的分段属于哪一个数据报（当一个数据报过大时会被分段传输，到达目标主机后在组合起来）。同一个数据报的所有段它们的标识相同。

标志：MF(more fragment），表示“更多段”,MF=1标识后面还有分片。第二位是DF（don’t fragment）标识“不分段”，当DF=0时才允许分片。

片偏移量：较长的分组在分片后，某片在原分组中的相对位置。片偏移以8个字节为单位，因此除了最后一个分片，其它的分片中的有效数据载荷都是8的倍数

生存时间TTL：数据报在网路中可通过的路由数的最大值。路由器在分组转发前，先把TTL减去1，如果TTL变成0，就把它丢弃。

 

分片的原因:是因为一个数据链路层数据报能承载的最大数据量（MTU）有限制，不同的链路上MTU可能不同，如果IP数据报超过了MTU就要将其分片。

 

分片的过程：创建一个IP数据报时给它加一个标识号，当经过路由器要分片时，分出的片都有相同的标识号。IP的首部还有标志位，除了最后一个分片外，其它的标识位MF=1,DF=0;最后一个分片，MF=0,DF=1。重组的时候，根据标识来区分IP数据报，根据片偏移来确定数据的原始位置。

 

IP地址的特点：

1. 所有的网络号都是对等的；
2. 每一个IP地址都是由网络号和主机号组成
3. 分配IP地址的时候，管理机构只分配网络号，主机号由相关单位自行分配
4. 一个IP地址用来标志一个主机或一个路由器或一条链路的接口

 

IP 地址的分类：

 

A 类地址：以 0 开头，第一个字节范围： 0~127 ；

B 类地址：以 10 开头，第一个字节范围： 128~191 ；

C 类地址：以 110 开头，第一个字节范围： 192~223 ；

D 类地址：以 1110 开头，第一个字节范围为 224~239 ；

 

NAT？起专用网络和公用网络之间的转换作用，有助于保护专用网络

 

ARP协议？地址解析协议，根据IP地址获取到物理地址的一个TCP/ip协议

    地址解析协议是建立在网络中各个主机互相信任的基础上的，局域网络上的主机可以自主发送ARP应答消息，其他主机收到应答报文时不会检测该报文的真实性就会将其记入本机ARP缓存；由此攻击者就可以向某一主机发送伪ARP应答报文，使其发送的信息无法到达预期的主机或到达错误的主机，这就构成了一个ARP欺骗。

   具体实现过程（我的理解）：每一台主机都会在自己的ARP缓冲区建立一个ARP列表，表示IP地址和MAC地址之间的对应关系。就像微信朋友圈一样，当我需要给一个群内人发消息的时候，要看看我是否有这个人的对应信息，如果没有，就在圈里发一条动态，当他看到时，会记录下我，并给我发一条消息，我就可以记录下这个人的具体信息。

 

 

DHCP动态主机配置协议？局域网，服务器控制一段IP地址范围，客户端登陆服务器时，就自动分配获取一个服务器分配的IP地址和子网掩码

 

ICMP网络控制报文协议？用于在IP主机、路由器之间传递控制消息

 

局域网中的分组不用分片的原因？局域网中能够通过的最大分组，是提前整个局域网都知道的，所以不可能出现不能支持的分组。

 

 

输入网址后，执行的过程：

输入网址后，DNS会解析该域名得到服务器的IP地址，浏览器通过该IP地址给服务器发送一条HTTP请求，服务器响应请求，发回网页内容，浏览器解析内容，渲染呈现给用户。

 

HTTP包含哪些内容：GET，POST，PUT，DELETE

   其中GET，是从服务器中获取信息；POST是向服务器传送信息

   GET 传送的数据量小，不能大于 2KB ； post 传送的数据量较大，一般被默认为不受限制。

 

网络层 ： IP 协议、 ICMP 协议、 ARP 协议、 RARP 协议。

传输层 ： UDP 协议、 TCP 协议。

应用层 ： FTP（文件传送协议，下载和上传主页，21端口）、 Telenet（远程登录协议，23端口）、 DNS（域名解析协议，53端口）、 SMTP（邮件传送协议，一般开放25端口）， POP3协议（邮局协议，接受邮件，端口110），HTTP 协议。

 

数据链路成帧的方式：字符填充法、字符计数法、比特填充法、违规编码法。

 

DNS工作过程：
应用层协议，使用UDP。分为迭代查询和递归查询。采用分布式集群的工作方式，防止单点故障，增加通信容量。
迭代：主机访问本地域名服务器，若缓存没有IP则本地域名服务器进一步向其他根域名服务器查询。
递归：主机分别向多个服务器发出查询请求。

 

 

数据链路层：

主要功能可总结为：为网络层提供服务、链路管理、帧的封装、流量控制、差错控制。

 

向网络层提供的服务：有确认/无确认的面向连接的服务

 

差错控制：由于噪声和其他设备的影响，传输的数据会出现差错。（位错误、帧错误）

常用办法：自动重传请求法。

 

检错编码：奇偶校验码

 

载波侦听多路访问（CSMA）是一种介质访问控制（MAC）的协议。载波侦听（Carrier Sense） 指任何连接到介质的设备在欲发送帧前，必须对介质进行侦听，当确认其空闲时，才可以发送。 多路访问（Multiple Access） 指多个设备可以同时访问介质，一个设备发送的帧也可以被多个设备接收。

 

CSMA/CA 的基本思想：发送数据之前先告知其它结点，让其他结点在某段时间内不要发送数据，避免碰撞。

CSMA/CD的基本原理是：所有节点都共享网络传输信道，节点在发送数据之前，首先检测信道是否空闲，如果信道空闲则发送，否则就等待；在发送出信息后，再对冲突进行检测，当发现冲突时，则取消发送。

 

CSMA\CD协议和CSMA\CA的不同：

①CD可以检测冲突但无法避免冲突，CA可以尽量避免冲突。

②传输介质不同，一个总线型以太网，一个无线网

③检测方式不同。CD用电压来检测，CA用能量检测等三种方式来检测信道。

 

为什么PPP协议不使用帧的编号和确认机制来实现可靠传输？

①如果实现可靠传输的数据链路层协议，开销就会很大。

②PPP信息字段放入的数据是IP数据报。假如实现了可靠传输协议，上升到网络层后仍然可能被丢弃。它不能保证网络层也可靠。

③PPP可以保证无差错接受，因为有FCS。

 

##计算机组成原理：

冯诺依曼机的特点？

1. 五个组成部分：运算器、控制器、存储器、输入设备、输出设备
2. 数据和指令以同等的地位存储在主存储器当中，可按照地址访存
3. 指令和数据均用二进制代码表示
4. 指令由操作码和地址码组成，操作码表示操作性质，地址码表示操作数所在位置
5. 指令以顺序存放的。通常指令按顺序执行，在特定条件下根据运算结果或特定的条件改变执行顺序

6、早期冯诺依曼机以运算器为中心，输入输出设备通过运算器与存储器相连

 

为什么后来以存储器为中心？随着设备的不断更新换代，外部输入设备和cpu的运行效率严重不匹配，如果继续以运算器为中心，会降低运行效率。

 

 

 

描述一下计算机是怎样运作的？

从宏观上讲，是运算器、存储器、控制器、输入输出设备之间的相互协作。用户通过输入设备输入信息，计算机通过输出设备输出信息；当计算机读取到信息后，会由运算器进行分析处理，并将结构放在存储器里，这一切的协同，是由控制器来控制的。

从微观上讲，和存储程序的做法类似，是通过不断地重复“取指令、指令译码、执行指令”这三个过程实现的。

 

存储程序？程序在运行前，都先存在主存储器当中，按照其在程序中的首地址执行第一条指令，然后就按照该程序规定的顺序执行其它指令，顺序程序结束

 

计算机的主要性能指标？机器字长、数据通路带宽、主存容量、运算速度。

 

影响cpu运算速度的因素？吞吐量和响应时间、主频和CPU周期、CPI等

 

机器字长是计算机能直接处理的二进制数据的位数，机器字长一般等于内部寄存器的大小，它决定了计算机运算的精度

指令字长是一个指令中包含的二进制代码的位数

存储字长是一个存储单元包含的二进制代码的位数（都是和2进制有关）

 

用正负号所表示的数就是真值，真值是机器数所代表的实值。

原码简单直观的机器数表示法。原码的0有两种表示方法

补码的正数表示和原码相同，负数等于原码的非符号位取反再+1，补码加减法操作简单

，0的表示唯一。

反码的正数表示和原码相同，负数等于原码的非符号位取反。

移码常用来表示浮点数的阶码 ，它只能表示整数。

 

存储器的性能指标？存储容量、单位成本、存取速度

 

存取时间：启动一次存储器操作到完成该操作所需要的时间。

存取周期：存储器完成一次完整的读写操作所用的时间，即两次独立访问存储器操作之间所需的最小时间间隔

主存带宽：主存的数据传输率，每秒从主存进出信息的最大数量

（记：存取周期比存取时间长，在一次存取操作完成后，会进行状态的复原）

 

多级存储系统结构：寄存器、高速缓存、主存、辅助存储

 

Cache主要解决访问速度问题，虚拟存储解决主存容量问题。

 

段式存储器：段式按照程序的逻辑结构划分的，长度因程序的长度不同而不同。虚拟地址分为：段号和段内地址两个部分。

      优缺点：逻辑独立性强，便于多道程序共享；但是长度可变，易产生大量的碎片。

页式存储器：以页为基本的单位，大小固定，主存的页为实页，虚存的页为虚页。虚拟地址分为两个字段：虚页号和页内地址。

      优缺点：页表简单，长度固定。但是最后一个块有内部碎片，它的处理、保护和共享都不如段式

 

指令？计算机运行的最小功能的单位，计算机执行操作的命令。

      联系冯诺依曼，它是由操作码和地址码组成，和数据一起以二进制对等的存储在存储器中。

 

指令寻址：寻找下一条要执行的指令地址；数据寻址：寻找操作数的地址。

分为：顺序寻址和跳跃寻址两种。顺序寻址是PC+1自动生成的指令，而跳跃寻址是由本条指令给出下条地址的计算方式形成的，结果是修改PC的值，所以下一条指令仍然通过PC给出。

 

数据寻址是是指如何在指令中表示一个操作数的地址，如何用这种表示得到操作数或者怎样计算出操作数的地址

 

Cpu:是由运算器和控制器组成。

    功能：指令控制、操作控制、时间控制、数据加工、中断处理

 

指令周期：CPU从主存中每取出和执行一条指令所需的全部时间称为指令周期，

包括取指周期、间址周期、执行周期、中断周期。

 

指令的执行方案：单指令周期（每一条指令执行时间相同）、多指令周期（不同的指令用不同的方案来执行）、流水线。都是采用串行执行。

 

指令流水线

将一条指令分为多个子过程，每个子过程与其它的子过程并行执行，以提高计算机吞吐率的手段。当前常用的并行处理技术。

影响指令流水线的因素：

数据相关。在程序中，存在必须等待前一条指令执行完，才能执行后面一条指令的情况。解决犯法有1、把遇到数据相关的指令和后续指令都暂停几个周期；2、设置专用的数据通路，上一条指令的值不用写入寄存器，下一条指令也不用读寄存器组，而是直接把上一条指令计算结果作为下一条指令的输入数据开始计算，这叫做数据旁路技术。3、通过编译器对数据相关指令编译优化的方法，调整顺序来解决数据相关。

结构相关。多条指令在同一时刻争用同一资源而形成的冲突称为结构相关。解决办法：1、前一条指令访存时，后一条指令暂停一个时钟周期。2、单独设置数据存储器和指令寄存器，对资源重复配置。

控制相关。当流水线遇到转移指令和其它改变PC值的指令而造成的断流，会引起控制相关。解决办法：1、对转移指令进行分支预测，更好生成转移目标地址。2、取转移成功和不成功两个方向上的目标指令。3、加快和提前形成条件码。4、提高转移方向的准确率。

 

 

总线是一组能为多个部件分时共享的公共信息传输线路。

分类：片内总线、系统总线、通讯总线

总线传输周期：一次总线操作所需要的时间，包括申请阶段、寻址阶段、传输阶段、和结束阶段。

问题：如果设备过多，会引发总线冲突，需要总线终裁来解决。

 

 

##补充问题：

1. 二分排序可以用链表实现吗，然后问你为什么？
   二分排序再插入一个元素时使用二分查找法在前面已排序好的元素中找到插入元素所在的位置，二分查找法需要支持随机访问的存储结构，而链表只支持顺序访问，因此不行。
2. 哈希能够支持区间查询吗？比如查找0到18岁的？

        可以，拉链法，设计相应的hash函数。

1. 算法里面时间复杂度分析的大O表示什么？
   大O符号用来描述函数渐进行为的数学符号，一个大O,在其括号中用另一个函数来描述原来函数的数量级的渐进上界，常用于描述算法的复杂度。
2. 数据结构的复杂度o(1)是什么意思?
   时间复杂度O(n)，表示程序运行时间跟n有关，并且是线性关系。
   空间复杂度O(1)，表示所需辅助空间为常量，并且与n无关。
3. 哪些因素可以影响计算机的运行速度？
   CPU、显卡、内存、硬盘
4. UML里面有哪些图？
   UML图包括九种：使用案例图、类图、对象图、构件图、部署图、活动图、协作图、状态图、序列图。在这些图中使用案例图、类图、序列图是最有用的。
5. UML：统一建模语言，它是一个支持模型化和软件系统开发的图形化语言，为软件开发的所有阶段提供模型化和可视化支持。
6. C语言：
   函数调用之前的工作：
   （1）为被调用函数分配数据存储区；
   （2）将所有的实参、返回地址等信息传给被调用函数保存；
   （3）将控制转移到被调用函数的入口。
   返回前的工作：
   （1）保存计算结果；
   （2）释放存储区；
   （3）控制转移。

 

 

提供一个好网址：https://blog.csdn.net/qq_26347051/article/details/79821063