2013年软件设计师考试大纲.doc

2012软件设计师考试大纲一、考试说明1考试目标通过本考试的合格人员能根据软件开发项目管理和软件工程的要求，按照系统总体设计规格说明书进行软件设计，编写程序设计规格说明书等相应的文档，组织和指导程序员编写、调试程序，并对软件进行优化和集成测试，开发出符合系统总体设计要求的高质量软件；具有工程师的实际工作能力和业务水平。2考试要求(1) 掌握计算机内的数据表示、算术和逻辑运算方法；(2) 掌握相关的应用数学及离散数学基础知识；(3) 掌握计算机体系结构以及各主要部件的性能和基本工作原理；(4) 掌握操作系统、程序设计语言的基础知识，了解编译程序的基本知识；(5) 熟练掌握常用数据结构和常用算法；(6) 熟悉数据库、网络和多媒体的基础知识；(7) 掌握C程序设计语言，以及C+、Java中的一种程序设计语言；(8) 熟悉软件工程、软件过程改进和软件开发项目管理的基础知识；(9) 掌握软件设计的方法和技术；(10) 了解信息化、常用信息技术标准、安全性，以及有关法律、法规的基础知识；(11) 正确阅读和理解计算机领域的英文资料。3考试科目(1) 计算机与软件工程知识，考试时间为150分钟，笔试，选择题；(2) 软件设计，考试时间为150分钟，笔试，问答题。二、考试范围考试科目1：计算机与软件工程知识1. 计算机科学基础知识1.1数制及其转换l 二进制、八进制、十进制和十六进制等常用数制及其相互转换1.2 计算机内数据的表示l 数的表示（补码表示，整数和实数的表示，精度和溢出）l 非数值表示（字符和汉字表示，声音表示、图像表示）1.3算术运算和逻辑运算l 计算机中的二进制数运算方法l 逻辑代数的基本运算1.4其他数学基础知识l 常用数值计算l 排列组合，概率论应用，应用统计（数据的统计分析）l 编码基础l 命题逻辑、谓词逻辑、形式逻辑的基础知识l 运筹基本方法2. 计算机系统知识2.1计算机硬件基础知识2.1.1计算机系统的组成、体系结构分类及特性l CPU、存储器的组成、性能和基本工作原理l 常用I/O设备、通信设备的性能以及基本工作原理l I/O接口的功能、类型和特性l CISC/RISC，流水线操作，多处理机，并行处理2.1.2存储系统l 虚拟存储器基本工作原理，多级存储体系l RAID类型和特性2.1.3可靠性与系统性能评测基础知识l 诊断与容错l 系统可靠性分析评价l 计算机系统性能评测方法2.2计算机软件知识2.2.1数据结构与算法知识l 数组l 链表l 队列、栈l 树l 图的定义、存储和基本操作l 杂凑（Hash表）l 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法l 算法描述和分析2.2.2 操作系统知识l 操作系统的内核l 处理机管理l 存储管理l 设备管理l 文件管理l 作业管理l 网络操作系统和嵌入式操作系统基础知识l 操作系统的配置2.2.3程序设计语言和语言处理程序知识l 汇编、编译、解释系统的基础知识和基本工作原理l 程序设计语言的基本成分（数据、运算、控制和传输），程序调用的实现机制l 各类程序设计语言的主要特点和适用情况2.2.4 数据库知识l 数据库模型（概念模式、外模式、内模式）l 数据模型，ER图，规范化l 数据操作l 数据库语言l 数据库管理系统的功能和特征l 数据库的控制功能l 数据仓库和分布式数据库基础知识2.3 计算机网络知识l 网络体系结构l 传输介质，传输技术，传输方法，传输控制l 常用网络设备和各类通信设备的特点l Client-Server结构，Browser-Server结构l LAN（拓扑，存取控制，组网，网间互连）l Internet 和Intranet 基础知识以及应用l 网络软件l 网络管理，网络性能分析2.4 多媒体基础知识l 多媒体系统基础知识l 简单图形的绘制，图像文件的处理方法l 音频和视频信息的应用l 多媒体应用开发过程3. 系统开发和运行知识3.1软件工程知识l 软件生存周期与软件生存周期模型l 软件开发方法l 软件开发项目管理l 软件开发工具与软件开发环境3.2 系统分析基础知识l 系统分析的主要步骤l 机构化分析方法3.3 系统设计基础知识l 概要设计与详细设计的基本任务l 系统设计的基本原理l 系统模块结构设计l 结构化设计方法l 面向数据结构的设计方法l 系统详细设计3.4 系统实施基础知识l 系统实施的基本内容l 程序设计方法l 程序设计的基本模块l 系统测试l 系统转换3.5 系统运行和维护基础知识l 系统可维护性的概念l 系统维护的类型l 系统评价的概念和类型3.6 软件质量管理基础知识l 软件质量特性（ISO/IEC 9126软件质量模型）l 软件质量保证l 软件复杂性的概念及度量方法（McCabe度量法）l 软件评审（设计质量评审、程序质量评审）l 软件容错技术3.7 软件过程改进基础知识l 软件能力成熟度模型CMMl 统一过程（UP）与极限编程（XP）的基本概念4. 面向对象基础知识l 面向对象的基本概念l 面向对象分析与设计知识l 分析模式与设计模式知识l 面向对象程序设计知识l 面向对象数据库、分布式对象基础知识5. 信息安全知识l 信息系统安全基础知识l 信息系统安全管理l 保障完整性与可用性的措施l 加密与解密机制基础知识l 风险管理（风险分析、风险类型、抗风险措施和内部控制）l 计算机安全相关的法律、法规基础知识6. 标准化、信息化和知识产权基础知识6.1 标准化基础知识l 标准化意识，标准化组织机构，标准的内容、分类、代号与编号规定，标准制订过程l 国际标准、国家标准、行业标准、企业标准l 代码标准、文件格式标准、安全标准、互联网相关标准、软件开发规范和文档标准、基于构件的软件标准6.2 信息化基础知识l 全球信息化趋势、国家信息化战略、企业信息化战略和策略l 互联网相关的法律、法规l 个人信息保护规则l 远程教育、电子商务、电子政务等基础知识l 企业信息资源管理基础知识6.3 知识产权基础知识l 保护知识产权有关的法律、法规7. 计算机专业英语l 具有工程师所要求的英语阅读水平l 理解本领域的英语术语考试科目2：软件设计1外部设计1.1 理解系统需求说明 1.2 准备进行系统开发 l 选择开发方法、准备开发环境、制订开发计划 1.3 设计系统功能 l 选择系统结构l 设计各子系统的功能和接口l 设计安全性策略、需求和实现方法l 制订详细的工作流和数据流 1.4 设计数据模型 l 设计ER模型及其他数据模型 1.5 编写外部设计文档 l 系统配置图、各子系统关系图l 系统流程图、系统功能说明书l 输入输出规格说明、数据规格说明、用户手册框架 l 设计系统测试要求 1.6 外部设计的评审2内部设计2.1 设计软件结构l 按构件分解，确定构件功能、规格以及构件之间的接口l 数据结构与算法设计l 采用中间件和工具 2.2 设计输入输出2.3 设计物理数据2.4 构件的创建和重用l 创建构件、重用构件l 使用子程序库或类库 2.5 编写内部设计文档l 构件划分图、构件间的接口、构件处理说明l 屏幕界面设计文档、报表设计文档、文件设计文档、数据库设计文档 2.6 内部设计的评审3数据库应用分析与设计 l 设计关系模式l 数据库语言（SQL）l 数据库访问4程序设计 4.1 模块划分4.2 编写程序设计文档4.3 程序设计评审 5系统实施 5.1 配置计算机系统及环境5.2 选择合适的程序设计语言5.3 用C程序设计语言以及C+、Java中的任一种程序设计语言进行程序设计5.4 系统测试l 指导程序员进行模块测试，并进行验收l 准备系统集成测试环境和测试工具l 准备测试数据l 写出测试报告6软件工程应用6.1 软件开发周期模型6.2 需求分析6.3 软件设计l 软件设计的基本原则l 软件设计方法l 程序设计（结构化程序设计、面向对象程序设计）6.4 软件测试的原则与方法6.5 软件质量（软件质量特性、软件质量控制）6.6 软件过程评估基本方法、软件能力成熟度评估基本方法6.7 软件开发环境和开发工具6.8 面向对象技术l 面向构件技术l 统一建模语言（UML）l 软件过程改进模型和方法6.9 网络环境软件技术三、题型举例（一）选择题1. 某系统的可靠性结构框图如下图所示。该系统由4个部件组成，其中2、3两部件并联冗余，再与1、4部件串联构成。假设部件1、2、3的可靠度分别为0.90、0.70、0.70。若要求该系统的可靠度不低于0.75，则进行系统设计时，分配给部件4的可靠度至少应为 （1） 。（1）A. B. C. D. 2. 结构化开发方法中，数据流图是 （2） 阶段产生的成果。（2）A. 需求分析 B. 总体设计 C. 详细设计 D. 程序编码3. 在进行面向对象设计时，采用设计模式能够（3）。（3）A. 复用相似问题的相同解决方案B. 改善代码的平台可移植性C. 改善代码的可理解性D. 增强软件的易安装性4. Model-driven analysis emphasizes the drawing of pictorial system models to document and validate both existing and/or proposed systems. Ultimately, the system models become the （5） for designing and constructing an improved system. （6） is such a technique. The emphasis in this technique is process-centered. Systems analysts draw a series of process models called （7） . （8） is another such technique that integrates data and process concerns into constructs called objects.（4）A. PrototypingB. AcceleratedC. Model-drivenD. Iterative（5）A. imageB. pictureC. layoutD. blueprint（6）A. Structured analysis B. Information EngineeringC. Discovery PrototypingD. Object-Oriented analysis（7）A.PERTB. DFDC. ERDD. UML（8）A. Structured analysis B. Information EngineeringC. Discovery PrototypingD. Object-Oriented analysis（二）问答题试题一 软件设计必做样题阅读下列说明以及图1-1和图1-2，回答问题1、问题2和问题3，将解答填入答题纸的对应栏内。说明某电话公司决定开发一个管理所有客户信息的交互式网络系统。系统的功能如下：1.浏览客户信息：任何使用Internet的网络用户都可以浏览电话公司所有的客户信息（包括姓名、住址、电话号码等）。2.登录：电话公司授予每个客户一个帐号。拥有授权帐号的客户，可以使用系统提供的页面设置个人密码，并使用该帐号和密码向系统注册。3.修改个人信息：客户向系统注册后，可以发送电子邮件或者使用系统提供的页面，对个人信息进行修改。4.删除客户信息：只有公司的管理人员才能删除不再接受公司服务的客户的信息。系统采用面向对象方法进行开发，在开发过程中认定出的类如下表所示：编号类名描述1InternetClient网络用户2CustomerList客户信息表，记录公司所有客户的信息3Customer客户信息，记录单个客户的信息4CompanyCustomer公司客户5InternalClient公司的管理人员网络用户公司客户管理人员ABCD图1-1InternetClient+search(s:String):StringCustomerList+search(s:String):Customer+getCustomer(number:String):Customer+addCustomer(c:Customer):Boolean+removeCustomer(c:Customer):BooleanCompanyCustomer+login(number:String,passwd:String):Boolean+update(webpage:String,e_mail:String):Boolean+viewMyInfo():StringCustomer-number:String-name:String-address:String-e_mail:String-webpage:String-passwd:String+check_pwd(s:String):Boolean+showInfo():StringInternalClient+updateCustomer(number:String,.):Boolean+addCustomer(name:String,.):Boolean+removeCustomer(number:String):Boolean+viewCustomer(number:String):String0.*1 (1) (2) (3) (4) 图1-2【问题1】在需求分析阶段，采用UML的用例图（use case diagram）描述系统功能需求，如图1-1所示。请指出图中的A、B、C和D分别是哪个用例？【问题2】在UML中，重复度（Multiplicity）定义了某个类的一个实例可以与另一个类的多少个实例相关联。通常把它写成一个表示取值范围的表达式或者一个具体的值。例如图3-2中的类InternetClient和CustomerList，InternetClient端的“0.*”表示：一个CustomerList的实例可以与0个或多个InternetClient的实例相关联；CustomerList端的“1”表示：一个InternetClient的实例只能与一个CustomerList的实例相关。请指出图1-2中(1)到(4)处的重复度分别为多少？【问题3】类通常不会单独存在，因此当对系统建模时，不仅要识别出类，还必须对类之间的相互关系建模。在面向对象建模中，提供了四种关系：依赖（dependency）、概括（generalization）、关联（association）和聚集（aggregation）。请分别说明这四种关系的含义，并说明关联和聚集之间的主要区别。试题二 C语言选做样题阅读以下预备知识、函数说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。【预备知识】（1）对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合a，b，c，d及其权值2、7、4、5，可构造如下所示的最优二叉树和相应的结构数组Ht（数组元素Ht0不用）。b d a c 010011最优二叉树数组下标chweightparentlchildrchild1a25002b77003c45004d560056613611745718026 结构数组Ht结构数组Ht的类型定义如下：#define MAXLEAFNUM 20struct nodechar ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/int weight; /*当前结点的权值*/ int parent; /*当前结点的父结点的下标，为0时表示无父结点*/ int lchild,rchild; /*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/Ht2*MAXLEAFNUM;（2）用0或1标识最优二叉树中分支的规则是：从一个结点进入其左（右）孩子结点，就用0（1）标识该分支（示例见上图）。（3）若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由0、1组成的一个序列，称此序列为该叶子结点的前缀编码。例如上图所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。【函数说明】函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。在构造过程中，将Htp.weight域用作被遍历结点的遍历状态标志。【函数】char *Hc;void LeafCode(int root,int n) /*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/int i, p = root, cdlen = 0; char code20; Hc = (char *)malloc(n+1)*sizeof(char *); /*申请字符指针数组*/ for(i = 1; i = p; +i) Hti.weight = 0; /*遍历最优二叉树时用作被遍历结点的状态标志*/while(p) /*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/if(Htp.weight = 0) /*向左*/ Htp.weight = 1; if (Htp.lchild != 0) p = Htp.lchild; codecdlen+ = 0; else if (Htp.rchild = 0) /*若是叶子结点，则保存其前缀编码*/ Hcp = (char *)malloc(cdlen+1)*sizeof(char); (1) ; strcpy(Hcp,code); else if(Htp.weight = 1) /*向右*/ Htp.weight = 2; if (Htp.rchild != 0) p = Htp.rchild; codecdlen+ = 1; else /* Htp.weight=2，回退*/ Htp.weight = 0;p = (2) ; (3) ; /*退回父结点*/ /*while结束*/【函数说明】函数void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。【函数】void Decode(char *buff, int root) int pre = root, p;while (*buff != 0) p = root; while (p != 0) /*存在下标为p的结点*/ pre = p; if ( (4) ) p = Htp.lchild; /*进入左子树*/ else p = Htp.rchild; /*进入右子树*/ buff+; /*指向前缀编码序列的下一个字符*/ (5) ;printf(%c, Htpre.ch); 试题三 C+语言选做样题阅读以下说明和C+代码，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明】在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时，关注此OfficeDoc类对象的相应的DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组DocExplorer对象。当OfficeDoc对象的内容或状态发生变化时，所有与之相关联的DocExplorer对象都将得到通知，这种应用被称为观察者模式。以下代码写在一个C+源文件中，能够正确编译通过。【C+代码】#include const OBS_MAXNUM=20; /最多与OfficeDoc对象相关联的DocExplorer对象的个数 (1) ;class DocExplorer /关注OfficeDoc公文对象的类public:DocExplorer ( (2) *doc); /构造函数 (3) void update(OfficeDoc *doc)=0; /更新自身状态的函数/其它相关属性和方法省略;class OfficeDoc /公文类private:DocExplorer *myObsOBS_MAXNUM; /关注此公文类的DocExplorer类对象指针数组int index; /与OfficeDoc对象关联的DocExplorer对象的个数public:OfficeDoc()index=0;void attach(DocExplorer *o) /将一DocExplorer对象与OfficeDoc对象相关联if (index = OBS_MAXNUM | o = NULL) return;for(int loop = 0; loop index; loop+)if(myObsloop = o)return; myObsindex = o; index+;void detach(DocExplorer *o) /解除某DocExplorer对象与OfficeDoc对象的关联if(o=NULL) return;for(int loop = 0; loop index; loop +)if(myObsloop = o)if(loop = index-2) myObsloop = myObsindex-1;myObsindex-1=NULL;index-;break;private:void notifyObs() /通知所有的DocExplorer对象更改自身状态for(int loop = 0; loop (4) ; /DocExplorer对象更新自身状态/其它公文类的相关属性和方法;DocExplorer:DocExplorer(OfficeDoc *doc) /DocExplorer类对象的构造函数doc- (5) ; /将此DocExplorer对象与doc对象相关联试题四 Java语言选做样题阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明】在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时，关注此OfficeDoc类对象的相应的DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组DocExplorer对象。当OfficeDoc对象的内容或状态发生变化时，所有与之相关联的DocExplorer对象都将得到通知，这种应用被称为观察者模式。以下代码采用Java语言实现，能够正确编译通过。【Java 代码】/ Subject.java文件public interface Subject public void attach(Observer DocExplorer);public void detach(Observer DocExplorer);void notifyObservers();/ Observer.java文件public interface Observervoid update( (1) );/ OfficeDoc.java文件import java.util.*;public class OfficeDoc implements Subject /OfficeDoc类实现Subject接口private Vector ObserverVector = new java.util.Vector();/ 存储与OfficeDoc相关联的DocExplorer对象public void attach(Observer observer) /将某DocExplorer对象与OfficeDoc相关联ObserverVector.addElement(observer);public void detach(Observer observer)/解除某DocExplorer对象与OfficeDoc的关联关系ObserverVector.removeElement(observer);public void notifyObservers()/当OfficeDoc对象状态已发生变化时，通知所有的DocExplorer对象Enumeration enumeration = (2) ;while (enumeration.hasMoreElements()(Observer)enumeration.nextElement(). (3) ;public Enumeration Observers()return ObserverVector.elements();/其它公文类的属性和方法省略/ DocExplorer.java文件public class DocExplorer implements (4) public void update( (5) )/更新DocExplorer自身的状态，代码省略软件设计师培训指南一、考试说明1考试目标通过本考试的合格人员能根据软件开发项目管理和软件工程的要求，按照系统总体设计规格说明书进行软件设计，编写程序设计规格说明书等相应的文档，组织和指导程序员编写、调试程序，并对软件进行优化和集成测试，开发出符合系统总体设计要求的高质量软件；具有工程师的实际工作能力和业务水平。2考试要求(1) 掌握计算机内的数据表示、算术和逻辑运算；(2) 掌握相关的应用数学及离散数学基础知识；(3) 掌握计算机体系结构以及各主要部件的性能和基本工作原理；(4) 掌握操作系统、程序设计语言的基础知识，了解编译程序的基本知识；(5) 熟练掌握常用数据结构和常用算法；(6) 熟悉数据库、网络和多媒体的基础知识；(7) 掌握C程序设计语言，以及C+、Java中的一种程序设计语言；(8) 熟悉软件工程、软件过程改进和软件开发项目管理的基础知识；(9) 掌握软件设计的方法和技术；(10) 了解信息化、常用信息技术标准、安全性，以及有关法律、法规的基础知识；(11) 正确阅读和理解计算机领域的英文资料。3考试科目(1) 计算机与软件工程知识，考试时间为150分钟，笔试，选择题；(2) 软件设计，考试时间为150分钟，笔试，问答题。二、考试内容说明: “I”、“II”和“III”表示掌握或熟悉的程度：“I”是指对所列知识要理解其内容及含义（理解）。“II” 指在有关问题中能直接使用（一般应用）。“III”是指对所列知识要理解其确切含义及与其它知识的联系，能够进行叙述和解释，并能在实际问题的分析、综合、推理和判断等过程中运用（综合应用）。考试科目1：计算机与软件工程知识1. 计算机科学基础知识 1.1数制及其转换l 二进制、八进制、十进制和十六进制等常用数制及其相互转换 （）1.2 计算机内数据的表示l 数的表示 带符号定点数据（纯整数和纯小数）的原码、反码、补码和移码表示（） 浮点数（实数）的表示（） 溢出的概念（）1.3算术运算和逻辑运算l 计算机中的二进制数运算方法 补码表示下定点数的加、减、乘、除运算方法（I）l 逻辑代数的基本运算 基本的逻辑运算：与、或、非、异或（）1.4其他数学基础知识l 常用数值计算 矩阵和行列式、近似求解、插值、数值积分、常微分方程等常用的数值运算方法及运算误差的概念（I）l 排列组合，概率论应用，应用统计（数据的统计分析）（I）l 编码基础（ASC码，汉字编码，奇偶校验，海明码，霍夫曼码、循环冗余码） 奇偶校验码、海明码、霍夫曼码、循环冗余码的编码方法及指定实例时校验码的计算（I）l 命题逻辑、谓词逻辑、形式逻辑的基础知识 （I）2. 计算机系统基础知识 2.1计算机硬件基础知识 2.1.1计算机系统的组成、体系结构分类及特性l CPU、存储器的组成、性能和基本工作原理 CPU的基本组成结构（I） 存储器的组成及特点：内存、外存、缓存Cache）、闪存（） 存储器的性能指标定义：存取周期、存储容量和可靠性（）l 常用I/O设备、通信设备的性能以及基本工作原理（I）l I/O接口的功能、类型和特性 CPU在与I/O设备进行数据交换时存在的主要问题：速度不匹配、时序不匹配、信息格式不匹配、信息类型不匹配（I） CPU与外设之间的数据交换必须通过接口来完成，I/O接口的主要功能（） 接口的控制方式及特点：CPU通过接口对外设进行控制的方式程序查询方式、中断处理方式、DMA（直接存储器存取）传送方式（）l CISC/RISC，流水线操作，多处理机，并行处理 RISC（精简指令集计算机）和CISC（复杂指令集计算机）的定义和特点（I） 流水线的定义及操作特点（） 多处理机的概念（I） 单指令流单数据流（SISD）、单指令流多数据流（SIMD）、多指令流单数据流（MISD）、多指令流多数据流（MIMD）的概念和特点（） 并行处理的基本概念（I）2.1.2存储系统l 虚拟存储器基本工作原理，多级存储体系 虚拟存储器的定义和管理方式（I） 多级存储体系的组成及特点（）l RAID类型和特性 RAID的定义和基本特点（I） RAID 0RAID 7、RAID 10、RAID 53等规范的特征（I）2.1.3可靠性与系统性能评测基础知识l 诊断与容错 容错技术与容错控制（I）l 系统可靠性分析评价 系统的可靠性定义（I） 串联系统特点及可靠性度量（） 并联系统特点及可靠性度量（） 模冗余系统等可靠性数学模型的特点（I）l 计算机系统性能评测方法 平均无故障时间（MTBF）的定义 （I） 平均修复时间（MTRF）的定义（I） 可用性的定义（I）2.2计算机软件基础知识2.2.1数据结构与算法知识 l 数组 二维数组：按行存储和按列存储，数组元素存储位置的计算（） 特殊矩阵和稀疏矩阵的特点及压缩存储（） 静态数组（固定容量数组）（I） 动态数组（根据应用需要申请或扩充数组的容量）（I）l 链表 线性表的定义和基本运算（I） 线性表的顺序存储和特点（I） 单向链表、双向链表和环形链表的运算特点（） 指针、结点、头指针和头结点的概念（）l 队列和栈 队列的定义、运算和存储结构（） 栈的定义、运算和存储结构（）l 树 二叉树的定义（） 满二叉树、完全二叉树的定义（） 二叉树的性质（） 二叉树的顺序存储和二叉链表存储（） 二叉树的遍历：先序、中序、后序和层序（） 最优二叉树的定义、特点和构造方法（） 二叉排序树的定义和运算（） 平衡二叉树、B-树、B+树的概念（I） 树与二叉排序树的相互转换（）l 图 图结构的定义（I） 图的邻接矩阵存储和邻接表存储（I） 图的广度优先遍历和深度优先遍历操作（）l 杂凑 哈希（杂凑）表的构造、冲突的处理和元素的查找，平均查找长度的计算（）l 常用算法 插入排序、冒泡排序、选择排序算法（） 希尔排序、快速排序、堆排序、归并排序方法及特点（） 顺序查找、二分查找方法及特点（） 模式匹配算法（） 图的遍历算法、求最小生成树算法、拓扑排序算法、求最短路径算法、求关键路径算法的算法思想（） 递归算法的设计方法（）l 算法描述和分析 算法的实现与数据结构的关系（） 算法的效率分析（） 算法的流程图、伪代码描述方式（） 算法的时间复杂性和空间复杂性概念（I）2.2.2 操作系统知识l 操作系统的内核 操作系统内核的功能和基本组成（I） 内核与用户程序的运行方式差别（I） 内核运行、中断控制的基本知识（I）l 处理机管理 进程、线程等基本概念，程序顺序执行和并发执行的基本特征（I） 进程的基本组成，进程的基本状态及状态间的切换，三态模型与五态模型（II） 进程间的通信：同步与互斥、临界资源、临界区、信号量、PV操作（II） 管程的概念（I） 进程调度方式及常用的进程调度算法（II） 死锁的定义、产生死锁的原因、产生死锁的必要条件（II）l 存储管理 虚拟地址、地址空间、存储空间、地址重定位的基本概念（I） 分页存储管理（II） 程序的局部性特点，虚拟存储器的实现方法（I） 页面置换算法：最佳置换算法、先进先出置换算法、最近最久未使用置换算法、最近未用置换算法（II）l 设备管理 设备分类方法（I） 通道、DMA的概念及特点（I） Spooling（Simultaneous Peripheral Operations On Line）定义、组成和结构（I） 磁盘调度算法：先来先服务（First-Come First-Served，FCFS）、最短寻道时间优先SSTF（Shortest Seek Time First）、扫描算法（SCAN）、单向扫描调度算法（CSCAN）磁盘调度算法的基本思想（II）l 文件管理 文件、文件系统、文件类型、文件组织结构的基本概念（I） 文件的物理结构：连续结构、链接结构、索引结构、多个物理块的索引表结构的基本概念（I） 目录，一级目录、二级目录、多级目录的基本概念（I） 文件的存取方法：顺序存取法、直接存取法、按键存取法的基本概念（I） 文件存储空间的管理：位示图、空闲区表、空闲块链、成组链接法基本思想（I）l 作业管理 作业的状态（提交、后备、执行、完成）、作业控制块和作业后备队列的基本概念（I） 先来先服务、短作业优先、响应比高优先作业调度算法思想（II） 优先级调度算法思想（II）l 网络操作系统和嵌入式操作系统基础知识 网络操作系统的特征和分类（I） 嵌入式操作系统的特点（I） 操作系统的配置（I）2.2.3 程序设计语言和语言处理程序知识 l 汇编、编译、解释系统的基础知识和基本工作原理 语言翻译的基本概念（I） 汇编的基本方法（I） 编译的基本过程及编译各阶段的基本任务（I） 解释的基本过程（I） 有限自动机的定义及构造（） 正规表达式的定义、构造及特点 （） 上下文无关文法的定义（I） 句子的推导（）l 程序设计语言的基本成分：数据、运算、控制和传输，程序调用的实现机制 程序设计语言的数据、运算、控制及输入输出处理机制（I） 函数的参数传递机制：传值、传地址（）l 各类程序设计语言的主要特点和适用情况 过程式程序语言、面向对象程序设计语言、函数式程序设计语言、逻辑程序设计语言的基本特点（I） 脚本语言的特点（I）2.2.4 数据库知识 l 数据库模型（概念模式、外模式、内模式） 概念模式（模式）、外模式（用户模式或子模式）、内模式（物理模式）的基本概念（） 三级模式和两级映像（模式/内模式映像、外模式/模式映像）的基本概念（） 数据的独立性（数据的逻辑独立性、数据的物理独立性）的基本概念（）l 数据模型，ER图，规范化 数据模型：层次模型、网状模型、关系模型、面向对象模型的基本概念（）关系模型的应用方法（） 数据模型的三要素（数据结构、数据操作、数据的约束条件）的含义（） E-R模型方面的基本概念（）；E-R图（E-R模型）向关系模型的转换的基本方法（） 实体中主键、候选键、外键方面的基本概念（） 联系类型（一对多（1：1）、一对多（1：n）、多对多（m：n）的基础知识（） 属性（简单属性、复合属性、单值属性、多值属性、NULL属性、派生属性）的含义（） 关系模式规范化的程度：第一、第二、第三范式（）l 数据操作 关系数据库、关系数据库模式的基本概念（） 关系模型的完整性规则：实体完整性、参照完整性、用户定义完整性的基本概念（） 5种基本的关系运算（并、差、笛卡尔积、投影、选择）的基本概念（）；扩展的关系运算中选择、投影、连接运算方法（）；扩展的关系运算中的除法、外联接方面的基本概念（）l 数据库语言 数据定义语言(DDL)：CREATE TABLE (创建表)使用方法（） 数据操纵语言(DML)：SELECT(查询)、INSERT(插入)、DELETE(删除)和UPDATE(修改) 使用方法（） 完整性(integrity)定义：PRIMARY KEY、FOREIGN KEY REFERENCES使用方法（） 权限管理(authorization) ：GRANT和REVORK使用方法（）l 数据库管理系统的功能和特征 数据库管理系统的特征、功能与组成、文件系统的特征，文件系统与数据库管理系统的差异的基本概念（）l 数据库的控制功能 事务的基本概念、事务的特性、故障的类型的基础知识（） 数据不一致性（丢失修改、不可重复读、读脏数据）的基础知识（） 并发控制中活锁/死锁、可串行性、两段锁协议的基本概念（） 安全控制（权限机制、视图机制、加密机制）的基本概念（） 事务、事务的特性、事务的状态、事务状态的转换的基本概念（） 故障的类型、故障的恢复技术、恢复策略的基础知识（） 并发控制后会产生丢失修改、不可重复读、读脏数据三类数据不一致性（），造成数据不一致性的原因（） 并发控制中事务的调度（串行调度、并行调度）、活锁/