《软件技术基础》课程复习要点
第一章 数据结构
第一节 数据结构的基本概念
1、数据结构的定义，识记
计算机系统中数据的组织形式及其相互关系 2、术语：数据、数据元素、数据项，识记
3、数据结构三个层次：逻辑结构、存储结构、算法（数据的操作集合），识记 4、数据结构三个层次之间的关系，领会
5、类C语言风格的算法描述方法，简单应用
6、运用数据结构方法，抽象描述物理对象，简单应用 7、存储结构的四种类型，识记 顺序（经常进行查找运算 ）
链接（经常进行插入删除的话选这个） 索引 散列
第二节 线性结构
1、线性表的定义和特点，识记 2、顺序表的结构声明，识记
3、顺序表的插入、删除算法，领会和熟练应用 4、单向链表的结构声明、特点，识记
5、单向链表的创建、插入、删除、查找算法，领会和熟练应用 6、双向链表的结构及插入和删除算法，识记 7、循环链表的结构特点，领会
8、利用顺序表和链表解决简单问题，综合应用
9、栈的定义、特点，顺序栈、链栈的入栈和出栈算法，识记 10、利用栈的特点解决简单问题，综合应用 11、队列的定义、特点，循环队列的特点，识记 12、利用队列的特点解决简单问题，综合应用 13、二维矩阵数据元素的位置计算，简单应用
14、二维矩阵的压缩方法，特别是三元组方法，领会 15、串的特点和串的存储结构，了解
第三节 非线性结构
1、树结构的定义，识记
2、树的相关术语：节点、度、深度、有序树、无序树、森林等，识记 3、二叉树的定义和结构声明，识记 4、二叉树 记
7、二叉树的遍历算法，领会和简单应用 8、二叉排序树的创建，领会和简单应用
8、树、森林和二叉树的转换，领会 9、图的定义和相关术语，识记
10、利用邻接矩阵存储图，识记和简单应用 11、利用邻接表存储图，识记和简单应用
12、图的深度优先和广度优先遍历算法，领会（能根据图写出遍历顺序）
第四节 查找和排序
排序： 简单排序法
简单插入排序（从无序表中取插入到有序表中）
简单选择排序（从无序表选择最大或最小的元素交换到有序表的另一端） 冒泡排序
快速排序（出现逆序就交换位置） 归并排序（合二为一）
1、顺序查找算法，识记，平均查找长度的计算，领会 2、二分查找的特点和算法，识记和简单应用 （顺序储存，排列有序） 3、分块查找的特点，了解 块内无序 块间有序
4、二叉排序树的查找算法和特点，领会和简单应用
5、哈希查找的特点及线性探测再散列、二次探测再散列方法，领会和简单应用 （不需要进行关键字值比较）
6、排序的基本概念，排序算法的稳定性，识记 7、简单插入算法、简单选择算法，识记 8、冒泡排序算法，领会 9、快速排序算法，领会 （出现逆序就交换位置）（不稳定的） 10、归并排序算法，了解
第二章 操作系统
第一节 操作系统概述
1、操作系统的定义，识记
操作系统由硬件软件两部分组成，是计算机最重要的系统软件，在计算机系统中占据了特殊重要的地位。不仅是硬件与所有其他软件的接口，而且是整个计算机系统的控制和管理中心。 2、操作系统的发展过程，领会
3、操作系统的功能，识记
处理机管理（cpu，基本任务：按一定的调度策略，对处理机进行分配及资源回收）
储存器管理（内存管理，任务市委多道程序的执行提供必要和良好的环境，提高存储器的利用率，并为用户提供足够大的存储空间）
文件管理（对计算机软件资源的管理，幼教信息管理）
用户接口
4、操作系统的特征，识记
并发性（轮流交替的被cpu所调用）
共享性（两种方式：互斥共享，并发访问） 虚拟性
不确定性（指程序的 不确定）
5、批处理系统、分时系统和实时系统的特点，领会 批处理系统
分时系统：多个用户 联机使用 交互方式 特点：多路，交互，独立，及时 实时系统：特点：多路，交互（简单的交互），及时，高可靠 6、其它操作系统，了解
第二节 处理机管理
1、程序并发执行的特征，领会
2、进程的定义，识记
一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是资源分配和调度的基本单位
3、进程的特征，识记
动态性（暂时挂起条件满足时继续执行） 并发性 独立性 异步性
【简答】与程序的关系：
1.进程是程序的执行过程，指一次运行的活动，是动态的概念；程序是一组指令的集合，是静态的概念；
2.进程是程序的执行过程具有一定的生命期，而程序可以作为一种资源以文件的形式长期保存
3.一个进程可以执行多个程序，一段程序也可以被多个程序执行 4、进程控制块的概念、内容和作用，识记 概念：
PCB是操作系统为了反映进程的动态特性，便于系统控制和描述进程的活动过程而专门定义的一种数据结构。用于记录和描述进程执行情况和状态变化 内容：
进程标识信息 处理机状态信息
进程调度信息：描述进程的当前状况 进程控制信息
PCB是进程存在的唯一标志 5、进程状态及转换，领会
就绪状态（万事俱备只差cpu正在被其他进程占用）（就绪的进程占有处理器）