《软件设计师》重点笔记.pdf

《《软件设计师》重点笔记.pdf》由会员分享，可在线阅读，更多相关《《软件设计师》重点笔记.pdf（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作者序言为什么要分享软设笔记?一直以来，我都认为人类世界最美好的事情莫过于用一个生命去影响另一个生命（前提是正面影响）。如果我的一点点努力，能够帮助你通过软考，我想，这将是很有意义的一件事情。考软设的人很多，我作为过来人，希望能够给予你们一些帮助。为什么要写序言?每一位读者，都不是我本人。看这本笔记，未必知道如何去看，所以我写下想说的话,希望你们在看笔记的过程中，少走弯路。软设，我付出了许多的心血，虽然不至于头悬梁锥刺股，但也是为其折腾了许多日子,至少，是送了好多钱 这一路走来，有很多感想，写在这里，也算是将其作为一个树洞吧。软考难吗?相信许多初次考软设的人都喜欢问老司机这个问题，其实没有人能

2、给你正确答案，除了你自己。对于一般人来说，上清华北大难吗？当然难，但是当中不乏NB之人，能够轻易过线，对他们来说就是so easy。所以，难与不难，取决与你的实力。为什么要考软考?软考的中级证书是能够拿来直接评职称的（听说），也许你不知道什么是职称，其实我也不知道感觉好像是蛮有用的东西，自行百度吧。我只是个学生，大学时间相对工作而言还是比较多的，考考证，也不是什么坏事。而且，努力久了，软设不仅仅是一门专业证书的考试，更是我的信仰。对于求职，听说没什么大用，毕竟，计算机的发展大家也都知道，技术是第一位的。但是软设证书，如果人家有，你没有，我想这感觉应该不会太好。对于经济，考一次140RMB（浙江

3、省价格）。曾经有人在群里收购软设挂证，开价3000元，对于学生的我，还是蛮开心的。这个笔记与 软件设计师教程的区别先说说这个笔记的由来吧。人脑毕竟存储空间有限，且极易遗忘。所以我把重要的知识点都会记下来，反复看。有 本 软件设计师教程（以下简称教程），他写的非常详细。如果要买，我建议去某鱼看看，正版太贵了，个人建议阿，如果你钱多，或者坚决支持正版，当我没说。我与这本书的主要区别在于精。教程一共700页，共 计 100万汉字，写得非常非常详细，但是一般人都看不了多少页，枯燥难懂。而我的笔记，根据多套试卷的考点考频来综合考虑，记录了高频的一些知识点。且用最简单易懂的语言来解释，有必要的话，我也配上

4、了练习题与解析总共才2 万汉字，几乎都是高频考点，如果我的笔记写的不够详细，可以再去看对应教程中的知识点。复习软设的注意事项第一点，建议你们买一本 软件设计师同步辅导，这本书是比较简短的知识点，详细度不如教程，但是他不仅仅是按章节分类，更是具备了课后习题与解析。虽然不得不说，解析不咋滴。第二点，千万不要以为得到了这本笔记就和得到了 九阴真经一样，这本书，最适合的读者是谁？是我！他针对的是我的弱点，每个知识点都是一针见血。对于读者，我写的知识点未必是你不会的，没写的知识点未必是你会的。只能说，最适合的读者是我。所以，我建议大家只是把这本笔记当作一个小小的参考资料，根据自己的做题经验，去写本专属自

5、己的笔记。第三点，不用去搜什么模拟卷，真题多的是。网上都有，另外，不要做年份太早的，我最初是从06年开始做的，知识点差的太多了 建议大家刷2010年之后的题。第四点，虽然我是计算机专业，但是我的。ffice功底确实渣的一批，所以排版也是非常糟糕的，只会用标题一，标题二，标题三来区分知识点的从属关系。我以个人的理解，将众多的知识分成了多个章节，数据结构、软件工程、多媒体等。所以可能分的不太科学，只是根据自己的理解而己。但是没关系，考试不会考你某个知识点是属于哪个章节的，你会做就可以。这本笔记的最佳使用方法是打开w ord的导航窗体，根据章节去看。标题 页面 结果艮习软设的注意事项 q软件测试编译

6、原理,软件工程/软件生命周期问题定义可行性研究需求分析开发阶段百/统T (U P)简介初启阶段精化阶段构建阶段台 阶 段 Vlr明天，也很美好明天，就是2016年下半年的软设开考之日。没错，作为这本笔记的书写者，自己都还没通过软设我程序员考了 2 次才过，软设，这是第2 次考，希望能过吧。但是讲实话,若是没过，我也不会特别难过，放平心态吧，尽人事听天命。只能说技不如人，不能怨天尤人。拥有一个良好的心态，我觉得比拥有所谓的证书更重要。留个QQ吧，我也不知道留了有啥用，出版社也不会来找我，我就是想留一个948832626.如果学习的过程中有疑问的，还是别+我 QQ 了，我考完就忘了，回答不了你。我

7、 留 Q Q 纯粹就是觉得应该有一个自己的标识，就是这样希望这本笔记，能让你们早日成为软件设计师！2016年 11月 1 1 日数据结构邻接矩阵无向图无向图邻接矩阵：其邻接矩阵第i 行元素的和即为顶点i 的度,例如：顶点4 的度就是第四行的和，即 2。有向图其邻接矩阵的第i 行元素之和为顶点i 的出度，而邻接矩阵的第j 列元素之和为顶点j 的入度。例如：顶点3 的出度和入度分别为5 和 16.H 0 可提金.11千也当为5 电 旭 却 能浓上知必肾在为上的位支向依7、耳画 联因,座利屯有身份2存储结构顺序存储结构用一组地址连续的存储单元依次存储线性表的各个数据元素，适用于频繁查询时使用。入接出

8、最图3-1栈的示意图，链式存储结构在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），适用于在较频繁地插入、删除、更新元素时使用。单链表循环链表数据指针域*双链表各链表的比较因为双链表有两个指针域，因此，双链表的灵活度优于单链表，但是双链表的开支要大一些散列存储结构将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即键值对。bucket array索引存储结构索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。比如数据库ROOT住键索引Col2)树二叉排序树若它的左子树

9、非空，则左子树上所有节点的值均小于它的根节点的值若它的右子树非空，则右子树上所有结点的值均大于等于它的根节点的值它的左、右子树也分别为二叉排序树。查找的时候，中序遍历二叉树，得到一个递增序列关键字最大的结点可以有左子树，但一定没有右子树哈夫曼树(最优二叉树)定义是带权路径(W P L)最短的树，权值越大的叶子节点越靠近根节点。构造哈夫曼树及WPL计算例题已知一个文件中出现的各字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为（）。若采用Huffman编码，则字符序列“face”的编码应为（）。abcdef廨（%）4513121695A.2B.3C.4D.5A.1 1 0 0

10、 0 1 0 0 1 1 0 1B.0 0 1 1 1 0 1 1 0 0 1 1C.1 0 1 0 0 0 0 1 0 1 0 0D.0 1 0 1 1 1 1 0 1 0 1 1解析：所谓定长编码是指用多少位二进制足够表示字符，图中字符是有6个的，a、b、c、d、e、f,可用0 0 0 到 1 0 1 表示a到 f,这样编码字符的码长可以为3,4位当然也是可以,但我们是找最合适的，自 然 3位能满足要求。第二问，哈夫曼树的左节点未必要比右节点小，但是通常做题时需要写成左小右大的形式，再左0右 1 赋值，所 谓“f a c e”编码，是指找到这4个字母，从根节点出发，要经历的编码数。如下图所

11、示，所以答案为B A平衡二叉树平衡二叉树（B a l a n d B i n a r y T r e e）又被称为A V L 树（有别于A V L 算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。满二叉树除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或0个子节点的二叉树。查找方法二分查找法（折半查找法）适用情况不经常变动而查找频繁的有序列表优点1、比较次数少2、查找速度快3、平均性能好缺点1、要求待查表为有序表2、插入删除困难实现算法首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者

12、相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。分块查找适用情况节点动态变化的情况优点比顺序查找算法（就是一个一个的去比较）快得多缺点速度不如折半查找法实现算法把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的 i,第 i 块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还

13、要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。平均查找长度(E(n)假设某个线性表中共有n 个节点，分成大小相等的b 块，每块有s=n/b,则E(n)=Eb+Es二b+l.s+l-d-2 2+1P排序直接插入排序每一-趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成,比如斗地主抽牌就是这样的规则。

14、简单选择排序每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。排序前：9125748635第1趟：1925748635第2趟：1295748635第3趟：1235748695第4趟：1234758695第5趟：1234578695红色粗体表示位置发生变化的元素第6趟：1234558697第7趟：1234556897第8趟:1234556798第9趟：1234556789排序后：1234556789图-简单选择排序示例图Victor Ihang冒泡排序两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。第三遍排序后第二遍

15、排序后第一遍排序后初始状态希尔排序把记录按步长g用分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。初始9125748659125748635I Igap=5第一趟排序-,-1598657T23L4123598657r 4 1gap=2-r第二趟排序12143s 657892143565789gap=1 I I I I I I I I I I第三趟排序-L1234556789图-希尔排序示例图 Zhang快速排序通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的

16、数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。采用了分治法的算法策略。left right牛？left rightleft rightlefts right 第一步：设置两个指针怙咕口 right,分别指向数组的头部(2)和尾部(3)。并且以头部元素(2)为基准数base。第二步：从右至左扫描，通过偏移right指针，寻找比基准数小的元素。我们找到比基准数小的元素,我们将其赋值给left指针所指的位置。第三步：从左向右扫描，通过偏移10ft指针，寻找比基准数大的元素。我们找到比基准数大的元素，我们将其赋值给righ

17、t指针所指向的位置。第四步：不断重复二、三步骤,直到left、right指 针 络。这样，所有的元素都被扫描了一遍。我们将基准数赋给重合位置。此时，已完成了一次排序。基准数的左边都是比它小的数,而右边都是比它大的数。第五步：以基准数(2)为分割点。对其左侧和右侧的数分别按照一、二、三、四步骤去进行排序。经过递归过程，最后排序结束。Victor Zhang堆排序堆排序中堆的定义：n个元素的序列 k i，k 2,，k J当且仅当满足下列关系时，称为堆。层请；1或 /羡:(i=1 2,即归并排序将待排序序列R O.n-l 看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有

18、序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。gap=2gap=4gap=8gap=1基数排序基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。设有一个初始序列为:R 50,123,543,187,49,30,0,2,11,100。我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以09来表示的。所以我 们 不 妨 把09视 为10个 桶。我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R0=5 0,

19、个 位 数 上 是0,将这个数存入编号为0的桶中。05030010011122312354345671878949分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。按照个位数排序：50,30,0,100,11,2,123,543,187,49。排序的比较排序方法最好时间复杂度平均时间复杂度最坏时间复杂度辅助空间稳定性直接插入O(n)O(n2)O(n2)0(1)稳定简单选择O(n2)O(n2)O(n2)。不稳定冒泡排序O(n)O(n2)O(n2)0(1)稳定希尔排序不存在O(n13)不存在。不稳定快速排序O(nlog2

20、n)O(nlog2n)O(n2)O(log2n)不稳定堆排序O(nlog2 n)O(nlog2 n)O(nlog2n)0(1)不稳定归并排序O(nlog2 n)O(nlog2 n)O(nlog2 n)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,C.(10,15,D.(10,30,15,20,50,18,50,80,60,20,15,80,30,60)30,60,20)18,50,80)根据定义可知选B广义表广义表的长度是将最外面那层的括号删了

21、以后所剩下的元素(组)个数，深度是括号的层数例题L l=(a,(a,b),(a,b),c),L 2=(l,2,3),L 3=(l,2,3)。求 L I、L 2、L 3 的长度和深度答案：长度深度L114L212L331归并排序的归并路数归并路数=l o g k m 其中m为元素个数，k为多路归并趟数例题若对2 7 个元素只进行三趟多路归并排序，则选取的归并路数为(3 7)oA.2 B.3 C.4 D.5根据公式可得l o g 以 3为底，以 2 7 为真数的答案为3。所以选B表达式的记法前缀表达式(前缀记法、波兰式)从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数

22、,用运算符对它们做相应的计算(栈顶元素op次顶元素)，并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。例 如 前 缀 表 达 式 X +3 4 5 6”：(1)从右至左扫描，将 6、5、4、3 压入堆栈；(2)遇到+运算符，因此弹出3 和 4 (3 为栈顶元素，4为次顶元素，注意与后缀表达式做比较)，计算出3+4 的值，得 7,再将7 入栈；(3)接下来是X运算符，因此弹出7 和 5,计算出7 义5=3 5,将 3 5 入栈；(4)最后是-运算符，计算出3 5-6 的值，即 2 9,由此得出最终结果。中缀表达式我们平常用的表达式a+b-c这样的就是中缀表达式后缀表

23、达式(后缀记法、逆波兰式)从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素o p栈顶元素)，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。例如后缀表达式“3 4 +5 X 6(1)从左至右扫描，将3和4压入堆栈；(2)遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素，注意与前缀表达式做比较)，计算出3+4的值，得7,再将7入栈；(3)将5入栈;(4)接下来是X运算符，因此弹出5和7,计算出7义5=3 5,将35入栈；(5)将6入栈：(6)最后是-运算符，计算出35-6的值，即2 9,由此

24、得出最终结果。系统基础符号数原码正数的原码等于自身的二进制数，负数的原码第一位为1(符号位，表示负数)，后面为自身的二进制数反码正数的反码等于自身的二进制数，负数的反码符号位不动，其余各位按位取反补码正数的补码等于自身的二进制数，负数的补码是在反码的基础上+1移码(增码)无论正负数，只要将其补码的符号位取反即可符号数的应用在计算机中，最适合数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码。定点数所谓定点数，就是小数点的位置固定不变的数。小数点的位置通常有两种约定形式：定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值位之前）。机器字长为n时

25、各种码制表示的带符号数的范围码制定点整数定点小数原码-(2n-l),2n-1-l1-2(-1)反码_（1_牙 叫 一 牙 补码-2n l,2nH-l-1,1-2-叫移码2-1-1-1,1-2记忆技巧当A=2 B=l-2 时，则有以下规律码制定点整数定点小数原码-(A-1),A-1-B,B反码-(A-D)A-U-B,B补码-A,A-l-1,B移码-A,A-l-1.B计算机指令系统立即寻址：操作数包含在指令中，获取操作数是最快的直接寻址：操作数的地址在指令中寄存器寻址：操作数在寄存器中寄存器间接寻址：操作数的地址在寄存器中中央处理器CPU的组成运算器、控制器、寄存器和内部总线，其中控制器不仅要保证

26、程序的正确执行，而且要能够处理异常事件。存储系统存储器的分类按位置分类内 存（主存）、外 存（辅存）按材料分类磁存储器、半导体存储器、光存储器按工作方式分类读写存储器、只读存储器按访问方式分类按地址访问的存储器、按内容访问的存储器（相联存储器）按寻址方式分类随机存储器、顺序存储器、直接存储器软件测试测试阶段划分单元测试（模块测试）一般是在编程阶段完成，由程序员对自己编写的模块自行测试，检查模块是否实现了详细设计说明书中规定的功能和算法，通常使用白盒测试。单元测试计划应该在详细设计阶段制定。单元测试期间着重从：模块接口、局部数据结构、重要的执行通路、出错处理、边界条件这几个方面对模块进行测试。集

27、成测试（组装测试）主要目标是发现模块间的接口和通信问题。集成测试主要发现概要设计阶段产生的错误，通常采用黑盒测试。集成测试计划应该在概要设计阶段制定。集成的方式可分为非增殖式和增殖式。确认测试检查软件的功能、性能和其他特征是否与用户的需求一致。它是以需求规格说明书作为依据的测试，通常采用黑盒测试。软件确认测试首先要进行有效性测试以及软件配置审查，然后进行验收测试。确认测试一般有以下三个步骤：（1）有效性测试（2）软件配置审查（3）验收测试a测试与B测 试（当一个软件是作为产品被许多客户使用时需要用这种测试）系统测试系统测试的任务是把软件放在实际的硬件和网络环境中进行测试，主要测试软件的非功能需

28、求和质量属性是否得到满足。系统测试是根据系统方案说明书来设计测试用例，通常采用黑盒测试。常见的系统测试有：恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试。在已确认的计算机软硬件环境下，通过与系统需求对比，发现系统与用户需求不符或矛盾的地方。回归测试在软件发生变更后进行的测试，以发现变更时引起的其他错误白盒测试语句覆盖使被测程序中的每条语句至少执行一次判定覆盖（分支覆盖）使被测程序中的每个判定表达式至少获得一次 真 值和 假 值条件覆盖使被测程序中的每个逻辑条件的各种可能的值至少满足一次判定/条件覆盖使得判定中的每个条件的，真 值和，假，值至少出现一次，并使本身判定结果的 真 值

29、和 假值至少出现一次条件组合覆盖使得每个判定中条件的各种可能值的组合都至少出现一次。满足条件组合覆盖的测试用例是一定满足判定覆盖、条件覆盖和判定/条件覆盖的路径覆盖覆盖被测试程序中所有可能的路径面向对象测试以下四个层次由低到高的顺序排列(1)测试与对象关联的单个操作，即算法层。(2)测试单个对象类，类 层。(3)测试对象集群，模板层(4)测试面向对象系统，系统层。编译原理校验码奇偶校验通常用于对少量数据的校验奇校验将信息数据的各位进行模二加法并作为校验码的称为奇校验。偶校验将信息数据的各位进行模二加法并取反作为校验码的称为偶校验。海明码采用多位校验码的方式，可以发现、纠正错误。数据位和校验位必

30、须满足关系式：2 梭 如数据位+校验位。码距至少是3。循环冗余校验码检错能力非常强，但是不能纠错。编码长度(C R C 字长)为数据位+校验位文法终结符和非终结符文法格式通常为：若字符为大写字母，则是非终结符，若字符为小写字母，则是终结符文法的分类0型文法(短语文法)设 6=(V N,V T,P,S),如果它的每个产生式a-B是这样一种结构：a G(V N U V T)*且至少含有一个非终结符，而 B G(V N U V T)*,则 G是 一 个。型文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(T u r i n g)。或者说,任何0型文语言都是递归可枚举的，反之，递归可枚举集必

31、定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。1型文法(上下文有关文法)此文法对应于线性有界自动机。它是在0型文法的基础上每 一 个。一 6,都 有 邛|=|&|。这里的I B|表示的是B的长度。注意：虽然要求|B|=|a 但有一特例：a-e也满足1 型文法。如有A-B a 则 如|=2,|a|=1 符 合 1 型文法要求。反之,如如-a,则不符合1 型文法。2 型文法（上下文无关文法）此文法对应于下推自动机。2型文法是在1 型文法的基础上,再满足：每 一 个 a -B都 有 a是非终结符。如 A-B a,符 合 2型文法要求。大多数程序设计

32、语言的语法规则可以用上下文无关文法描述如 A b-B a b 虽然符合1 型文法要求，但不符合2型文法要求，因为其a =A b,而 A b 不是一个非终结符。3 型文法（正规文法）此文法对应于有限状态自动机。它 是 在 2型文法的基础上满足:A-a a B （右线性）或A-a|B a （左线性）。如 有：A-a,A-a B,B-a,B-c B ,则 符 合 3 型 文 法 的 要 求。但 如 果 推 导为:A-a b,A-a B,B-a,B-c B 或推导 为:A-a,A-B a,B-a,B-c B 则不符合 3 型方法的要求了。具 体 的 说,例 子 A-a b,A-a B,B-a,B-c

33、B 中的A-a b 不符合3型文法的定义，如果把后 面 的 a b,改 成“一 个 非 终 结 符+一 个 终 结 符”的 形 式（即 为 a B）就对了。例子A-a,A-B a,B-a,B-c B 中如果把B-c B 改 为 B-B c 的形式就对了，因为A-a|a B （右线性）和 A-a|B a （左线性）两套规则不能同时出现在一个语法中，只能完全满足其中的一个,才 能 算 3型文法。数据流图（D a t a Fl ow D i a g r a m,D FD）在面向数据流的设计方法中，一般把数据流图中的数据流划分为两种类型，一种是变换流,一种是事务流。D FD 由数据流、加工、数据存储和

34、外部实体4个要素构成。编译过程词法分析从左到右逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字、标识符、常数、运算符和分隔符等。语法分析根据语言的语法规则将单词符号序列分解成各类语法单位，比如表达式、语句和程序等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。语义分析检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的

35、运算。例如：整除取余运算只能对整型数据进行运算，若其运算对象中有浮点数就认为是类型不匹配的错误。静态的语义错误是指编译程序可以发现，动态的语义错误是指源程序虽然能够被编译和执行，但是结果不对，一般是逻辑上的错误。进程进程的三态图就绪状态：进程）得到运行所需资源，只等待CPU的调度便可运行；运行状态：进程上得到运行所需资源，并且得到了CPU的调度；等待状态：不具备运行条件、等待时机的状态。另：等待状态也称阻塞状态。进程的五态图PV操作进入临界区时执行P操作(申请)，退出临界区时执行V操作(释放)操作系统内存编址已知主存容量为1 6M B,且按,求该主存地址至少需要多少位当的内容为“字节编址”时字

36、节编址就是 8 位的意思，所以 1 6M B=(1 6*1 0 24)KB=(1 6*1 0 24*1 0 24)b y t e=2,*2l0*2l0=224 b y t e.所以需要24 位当的内容为“4位编址”时先 将 编 址 方 式 凑 成 8位，即 2*4 位，相 应 的 主 存 容 量 也 扩 充 2 倍 为 32M B,所以32M B=(32*1 0 24)KB=(32*1 0 24*1 0 24)b y t e=25*2w*2l l=225b y t e.所以需要 25 位例题若内存按字节编址，用存储容量为32Kx 8比特的存储器芯片构成地址编号A 0 0 0 0 H-D F F

37、 F F H的内存空间，则至少需要 片。1、A.4 B.6 C.8 D.1 0空间大小为 D F F F F-A 0 0 0 0+l=2621 4 4 b y t e=25 6kb。组成内存储器的芯片数量=内存储器的容量/单个芯片的容量=(25 6kb*8 b)/(32k*8 b)=8,所以选 C指令运行参数设定变量T为指令运行总时间，t 为所需时间最长部分指令的时间(周期)，n 为指令条数指令相关公式顺序方式运行指令所需时间：T*n流水方式运行指令所需时间：T+(n-l)t重叠方式运行指令所需时间：(n+2)*t吞吐率：n/流水方式运行指令所需时间效率：效率=吞吐率*t加速比：加速比二效率*

38、n例题若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别是2ns,2ns,1 ns,则 1 0 0 条指令全部执行完毕所需的时间是多少ns答:因为指令运行时间=T+(nT)t,所以(2+2指令(1 行肘)*2=20 3。注意,若选择题中没有相应的选择，则将每段指令所需时间均设置为最长时间，就本题而言，应 该 是 2ns,2ns,2ns。(因为目前对于指令运行时间的算法没有统一)若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t 取指=5 At,分析时 间 t分析=2 At,执行时间t执行=5 A t。如果按顺序方式从头到尾执行完5 0 0 条指令需A t。如果按照

39、执行k、分 析 k+1、取指k+2重叠的流水线方式执行指令，从头到尾执行完5 0 0 条 指 令 需 t 4、A.5 5 90 B.5 5 95 C.60 0 0 D.60 0 75、A.24 92 B.25 0 0 C.25 1 0 D.25 1 5第一个空符合顺序方式，则时间为T*n=l2*5 0 0=60 0 0,第二个空符合重叠的流水线方式，则时 间 为(n+2)*t=(5 0 0+2)*5=25 1 0,所以选 C,C某指令流水线由5段组成，各段所需要的时间如下图所示。连续输入1 0 条指令时的吞吐率 为 _。6、A.1 0/7 0 A t B.1 0/4 9 A t C.1 0/3

40、5 A t D.1 0/30 A t吞吐率=n/T+(n-1)t=1 0/(1+3+1+2+1)+9*3)=1 0/35 At,所以选 C内存管理分配方案的比较分配办法单一连续分配固定分区分配可变分区分配分配类型静态分配法静态分配法动态分配法分配特点不分区，所有用户空间给某个进程或作业分成大小不等的区域，区域分完后固定不变分成大小不等的区域，根据用户要求动态分配可变分区分配算法首次适应法从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区，这种方法可实现快速分配，缩短查找时间。循环适应法是首次适应法的一个变种，也就是不再是每次都从头开始匹配，而是连续向下匹配。最佳适应法选择最接

41、近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。最差适应法选择整个主存中最大的内存自由区。虚存管理页式存储题目往往是给出下图求物理地址，首先，我们知道所谓的逻辑地址是页号+页内地址，页内地址=页面大小位数。具体的做法是：将逻辑地址转换为二进制，从右边开始数页内地址位数，剩下的左边二进制即为页号、根据图片找到对应的块号，则物理地址为块号（二进制）+页内地址。例题页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4 K,地址变换过程如下图所示，图中逻辑地址用十进制表示。图中有效地址经过变换后，十进制物理地址a应为 o供选择的答案A.3

42、3220 B.8644 C.4548 D.2500此题考查的是虚拟存储中的页式存储，题目已知页面大小为4 K,因为4K=212所以页内地址有12位。现在把逻辑地址8644转成二进制，W10 000T1100 0100,其中的低12位为页内偏移量，最高两位则为页号，所以逻辑地址8644的页号为1 0,即十进制的2,所以物理块号为8,化为二进制得1000。把物理块号和页内偏移地址拼合得1000 00011100 0100,化为十进制得33220。所以正确答案是A。段式存储考点二：存储一虚存管理2.段式存储组织段号段内地址31作业空阿16 15内存空间080K(MAIN)-O30K(X尸I20KT1

43、20K15K(S)=310K150K 不同管理方式之间的优缺点优点缺点段式存储便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响内存利用率低，内存碎片浪费大页式存储利用率高，产生的内存碎片小，内存间分配及管理简单要有相应的硬件支持，增加了系统开销，请求调页的算法如选择不当，有可能产生抖动现象段页式存储空间浪费小，存储共享容易、由于管理软件的增加，复杂存储保护容易、能动态连接性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降页面置换算法最优置换算法后续页面最先被访问的页面保留，淘汰那些很久才会被使用的页面先进先出算法优先淘汰最先进入的页面最近最少使用算法优先

44、淘汰存在最久的页面局部性原理时间局部性一个页面被访问后，很有可能再次被访问空间局部性一个页面被访问后，很有可能访问其周围的页面作业管理作业时间作业周转时间丁=作业完成时间-作业提交时间T=作业等待时间+作业运行时间作业平均周转时间T 平均=(T1+T2+.Tn)/n带权作业周转时间单个作业带权周转时间W=作业周转时间/作业实际运行时间作业平均带权周转时间W=(W1+W2+.+Wn)/n作业调度算法先来先服务按作业序号依次运行最短作业优先优先运行所需运行时间最短的作业优先数优先级高优先运行定时轮转规定一个时间片大小，作业按序号依次运行，每次运行时间与时间片大小等同，到期后继续运行下一个时间片长度

45、的任务，重复步骤。Cache（高速缓存）Cache的读写过程写直达当要写Cache时，数据同时写回主存写回当相应数据从Cache中被淘汰时写回主存标识法取数据时添加一个有效位为1,当修改主存数据后设置有效位为0.地址映像直接映像主存与Cache的映像主存的每一页与Cache的每一页相同大小，因为主存比Cache大得多，所以尽管每一页相等，主存的总页数远大于Cache的总页数。因此，根据Cache的页数大小，主存将相同分为多个组，每个组的页数与Cache总页数相等，其中的每一页正好配对。编号不一致的页是不能相互映像的。优缺点优点：地址变换简单。缺点：每块相互对应，不够灵活。主存与Cache的地址

46、组成主存：区号+块号+块内地址Cache：块号+块内地址示意图主存全相联映像主存与Cache的映像将主存与Cache划分成若干个大小相等的块，主存中每一块都可以调到Cache中的每一块。特点优点：访问灵活，冲突率低，只有Cache满时才会出现在冲突。缺点：地址变换比较复杂,速度相对慢。主存与C a c h e 的地址组成主存：块号+块内地址C a c h e：块号+块内地址示意图主存组相联映像主存与C a c h e 的划分主存：主存根据Cache大小划分成若干个区，每个区内划分成若干个组，每个组再划分成若干个块。Cache：划分成若干个组，每个组划分成若干个块。主存与C a c h e 的映

47、像主存的每个分区与Cache采用直接映像，主存的每个组之内采用全相联映像。特点融合了直接映像与全相联映像两种映像方式，结合了两者的优据点。具体实现容易，命中率与全相联映像接近。主存与C a c h e 的地址组成主存：区号+组号+块号+块内地址Cache：组号+块号+块内地址不意图主存勺存中的第1 2 7 区块冲突次数比较C a c h e标记。页标记1 页标记。页标记1 页.标记。页标记1 页发生块冲突次数从大到小排序为：直接映像 组相联映像 全相联映像例题某 3 2 位计算机的c a c h e 容 量 为 1 6 K B,c a c h e 块的大小为1 6 B,若主存与c a c h

48、e 的地址映射采用直接映射方式，则主存地址为1 2 3 4 E 8 E 8 （十六进制）的单元装入的c a c h e 地址为_ 0A.0 0 0 1 0 0 0 1 0 0 1 1 0 1 （二进制）B.0 1 0 0 1 0 0 0 1 1 0 1 0 0 （二进制）C.1 0 1 0 0 0 1 1 1 1 1 0 0 0 （二进制）D.1 1 0 1 0 0 1 1 1 0 1 0 0 0 （二进制）c a c h e 的容量为1 6 K B,块大小为1 6 B,因此一共有1 6 K B/1 6 B=1 0 2 4 个页，所以需要1 0 位来存 储（21 0=1 0 2 4）o 块所需

49、要的存储地址位数为4位（24=1 6）0因为采用的是直接映射方式,所以主存与c a c h e 的地址关系为：主存：区号+块号+块内地址C a c h e：块号+块内地址所以，c a c h e 地址一共是1 4 位，将主存地址转换为二进制后最后1 4 位就是C a c h e 地址了，选 C“C a c h e+主存储器”系统的平均周期若 t l 为 C a c h e 的周期时间，t 2 为主存储器周期时间，h为 C a c h e 的访问命中率，则系统的平均周期为h*t l+（l-h）*t 2命中率C a c h e 由两部分组成：控制部分和C a c h e 存储器部分。控制部分的功能

50、是判断C P U要访问的信息是否在C a c h e 存储器中，若在即为命中，若不在则没有命中。命中时直接对C a c h e 存储器寻址；未命中时，要按照替换原则决定主存的一块信息放到C a c h e 存储器的哪一块里。C a c h e 命中率=（平均存取时间-主存存取时间）/（高速缓存存取时间-主存存取时间）例题高速缓存c a c h e 与主存间采用全相联地址映像方式，高速缓存的容量为4 M B,分 为 4块，每块 1 M B,主存容量为2 5 6 M B。若主存读写时间为3 0 ns,高速缓存的读写时间为3 ns,平均读写时间为3.2 7 ns,则该高速缓存的命中率为由公式可得命中