文档介绍：软件技术基础考试复习提纲
一、 考试题型
判断题、选择题、填空题、简答题、分析题
二、 考试范围
四大部分内容：算法与数据结构、数据库、操作系统、软件工程
三、 复习提纲
第一部分算法与数据结构（分量最多）
算法的时间复杂度与空间复杂度。
数据结构：数据的最小单位和基本单位。
线性结构的特征。
线性表的顺序存储、链式存储，各自的特征及优缺点。
顺序表和链表的操作：插入、删除、查找。
插入、删除、查找操作时需要移动的元素个数或比较的次数。最 少和最多需要移动的元素个数。
在单链表中，删除p所指结点的直接后继的操作，在p所指结点 后插入新结点的操作。
栈：特征；顺序存储和链式存储；入栈，出栈。
队列：特征；顺序存储和链式存储；入队，出队。循环队列元素 个数计算。
树：特征及递归定义；基本术语——度，深度，叶子，双亲，孩 子。
二叉树的特征及递归定义；二叉树的判定。
二叉树的性质及其应用，每层的结点数，深度为k的二叉树的结 点数，度为。的结点数=度为2的结点数+1；重点：关于二叉树结 点数目的计算问题。
满二叉树和完全二叉树的特征。
二叉树和树的存储只做了解。
二叉树的遍历及其递归算法：先序，中序，后序。几种遍历的特 征。
森林与二叉树的转化。
赫夫曼树的基本特征：带权路径长度最小的二叉树。
图的定义、存储、遍历（深度优先搜索和广度优先搜索）
顺序、折半（二分）、分块、二叉排序树查找、散列查找的算法， 每一种查找的平均查找长度，比较的次数。
折半（二分）查找的条件：有序的顺序表。
排序方法及其特征的掌握：冒泡排序、插入排序（直接和折半）、 选择排序、快速排序、二路归并排序；
要求：能写出每遍的排序结果，根据每遍的排序结果判断是哪种 排序方法。
排序时需要比较和移动元素的次数。
第二部分数据库系统
数据库的定义及特征，基本目标，数据库的操纵：查询、插入、 修改、删除。
数据库的三个层次结构（三级模式）：外模式、概念模式和内模式。
对应的二级映射。
数据模型：概念模型、逻辑模型、物理模型。
概念模型——E-R模型：实体、属性、联系。
逻辑模型——层次模型，网状模型，关系模型。
关系模型：关系（二维表）。基本概念：属性，兀组，域，字段， 键，候选键，主键，外键，全键。
关系的数据完整性约束：实体完整性，参照完整性，用户定义完 整性。
关系模型的运算：投影，选择，并，差，交，笛卡尔积（乘），除, 自然连接。
关系规范化：规范化问题的提出，目的。关系规范化是对异常的 关系进行分解以消除异常的过程。
三个范式，部分函数依赖，传递函数依赖。
第三部分操作系统
操作系统的定义、发展及分类。
概念理解：批处理、单道、多道、分时、实时、并发。
操作系统的功能：CPU管理、存储管理、设备管理、文件管理、 用户接口。
CPU —进程概念，线程的概念。程序、进程、线程区别。
进程的基本特征：动态，并发，独立，异步。
进程的三种状态：就绪、运行、阻塞；三种状态之间的转化条件。
进程的同步、互斥的概念。
临界区与临界资源。
定义信号量S及其P、V操作。
描述用P-V操作实现进程同步和互斥。
进程的死锁：定义、产生条件及解决。
\L存储-一主要是内存的管理。
地址重定