《计算机软件技术基础》知识要点

《《计算机软件技术基础》知识要点》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》知识要点（13页珍藏版）》请在装配图网上搜索。

1、计算机软件技术基础知识要点wwb19920406呕心整理收到的记得粉我哦一第一章信息与计算机1、信息是经过加工的数据。2、数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看 到的景象。3、信息与数据的关系信息是有一定含义的数据信息是经过加工（处理）后的数据信息是对决策有价值的数据4、信息的基本属性（1）事实性（2）等级性（3）可压缩性（4）可扩散性（5）可传输性（6）共享性（7）增值性与再生性（8）转换性5、信息的三种层次数据采集一一数据 数据处理信息信息融合一一知识6、信息化是社会经济发展的必然结果，表现在：1） 信息科学的巨大发展自然科学领域社会科学领域2）信息技术的长足进

2、步 I3）社会生产力的需求4）信息需求已成为普遍的社会需求7、信息时代的特点市场环境变化巨大机遇与挑战并存风险与效益并存多媒体、全球互联网络、信息高速公路8、计算机的主要特点（1）高速自动的操作功能（2）具有记忆能力（3）可以进行各种逻辑判断（4）精确高速的计算能力9、计算机的发展阶段第一代 20世纪40年代50年代末 电子管第二代 20世纪50年代末60年代前 晶体管第三代 20世纪60年代中70年代前 集成电路第四代 超大规模集成电路从应用角度60年代 大型机；70年代 小型机；80年代 个人机；90年代 全球网络10、数字化信息的特点 容易交换，只要有传播媒体，即可畅通无阻，无处不达。

3、可以大容量高速度传输以满足人们对信息的需求 稳定性高，传输途中不受干扰，可以原原本本还其本来面貌11、计算机的应用领域科学研究与科学计算事务处理计算机辅助功能生产过程控制人工智能计算机网络通信计算机教育多媒体12、计算机面临的挑战建立未来的应用管理企业的应用新的电子商务的应用解决人机文化的差异13、系统定义：为完成特定任务而由相关部件或要素组成的有机整体称为系统 特点：整体性层次性适应性CPU运算器控制器一14、计算机系统硬件系统说2存储器二内存储器（主存） 输入设汀 外存储器（辅存） 输出设备硬件与软件结合说 广义系统说 人员数据设备程序规程15、硬件：泛指实际存在的物理设备，包括计算机本身

4、及其外围设备软件：指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的 数据16、微型计算机的硬件系统 主机：中央处理器 内存储器 外存储器：磁盘光盘输入设备：键盘鼠标图形扫描仪光笔 输出设备：显示器打印机绘图仪 微机的系统总线：数据总线地址总线控制总线17、微型计算机的软件系统系统软件：操作系统编译程序诊断程序系统服务程序语言处理程序 数据库管理系统网络通信管理软件应用软件：为特定需要开发的实用程序 为方便用户使用而提供的软件硬件、软件的关系：1）互相依存2）无严格界面3）互相促进多媒体基本要素：文本图形图像 动画 声频 视频18、软件技术阶段60年代高级语言阶段70年代结构程序设计

5、阶段80年代至今自动程序设计阶段程序设计方法论 由顶向下法 自底向上法自动程序设计方法快速原型法甚高级语言法软件可重用法19、第一代语言19461950机器语言第二代语言19501960汇编语言第三代语言 19601980 第四代语言 19801995 第五代语言 1995过程化编程语言 非过程化编程语言 应用程序开发用专家系统第二章常用数据结构及其运算1、数据：信息的载体、可以用计算机表示并加工。 数据元素：数据集合中的一个个体，是数据的基本单位。 数据对象：具有相同性质的数据元素的集合称为数据对象 数据结构：指同一数据对象各数据元素间存在的关系。S=(D,R) 数据类型：指程序设计语言中允

6、许的变量类型2、时间复杂度：0(1):常量型0(n),0(n2)0(nk)多项式型O(log2n),O(nlog2n)对数型0(2n),0(en)指数型空间复杂度3线性表是数据元素的有序数列L=(D,R)D=ai，a2，an R=|ai-iaiUD,2WiWn若aiai 1i=2,3,n为有序表 否则为无序表基本运算：插入、删除、查找、排序删除算法DELETELIST (V,n,i)1.if(in) then 参数错 return2. for j=i to n-13. Vji j+1 4. e nd(j)5. V i x6. nn-17. return4、插入算法INSERTLIST(Vn,i

7、,x)1.if(iv1)0R(in+1) then 参数错 return2. for j=n to i step (-1)3. Vj+1-V j 4. e nd(j)5. V i x6. nn+17. Retur n5、运算时间插入 移动次数平均值Ej刃pi (n i +1)i=1等概率 Pi=1/(n+1)有 Ejn=1/(n+1)迟 pi(n i +1) =n/2i=1删除 移动次数平均值Ede=工qi(n-1)i=1datan exti=1等概率q1/n有 Ede=1/n 工 qi(n 1) =(n-1)/26、链式存储结构元素：数据域指针域a7、基本运算指针赋值：sp qnext(p)

8、指针移动：pnext(p) 后插：next(s)next(p)next(p)p前插：qheadWhile (n ext(q)Hp) do qnext(q) Next(q)s n ext(s)p&获取一个接点指针指向p算法回收一个接点指针指向p算法RET(P)1. n ext(p)av2. avp3. returnGETNODE(P)1. pav2. avnext(av)3. Retur n插入运算INLINKST (headab)1. GETNODE(p); data(p)b2.If (head=nil) the n headp; n ext(p)nil,retur n3.If (data(h

9、ead)=a) the n n ext(p)head,headp,retur n4. LOOKFOR (head,a,q)5. Next(p)next(q); next(q)p6. Retur n删除运算DELINKST(head,a)1.if (head=nil) then 空表 return2.If (data(head)=a) the n snext (head);RET(head);heads;retur n3. LOOKFOR(head,a,q)4.If (next(q)=nil then 无此结点 return)5. pnext(q); next (q)next(p)6. RET(

10、p)7. Retur n线性链表其他形式1)循环链表2)双向链表9. 重点一元多项式相加p32e.g.设有一元多项式A (x)和B (x)，要求其相加结果C (x) =A (x) +B (x)ADD-POLY (hA,hB)1. pnext(h );qnext(h )2. Preh ;h hA C A3. While (pHnil) AND (qHnil ) do4. Case5. EXP(p)VEXP(q)6. Prep;pnext(p)7. EXP(p)=EXP(q)8. xCOEF(p)+COEF(q);9.If (xHO) then COEF (p)x;prep10. else nex

11、t (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. |f (qHnil) then next(Pre)q17. RET(hB)18. return10、栈 限定只能在表的一端进行插入和删除操作的线性表。允许插入或删除 的一段成为栈顶，另一端称为栈底进栈算法PUSH (s,m.top,x)1.if (top=m) then 上溢”,return2. toptop+13.

12、 sstopx4. return退栈算法POP (s,top,y)1.if (top=0) then 下溢”,return2. ysstop3. toptop-14. return11、队是不同于栈的另一种特殊的线性表，他只允许在一端进行插入在另一端进行删除。插入队算法ADDLINK(rear,fro nt,x)1. GETNODE(p)2. data(p)x ;n ext(p)nil3. Next(rear)p;rearp4. return删除队算法DELLINK(fro nt,rear,y)1.If(rear=fr ont) the n队空retu rn2.ydata( next(fr o

13、n t); next (fr on t)next( next(fro nt)3.I f( next(fr on t)=n il) the n rearfr ont4.return12、|重点三元组P46用一个具有三个数据域的一位数组表示稀疏矩阵 没方三个字段组成(行下标 列下标 值)13、树 由n个(n$0)结点的有限集合T有且仅有一个结点称为根结点，其 余接点称为根节点的子树。N=0时为空树。14、二叉树 B-T=(D,R) 二叉树的基本性质(1) 二叉树的第i层上至多有2i-1 (i$1)个结点(2) 深度为h的二叉树中至多含有2h-1个结点(3) 在任意二叉树中，若有n0个叶子结点，n2

14、个度为2的结点，则必有:n0=n2+115 .|重点一般树转换为二叉树呷16 重点哈夫曼树P60从树中一个结点到另一个结点之间的分支数目称为这对节点之间的路径长度(PL)PL$工log2k 最短路径长度PL=工log2k完全二叉树带权路径长度：WPL= wklkk=117重点 构造哈夫曼树 P61、p6218、图是由顶点集合V顶点之间关系集合R组成 记作G=(V,R)重点图的应用|求单源最短路径P73拓扑排序AOV网P75关键路径 AOE网P77P7819、查找线性查找对分查找分块查找二叉排序树查找哈希表技术及其查找20、构造哈希函数的方法(1) 数字分析法(2) 平方取中法(3) 除留余数法

15、(4) 折叠法移位折叠、边界折叠解决冲突的方法(1) 线性探测再散列(2) 平方探测再散列(3) 随机探测再散列(4) 链地址法21、排序选择排序：简单选择排序、堆排序插入排序：线性插入排序、对半插入排序交换排序：冒泡排序、快速排序第三章操作系统1、操作系统的发展过程1) 手工操作阶段2)早起批处理阶段(联机 脱机)3)执行系统阶段4)多道程序阶段2、操作系统的分类多道批处理操作系统、分时系统、实时系统3、操作系统的功能处理器管理、存储管理、设备管理、文件管理、用户接口(程序一级的接口 作业控制语言和操作命令)4、操作系统的特性共享性、并发性、不确定性5、三级存储器：高速缓存存储器、主存储器、

16、外部存储器6、存储管理的功能内存分配-地址转换或重新定位 地址空间和存储空间 重定位（动态、静态）存储保护内存扩充7、实存储管理分区分配：固定分区分配、可变分区分配（空间分配、空间回收）、空闲区分 配算法（首次适应算法、最佳适应算法、最差适应算法）可重定位分区分配：碎片问题和存储区的紧缩、程序浮动和重定位覆盖技术交换技术&虚存储管理分页存储管理、分段存储管理、段页式存储管理先进先出法缺页中断率f=F页面走向总数最近最少使用法9分页管理优点不要求作业在内存中连续存放，较好地解决了碎片问题。作业地址空间不受内存的限制，对一些不常用的部分不必常驻内存，为用 户提供足够大的存储空间，从而更有利于多道程

17、序作业。缺点要求一定的硬件支持、增加了成本系统要增加页表及其管理程序，因而增加了内存的开销，同时CPU要占 有一定时间来处理页面交换。10、分段管理优点便于程序模块化处理 便于处理化的数据便于共享分段缺点增加硬件成本，为地址变换花费CPU时间为表格提供附加的存储空间。大小受到主存的限制，由于段的长度不固定，又会出现“碎片问题”处 理机要为存储器的紧缩付出代价。11、段页式管理优点：具有分页分段的管理的优点应用最广泛、最灵活。缺点：需要更多的硬件支持，增加了硬件成本，同时也增加了软件复杂性和管理 开销。12、时间局部性：当程序中某个地址最近被访问了，那么往往很快又被再次访 问。空间局部性：当程序

18、中某个地址最近被访问了，那么它附近的地址也会被访问。13、处理器管理作业：用户在一次算题过程中或一个事务处理中要求计算机系统所做工作的集合 作业步：一个作业是由一系列有序的作业步所组成。14、指令：特权指令只能由操作系统使用非特权指令 供一般用户使用15、 执行状态管态（主态 执行状态）目态（算态题目状态）16、作业调度（宏观）分为提交、收容、执行、完成四个状态。作业控制块 作业名状态优先数运行时间位置 长度外设申请作业调度算法1）先来先服务算法2）基于优先级的调度算法【优先数=（等待时间）2-（要求运行时间）-（输出量）】3）分时和优先级相结合的作业调度17、进程调度（微观）分为就绪、运行、

19、阻塞状态作业控制块进程名 优先数当前状态 寄存器内容指向下一个PCB进程控制原语：创建原语挂起原语激活原语撤消原语进程调度算法：1）优先数法2）轮转调度法3）分级调度法18、多道程序并发运行同步互斥现象同步：指两个时间的发生存在某种时序上的关系，如果系统中由若干个进程要共 同完成某一任务，那么他们相互之间必须协调配合，这就需要有一种工具使他们 同步进行。互斥：当多个进程要求系统中某些硬件或软件资源，而这些资源却又要求排他性 使用时，这样往往引起由于多个进程竞争统一资源使运行结果出现问题。解决方法：P-V操作19、死锁原因系统资源不足进程推进的顺序不当必要条件：所涉及的资源是非共享的进程在等待新

20、资源时，继续占用已分配到的资源一个进程占有的资源不能被别的进程强行抢占一个进程获得的资源同时被另一个进程所请求，从而形成一 个进程的循环性。解决方法：预防、避免、检查和恢复20、顺序程序设计的特点（1）程序的顺序性（2）程序环境的封闭性（3）程序运行的确定性和可在现性 并行程序设计的特点（1）并行性（2）共享性（3）同步与互斥21、设备管理功能：（1）方便性（2）设备独立性（3）并行性（4）有效性与 均衡性按设备使用性质分类：独享设备共享设备虚拟设备逻辑设备与物理设备：绝对设备号相对设备号相对号符号名22、文件分类按用途：系统文件、库文件、用户文件 按存取权限：可执行文件、只读文件、读写文件、不保护文件文件的物理结构：1）顺序结构2）链接结构3）索引结构文件共享：通过文件路径实现共享、通过链接实现共享文件存储控制 分类：文件主、同组用户、一般用户