2022年《计算机软件技术基础教案》

1、精品word 名师归纳总结 - - - - - - - - - - - -Teaching PlanFor“Basis of Software of Computer”ByZhonghua LiangDepartment of Communication Engineering, School of Information Engineering,Chang an University, Xi an, 710064, People sRepublic of ChinaDate of Creation: September 19, 2021精选名师 优秀名师 - - - - - - - - -

2、-第 1 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -Teaching Program（教学大纲）一本课程的性质和任务本课程是通信工程专业的一门重要基础课程；其任务为通过对软件工程、数据结构、操作系统和数据库等方面的基本概念及基本技术的学习和把握，使同学对运算机软件有比较深化、系统的明白，为将来能够娴熟地编写比较复杂的应用程序打下坚实的基础；二本课程的基本要求1对才能培育的要求1). 软件开发方法和技术 ：要求同学学习和把握软件的基本概念，软件的研制过程、软件工程概述、软件设计方法、程序结构、算法描述工具，如

3、流程图和算法语言；2). 数据结构 ：要求同学学习和把握数据结构的基本概念与原理、线性表、次序储备结构和链式储备结构、算法实现、数 组、栈、队列、树等；3). 操作系统 ：要求同学学习和把握操作系统的基本概念与原理、操作系统供应的接口、进程与进程治理、多道程序技术、同步与互斥、内存治理、设备治理、文件系统的原理、文件的使用；4). 数据库技术 ：要求同学学习和把握数据库的基本概念与原理、数据模型、关系数据库；精选名师 优秀名师 - - - - - - - - - -第 2 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - -

4、 - -5). 网络及数据安全技术 ：要求同学学习和把握网络及数据安全技术的基本概念与原理；2重点和难点1). 本课程的重点：其次章数据结构；2). 本课程的难点 ： a线性链表； b树、图的遍历；c查找、索引和排序技术运算及其应用；3先修课程：运算机基础； C 语言；三课程内容1理论学问：（ 22 学时）1). 运算机软件概述 ：运算机软件的基本概念、程序设计技术、数据结构的基本概念及术语、算法描述及算法分析初步；2). 线性表：线性表的规律结构、线性表的次序储备结构、线性表的链式储备结构、表的基本运算在特定储备结构中的实现及应用；3). 栈和队列 ：栈的定义、表示和实现、栈的应用、队列的定

5、义、表示和实现、队列的应用；4). 树：树的定义和基本操作、二叉树定义和表示、遍历二叉树和线索二叉树、树和森林、哈夫曼树及其应用；5). 串和图 ：串及图的定义、表示和操作、储备结构图的遍历；6). 查找和排序：查找和排序及其运算的基本学问和算法；精选名师 优秀名师 - - - - - - - - - -第 3 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -7). 操作系统 ：学习和把握操作系统的基本概念与原理、操作系统供应的接口、进程与进程治理、多道程序技术、同步与互斥、内存治理、设备治理、文件系统的原理、文

6、件的使用；8). 数据库 ：学习和把握数据库的基本概念与原理、数据模型、关系数据库、SQL语言；9). 运算机网络 ：学习和把握运算机网络体系结构、网络互联与互联网、网络安全及防火墙技术、运算机病毒及防治；10). 软件工程：学习和把握软件开发与技术，要求同学学习和把握软件的基本概念，软件的研制过程、软件工程概述、软件设计方法、程序结构、算法描述工具，如流程图和算法语言；2课外作业：加深对课内所学的理论学问的懂得，锤炼分析问题和解决问题的才能；3 上机试验：环绕本课程学习的重点和难点，实践理论学问，上机完成题目（8 学时）；4考核方式：考核成果主要依据：同学平常听课、完成作业 情形20% ；上

7、机试验、完成试验报告20% ；期末考试成果 60% 来综合评定；四课程教材及主要参考书1课程教材：1.运算机软件技术基础第三版，沈被娜等编著，清华高校出版社；2教学参考书：精选名师 优秀名师 - - - - - - - - - -第 4 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -1. 运算机软件技术基础，庞丽萍编，华南理工高校出版社；2.OperatingSystems-DesignandImplementation ， Second Edition, Andrew S, Tanenbaum, Albert

8、 S. Woodhull, 清 华 大 学 出 版 社 和PRENTICE HALL.3.SoftwareEngineering-APractitionersApproach， FourthEdition,Roger,S.Pressman,机械工业出版社和McGraw-Hill.4. DataStructureAlgorithms,andApplicationsinC+ ， FirstEdition,McGraw-Hill.SartajSahni,机械工业出版社和第 1 章算法1算法的基本概念1). 算法的基本特点 ：(1). 能行性 effectivenessa). 算法中的每一个步骤必需能

9、够实现，例如在算法执行中，分母不能为零，实数范畴内不能求一个负数的平方根等等；b). 算法执行的结果要能够达到预期目的，例如需要考虑运算精度的影响；(2). 确定性 definiteness精选名师 优秀名师 - - - - - - - - - -第 5 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -算法中的每一个步骤都必需是有明确定义的，不答应有模棱两可的说明或多义性；(3). 有穷性 finiteness算法必需能在有限的时间内昨晚，运算法必需能在执行有限个步骤后终止；例如无穷级数的运算只能是依据精读要求取

10、有限项的有穷运算；假如一个算法需要执行千万年，就失去了有用价值；3. 拥有足够的情报（sufficient information）通常算法中的各种运算总是要施加到各个运算的对象上，而这些对象又可能具有某种初始状态，这是算法执行的起点或依 据；因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出；当输入不够或输入错误时，算法本身也就无法执行或导致执行有错；一般来说，当算法拥有足够的情报时，此算法才是有效的，而当情报不够时，算法并不有效；综上所述 ：所谓算法，是一组严谨地定义运算次序的规章， 并且每一个规章都是有效的，且是明确的，此次序将在有限的次数下终止；2). 算

11、法的基本要素 ：(1). 对数据对象的运算和操作：a). 算术运算，加、减、乘、除等运算；b). 规律运算，“与”、“或”、“非”等运算；精选名师 优秀名师 - - - - - - - - - -第 6 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -c). 关系运算，“大于”、“小于”、“等于”、“不等于”等运算；d). 数据传输，主要包括赋值、输入、输出等操作；留意：运算机程序仅作为算法的一种描述；但通常不直接用运算机程序来描述算法，而是用别的描述工具（如流程图、特地的算法描述语言，甚至自然语言）来描述算法；

12、(2). 算法的掌握结构：一个算法的功能不仅取决于所选用的操作，而且仍与各操作之间执行次序有关；算法中各操作之间的执行次序称为算法的控制结构；一个算法一般可以用次序、挑选、循环3种基本的掌握结构组合而成；2算法设计基本方法1). 列举法：举例白鸡问题，画出搜寻空间的立体示意图；2). 归纳法：基本思想和本质（抽象）；3). 递推法：本质（归纳法）；4). 递归法：基本思想（逐层分解）；基础（归纳）；5). 减半递推法 ：又称为分治法；“减半”是将问题的规模减半；“递推”是指重复“减半”；举例：矩阵相乘；二分法求实根；6). 回溯法：基本思想（“试”），处理复杂数据结构方面有广泛应用；举例：求解

13、皇后问题，用方格图 讲解；精选名师 优秀名师 - - - - - - - - - -第 7 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -3算法的复杂度分析1). 算法的时间复杂度 ：所谓算法的时间复杂度，是指执行算法所需要的运算工作量；可用算法在执行过程中所需基本运算的执行次数来度量算法的工作量；算法的工作量用算法所执行的基本运算次数来度量，而算法所 执行的基本运算次数是问题规模的函数（see page 10）；在同一问题规模下，假如算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法

14、的工作量：(a) 平均性态（ average behaviour）分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量（定义，see page 10）；(b) 最坏情形复杂性（worst-case complexity）分析是指在规模为n时，算法所执行的基本运算的最大次数（上界），更具使用价值（定义，see page 10）；两者的分析比较举例（例1.5, see pages 10-11）；留意 ：本小节最终一段的论述（提及算法的工作量与输入无关时的情形）；2). 算法的空间复杂度 ：一般是指执行这个算法所需要的内存空间；一个算法所占用的储备空间包括算法程序所占的空间， 输入的

15、初始数据所占的储备空间以及算法执行过程中所需要的额外空间；其中额外空间包括算法程序执行过程中的工作单元精选名师 优秀名师 - - - - - - - - - -第 8 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -以及某种数据结构所需要的附加储备空间（例如在链式结构中，除了要储备数据本身外，仍需要储备连接信息）；4习题讲解及作业布置： 举例讲解： 1.1 、 1.3 ；第一次上机试验：1.2 、1.4 、1.5三题中任选2题（三题难度系数分别为1.0, 1.0, 1.2）；第 2 章数据结构及其运算1数据结构的

16、基本概念数据结构作为运算机的一门学科，主要争论以下三个方面的问题：(a). 数据集合中各数据元素之间所固有的规律关系，即数据的规律结构；(b). 在对数据进行处理时，各数据元素在运算机中的储备关系，即数据的储备结构；(c). 对各种数据结构进行的运算；争论以上各问题的主要目的是为了提高数据处理的效率；所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度；二是尽量节约数据处理过程中所占用的运算机储备空间；精选名师 优秀名师 - - - - - - - - - -第 9 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - -

17、- - - -1.两个实例 ： a.无序表和有序表的查找效率对比；b.学生情形登记表； 1.数据结构的定义 ：相互有关联的数据元素的集合； a.数据元素的含义；b.前后件关系；(1). 数据的规律结构：反映数据元素之间规律关系的数据结构；两个要素：一是数据元素的集合D ；二是D上的关系R ；一个数据结构可以表示为B=D,R；举例（seepage 18 ）更正： page18中最终一行和page19中第一行： D i 应改为Ai；(2). 数据的储备结构（物理结构）：数据的规律结构在运算机储备空间中的存放形式；常用的储备结构：次序；链接；索引；3. 数 据 结 构 的 图 形 表 示 ： 直 观

18、1. 需要懂得的概念名词：根节点；终端结点；内部节点；(2). 数据结构的基本运算：插入和删除；其它运算仍有：查找分类合并分解复制和修改等；(3). 数据结构中依据各数据元素之间前后件关系的复杂度，一般将数据结构分为：线性结构和非线性结构；一般来说，假如一个非空的数据结构满意两个条件：a 有且只有一个根节点；b 每个节点最多有一个前件，也最多只有一个后件；就称该数据结构为线性结构，又称线性表；精选名师 优秀名师 - - - - - - - - - -第 10 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -此外：

19、在插入或删除任何一个节点后仍应当满意上述条件；2线性表及其次序储备结构1). 线性表及其运算 ：(1). 什么是线性表 a. 需要懂得的概念名词：记录；文件；b. 非空线性表的结构特点（see page 22）；(2). 线性表的次序储备结构(a). 基本特点：（ see page 22）；(b). 初始化线性表的次序储备空间（seepage23 ）， new和delete语句成对使用的习惯：申请空间-释放空间；(c). 线性表的主要运算：（see page 23）(3). 线性表在次序储备下的插入运算：例2.7(a). 插入前后两线性表中的元素关系（see page 24）(b). 平均移动

20、元素数量的运算：0+1+n/n+1=n+10+n/2/n+1=n/2(c). 由于 C+ 中数组下标从0开头，涉及到数组下标的变量均要减去 1 ；(4). 线性表在次序储备下的删除运算 a. 删除前后两线性表中的元素关系（see page 26） b. 平均移动元素数量的运算：精选名师 优秀名师 - - - - - - - - - -第 11 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -0+1+n-1/n=n0+n-1/2/n=n-1/2更正： page26中最终一行应改为：认为删除第 n+1 个元素，即无此

21、元素；(5). 次序表类将次序表的数据和基本操作（包括初始化、输出、插入和删除）封装成类；更正： page30中其次段应当为：假如次序表非空，就调用2). 栈及其应用：(1). 什么是栈（ stack ）：一种特别的线性表，其插入和删除都只在线性表的一端进行，即一端封闭，另一端开口；概念名词：栈顶（top ）；栈底（ bottom ）；入栈（ push ）；退栈（ pop ）(2). 栈的次序储备及其运算：see page 33-34留意：程序中数组下标减一的操作； 3. 次序栈类4. 表 达 式 的 计 算4. 递 归 的 实 现3. 队列及其应用 ：1. 什么是队列（queue ）：一种特

22、别的线性表，答应在一端进行插入，而在另一端进行删除；FIFO or LILO精选名师 优秀名师 - - - - - - - - - -第 12 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -概念名词：排头指针（front ）；队尾指针（rear ）；入队运算；退队运算 2. 循环队列及其运算：see page 42-43 3. 循环队列类4. 队列的应用： a. 安排工作； b. IO缓冲区； c.加油模拟3线性链表及其运算1). 线性链表的基本概念 ：(1). 线性表的次序储备结构的缺点：a. 插入或删除线性

23、表中元素过程中需要移动大量数据元素；b. 储备空间不便于扩充；c. 不便于对储备空间的动态安排；(2). 链式储备方式中的储备结点构成：a. 数据域； b. 指针域(3). 线性链表：线性表的链式储备结构；(4). 基本概念： a.Head指针； b.NULL或 0； c. 线性单链表； d.线性双向链表；e. 左指针（ Llink ）； f.右指针（ Rlink ）(3). 线性链表类(4). 链栈及其基本操作：a. 初始化； b.入栈； c. 退栈； d.读栈顶元素；(5). 链队及其基本操作：a. 初始化； b.入队； c. 退队；精选名师 优秀名师 - - - - - - - - -

24、-第 13 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -2). 线性链表的基本运算 ：1. 插入：在指定元素的结点之前插入一个新元素；2. 删除：删除包含制定元素的结点；(3). 合并：将两个线性链表按要求合并为一个线性链表；(4). 分解：将一个线性链表按要求进行分解；5. 逆转； 6. 复制； 7. 排序； 8. 查找；3). 循环链表：为了克服对空表与非空表运算的不统一问题；(1). 增加一个表头结点：其数据域为任意或依据需要来设置，指针域指向线性表的第一个元素的结点；(2). 最终一个结点的指针域不是

25、空（NULL ），而是指向表头结点；即在循环链表中，全部结点的指针域构成了一个环状链；3. 多项式的表示与运算 ：略4数组二维数组：矩阵在程序设计语言中的表示；程序设计语言中的数组在运算机中是次序储备的；当矩阵中的绝大部分元素为零时，采纳一般的两维数组储备方式会铺张大量的储备空间，同时也做了大量不必要的运算；1. 数组的次序储备结构 ：1. 二维数组以行为主的次序储备：逐行、从左至右的次序；精选名师 优秀名师 - - - - - - - - - -第 14 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -ADRa

26、 ij=ADRa11 +i-1n+j-1L, where 1 i m, 1 j nBASIC、C 中的多维数组采纳以行为主的次序储备； 2. 二维数组以列为主的次序储备：逐列、从上至下的次序；ADRa ij =ADRa 11 +j-1m+i-1L, where 1 i m, 1 j nFORTORA中N 的多维数组采纳以列为主的次序储备；2. 规章矩阵的压缩(1). 下三角阵（ lower triangular matrix）；(2). 对称阵（ symmetrical matrix）；(3). 三对角阵（ tridiagonal matrix）；3. 一般稀疏矩阵（sparse matrix

27、）的表示(1). 三列二维数组：a. 矩 阵 的 大 小 总 行 数 （ numberofrows） 和 总 列 数（ number of columns）；b. 非零元素的位置（行号和列号）；c. 非零元素的值；d. POS和 NUM ；e. 操作：生成；输出；转置；相加；相乘；(2). 线性链表：(3). 十字链表： （自学，不考）精选名师 优秀名师 - - - - - - - - - -第 15 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -5树与二叉树1). 树的基本概念：一种简洁的非线性结构；1. 基

28、本概念： a.父结点； b.子结点； c.根； d.度； e.树的度； f. 叶子结点2). 二叉树及其基本性质：一种有用的非线性结构（binary tree ）1. 特点： a.非空二叉树只有一个根结点；b.每个结点最多有两颗子树（称为左子树和右子树）；2. 基本性质： 1 ， 2， 3， 4， 5， 63. 遍历： a. 前序遍历； b. 中序遍历； c. 后序遍历；6图（自学，不考）7习题讲解及作业布置： 举例讲解： 2.1 0；第一次作业： 2.5 、2.6 、2.8其次次试验：2.9 、 2.13 中选1题 ； 2.10 、 2.11 、2.12 、2.14 中选 1 题（各题难度系

29、数均为1.0 ）；其次次作业：2.15 、 2.16 、 2.17 中选1题 ； 2.20 、2.21 、2.22 精选名师 优秀名师 - - - - - - - - - -第 16 页，共 19 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -第 3 章查找与排序技术1基本的查找技术基本概念：所谓查找是指在一个给定的数据结构中查找某个指定的元素；通常依据不同的数据结构，采纳不同的查找方 法；1). 次序查找 ：次序搜寻；从线性表的第一个元素开头，依次比较，结果为找到或失败；平均搜寻比较次数为n/2 ；以下两种情形下必需使用次序查找：a.无序表； b. 链式储备结构；2). 对分查找：适用于有序表；3). 分块查找 ：索引次序查找；分块有序表的结构：a.线性表本身采纳次序储备结构；b.建立一个索引表