计算机软件技术基础总复习

《计算机软件技术基础总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总复习各部分内容比例数据结构50%左右操作系统30%左右数据库系统15%左右软件工程5%左右考试时间：12周四6-7考试地点：231：M206/M306251：D209/B209集中答疑时间：12周二6-7，周三下午答疑地点：实验楼304数据结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为Group=（D，R）(亦称物理结构)数组逻辑结构存储结构（定义，特点）顺序存储结构链式存储结构相关运算及应用插入、删除等线性表定义，特点存储结构相关运算

2、及应用栈和队列多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。稀疏矩阵的三元组表示数组树的概念，包括与树有关的各个名词的意义二叉树的定义二叉树的性质两种特殊情形的二叉树(完全二叉树和满二叉树的定义)二叉树的遍历:能够熟练排出二叉树的三种遍历次序。三种遍历算法的实现，运用这些算法解决简单的问题。二叉排序树二叉排序树的插入和生成，给定一个序列，画出二叉排序树的生成过程。二叉排序树中结点的删除。哈夫曼树:用图示法画出哈夫曼树根据哈夫曼树给出最优前缀码。树形结构图形结构图的概念包括与图有关的各个名词的意义图的邻接矩阵表示法和邻接表表示法根据表示法画出图或者

3、根据图写出邻接矩阵表示或画出邻接表。图的遍历深度优先遍历广度优先遍历单源最短路径拓扑排序查找查找的基本概念，平均查找长度的定义及计算线性表的查找有三种方法顺序查找、二分查找、分块查找二叉排序树查找哈希查找，什么是哈希表?哈希函数、哈希值、哈希的含义。冲突(碰撞)、同义词的含义。处理哈希表中冲突的方法：开放定址法拉链法画出哈希表，并计算哈希表中查找的平均查找长度排序方法插入排序选择排序交换排序归并排序线性插入排序对半插入排序简单选择排序堆排序冒泡排序快速排序排序操作系统概念操作系统基本概念定义、目的、特征操作系统的分类批处理系统、分时系统、实时系统。。操作系统的功能处理机管理、存储管理

4、、设备管理、文件管理、作业管理处理机管理作业的概念作业的定义、组成、JCB、状态进程的概念进程的定义、PCB、进程与程序进程状态及进程控制进程状态及转换、进程队列、进程控制处理机调度高级调度、低级调度、调度算法进程的同步与互斥概念、解决同步互斥的软件工具（P-V操作）、生产者─消费者问题死锁产生死锁的原因、必要条件、解决死锁方法解决死锁方法预防：在系统运行之前就采取措施，严格防止死锁的产生。方法为：破坏死锁产生的四个必要条件之一。一次性分配资源。申请不到资源，则释放全部资源。资源编号，从低到高申请。避免：允许死锁产生的四个必要条件存在，当系统有可能产生死锁时，小心地避免。银行家算法。

5、检测和恢复：允许死锁的产生，每隔一段时间进行检测，若存在死锁，则即决之。化简资源分配图。撤销进程。按某种次序强行从系统中撤销一个或多个卷入死锁的进程，收回它们的资源，直到有足够的资源可供其他进程执行完毕。挂起进程。使用挂起/激活机构挂起一些进程，暂时剥夺它们占有的资源，以解除死锁，待以后条件满足后再激活被挂起的进程。存储管理存储管理任务主存空间分配、地址映射、内存保护、内存“扩充”实存储管理固定分区、动态分区（空闲分区分配算法、动态重定位）虚拟存储管理请求分页（概念、特点、地址转换、页面置换算法）请求分段设备管理有关概念设备管理的功能、任务I/O请求的检测与控制循环测试、中断、DMA

6、、通道缓冲技术概念、目的设备管理程序逻辑设备与物理设备虚拟设备技术虚拟设备、SPOOLing技术文件管理基本概念与术语文件、文件系统文件分类文件的结构逻辑结构（记录式文件、流式文件）、物理结构（连续分配、链接分配、索引分配）文件目录FCB、文件目录、目录项、目录文件、目录结构（单级、目录、目录）、路径文件存储空间的管理数据库系统概述数据库基本概念DB、DBMS、DBS、DBA数据模型数据模型（E-R图）、结构模型（层次、网状、关系）、E-R图转换为关系模型数据库系统结构（三级模式结构）外模式、模式、内模式、外模式/模式映象、模式/内模式映象、逻辑独立性、物理独立性关系数据库的基本概念

7、关系、元组、属性、候选码、主码关系模式、关系模型、关系特点关系数据操作语言关系代数传统的集合运算（并、交、差、广义笛卡尔积）专门的关系运算（选择、投影、连接（条件连接、自然连接））结构化查询语言SQLSQL：DDL、DML、DCLSELECT语句的使用数据库设计与应用关系模式规范化范式、规范化、1NF、2NF、3NF数据库设计软件工程软件工程基本概念软件、软件危机软件生命周期软件开发过程过程模型软件开发方法结构化、面向对象软件开发工具结构化软件开发方法可行