本篇内容为省计算机二级等级考试中软件技术基础部分的考试大纲

软件技术基础： 1、线性结构(线性表、堆栈、队列、数组、串等)和非线性结构(树、图) 2、线性表的查询算法：顺序、二分法、分块 3、内排序：插入法、选择排序、冒泡法、并归法 4、线性链表(前趋、数据域、后继)。单、循环链表 软件工程： 1、软件的生存周期：计划、开发、运行 2、需求说明、总体设计(概要设计)、详细设计、代码编写、集成和测试 要求：每个阶段的文档。 3、SA(结构化分析)、SD(结构化设计)、SP(结构化程序设计)、OOP 4、软件测试(黑盒、白盒法) 操作系统： 1、操作系统分类 2、功能：处理器管理、存储器管理、设备管理、文件管理、作业管理 3、DMA方式 4、进程的组成：PCB、程序、数据集合 5、进程状态转换图 6、死锁的预防和解决 7、虚拟设备 8、内存管理：分区、分页、分段、段页式 9、文件管理：文件按名存取 数据结构篇 第一部分：基本知识 一、 基本概念 1、 什么是数据结构 2、 数据结构的三个基本层次： 数据的逻辑结构、数据的存储结构（物理结构）、数据相关算法集合 3、 数据、结构、数据元素、算法（时间复杂度和空间复杂度） 二、 逻辑结构 1、 线性结构：有始有终，前后连接（称为前趋和后继） 2、 非线性结构：一个元素有多个前趋或后继 三、 数据的存储方法（物理结构）：分为四类 1、 顺序存储方法（主要用于线性表或者数组） 2、 链接存储方法：采用指针方式 数据 下个地址 3、 索引存储方式（需要建立单独的索引文件, 索引一般形式：关键字、地址） 4、 散列存储方式（根据元素的关键字通过事先编制好的散列函数直接给出该单元存储地址） 四、 基本操作： 遍历、插入、删除、更新、查找、排序等 第二部分：线性结构 五、 基本特点：数据元素有限并有序 六、 常见的线性结构（线性表、堆栈、队列、数组、字符串等） 七、 顺序表（理解特点P265） 八、 线性链表（单向链表、双向链表、循环链表） 九、 堆栈（先进后出）：口袋装大米 十、 队列（先进先出）：排对买大米 第三部分：非线性结构 十一、 树（根、叶、分支结点。其它：深度、度、父子兄弟） ： 特点见 P267 è 森林 十二、 二叉树（每个结点只有最多两个分支的树） 十三、 遍历：先序（先根：根左右）、中序（中根：左根右）、后序（后根：左右根） 十四、 图（结点、边） 十五、 关系数据库：线性表 层次数据库：树 网状数据库：图 第四部分：线性表的查找和排序 十六、 查找 十七、 顺序查找 十八、 二分法查找（先对关键字排序，然后再对排序好的数据查找。） 十九、 分块查找（先分块：块间有序<二分法>、块内无序<顺序查找>） 二十、 排序（又称分类，分为内排序和外排序） 二十一、 插入法：将新数据比较插入到已经排序好的部分中。 二十二、 选择法：每次产生一最小数据《不稳定的排序方法》 二十三、 冒泡法：每次产生一最大数据 二十四、 规并法：相临近数据序列两两合并