自15计算机软件基础复习纲要(1).doc

自1501-02计算机软件基础_复习纲要2017-6-22第二章 线性数据结构1理解算法的时间复杂度和空间复杂度的含义，能够从算法的C语言程序说明算法的功能，并能评价C语言程序所表示算法的复杂度。2掌握线性数据结构的顺序和链式存储方法原理和基本查找算法的程序；能够写出查找指定元素位置的C程序，和计算链表元素个数的C程序。能够画出用链表表示的多项式结构示意图，并能够画出链表表示的多项式加减法运算的结构示意图。3栈和队列掌握栈的原理，能够画出数据动态进出栈情况下栈内数据的存储示意图。能够画出并整理特定出栈或进栈情况下的进栈或出栈序列。4数组和矩阵掌握矩阵的两种存储方式（行优先和列优先），能够画出给定稀疏矩阵的三元组表或由特定的三元组表画出对应的稀疏矩阵。第三章 非线性数据结构1. 二叉树:（1）掌握二叉树前序、中序和后序三种遍历方法，即能写出二叉树三种递归遍历算法的C程序，也能写出给定二叉树三种遍历方法的遍历结果。 （2）能够在二叉树前序、中序和后序三种递归遍历算法的C程序基础上，写出对二叉树中不同结点数量进行统计的C程序。 2. 霍夫曼树和霍夫曼编码:能够按指定的字符集和所表示的文本，画出该字符集的霍夫曼树，给出该字符集的霍夫曼编码二进制前缀编码，并给出（画出）编码过程。3. 图及其基本概念：掌握无向图和有向图的邻接矩阵求法，并会求各顶点的度（有向图包括顶点的出度和入度），能够根据指定的图，求出其邻接矩阵和邻接表。能够根据邻接矩阵或邻接表画出图（包括无向和有向图）。能够根据图和对应的邻接表写出按深度优先搜索法和广度优先搜索法，从指定顶点出发对该图进行遍历的遍历结点序列。能够画出按深度优先搜索法和广度优先搜索法对指定图进行遍历的生成树。第四章 查找与排序技术1掌握顺序表查找、折半查找和分块查找的基本原理，能够计算顺序表查找和u2二叉排序树：掌握二叉排序树的构造原理，能够按给定的关键字序列构造二叉排序树，并能够计算等概率情况下查找成功的平均查找长度。3哈希查找：在给定哈希函数和哈希存储空间长度的情况下，可以为指定的关键字序列创建哈希掌存储表（需要计算过程），能够按“开放定址法”（包括线性探测再散列和二次探测再散列）和“链地址法”给出指定序列哈希查找等概率情况下对该哈希表进行查找时查找成功的平均查找长度。4排序（1）掌握五种排序的方法，能够给出指定序列的五种排序算法的每一趟排序结果。（快速排序算法能够写出一趟排序一次划分结果即可）。（2）理解直接插入排序、简单选择排序和冒泡排序算法的C程序。能够分析给的C程序的排序方法。第五章 操作系统原理1进程的三种状态和它们间的转换关系：进程除了有书上说的三种状态外，运行中的进程在完成自己的任务后，还可以直接消亡。因此实际上进程可以在四种状态中转换，如下图示：消亡任务完成等待的事 件未发生运行就绪等待调度 时间片用完等待的事 件未发生等待的事件已发生2存储管理：掌握存储器段式管理的逻辑地址到物理地址的换算方法，会判断逻辑地址是否越界。第五章作业题P154，第16题根据进程对主存地址的访问序列，可以求出页面访问序列，并求出该访问序列在FIFO置换算法下的页面失效率。第五章作业题P154，第17题3磁盘设备管理：给定磁道的请求序列，能够按（1）FCFS、（2）SSTF和（3）SCAN三种调度策略求出磁头的移动顺序和磁头移动的磁道数量。第五章作业题P154，第18题第六章 数据库技术基础第七章 关系数据库系统 掌握并能够写出SQL语言对表中记录进行插入、删除和修改的完整语句；掌握并能够写出用SQL语言的SELECT语句进行简单和连接查询的完整语句。（从三个表按指定的条件和所需结果进行查询的完整语句）