《软件设计师笔记最终版.docx》由会员分享，可在线阅读，更多相关《软件设计师笔记最终版.docx（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、作者序言为什么要分享软设笔记？一直以来，我都认为人类世界最美好的事情莫过于用一个生命去影响另一个生命（前提是正面影响）。如果我的一点点努力，能够帮助你通过软考，我想，这将是很有意义的一件事情。考软设的人很多，我作为过来人，希望能够给予你们一些帮助。为什么要写序言？每一位读者，都不是我本人。看这本笔记，未必知道如何去看，所以我写下想说的话，希望你们在看笔记的过程中，少走弯路。软设，我付出了许多的心血，虽然不至于头悬梁锥刺股，但也是为其折腾了许多日子，至少，是送了好多钱这一路走来，有很多感想，写在这里，也算是将其作为一个树洞吧。软考难吗？相信许多初次考软设的人都喜欢问老司机这个问题，其实没有人能给
2、你正确答案，除了你自己。对于一般人来说，上清华北大难吗？当然难，但是当中不乏NB之人，能够轻易过线，对他们来说就是so easy。所以，难与不难，取决与你的实力。为什么要考软考？软考的中级证书是能够拿来直接评职称的（听说），也许你不知道什么是职称，其实我也不知道感觉好像是蛮有用的东西，自行百度吧。我只是个学生，大学时间相对工作而言还是比较多的，考考证，也不是什么坏事。而且，努力久了，软设不仅仅是一门专业证书的考试，更是我的信仰。对于求职，听说没什么大用，毕竟，计算机的发展大家也都知道，技术是第一位的。但是软设证书，如果人家有，你没有，我想这感觉应该不会太好。对于经济，考一次140RMB（浙江省
3、价格）。曾经有人在群里收购软设挂证，开价3000元，对于学生的我，还是蛮开心的。这个笔记与软件设计师教程的区别先说说这个笔记的由来吧。人脑毕竟存储空间有限，且极易遗忘。所以我把重要的知识点都会记下来，反复看。有本软件设计师教程（以下简称教程），他写的非常详细。如果要买，我建议去某鱼看看，正版太贵了，个人建议阿，如果你钱多，或者坚决支持正版，当我没说。 我与这本书的主要区别在于精。教程一共700页，共计100万汉字，写得非常非常详细，但是一般人都看不了多少页，枯燥难懂。而我的笔记，根据多套试卷的考点考频来综合考虑，记录了高频的一些知识点。且用最简单易懂的语言来解释，有必要的话，我也配上了练习题与
4、解析总共才2万汉字，几乎都是高频考点，如果我的笔记写的不够详细，可以再去看对应教程中的知识点。复习软设的注意事项第一点，建议你们买一本软件设计师同步辅导，这本书是比较简短的知识点，详细度不如教程，但是他不仅仅是按章节分类，更是具备了课后习题与解析。虽然不得不说，解析不咋滴。第二点，千万不要以为得到了这本笔记就和得到了九阴真经一样，这本书，最适合的读者是谁？是我！他针对的是我的弱点，每个知识点都是一针见血。对于读者，我写的知识点未必是你不会的，没写的知识点未必是你会的。只能说，最适合的读者是我。所以，我建议大家只是把这本笔记当作一个小小的参考资料，根据自己的做题经验，去写本专属自己的笔记。第三点
5、，不用去搜什么模拟卷，真题多的是。网上都有，另外，不要做年份太早的，我最初是从06年开始做的，知识点差的太多了。建议大家刷2010年之后的题。第四点，虽然我是计算机专业，但是我的office功底确实渣的一批，所以排版也是非常糟糕的，只会用标题一，标题二，标题三来区分知识点的从属关系。我以个人的理解，将众多的知识分成了多个章节，数据结构、软件工程、多媒体等。所以可能分的不太科学，只是根据自己的理解而已。但是没关系，考试不会考你某个知识点是属于哪个章节的，你会做就可以。这本笔记的最佳使用方法是打开word的导航窗体，根据章节去看。明天，也很美好明天，就是2016年下半年的软设开考之日。没错，作为这
6、本笔记的书写者，自己都还没通过软设我程序员考了2次才过，软设，这是第2次考，希望能过吧。但是讲实话，若是没过，我也不会特别难过，放平心态吧，尽人事听天命。只能说技不如人，不能怨天尤人。拥有一个良好的心态，我觉得比拥有所谓的证书更重要。留个QQ吧，我也不知道留了有啥用，出版社也不会来找我，我就是想留一个948832626.如果学习的过程中有疑问的，还是别+我QQ了，我考完就忘了，回答不了你。我留QQ纯粹就是觉得应该有一个自己的标识，就是这样希望这本笔记，能让你们早日成为软件设计师！2016年11月11日数据结构邻接矩阵无向图无向图邻接矩阵：其邻接矩阵第i行元素的和即为顶点i的度,例如：顶点4的度
7、就是第四行的和，即2。有向图其邻接矩阵的第i行元素之和为顶点i的出度，而邻接矩阵的第j列元素之和为顶点j的入度。例如：顶点3的出度和入度分别为5和16.存储结构顺序存储结构用一组地址连续的存储单元依次存储线性表的各个数据元素, 适用于频繁查询时使用。链式存储结构在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)，适用于在较频繁地插入、删除、更新元素时使用。单链表循环链表双链表各链表的比较因为双链表有两个指针域，因此，双链表的灵活度优于单链表，但是双链表的开支要大一些散列存储结构将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即键值对。索
8、引存储结构索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。比如数据库树二叉排序树若它的左子树非空，则左子树上所有节点的值均小于它的根节点的值若它的右子树非空，则右子树上所有结点的值均大于等于它的根节点的值它的左、右子树也分别为二叉排序树。查找的时候，中序遍历二叉树，得到一个递增序列关键字最大的结点可以有左子树，但一定没有右子树哈夫曼树(最优二叉树)定义是带权路径(WPL)最短的树，权值越大的叶子节点越靠近根节点。构造哈夫曼树及WPL计算例题已知一个文件中出现的各字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符
9、的码长应为（）。若采用Huffman编码，则字符序列“face”的编码应为（）。A2B3C4D5A110001001101B001110110011C101000010100D010111101011解析：所谓定长编码是指用多少位二进制足够表示字符，图中字符是有6个的，a、b、c、d、e、f，可用000到101表示a到f，这样编码字符的码长可以为3，4位当然也是可以，但我们是找最合适的，自然3位能满足要求。第二问，哈夫曼树的左节点未必要比右节点小，但是通常做题时需要写成左小右大的形式，再左0右1赋值，所谓“face”编码，是指找到这4个字母，从根节点出发，要经历的编码数。如下图所示，所以答案为
10、BA平衡二叉树平衡二叉树（Baland Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。满二叉树除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或0个子节点的二叉树。查找方法二分查找法(折半查找法)适用情况不经常变动而查找频繁的有序列表优点1、比较次数少2、查找速度快3、平均性能好缺点1、要求待查表为有序表2、插入删除困难实现算法首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两
11、个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。分块查找适用情况节点动态变化的情况优点比顺序查找算法（就是一个一个的去比较）快得多缺点速度不如折半查找法实现算法把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值
12、，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。平均查找长度(E(n)假设某个线性表中共有n个节点，分成大小相等的b块，每块有s=n/b,则排序直接插入排序每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成,比如斗地主抽牌就是这样的规则。简单选择排序每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。冒泡排序两两比
13、较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。希尔排序把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。快速排序通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。采用了分治法的算法策略。堆排序堆排序中堆的定义：n个元素的序列k1，k2，kn当且仅当满足下列关系时，称为堆。kik2i
14、kik2i+1或kik2ikik2i+1i=1,2,n2归并排序将待排序序列R0.n-1看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。基数排序基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。设有一个初始序列为: R 50, 123, 543, 187, 49, 30, 0, 2, 11, 100。我们知道，任何一个阿拉伯数，它的各个位数上的基
15、数都是以09来表示的。所以我们不妨把09视为10个桶。 我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R0 = 50，个位数上是0，将这个数存入编号为0的桶中。分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。 按照个位数排序： 50, 30, 0, 100, 11, 2, 123, 543, 187, 49。排序的比较排序方法最好时间复杂度平均时间复杂度最坏时间复杂度辅助空间稳定性直接插入O(n)O(n2)O(n2)O(1)稳定简单选择O(n2)O(n2)O(n2)O(1)不稳定冒泡排序O(n)O
16、(n2)O(n2)O(1)稳定希尔排序不存在O(n1.3)不存在O(1)不稳定快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d(n+rd)O(d(n+rd)O(d(n+rd)O(rd)稳定例题堆是一种数据结构，(34)是堆排序A(10， 50， 80， 30， 60， 20， 15， 18)B(10，18，15，20，50，80，30，60)C(10，15，18，50，80，30，60，20)D(10，30
17、，60，20，15，18，50，80)根据定义可知选B广义表广义表的长度是将最外面那层的括号删了以后所剩下的元素(组)个数，深度是括号的层数例题L1=(a,(a,b),(a,b),c)，L2=(1，2，3)，L3=(1，2，3)。求L1、L2、L3的长度和深度答案：长度深度L114L212L331归并排序的归并路数归并路数 =|logkm|，其中m为元素个数，k为多路归并趟数例题若对27个元素只进行三趟多路归并排序，则选取的归并路数为 (37) 。A2 B3 C4 D5根据公式可得log以3为底，以27为真数的答案为3。所以选B表达式的记法前缀表达式（前缀记法、波兰式）从右至左扫描表达式，遇到
18、数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。例如前缀表达式“- + 3 4 5 6”：(1) 从右至左扫描，将6、5、4、3压入堆栈；(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；(3) 接下来是运算符，因此弹出7和5，计算出75=35，将35入栈；(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。中缀表达式我们平常用的表达式a+b-c这样的就是中缀
19、表达式后缀表达式（后缀记法、逆波兰式）从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。例如后缀表达式“3 4 + 5 6 -”：(1) 从左至右扫描，将3和4压入堆栈；(2) 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；(3) 将5入栈；(4) 接下来是运算符，因此弹出5和7，计算出75=35，将35入栈；(5) 将6入栈；(6) 最后是-运算符，计算出3
20、5-6的值，即29，由此得出最终结果。系统基础符号数原码正数的原码等于自身的二进制数，负数的原码第一位为1(符号位，表示负数)，后面为自身的二进制数反码正数的反码等于自身的二进制数，负数的反码符号位不动，其余各位按位取反补码正数的补码等于自身的二进制数，负数的补码是在反码的基础上+1移码(增码)无论正负数，只要将其补码的符号位取反即可符号数的应用在计算机中，最适合数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码。定点数所谓定点数，就是小数点的位置固定不变的数。小数点的位置通常有两种约定形式：定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值
21、位之前）。机器字长为n时各种码制表示的带符号数的范围码制定点整数定点小数原码-(2n-1-1),2n-1-1-(1-2-(n-1),1-2-(n-1)反码-(2n-1-1),2n-1-1-(1-2-(n-1),1-2-(n-1)补码-2n-1,2n-1-1-1,1-2-(n-1)移码-2n-1,2n-1-1-1,1-2-(n-1)记忆技巧当A=2n-1，B=1-2-(n-1)时，则有以下规律码制定点整数定点小数原码-(A-1),A-1-B,B反码-(A-1),A-1-B,B补码-A,A-1-1,B移码-A,A-1-1,B计算机指令系统立即寻址 ：操作数包含在指令中，获取操作数是最快的直接寻址
22、：操作数的地址在指令中寄存器寻址 ：操作数在寄存器中寄存器间接寻址：操作数的地址在寄存器中中央处理器CPU的组成运算器、控制器、寄存器和内部总线，其中控制器不仅要保证程序的正确执行，而且要能够处理异常事件。存储系统存储器的分类按位置分类内存（主存）、外存（辅存）按材料分类磁存储器、半导体存储器、光存储器按工作方式分类读写存储器、只读存储器按访问方式分类按地址访问的存储器、按内容访问的存储器（相联存储器）按寻址方式分类随机存储器、顺序存储器、直接存储器软件测试测试阶段划分单元测试（模块测试）一般是在编程阶段完成，由程序员对自己编写的模块自行测试，检查模块是否实现了详细设计说明书中规定的功能和算法
23、，通常使用白盒测试。单元测试计划应该在详细设计阶段制定。单元测试期间着重从：模块接口、局部数据结构、重要的执行通路、出错处理、边界条件这几个方面对模块进行测试。集成测试（组装测试）主要目标是发现模块间的接口和通信问题。集成测试主要发现概要设计阶段产生的错误，通常采用黑盒测试。集成测试计划应该在概要设计阶段制定。集成的方式可分为非增殖式和增殖式。确认测试检查软件的功能、性能和其他特征是否与用户的需求一致。它是以需求规格说明书作为依据的测试，通常采用黑盒测试。软件确认测试首先要进行有效性测试以及软件配置审查，然后进行验收测试。确认测试一般有以下三个步骤：（1） 有效性测试（2） 软件配置审查（3）
24、 验收测试测试与测试（当一个软件是作为产品被许多客户使用时需要用这种测试）系统测试系统测试的任务是把软件放在实际的硬件和网络环境中进行测试，主要测试软件的非功能需求和质量属性是否得到满足。系统测试是根据系统方案说明书来设计测试用例，通常采用黑盒测试。常见的系统测试有：恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试。在已确认的计算机软硬件环境下，通过与系统需求对比，发现系统与用户需求不符或矛盾的地方。回归测试在软件发生变更后进行的测试，以发现变更时引起的其他错误白盒测试语句覆盖使被测程序中的每条语句至少执行一次判定覆盖（分支覆盖）使被测程序中的每个判定表达式至少获得一次“真”值和
25、“假”值条件覆盖使被测程序中的每个逻辑条件的各种可能的值至少满足一次判定/条件覆盖使得判定中的每个条件的“真”值和“假”值至少出现一次，并使本身判定结果的“真”值和“假”值至少出现一次条件组合覆盖使得每个判定中条件的各种可能值的组合都至少出现一次。满足条件组合覆盖的测试用例是一定满足判定覆盖、条件覆盖和判定/条件覆盖的路径覆盖覆盖被测试程序中所有可能的路径面向对象测试以下四个层次由低到高的顺序排列(1)测试与对象关联的单个操作，即算法层。(2)测试单个对象类，类层。(3)测试对象集群，模板层(4)测试面向对象系统，系统层。编译原理校验码奇偶校验通常用于对少量数据的校验奇校验将信息数据的各位进行
26、模二加法并作为校验码的称为奇校验。偶校验将信息数据的各位进行模二加法并取反作为校验码的称为偶校验。海明码采用多位校验码的方式，可以发现、纠正错误。数据位和校验位必须满足关系式：2校验位-1数据位+校验位。码距至少是3。循环冗余校验码检错能力非常强，但是不能纠错。编码长度(CRC字长)为数据位+校验位文法终结符和非终结符文法格式通常为：，若字符为大写字母，则是非终结符，若字符为小写字母，则是终结符文法的分类0型文法(短语文法)设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT)*且至少含有一个非终结符，而(VNVT)*，则G是 一个0型文法。一个非常重要的理论结果是：0型
27、文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。1型文法(上下文有关文法)此文法对应于线性有界自动机。它是在0型文法的基础上每一个,都有|=|。这里的|表示的是的长度。注意：虽然要求|=|，但有一特例：也满足1型文法。 如有A-Ba则|=2,|=1符合1型文法要求。反之,如aA-a，则不符合1型文法。2型文法(上下文无关文法)此文法对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个都有是非终结符。如A-Ba,符合2型文法要求。大多数程
28、序设计语言的语法规则可以用上下文无关文法描述如Ab-Bab虽然符合1型文法要求,但不符合2型文法要求，因为其=Ab，而Ab不是一个非终结符。3型文法(正规文法)此文法对应于有限状态自动机。它是在2型文法的基础上满足:A|B（右线性）或A|B（左线性）。如有：A-a,A-aB,B-a,B-cB，则符合3型文法的要求。但如果推导 为:A-ab,A-aB,B-a,B-cB或推导 为:A-a,A-Ba,B-a,B-cB则不符合3型方法的要求了。具体的说，例子 A-ab,A-aB,B-a,B-cB中的A-ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结 符一个终结符”的形式（即为aB）就对了
29、。例子A-a,A-Ba,B-a,B-cB中如果把B-cB改为 B-Bc的形式就对了,因为A|B（右线性）和A|B（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算 3型文法。数据流图(Data Flow Diagram，DFD)在面向数据流的设计方法中，一般把数据流图中的数据流划分为两种类型，一种是变换流，一种是事务流。DFD由数据流、加工、数据存储和外部实体4个要素构成。编译过程词法分析从左到右逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字、标识符、常数、运算符和分隔符等。语法分析根据语言的语法规则将单词符号序列分解成
30、各类语法单位，比如表达式、语句和程序等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。语义分析检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如：整除取余运算只能对整型数据进行运算，若其运算对象中有浮点数就认为是类型不匹配的错误。静态的语义错误是指编译程序可以发现，动态的语义错误是指源程序虽然能够被编译和执行，但是结果不对，一般是逻辑上的错误。进程进程的
31、三态图进程的五态图PV操作进入临界区时执行P操作（申请），退出临界区时执行V操作（释放）操作系统内存编址已知主存容量为16MB,且按,求该主存地址至少需要多少位当的内容为“字节编址”时字节编址就是8位的意思,所以16MB=(16*1024)KB=(16*1024*1024)byte=24*210*210=224 byte.所以需要24位当的内容为“4位编址”时先将编址方式凑成8位，即2*4位，相应的主存容量也扩充2倍为32MB，所以32MB=(32*1024)KB=(32*1024*1024)byte=25*210*210=225byte.所以需要25位例题若内存按字节编址，用存储容量为32K
32、8比特的存储器芯片构成地址编号 A0000HDFFFFH的内存空间，则至少需要_片。1、A4 B6 C8 D10空间大小为DFFFF-A0000+1=262144byte=256kb。组成内存储器的芯片数量=内存储器的容量/单个芯片的容量=(256kb*8b)/(32k*8b)=8，所以选C指令运行参数设定变量T为指令运行总时间，t为所需时间最长部分指令的时间（周期），n为指令条数指令相关公式顺序方式运行指令所需时间：T*n流水方式运行指令所需时间：T+(n-1)t 重叠方式运行指令所需时间：（n+2）*t 吞吐率：n/流水方式运行指令所需时间效率：效率=吞吐率*t加速比：加速比=效率*n例题
33、若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别是2ns,2ns,1ns，则100条指令全部执行完毕所需的时间是多少ns答：因为指令运行时间=T+(n-1)t，所以(2+2+1)+(100-1)*2=203。注意，若选择题中没有相应的选择，则将每段指令所需时间均设置为最长时间，就本题而言，应该是2ns,2ns,2ns。(因为目前对于指令运行时间的算法没有统一) 若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指=5t，分析时间t分析=2t，执行时间t执行=5t。如果按顺序方式从头到尾执行完500条指令需_t。如果按照执行 k、分析 k+1、取指 k+2重叠的流
34、水线方式执行指令，从头到尾执行完500条指令需_t。4、A5590 B5595 C6000 D60075、A2492 B2500 C2510 D2515第一个空符合顺序方式，则时间为T*n=12*500=6000，第二个空符合重叠的流水线方式，则时间为（n+2）*t=(500+2)*5=2510，所以选C，C某指令流水线由5段组成，各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为_。6、A10/70t B10/49t C10/35t D10/30t吞吐率= n/ T+(n-1)t=10/(1+3+1+2+1)+9*3)= 10/35t，所以选C内存管理分配方案的比较分配办法单一连续分
35、配固定分区分配可变分区分配分配类型静态分配法静态分配法动态分配法分配特点不分区，所有用户空间给某个进程或作业分成大小不等的区域，区域分完后固定不变分成大小不等的区域，根据用户要求动态分配可变分区分配算法首次适应法从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区，这种方法可实现快速分配，缩短查找时间。循环适应法是首次适应法的一个变种，也就是不再是每次都从头开始匹配，而是连续向下匹配。最佳适应法选择最接近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。最差适应法选择整个主存中最大的内存自由区。虚存管理页式存储题目往往是给出下图求物理地
36、址，首先，我们知道所谓的逻辑地址是页号+页内地址，页内地址=页面大小位数。具体的做法是：将逻辑地址转换为二进制，从右边开始数页内地址位数，剩下的左边二进制即为页号。根据图片找到对应的块号，则物理地址为块号(二进制)+页内地址。例题段式存储不同管理方式之间的优缺点优点缺点段式存储便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响内存利用率低，内存碎片浪费大页式存储利用率高，产生的内存碎片小，内存间分配及管理简单要有相应的硬件支持，增加了系统开销，请求调页的算法如选择不当，有可能产生抖动现象段页式存储空间浪费小，存储共享容易、存储保护容易、能动态连接由于管理软件的增加，复杂性和开销也随
37、之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降页面置换算法最优置换算法后续页面最先被访问的页面保留，淘汰那些很久才会被使用的页面先进先出算法优先淘汰最先进入的页面最近最少使用算法优先淘汰存在最久的页面局部性原理时间局部性一个页面被访问后，很有可能再次被访问空间局部性一个页面被访问后，很有可能访问其周围的页面作业管理作业时间作业周转时间T=作业完成时间-作业提交时间T=作业等待时间+作业运行时间作业平均周转时间T平均=（T1+T2+Tn）/n带权作业周转时间单个作业带权周转时间W=作业周转时间/作业实际运行时间作业平均带权周转时间W=（W1+W2+Wn）/n作业调度算法先来先服
38、务按作业序号依次运行最短作业优先优先运行所需运行时间最短的作业优先数优先级高优先运行定时轮转规定一个时间片大小，作业按序号依次运行，每次运行时间与时间片大小等同，到期后继续运行下一个时间片长度的任务，重复步骤。Cache（高速缓存）Cache的读写过程写直达当要写Cache时，数据同时写回主存写回当相应数据从Cache中被淘汰时写回主存标识法取数据时添加一个有效位为1，当修改主存数据后设置有效位为0.地址映像直接映像主存与Cache的映像主存的每一页与Cache的每一页相同大小，因为主存比Cache大得多，所以尽管每一页相等，主存的总页数远大于Cache的总页数。因此，根据Cache的页数大小
39、，主存将相同分为多个组，每个组的页数与Cache总页数相等，其中的每一页正好配对。编号不一致的页是不能相互映像的。优缺点优点：地址变换简单。缺点：每块相互对应，不够灵活。主存与Cache的地址组成主存：区号+块号+块内地址Cache：块号+块内地址示意图全相联映像主存与Cache的映像将主存与Cache划分成若干个大小相等的块，主存中每一块都可以调到Cache中的每一块。特点优点：访问灵活，冲突率低，只有Cache满时才会出现在冲突。缺点：地址变换比较复杂，速度相对慢。主存与Cache的地址组成主存：块号+块内地址Cache：块号+块内地址示意图组相联映像主存与Cache的划分主存：主存根据C
40、ache大小划分成若干个区，每个区内划分成若干个组，每个组再划分成若干个块。Cache：划分成若干个组，每个组划分成若干个块。主存与Cache的映像主存的每个分区与Cache采用直接映像，主存的每个组之内采用全相联映像。特点融合了直接映像与全相联映像两种映像方式，结合了两者的优据点。具体实现容易，命中率与全相联映像接近。主存与Cache的地址组成主存：区号+组号+块号+块内地址Cache：组号+块号+块内地址示意图块冲突次数比较发生块冲突次数从大到小排序为：直接映像组相联映像全相联映像例题某 32 位计算机的 cache 容量为 16KB，cache 块的大小为 16B，若主存与 cache
41、的地址映射采用直接映射方式，则主存地址为 1234E8F8（十六进制）的单元装入的 cache 地址为_。A. 00 0100 0100 1101 (二进制)B. 01 0010 0011 0100 (二进制)C. 10 1000 1111 1000 (二进制)D. 11 0100 1110 1000 (二进制)cache的容量为16KB，块大小为16B，因此一共有16KB/16B=1024个页，所以需要10位来存储（210=1024）。块所需要的存储地址位数为4位（24=16）。因为采用的是直接映射方式，所以主存与cache的地址关系为：主存：区号+块号+块内地址Cache：块号+块内地址所
42、以，cache地址一共是14位，将主存地址转换为二进制后最后14位就是Cache地址了，选C “Cache+主存储器”系统的平均周期若t1为Cache的周期时间，t2为主存储器周期时间，h为Cache的访问命中率，则系统的平均周期为h*t1+(1-h)*t2命中率Cache由两部分组成：控制部分和Cache存储器部分。控制部分的功能是判断CPU要访问的信息是否在Cache存储器中，若在即为命中，若不在则没有命中。命中时直接对Cache存储器寻址；未命中时，要按照替换原则决定主存的一块信息放到Cache存储器的哪一块里。Cache命中率=（平均存取时间-主存存取时间）/（高速缓存存取时间-主存存
43、取时间）例题高速缓存cache与主存间采用全相联地址映像方式，高速缓存的容量为4MB，分为 4块，每块1MB，主存容量为256MB。 若主存读写时间为30ns，高速缓存的读写时间为3ns，平均读写时间为3.27ns，则该高速缓存的命中率为_由公式可得命中率为99%总线系统的数据传送速率计算公式公式Q=W*F/N，其中Q为总线数据传输率，W为总线数据宽度(总线位宽/8)，F为总线工作频率，N为完成一次数据传送所需的总线时钟周期个数。例题若总线位宽为16位，总线工作频率为8MHZ，完成一次数据传送需2个总线时钟周期，则总线的数据传输速率为多少？Q的计算公式为：(16/8)*8M)/2=8MB/s中
44、断响应时间从发出中断请求到进入中断处理所用的时间系统的可靠性设p1,p2为2个部件的可靠度串联与并联系统若为并联，则可靠度=1-(1-p1)(1-p2)若为串联，则可靠度=p1p2N模冗余系统N模冗余系统是当有一定量的部件做出相同的处理结果时，则输出该结果，概念太复杂，懒得写了，直接举例子吧，如上图所示，若该3个部件中有2个部件正常运行，则输出结果，因此要计算2个部件的情况和3个部件的情况，计算公式如下，其中N为总部件数，i为当前计算的正常运行的部件数，R为可靠性。平均无故障时间（MTBF）MTBF=1/，为失效率例题 三个可靠度R均为0.8的部件串联构成一个系统，如下图所示： 则该系统的可靠度为 _由串联公式可得：0.80.80.8=0.512同理，当R为0.5时可计算出可靠性为0.5，所以选择BA若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为10-7/H，在不考虑其他因素对可靠性的影响时，该计算机系统的平均故障间隔时间为_小时。根据公式可得MTBF=1/5*10-5=2*104缓冲区单缓冲区花费的时间=(读缓冲时间+传送用户时间)*磁盘块+每个磁盘处理时间双缓冲区花费的时间=读缓冲时间*磁盘块+传送用户时间+每个磁盘处理时间 软