计算机软件技术基础复习提纲2012_blue

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

1、计算机软件技术基础复习提纲V1.3_blue_Oct2012说明：课程复习以教材、课件内容和课后作业为主，本提纲所列内容未详尽。试卷题型题型总分值*每小题/空分值备注一、选择题50-601二、填空题10-201三、判断题0-100.5四、综合题20-303~93-6题**注：根据A/B卷不同，各题型部分分值/题数可能稍有出入。-4-数据结构1.数据结构的定义和研究内容；数据结构逻辑结构、存储结构的分类；2.算法的概念和算法衡量的指标3.线性表Ø线性表的概念、逻辑结构和存储结构Ø[{]顺序表的特点和基本操作；顺序表的插入运算、删除运算

2、等；相应操作时需要移动元素的个数；Ø链表的特点和基本操作Ø单链表、双向链表、循环链表；头指针、头结点、首结点；指针的操作；有头结点/无头结点时，空链表的判断条件。Ø[{]单链表创建（头插法和尾插法）、插入（后插结点和前插结点）、删除操作：基本思想和关键语句；Ø双向链表中结点的插入、删除操作；（//充分利用示意图、注意关键语句的次序不能颠倒）Ø循环链表的插入、删除操作；Ø顺序表和链表的比较、存储结构选用原则；4.栈Ø定义、特点；存储结构；基本操作特点；Ø顺序栈的操作：栈底设定为数组下标端/上标端时的入栈、出栈操作；Ø链栈的操作；Ø满栈

3、和空栈的判断条件；5.队列Ø定义、特点；存储结构、基本操作特点；Ø顺序队列的操作：假溢出及处理；Ø[{]循环队列队满和队空的判断条件；Ø链式队列：头指针、尾指针；创建、入队、出队、判队空操作；6.串Ø定义和基本运算的概念（根据给定的操作定义，给出操作结果）；Ø串的定长顺序存储；如何标识实际长度；7.数组和特殊矩阵Ø数组的内存映像（根据数组基址，按元素下标求地址的计算方法）；Ø典型的特殊矩阵、特殊矩阵的压缩存储思想（//了解）；Ø稀疏矩阵的三元组表存储方法；Ø唯一表示一个稀疏矩阵的条件：除了三元组表还有矩阵的行列信息。为了方便也同时存

4、储矩阵非零元素的个数。对于有m个非零元素的稀疏矩阵，可以用(m+1)*3的数组来存储：m*3对应于m个非零元素，1*3用于存储稀疏矩阵的行、列、非零元素个数。8.树和二叉树Ø基本概念；树的基本存储结构（思想）Ø二叉树的性质（1-5）Ø[{]二叉树的顺序存储结构（要改造为完全二叉树）Ø[{]二叉树的链式存储结构（二叉链表存储）Ø[{]二叉树的遍历：先序、中序、后序9.图-4-Ø图的概念和性质；无向完全图、有向完全图；图的2种表示方法（邻接矩阵、邻接表）的特点；Ø[{]图的邻接矩阵表示法；有向图/无向图邻接矩阵中非零元素的含义（与度/出

5、入度的关系）；邻接矩阵维数与图中顶点个数的关系；Ø[{]图的邻接表表示法；Ø[{]图的遍历：深度优先遍历、广度优先遍历；1.查找与排序Ø顺序查找、折半查找（二分查找）、分块查找（索引查找）的思想和特点；平均查找长度ASL的概念；三种查找方法的性能对比；Ø[{]三种简单排序（插入排序、简单选择排序、冒泡排序）概念、基本思想；排序过程；操作系统1)操作系统ü概念；引入操作系统的目的（系统管理人员角度、用户角度）ü操作系统的分类和功能；2)进程管理ü进程管理功能；进程的定义；进程的实体组成；进程控制块PCB的作用；ü进程的状态和转换（哪些

6、状态之间可以直接转换、哪些之间不可以直接转换）；ü[{]进程的协调（互斥与同步）；临界资源和临界区的概念ü[{]信号量和P、V操作；利用信号量和PV操作，实现进程互斥和进程同步的方法；ü进程死锁的概念；死锁的原因；死锁的四个必要条件；死锁的预防和避免；3)作业管理ü作业管理功能；作业的概念；ü作业的四种状态；4)存储器管理ü存储器的层次；ü程序的逻辑地址、物理地址；重定位的概念；ü存储器管理的功能；ü虚拟存储器的概念和基本特征；ü分页存储和分段存储的概念、实现思想、区别；ü分页系统中逻辑地址到物理地址的转换；5)设备管理ü设备管理功

7、能；常用设备分配技术；数据传送控制方式；ü缓冲技术的目的；SPOOLing系统的功能和实现思想；6)文件管理ü文件管理系统的功能；文件、文件系统、文件目录的概念；ü常见的目录结构；-4-软件工程1.软件的定义；软件的分类；2.软件工程概述；²软件工程的概念；“软件危机”的含义；软件工程学科出现的原因；²软件生存周期（3个时期，8个阶段）；软件开发模型（瀑布模型）3.可行性研究²可行性研究的目的和任务；²可行性研究的几个考虑方面（经济、技术、操作、社会）；²系统流程图的概念；4.软件需求分析²需求分析的任务；结构化分析SA的思想²数据

8、流图DFD(DataFlowDiagram)的定义和作用；²数据字典的定义、用途、内容；²加工描述逻辑工具（结构化语言、判定表、判定树）的特点、比较；5.软件设计²概要设计和详细设计的任务、目标；²模块独立性的概念、模块独立性度量的两