计算机软件课程设计

更新时间:2023-12-17 作者:用户投稿原创标记本站原创 点赞:17689 浏览:81188

《计算机组成原理》课程教学大纲

适用专业:计算机科学与技术学制年限:4年

总学时:54学分:3.5

制定者:向丽萍审核人:

一、说明

1,课程的性质,地位和任务:

计算机组成原理是计算机科学技术的一门核心专业基础课程.本课程比较全面地介绍了计算机硬件系统的工作原理和组成结构,剖析计算机的运算器,存储器,控制器和输入输出设备的组成,工作原理与相互关系其任务是使学生对计算机的内部结构,功能部件,功能特征,性能以及交互方式有一个完整的认识通过本课程的学习和课程配套的系列实验之后,不把计算机一个执行程序的黑匣子,可以从计算机的组成原理和系统结构,完整说明计算机的工作过程,并能根据计算机的特征编写出更加高效的程序,为后继课程的学习打下基础,同时也为计算机系统软件的设计和从事计算机维护管理工作打下基础.充分重视实践性教学环节《计算机组成原理黄钦胜朱娟编着电子工业出版社2003年8月《计算机组成原理-习题与解析》徐爱萍编着清华大学出版社.掌握的基本原理,概念和方法,在算法算法,数据结构的基础上,方法应用主要内容包括:,熟的环境1第一章绪论442第二章线性表6423第三章栈和队列6424第四章串225第五章数组和广义表226第六章树和二叉树10827第七章图8628第八章动态存储管理229第九章查找86210第十章内部排序108211第十一章外部排序4412第十二章文件22合计6452126,考核方式:


考试+实验+平时成绩

二、理论教学内容与学时安排(总学时:52学时)

第一章绪论(4学时)

1.数据,数据元素,数据对象,数据结构,存储结构和数据类型等概念术语的确定含义,

2.抽象数据类型的定义,表示和实现方法,描述算法的类PASCAL或c语言,

3.算法设计的基本要求以及从时间和空间角度分析算法的方法.

基本要求:

熟悉各名词,术语的含义,掌握基本概念,特别是数据的逻辑结构和存储结构之间的关系,分清哪些是逻辑结构的性质,哪些是存储结构的性质,了解抽象数据类型的定义,表示和实现方法,熟悉类PASCAL语言或c语言的书写规范,特别要注意值参和变参的区别,输入,输出的方式以及错误处理方式,理解算法的5个要素的确切含义:动态有穷性,确定性,有输入,有输出,可行性,掌握计算语句频度和估算算法时间复杂度的方法.

第二章线性表(4学时)

1.线性表的逻辑结构定义,抽象数据类型定义和各种存储结构的描述方法,

2.在线性表的两类存储结构上实现基本操作,

3.稀疏多项式的抽象数据类型定义,表示和加法的实现.

基本要求:

了解线性表的逻辑结构特性及计算机中表示逻辑结构的不同方法,掌握由不同方法得到的两类存储结构的描述方法,熟练掌握线性表在顺序存储结构上实现基本运算,掌握在各种链表结构中实现线性表操作的基本方法,能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合.

1.栈的结构特性及基本操作,

2.队列的结构特性及基本操作,

3.两种存储结构上如何实现栈和队列的基本操作,以及栈和队列在程序设计中的应用.

基本要求:

掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们,熟练掌握栈类型的两种实现方法,即两种存储结构表示时的基本操作实现算法,熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法,对学有余力的学生,可以理解递归算法执行过程中栈的状态变化过程,理解递归算到非递归算法的机械转化过程.

第四章串(2学时)

1.串的数据类型定义,

2.串的3种存储表示,

3.定长顺序存储结构,块链存储结构和堆分配存储结构,

4.串的各种基本操作的实现及其应用,串的模式匹配算法.

基本要求:

熟悉串的7种基本操作的定义,并能利用这些基本操作来实现串的其它各种操作的方法,熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法,掌握串的堆存储结构及在其上实现串操作的基本方法,了解串操作的应用方法和特点,对学有余力的学生,可以理解串匹配的KMP算法,熟悉NEXT函数的定义.

第五章数组和广义表(2学时)

1.数组的类型定义和表示方式,

2.特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现,

3.广义表的逻辑结构和存储结构,M元多项式的广义表表示以及广义表的操作的递归算法.

基本要求:

了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法,掌握对特殊矩阵进行压缩存储时的下标变换方式,了解稀疏矩阵的两种压缩存储方法的特点和适用范围,掌握广义表的结构特点及其存储表示方法.

第六章树和二叉树(8学时)

1.二叉树的定义,性质和存储结构,

2.二叉树的遍历和线索化以及遍历算法的各种描述形式,

3.树和森林的定义,存储结构,与二叉树树的转换,遍历,

4.树的多种应用.

基本要求:

熟练掌握二叉树的结构特性,了解相应的证明方法,熟悉二叉树树的各种存储结构的特点及适用范围,熟练掌握各种遍历策略的递归算法,能灵活运用遍历算法实现二叉树的其它操作,了解线索化的实质,熟练掌握二叉树树的线索化过程以及在中序线索化树上找给定结点的前驱或后继的方法,熟悉树的各种存储结构及其特点,掌握树和森林与二叉树树的转换方法,学会编写实现树的各种操作的算法,了解最优树的特性,掌握建立最优树和哈夫曼编码的方法.

第七章图(6学时)

1.图的定义和术语,

2.图的四种存储结构:数组表示法,邻接表,十字链表和邻接多重表,

3.图的两种遍历策略:深度优先搜索和广度优先搜索,

4.图的连通性:连通分量和最小生成树,拓扑排序和关键路径,

5.两类求最短路径问题的解法.

基本要求:

熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结构

和算法有密切联系,熟练掌握图的两种搜索路径的遍历,应用图的遍历算法求解各种简单路径问题.

第八章动态存储管理(2学时)

1.系统程序设计中采用的几种动态存储管理的策略和方法,

2.使用可利用空间表进行动态存储管理的分配策略,

3.操作系统中用以进行动态存储管理的边界标志法和伙伴系统,无用单元收集的标志算法.

基本要求:

深刻理解各种概念,了解本章所介绍的策略和算法.

第九章查找(6学时)

1.讨论静态查找表的各种实现方法,

2.讨论动态查找表的各种实现方法,

3.顺序表,有序表,树表和哈希表,

4.以及关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论.

基本要求:

熟练掌握顺序表和有序表的查找方法,并能灵活应用,熟悉静态查找树的构造方法和查找算法.理解静态查找树和折半查找的关系,掌握二叉衡树的构造方法和查找方法,掌握二叉树平衡树的维护平衡方法,理解B树和键树的特点以及它们的建树过程,掌握哈希表的构造方法,理解哈希表与其它结构的表的实质性的差别,熟练掌握描述查找过程的判定树的构造方法,以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度.

第十章内部排序(8学时)

讨论和比较各种内部排序方法:插入排序,交换排序,选择排序,归并排序和基数排序的基本思想,算法特点,排序过程以及它们的进间复杂度分析.

基本要求:

深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用,了解各种方法的排序过程及其依据的原则,掌握各种排序方法的时间复杂度的分析方法,理解排序方法"稳定"或"不稳定"的含义,弄清楚在什么情况下要求应用的排序方法必须是稳定的,了解"表排序"和"地址排序"的过程及其适用场合.

第十一章外部排序(4学时)

实现外部排序的基本方法,平衡归并排序中采取的策略.

基本要求:

熟悉外部排序的两个阶段和第二阶段——归并的过程,掌握外排过程中所需进行外存读/写次数的计算方法,了解败者树的建立过程,掌握实现多路归并的算法,熟悉置换——选择排序的过程,理解它能得到平均长度为工作区两倍的初始归并段的原因,熟悉最佳归并树的构造方法,理解缓冲区并行处理的过程,了解磁带多步归并的特点.

第十二章文件(2学时)

各类文件的构造方法,

文件操作的实现.

基本要求:

熟悉各类文件的特点,构造方法,掌握如何实现检索,插入和删除等操作.

三、实验教学内容与要求

实验一线性表的表示和实现(2学时)

实验目的与要求:了解线性表的顺序和链式存储和表示,熟练掌握编辑,编译,运行程序的一般步骤.

实验内容:1,启动TurboC,观察TurboC系统界面,了解菜单功能

2,启动VisualC++6.0,观察VisualC++6.0系统界面,了解菜单功能

3,在上述环境下编辑,编译,运行线性表程序

实验二队列和栈(2学时)

实验目的与要求:了解队列或栈的存储和表示,熟练掌握编辑,编译,运行程序的一般步骤.

实验内容:1,上机运行给定的队列或栈程序,分析,验证结果

2,分析给定的错误程序,改正并调试运行

实验三树和二叉树(2学时)

实验目的与要求:理解树和二叉树的原理和方法,掌握huffman树的基本用法.

实验内容:1,调试给定程序,分析,验证结果

2,分析给定的错误程序,改正并调试运行

实验四图(2学时)

实验目的与要求:熟练掌握图的有关定义和理论,熟练掌握最小生成树的2个常见算法.

实验内容:1,编写最小生成树的2个常见算法及程序,然后上机调试验证结果

实验五查找(2学时)

实验目的与要求:熟练掌握静态和动态查找的相关理论和技巧,熟练掌握各种查找方法.

实验内容:1,编写相关查找方法的算法和程序,并分析程序,然后上机调试验证结果

实验六排序(2学时)

实验目的与要求:熟练掌握各种排序方法的相关理论和技巧,熟练掌握各种查找方法.

实验内容:1,编写相关查找方法的算法和程序,并分析程序,然后上机调试验证结果

四、推荐教材及参考书

1,推荐教材:

1.《数据结构》(第二版C语言版)严蔚敏等清华大学出版社

2,参考书:

[1]徐绪松着《数据结构与算法导论》电子工业出版社

[2]谭浩强着.C程序设计(第二版).北京:清华大学出版社,1999

[3]杨薇薇编着.数据结构.武汉:华中科技大学出版社,1998