计算机软件技术基础知识要点.doc

计算机软件技术基础知识要点wwb19920406呕心整理 收到的记得粉我哦第1章 信息与计算机1、 信息是经过加工的数据。2、 数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。3、 信息与数据的关系信息是有一定含义的数据 信息是经过加工（处理）后的数据信息是对决策有价值的数据4、 信息的基本属性（1） 事实性 （2）等级性 （3）可压缩性 （4）可扩散性 （5）可传输性（6） 共享性 （7）增值性与再生性 （8）转换性5、 信息的三种层次数据采集数据 数据处理信息 信息融合知识6、 信息化是社会经济发展的必然结果，表现在：自然科学领域社会科学领域1） 信息科学的巨大发展2） 信息技术的长足进步3） 社会生产力的需求4） 信息需求已成为普遍的社会需求7、 信息时代的特点市场环境变化巨大 机遇与挑战并存 风险与效益并存多媒体、全球互联网络、信息高速公路8、 计算机的主要特点（1） 高速自动的操作功能 （2）具有记忆能力（3）可以进行各种逻辑判断 （4）精确高速的计算能力9、计算机的发展阶段第一代 20世纪40年代50年代末 电子管第二代 20世纪50年代末60年代前 晶体管第三代 20世纪60年代中70年代前 集成电路第四代 超大规模集成电路从应用角度 60年代 大型机；70年代 小型机； 80年代 个人机；90年代 全球网络10、 数字化信息的特点 容易交换，只要有传播媒体，即可畅通无阻，无处不达。 可以大容量 高速度传输以满足人们对信息的需求 稳定性高，传输途中不受干扰，可以原原本本还其本来面貌11、 计算机的应用领域科学研究与科学计算 事务处理 计算机辅助功能 生产过程控制人工智能 计算机网络通信 计算机教育 多媒体12、 计算机面临的挑战建立未来的应用 管理企业的应用 新的电子商务的应用 解决人机文化的差异13、 系统 定义：为完成特定任务而由相关部件或要素组成的有机整体称为系统特点：整体性 层次性 适应性 运算器 控制器硬件系统说 存储器 输入设备 输出设备硬件与软件结合说广义系统说 人员 数据 设备 程序 规程CPU内存储器（主存）外存储器（辅存）14、计算机系统15、 硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备软件：指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据16、 微型计算机的硬件系统主机：中央处理器 内存储器外存储器：磁盘 光盘输入设备：键盘鼠标 图形扫描仪 光笔输出设备：显示器 打印机 绘图仪微机的系统总线：数据总线 地址总线 控制总线17、 微型计算机的软件系统系统软件：操作系统 编译程序 诊断程序 系统服务程序 语言处理程序数据库管理系统 网络通信管理软件应用软件：为特定需要开发的实用程序 为方便用户使用而提供的软件硬件、软件的关系：1)互相依存 2）无严格界面 3）互相促进多媒体基本要素：文本 图形 图像 动画 声频 视频18、 软件技术阶段60年代 高级语言阶段70年代 结构程序设计阶段80年代至今 自动程序设计阶段程序设计方法论 由顶向下法 自底向上法自动程序设计方法 快速原型法 甚高级语言法 软件可重用法19、 第一代语言 19461950 机器语言第二代语言 19501960 汇编语言第三代语言 19601980 过程化编程语言第四代语言 19801995 非过程化编程语言第五代语言 1995 应用程序开发用专家系统第2章 常用数据结构及其运算1、 数据：信息的载体、可以用计算机表示并加工。 数据元素：数据集合中的一个个体，是数据的基本单位。 数据对象：具有相同性质的数据元素的集合称为数据对象 数据结构：指同一数据对象各数据元素间存在的关系。 S=(D,R) 数据类型：指程序设计语言中允许的变量类型2、 时间复杂度： O(1):常量型 O(n),O(n2)O(nk) 多项式型 O(log2n),O(nlog2n) 对数型 O(2n),O(en) 指数型 空间复杂度3. 线性表是数据元素的有序数列 L=(D,R)D=a1,a2,an R=|ai-1,aiD，2in若aiai-1 i=2,3,n 为有序表 否则为无序表基本运算： 插入、删除、查找、排序删除算法DELETELIST (V,n,i)1. if(in) then 参数错return2. for j=i to n-13. VjV j+1 4. end(j)5. V i x6. nn-17. return4、 插入算法INSERTLIST(V,n,i,x)1. if(in+1) then 参数错return2. for j=n to i step (-1)3. Vj+1V j 4. end(j)5. V i x6. nn+17. Return5、 运算时间插入 移动次数平均值 Ein= 等概率 Pi=1/(n+1) 有 Ein=1/(n+1)=n/2删除 移动次数平均值 Ede=等概率 qi=1/n 有 Ede=1/n =(n-1)/2datanext6、 链式存储结构元素：数据域 指针域 a7、 基本运算 指针赋值：sp qnext(p) 指针移动：pnext(p) 后插：next(s)next(p) next(p)p 前插：qhead While(next(q)p) do qnext(q) Next(q)s next(s)p回收一个接点 指针指向p 算法RET(P)1. next(p)av2. avp3. return8、获取一个接点 指针指向p 算法GETNODE(P)1. pav2. avnext(av)3. Return插入运算INLINKST (head,a,b)1. GETNODE(p); data(p)b2. If(head=nil) then headp; next(p)nil,return3. If(data(head)=a) then next(p)head,headp,return4. LOOKFOR (head,a,q)5. Next(p)next(q);next(q)p6. Return删除运算DELINKST(head,a)1. if (head=nil) then 空表 return2. If (data(head)=a) then snext (head);RET(head);heads;return3. LOOKFOR(head,a,q)4. If (next(q)=nil then 无此结点 return)5. pnext(q);next (q)next(p)6. RET(p)7. Return线性链表其他形式 1）循环链表 2）双向链表9、重点 一元多项式相加 p32e.g.设有一元多项式A（x）和B（x）,要求其相加结果C（x）=A（x）+B（x）ADD-POLY (hA,hB)1. pnext(hA);qnext(hB)2. PrehA;hChA3. While (pnil) AND (qnil ) do4. Case5. EXP(p)EXP(q)6. Prep;pnext(p)7. EXP(p)=EXP(q)8. xCOEF(p)+COEF(q);9. If (x0）then COEF (p)x;prep10. else next (pre)next(p);RET(p)11. pnext(pre);uq;qnext(q);RET(u)12. EXP(p)EXP(q)13. unext(q);next(q)p;next(pre)q;preq;qu14. end(case)15. end(while)16. If (qnil) then next(Pre)q17. RET(hB)18. return退栈算法POP（s,top,y）1. if （top=0） then 下溢，return2. ysstop3. toptop-14. return10、 栈 限定只能在表的一端进行插入和删除操作的线性表。允许插入或删除的一段成为栈顶，另一端称为栈底进栈算法PUSH（s,m.top,x）1. if （top=m） then 上溢，return2. toptop+13. sstopx4. return删除队算法DELLINK(front,rear,y)1. If(rear=front) then队空 return2. ydata(next(front);next (front)next(next(front)3. If(next(front)=nil) then rearfront4. return11、 队 是不同于栈的另一种特殊的线性表，他只允许在一端进行插入在另一端进行删除。插入队算法ADDLINK(rear,front,x)1. GETNODE(p)2. data(p)x;next(p)nil3. Next(rear)p;rearp4. return 12、重点 三元组 P46用一个具有三个数据域的一位数组表示稀疏矩阵没方三个字段组成（行下标 列下标 值）13、 树 由n个（n0）结点的有限集合T 有且仅有一个结点称为根结点，其余接点称为根节点的子树。N=0时 为空树。14、 二叉树 B-T=(D,R)二叉树的基本性质（1） 二叉树的第i层上至多有2i-1（i1）个结点（2） 深度为h的二叉树中至多含有2h-1个结点（3） 在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+115 .重点 一般树转换为二叉树 P5616 .重点 哈夫曼树 p60从树中一个结点到另一个结点之间的分支数目称为这对节点之间的路径长度（PL）PLlog2k 最短路径长度 PL=log2k 完全二叉树带权路径长度：WPL=wklk17.重点 构造哈夫曼树 P61、p6218、图 是由顶点集合V顶点之间关系集合R组成 记作 G=(V,R)重点 图的应用求单源最短路径 P73拓扑排序 AOV网 P75关键路径 AOE网 P77P7819、 查找线性查找对分查找分块查找二叉排序树查找哈希表技术及其查找20、 构造哈希函数的方法（1） 数字分析法（2） 平方取中法（3） 除留余数法（4） 折叠法 移位折叠、边界折叠解决冲突的方法（1） 线性探测再散列（2） 平方探测再散列（3） 随机探测再散列（4） 链地址法21、 排序选择排序 ：简单选择排序 、堆排序插入排序 ：线性插入排序 、对半插入排序交换排序 ：冒泡排序、快速排序第3章 操作系统1、 操作系统的发展过程1) 手工操作阶段 2）早起批处理阶段（联机 脱机） 3） 执行系统阶段 4）多道程序阶段2、 操作系统的分类多道批处理操作系统、分时系统、实时系统3、 操作系统的功能处理器管理、存储管理、设备管理、文件管理、用户接口（程序一级的接口作业控制语言和操作命令）4、 操作系统的特性 共享性、并发性、不确定性5、 三级存储器：高速缓存存储器、主存储器、外部存储器6、 存储管理的功能内存分配地址空间和存储空间重定位（动态、静态）地址转换或重新定位存储保护内存扩充7、实存储管理分区分配：固定分区分配、可变分区分配（空间分配、空间回收）、空闲区分配算法（首次适应算法、最佳适应算法、最差适应算法）可重定位分区分配：碎片问题和存储区的紧缩、程序浮动和重定位覆盖技术 交换技术8、 虚存储管理分页存储管理、分段存储管理、段页式存储管理先进先出法缺页中断率 f=最近最少使用法9. 分页管理 优点不要求作业在内存中连续存放，较好地解决了碎片问题。作业地址空间不受内存的限制，对一些不常用的部分不必常驻内存，为用户提供足够大的存储空间，从而更有利于多道程序作业。缺点要求一定的硬件支持、增加了成本系统要增加页表及其管理程序，因而增加了内存的开销，同时CPU要占有一定时间来处理页面交换。10、 分段管理优点便于程序模块化处理 便于处理化的数据 便于共享分段缺点增加硬件成本，为地址变换花费CPU时间 为表格提供附加的存储空间。大小受到主存的限制，由于段的长度不固定，又会出现“碎片问题”，处理机要为存储器的紧缩付出代价。11、 段页式管理优点：具有分页分段的管理的优点 应用最广泛、最灵活。缺点：需要更多的硬件支持，增加了硬件成本，同时也增加了软件复杂性和管理开销。12、 时间局部性：当程序中某个地址最近被访问了，那么往往很快又被再次访问。空间局部性：当程序中某个地址最近被访问了，那么它附近的地址也会被访问。13、 处理器管理作业：用户在一次算题过程中或一个事务处理中要求计算机系统所做工作的集合作业步：一个作业是由一系列有序的作业步所组成。14、 指令：特权指令 只能由操作系统使用 非特权指令 供一般用户使用15、 执行状态 管态（主态 执行状态） 目态（算态 题目状态）16、 作业调度（宏观）分为提交、收容、执行、完成 四个状态。作业控制块 作业调度算法 1）先来先服务算法 2）基于优先级的调度算法 【优先数=（等待时间）2-（要求运行时间）-（输出量）】 3）分时和优先级相结合的作业调度17、 进程调度（微观）分为就绪、运行、阻塞状态作业控制块进程控制 原语 ：创建原语 挂起原语 激活原语 撤消原语进程调度算法：1）优先数法 2）轮转调度法 3）分级调度法18、 多道