计算机软件技术基础复习提纲（精品）.doc

《计算机软件技术基础复习提纲（精品）.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件技术基础考试复习提纲一、考试题型判断题、选择题、填空题、简答题、分析题二、考试范围四大部分内容：算法与数据结构、数据库、操作系统、软件工程三、复习提纲第一部分算法与数据结构（分量最多）1.算法的时间复杂度与空间复杂度。2.数据结构：数据的最小单位和基本单位。3.线性结构的特征。4.线性表的顺序存储、链式存储，各口的特征及优缺点。5•顺序表和链表的操作：插入、删除、查找。6.7.插入、删除、查找操作时需要移动的元素个数或比较的次数。最少和最多需要移动的元素个数。在单链表中，删除p所指结点的直接后继的操作，在p所指结点后插入新结点的操作。8.栈：特征；顺序存储和链式存储;入栈，出栈。9.队列

2、：特征；顺序存储和链式存储；入队，出队。循环队列元素个数计算。10•树：特征及递归定义；基本术语——度，深度，叶子，双亲，孩子。11.二叉树的特征及递归定义；二叉树的判定。12.二叉树的性质及其应用，每层的结点数，深度为k的二叉树的结点数，度为0的结点数=度为2的结点数+1；重点：关于二叉树结点数目的计算问题。13•满二叉树和完全二叉树的特征。14•二叉树和树的存储只做了解。15•二叉树的遍历及其递归算法：先序，中序，后序。几种遍历的特征。16•森林与二叉树的转化。17•赫夫曼树的基本特征：带权路径长度最小的二叉树。图的定义、存储、遍历（深度优先搜索和广度优先搜索）19•顺序、折半（二分）、

3、分块、二叉排序树查找、散列查找的算法,每一种查找的平均查找长度，比较的次数。2（）.折半（二分）查找的条件：有序的顺序表。21•排序方法及其特征的掌握：冒泡排序、插入排序（直接和折半）、选择排序、快速排序、二路归并排序;22•要求：能写出每遍的排序结果，根据每遍的排序结果判断是哪种排序方法。23.排序时需要比较和移动元素的次数。第二部分数据库系统1.数据库的定义及特征，基本冃标，数据库的操纵：查询、插入、修改、删除。2.数据库的三个层次结构（三级模式人外模式、概念模式和内模式。对应的二级映射。1.数据模型：概念模型、逻辑模型、物理模型。2.概念模型——E-R模型：实体、属性、联系。3.逻辑模

4、型——层次模型，网状模型，关系模型。4.关系模型：关系（二维表）。基本概念：属性，元组，域，字段，键，候选键，主键，外键，全键。5.关系的数据完整性约束：实体完整性，参照完整性，用户定义完6.关系模型的运算：投影，选择，并，差，交，笛卡尔积（乘），除,自然连接。7.关系规范化：规范化问题的提出，目的。关系规范化是对异常的关系进行分解以消除异常的过程。10•三个范式，部分函数依赖，传递函数依赖。第三部分操作系统1・操作系统的定义、发展及分类。2.概念理解：批处理、单道、多道、分吋、实吋、并发。3.操作系统的功能：CPU管理、存储管理、设备管理、文件管理、用户接口。4.CPU—进程概念，线程的概

5、念。程序、进程、线程区别。5.进程的基本特征：动态，并发，独立，异步。6.进程的三种状态：就绪、运行、阻塞；三种状态之间的转化条件。2.进程的同步、互斥的概念。&临界区与临界资源。9.定义信号量S及其P、V操作。10・描述用P-V操作实现进程同步和互斥。11・进程的死锁：定义、产生条件及解决。2•存储管理主要是内存的管理。13•地址重定位：逻辑地址到物理地址的转换。静态、动态。14.分区式存储管理：固定分区和动态分区，分配策略。碎片。15•分页式存储管理：页，页内地址，页表。静态，动态，页面淘汰策略。16•段式存储管理：用户角度，程序逻辑段，段，段内地址，段表。17.段页式存储管理：二者结

6、合，段号，页号，页内地址。比•设备—I/O设备，独享，共享。19.外部设备的输入输出(计算机访问外设)的方式：循环测试I/O方式，中断I/O方式，通道I/O方式。20•缓冲技术和假脱机(spooling)技术。文件管——文件的三种物理结构：连续结构，链结构和索引结构。22•文件的存储管理(外存)：以字符块为单位，空闲物理块的管理。23•空闲物理块的管理方法：空闲区表，位图法，空闲块链，空闲块索引表。24.文件目录结构：文件控制块(FCB),—级目录，二级目录，目录树结构。25•文件的操作：区分“创建”和“打开”，区分“关闭”和“删除”,区分“读”和“写”，各个操作中的文件控制块情况。W用户接

7、口—两类用户：操作员、用户程序，三类用户接口。27•三种用户接口：系统调用，联机命令,可视化图形接口。第四部分软件工程1.软件工程概念的提出：解决软件危机。2.软件工程：工程、科学和数学的原理;软件工程的要索：方法,工具和过程。3.软件的生命周期及其各个阶段。4.软件设计的基本原则——模块独立性:内聚性和耦合性。5.需求分析——结构化分析方法及工具：数据流图，数据字典。■■■III6.概要设计——面向数据流的