计算机软件技术基础教学大纲.doc

计算机软件技术基础课程教学大纲（总学时：51）一、 教学基本要求1通过本课程的学习，学生应了解的内容：（1） 数据结构形成和发展的背景；（2） 操作系统的发展过程；（3） 算法的特性、描述以及算法分析技术；（4） 操作系统的作用和目标（5） 操作系统的分类和各自的特性2通过本课程的学习，学生应熟悉的内容：（1） 数据结构的基本概念和相关术语；（2） 线性结构与非线性结构的逻辑特征；（3） 线性表的应用-一元多项式的表示及相加；（4） 栈的应用-表达式求值；（5） 队列的顺序表示和实现以及假溢出的问题；（6） 串的表示和实现；（7） 操作系统中进程的概念以及引入的目的；（8） 处理机调度按层次划分的三级调度各自实现的功能；（9） 多道环境下进程之间存在的相互关系-同步、互斥，以及实现技术；（10） 虚拟存储器的概念；（11） 文件系统的功能以及文分类；（12） 设备管理的功能以及设备分配技术；3通过本课程的学习，学生应掌握的内容：（1） 线性表的顺序、链式表示和实现及其特点；（2） 队列的链式表示与实现及其特点；（3） 栈的表示与实现及其特点；（4） 矩阵的压缩存储及其应用；（5） 二叉树的定义、性质、存储结构及其遍历算法；（6） 树、二叉树、森林的区别与联系；（7） 几种查找算法-顺序、二分、分块、哈希查找的工作原理以及性能；（8） 几种内部排序算法-归并、插入、选择、冒泡、快速排序的工作原以及性能；（9） 进程的基本状态及其变迁；（10） 信号灯上的P、V操作及其应用；（11） 几种常用调度算法的思想以及各自的性能；（12） 请求式分页、分段的实现以及其优缺点；（13） 几种页面淘汰算法的工作原理和性能比较；（14） 常用的磁盘调度算法的性能分析；（15） 文件的物理组织结构以及主要操作。二、 教学大纲第一部分数据结构1绪论（3学时）11计算机应用与非数值运算1 2数据、数据项、数据元素与数据结构1 3算法的五大特性1 4算法描述语言和算法分析2线性表（4学时）2 1线性表概念与运算22线性表的顺序存储结构23线性表的链式存储结构24循环链表与双向链表3栈与队列（3学时）3 1栈的定义32栈的运算33栈的存储结构及算法34顺序队列与链队列35栈与队列的应用4数组（2学时）4 1数组的定义以及运算42数组的顺序存储结构43稀疏矩阵的存储表示及转置算法4 4规则矩阵的压缩存储5串（1学时）5 1串的基本概念52串的顺序、链接表示法53串的基本运算6树（4学时）6 1树的定义、基本术语和存储结构62二叉树及其遍历63树、森林与二叉树的关系64哈夫曼树与哈夫曼算法7查找（3学时）7 1概念与术语72顺序表查找73散列查找74各种查找算法的比较8排序（3学时）8 1基本概念82归并排序83插入排序 84选择排序 85交换排序第二部分 操作系统1概述（3学时）11计算机发展简史12操作系统的发展过程1 3什么是操作系统1 4操作系统的服务功能1 5操作系统的环境1 6操作系统的体系结构1 7操作系统的分类2进程管理（5学时）2 1进程概念22进程控制23进程间的相互作用和通信3处理机管理（4学时）3 1作业调度32进程调度33中级调度34性能评价标准35常用调度算法4存储管理（6学时）4 1引言42早期的存储管理技术43多道程序对换技术44虚拟存储器的概念45请求分页式存储管理46段式存储管理47段页式结合系统5设备管理（4学时）5 1概述52缓冲技术53设备分配及术语SPOOLing系统54磁盘的调度6文件系统（6学时）6 1概述62文件的物理组织63目录结构64文件存储空间的管理65对文件的主要操作和保护7 6文件系统与数据库三、 教材与主要参考书1教材：自编讲义2主要参考书：数据结构 严蔚敏 吴伟民 编著 清华大学出版社2000年1 月第1版（C语言版）；高等学校工科电子类规划教材精选系例 计