软件设计师--中级
目录
1）堆定义
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子结点的值；
其中，如果父亲结点的值大于或等于孩子结点的值，那么称这样的堆为大顶堆，这时每个结点的值都是以它为根结点的子树的最大值；
如果父亲结点的值小于或等于孩子结点的值，那么称这样的堆为小顶堆，这时每个节点的值都是以它为根结点的子树的最小值。
- 堆一般用于优先队列的实现，而优先队列的实现默认情况下使用的是大顶堆。
- 堆是非线性数据结构，相当于一维数组，有两个直接后继
例题：
D选择中，不满足堆定义：每个结点的值都不小于（或不大于）其左右孩子结点的值；
2）”4+1“视图模型
指用5个视图组成的模型来描述软件架构
该模型包含五个主要的视图：
- 逻辑视图（Logical View），设计的对象模型（使用面向对象的设计方法时）。
- 过程视图（Process View），捕捉设计的并发和同步特征。
- 物理视图（Physical View），描述了软件到硬件的映射，反映了分布式特性。
- 开发视图（Development View），描述了在开发环境中软件的静态组织结构。
架构的描述，即所做的各种决定，可以围绕着这四个视图来组织，然后由一些用例 （use cases）或场景(scenarios)来说明，从而形成了第五个视图。正如将看到的，实际上软件架构部分从这些场景演进而来
例题：
3)后缀表达式
后缀表达式又称逆波兰表达式，运算符位于操作数之后 (波兰表达式---前缀表达)
比如:3 4 + 5 × 6 -
后缀表达式计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；
重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如后缀表达式“3 4 + 5 × 6 -”：
- 从左至右扫描，将3和4压入堆栈；
- 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
- 将5入栈；
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
- 将6入栈；
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
例题：
4）归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
算法步骤
-
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
-
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
-
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
-
重复步骤 3 直到某一指针达到序列尾；
-
将另一序列剩下的所有元素直接复制到合并序列尾。
此图参考：https://www.runoob.com/w3cnote/merge-sort.html
例题：
次方法用指针操作
5）静态绑定、动态绑定
以C++在面向对象编程中为例
- 静态类型：对象在声明时采用的类型，在编译期既已确定；
- 动态类型：通常是指一个指针或引用目前所指对象的类型，是在运行期决定的；
- 静态绑定：绑定的是静态类型，所对应的函数或属性依赖于对象的静态类型，发生在编译期；
- 动态绑定：绑定的是动态类型，所对应的函数或属性依赖于对象的动态类型，发生在运行期；
静态绑定和动态绑定的区别：
1. 静态绑定发生在编译期，动态绑定发生在运行期；2. 对象的动态类型可以更改，但是静态类型无法更改；
3. 要想实现动态，必须使用动态绑定；
4. 在继承体系中只有虚函数使用的是动态绑定，其他的全部是静态绑定；
例题：
6）常用的页面调度算法
(1)最优(OPT)算法：选择不再使用或最远的将来才被使用的页。该算法难以实现，常用于淘汰算法的比较。
(2)随机(RAND)算法：随机地选择被淘汰的页，开销小，但是可以选中立即就要访问的页。
(3)先进先出(First In First Out，FIFO)算法，又称轮转法(RR)：选择在内存驻留时间最长的页。该算法似乎合理，但可能淘汰掉频繁使用的页。另外，使用FIFO算法时，在未给予进程分配足够的页面数时，有时会出现给予进程的页面数增多，缺页次数反而增加的异常现象。FIFO算法简单，可采用队列实现。
(4)最近最少使用(Least Recently Used，LRU)算法：选择离当前时间最近的一段时间内使用得最少的页。这个算法的主要出发点是，如果某个页被访问了
例题：
7）UML 图
UML中有多种类型的图，其中通信图显示在某种情况下对象之间发送的消息（强调是连接）
UML图分为用例视图、设计视图、进程视图、实现视图和拓扑视图，又可以静动分为静态视图和动态视图
静态图分为：用例图，类图，对象图，包图，构件图，部署图。
动态图分为：状态图，活动图，协作图，序列图。
例题：
8）路由协议
- 路由信息协议（RIP）
- 内部网关协议（IGRP）
- 开放式最短路径优先（OSPF）
- 外部网关协议（EGP）
- 增强的内部网关路由协议（EIGRP）
- 边界网关协议（BGP）
- 中间系统到中间系统（IS-IS）
路由信息协议（RIP）
RIP（路由信息协议）是在局域网和广域网中使用的强制协议类型。RIP（路由信息协议）类型是使用距离矢量算法的内部网关协议。路由信息协议于1988年定义。它也有版本2，如今两个版本都在使用。从技术上讲，它已被（OSPF）和OSI协议IS-IS等更复杂的技术所淘汰。
内部网关路由协议（IGRP）
是思科的距离矢量IGRP（内部网关协议）。路由器使用它来交换独立系统中的路由数据。内部网关路由协议的创建部分是为了克服大型网络中RIP（路由信息协议）的局限性。它为每个路由以及可靠性，MTU，延迟负载和带宽维护多个指标。EIGRP的最大跃点为255，路由更新正在传输90秒。它使用有类路由协议进行度量，但由于浪费IP地址空间而不太受欢迎。
首先打开最短路径（OSPF）
开放式最短路径优先（OSPF）是Internet协议中使用的活动路由协议。特别是它是一个链接状态路由协议，并包含在内部网关协议组中。开放式最短路径优先（OSPF）在不同的自治系统中运行。开放式最短路径优先（OSPF）的版本2在1998年为IPv4定义，然后在RFC 5340中为OSPF版本3于2008年定义。开放式最短路径优先（OSPF）在大型企业网络中使用最广泛。
外部网关协议（EGP）
互联网的绝对路由协议是外部网关协议，它由1982年由Eric C.EGP（外部网关协议）指定，最初由RFC827表示，并于1984年在RFC 904中正确指定。外部网关协议（EGP）与距离矢量和路径向量协议。它就像树一样是拓扑。
增强的内部网关路由协议（EIGRP）
基于原始IGRP的增强型内部网关路由协议（EIGRP），它是Cisco专有的路由协议。在优化过程中，它是一种预先设置的距离矢量路由协议，以减少拓扑更改后引起的路由不稳定，以及支持增强型内部网关路由协议的路由器中带宽和处理能力的使用，将自动将路由信息重新分配给IGRP（通过将32位EIGRP（增强型内部网关路由协议）度量标准交换为24位IGRP度量标准，增强了内部网关路由协议）的邻居。通常，基于SRI的DUAL工作进行的优化可确保无环路运行并提供快速结点的手段。
边界网关协议（BGP）
边界网关协议（BGP）是Internet的核心路由协议，负责维护Internet协议网络表，该表授权AS之间的网络到达功能。边界网关协议（BGP），表示为路径向量协议。它不使用常规的IGP度量标准，而是根据路径，网络策略进行路由判断。它的创建是为了替换外部网关协议（EGP）路由协议，以允许完全分散的路由，以便允许移除允许互联网转变为真正分散系统的NSF Net。自1994年以来一直使用第四版边界网关协议（BGP），从2006年开始使用第四版。RFC4271第4版具有许多功能，例如它可以纠正许多以前的错误，
中间系统到中间系统（IS-IS）
中间系统到中间系统（IS-IS）是一种很棒的协议，网络设备使用该协议来确定从数据包交换网络到另一端提升数据报的最佳方法，此过程称为路由。它是在OSI参考设计的ISO / IEC 10589 2002中定义的。中间系统到中间系统（IS-IS）在级别1和级别2之间进行区分。可以更改路由协议，而无需联系内部区域路由协议。
例题：
持之以恒，加油
文章来源: guo-pu.blog.csdn.net，作者：一颗小树x，版权归原作者所有，如需转载，请联系作者。
原文链接：guo-pu.blog.csdn.net/article/details/103829942