计算机软件技术基——复习.ppt

《计算机软件技术基——复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机软件技术基础复习第一章概论计算机的应用领域计算机语言的发展阶段软件的定义第二章常用数据结构及其运算数据结构及相关概念（数据元素、逻辑结构、物理结构，逻辑结构、物理结构有那些主要常见类型）算法分析——算法、算法复杂度线性表线性结构的定义与特征线性表的插入与删除操作（在两种存储结构下）顺序存储相对于链式存储结构的缺点顺序存储结构1.顺序存储结构2.顺序存储结构的插入运算3.顺序存储结构的删除运算链式存储结构链式存储结构基本运算1、前插2、后插3、删除前插基本运算算法后插基本运算算法DATA指针DATA指针DA

2、TA指针链表的删除基本运算①在链表中找到第i－1个结点②i结点指针域赋给i－1结点的指针域next(p)←next(next(p))③释放i结点特殊线性表——栈和队栈的定义和基本操作顺序栈1、判断栈空、栈满的条件2、进、出栈top的操作3、栈的基本运算链栈的结构及基本运算anan-1a1s[n-1]top栈顶进栈s[0]栈底出栈例有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列如图所示(假设以I和O表示进栈和出栈操作)。队队的定义访问算法顺序队1、基本操作：出队：f

3、ront＋＋入队：rear＋＋2、循环队列判断队空、队满的条件3、基本运算队的结构和运算——顺序队front：队头指针，指向队头元素之前rear：队尾指针，指向队尾元素循环队列队列为空front＝＝rearfront=rear+1队列已满链队带头结点的链表判断队空的条件：rear=front基本运算数组数组的两种顺序存储方式顺序存储地址公式下三角矩阵的地址公式稀疏矩阵的三元组表示和辅助向量的三元组表示Loc(aij)=Loc(a11)+(i-1)*n+(j-1)Loc(aij)=Loc(a11)+i(i−1)/

4、2+(j−1)非线性数据结构——树与二叉树树及其基本概念二叉树的定义二叉树的基本性质三种特殊形态的二叉树树与二叉树的转换图一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后一般树转换为二叉树二叉树的遍历先序、中序、后序二叉排序树性质、生成哈夫曼树路径长度、带权路径长度、哈夫曼树的生成、哈夫曼编码ACBDEFGHABDGECFHDGBEAFHCGDEBHFCA查找评价查找算法好坏的依据——平均查找长度顺序查找对分查找分块查找二叉排序树查找平均查找长度和什么有关查找方法的比较1、相同

5、之处:都适合于以向量作存储结构的线性表2.不同之处：⑴平均查找长度：顺序查找＞分块查找＞对分查找⑵表的结构：顺序查找对有序表、无序表均可对分查找仅适合于有序表分块查找要求逐段有序⑶存储结构：顺序查找分块查找对分查找只适合于向量，不适合于链表排序衡量排序算法效率的方法——比较次数和移动次数选择排序简单选择排序堆排序1、堆2、构造堆排序插入排序冒泡排序快速排序基本思路第3章操作系统操作系统的类型：特点多道批处理系统、分时系统、实时系统操作系统的功能：基本部分中央处理器管理、存储管理、设备管理、文件管理及用户接口。存

6、储管理存储管理的功能内存分配地址转换：静、动态地址重定位的区别存储保护内存扩充实存储管理分区分配固定分区可变分区：寻找空闲区的算法——最先、最佳、最差适应算法可重定位分区覆盖技术交换技术虚拟存储管理分页存储管理地址转换页面更换：先进先出法、最近最少使用法例在某个分页管理系统中，某一个作业有4个页面，被分别装入到主存的第3，4，6，8页架中，假定页面和页架大小均为1024字节，当作业在CPU上运行时，执行到其地址空间第500号处遇到一条传送命令MOV2100，3100请用地址变换计算出MOV指令中两个操作数的物理

7、地址。解答逻辑地址2100页号为2，页内位移为523100页号为3，页内位移为28段式、段页式存储管理基本思路优、缺点处理器管理基本术语：作业、作业步、进程作业调度：作业状态转换作业调度算法：先来先服务、优先级法进程调度：进程的状态及转换调度算法：先来先服务、短进程优先、优先级调度、轮转调度法进程的同步与互斥进程的同步进程互斥临界区P-V操作死锁死锁的定义必要条件死锁的预防死锁的避免：安全状态的判断设备管理设备分类按使用方法：绝对设备号、相对设备号缓冲技术的目的、缓冲区的位置假脱机系统的目的