软件设计师考点内容分析(一)

1、CPU构成

• 程序计数器(PC)：存放执行指令的地方，计算之前要用到
• 累加器(AC)：暂时存放算数逻辑运算部件ALU运算的结果信息
• 指令寄存器(IR)：保存当前正在执行的一条指令
• 地址寄存器(AR)：保存当前CPU所要访问的内存单元的地址

2、DMA(Direct Memory Access，直接内存存取)

• DMA工作方式，是在DMA控制硬件的控制下，实现内存与外设间数据的直接传送，并不需要CPU参与工作，由于DMA方式是在DMA控制硬件的控制下实现数据的传送，不需要CPU执行程序，故这种方式传送的速度最快。

3、系统可靠度

• 并联部件的可靠度=1-部件失效率的乘积

4、海明码

• 海明码是一种可以纠正一位差错的编码
• 公式：2^r>=k+r+1 (r增加的冗余位，k有效的信息位)

5、高速缓存Cache

• Cache位于CPU和主存之间，由硬件实现，容量小，一般在几KB到几MB之间，速度一般比主存快5到10倍，由快速半导体存储器制成，其内容是主存内容的副本(Cache无法扩大主存的容量)，Cache既可存放程序又可存放数据。

6、软件分析到设计的过程

• 研究、分析和审查数据流图。根据穿越系统边界的信息流初步确定系统与外部接口
• 根据数据流图决定问题的类型。数据处理问题通常有两种类型：变换型和事务型
• 由数据流图推导出系统的初始结构图
• 利用一些启发式原则来改进系统的初始结构图，直到得到符合要求的结构图为止
• 根据分析模型中的实体关系图和数据字典进行数据设计，包括数据库设计和数据文件的设计
• 在设计的基础上，依旧分析模型中的加工规格说明、状态转换图进行过程设计。

7、螺旋模型

• 螺旋模型是一种演化软件开发过程模型，它兼顾了快速原型的迭代的特征以及瀑布模型的系统化与严格监控。螺旋模型最大的特点在于引入了其他模型不具备的风险分析，使软件在无法排除重大风险时有机会停止，以减小损失。同时，在每个迭代阶段构建原型是螺旋模型用以减小风险的途径。螺旋模型更适合大型的昂贵的系统级软件应用。

8、多态

• 多态是同一操作用于不同对象，可以有不同的解释，产生不同的执行结果。在运行时，可以通过指向基类的指针，来调用实现派生类中的方法。也就是说客户类其实在调用方法时，并不需要知道特定子类的实现，都会用统一的方式来调用。

9、装饰模式、外观模式

• 装饰模式是一种对象结构型模式，可动态的给一个对象增加一些额外的职责，就增加对象功能来说，装饰模式比生成子类实现更为灵活。通过装饰模式，可以在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；当需要动态的给一个对象增加功能，这些功能可以再动态的被撤销时可使用装饰模式；当不能采用生成子类的方法进行扩充时也可使用装饰模式。
• 外观模式是对象的结构模式，要求外部与一个子系统的通信必须通过一个统一的外观对象进行，为子系统中的一组接口提供一个一致的界面，外观模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。

10、共享锁和排它锁

• 共享锁(S锁)，又称为读锁，若事务T对数据对象A加上S锁，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上面的S锁。
• 排它锁(X锁)，又称为写锁，若事务T对数据对象A加上X锁，其他事务不能再对A加任何锁，直到T释放A上的锁。

11、二叉树遍历

• 先序遍历：先根后左子树再右子树
• 中序遍历：先左子树后根再右子树
• 后序遍历：先左子树后右子树再根

12、算法设计策略

• 贪心法：求解问题最优解，将问题分解为若干步，每一步都取当前最优解，即局部最优解。
• 分治法：求解问题唯一解，将问题分解为小规模的子问题，子问题之间相互独立。
• 回溯法：求解问题最优解或唯一解，就是深度优先搜索，常用递归实现。
• 分支限界法：求解问题最优解或唯一解，活结点。
• 动态规划：求解最优解。同分治法类似，只是动态规划保存了之前求得的所有子问题的解，以避免重复的计算。
• 随机化算法：分类有
  • ①数值随机算法：用于数值问题的求解，得到近似解。
  • ②蒙特卡洛算法：计算数学中的一种计算方法，用于求问题的准确解，得到正确的概率以来与时间。
  • ③拉斯维加斯算法：与蒙特卡洛算法相似，但是绝不返回错误的解。
  • ④舍伍德算法：在确定性算法中加入随机性来降低最坏情况出现的概率。

13、域名查询记录

• 域名查询记录先本地DNS缓存，再HOSTS表，然后再查找本地DNS服务器，顶级域名服务器、权限域名服务器。

14、TCP/IP协议栈中协议和层次对应的关系

tcp.png

15、小根堆和大根堆

• 小根堆满足关系：k_i ≤ k_2i 且 k_i ≤ k_2i+1（I=1,2,....,n/2）
• 大根堆满足关系：k_i ≥ k_2i 且 k_i ≥ k_2i+1（I=1,2,....,n/2）