计算机软件技术复习市公开课金奖市赛课一等奖课件

计算机软件技术基础复习*第1页第二章惯用数据结构及其运算算法分析——算法复杂度算法、数据结构（逻辑结构、存放结构）*第2页例题下面程序段时间复杂度为（）。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)*第3页线性表次序存放结构1.次序存放结构

2.次序存放结构插入运算3.次序存放结构删除运算*第4页线性表链式存放结构链式存放结构基本运算

1、前插

2、后插

3、删除*第5页特殊线性表——栈和队栈定义和基本操作判断栈空、队满条件有三个元素进栈序列是1，2，3，举出此三个元素可能出栈序列，并写出对应进栈和出栈操作序列如图所表示(假设以I和O表示进栈和出栈操作)。*第6页队队定义访问算法次序队

1、基本操作：出队：front＋＋入队：rear＋＋

2、循环队列结构及判断队空、队满条件

3、基本运算*第7页循环队列队列为空front＝＝rearfront=rear+1队列已满*第8页数组数组两种次序存放方式次序存放地址公式Loc(aij)=Loc(a11)+(i-1)*n+(j-1)按行优先储存按列优先储存Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*第9页数组有一个N×N下三角矩阵A，若采取行优先进行次序存放，每个元素占用4个字节，则Aij(1≤i≤N,1≤j≤i)元素相对字节地址（相对首元素地址而言）为

。

A.（i×（i+1）/2+j-1）×4B.（i×i/2+j）×4C.（i×（i-1）/2+j-1）×4D.（i×（i-1）/2+j）×4A=a110…0a21a22…0

an1an2…ann

C第10页非线性数据结构——树与二叉树树及其基本概念二叉树定义三种特殊形态二叉树满二叉树、完全二叉树编号*第11页二叉树基本性质性质1：二叉树第i层最多有2i-1

个结点。(i1)性质2：深度为k二叉树最多有个结点。性质3：对一棵二叉树，假如叶子结点数为n0，度为2结点数为n2，则n0=n2+1。第12页设一棵完全二叉树有1000个结点，试问

1)有多少个叶子结点，

2)有多少个度为2结点；

3)有多少个结点只有非空左子树。二叉树基本性质第13页二叉树遍历先序、中序、后序二叉排序树性质、生成

哈夫曼树带权路径长度、哈夫曼树生成*第14页有如图所表示一棵二叉树，则该二叉树先序、中序、后序遍历序列为

。CBDAEGFABCDEFGCDBGFEA先序中序后序二叉树遍历第15页

给定序列{52，8，5，16，78，19}，画出产生一棵二叉排序树过程。*第16页*第17页

字符：S、C、T、A、空格权值：{6，2，4，5，3}①以字符权值作为叶子结点权值结构一棵哈夫曼树，并求出其带权路径长度。②试对电文“1000100”进行翻译2094511562301010101TACS答案：CAT二叉树应用*第18页

图顶点度

在无向图中，顶点度就是和该顶点相关联边数目。在有向图中：顶点度=入度+出度第19页两种最惯用表示方法：邻接矩阵邻接表

图存放结构第20页查找评价查找算法好坏依据——平均查找长度次序查找对分查找分块查找二叉排序树查找*第21页已知长度为6线性表：(45，24，53，13，30，85)1）按次序依次插入，二叉排序树；2）试分别求出在等概率情况下二叉排序树查找成功平均查找长度。*第22页树平均查找长度为

ASL(a)=1/6[1+2+2+3+3+3]=14/6*第23页排序选择排序插入排序冒泡排序快速排序第24页初始状态[46745314263886652734]第一趟[465314263874652734]86第二趟[4614263853652734]7486第三趟[14263846532734]657486第四趟[142638462734]53657486第五趟[1426382734]4653657486第六趟[14262734]384653657486第七趟[14262734]384653657486冒泡第25页第3章操作系统操作系统类型：特点

多道批处理系统、分时系统、实时系统*第26页存放管理存放管理功效 内存分配 地址转换：静、动态地址重定位区分 存放保护 内存扩充*第27页实存放管理分区分配

固定分区可变分区：

寻找空闲区算法——

最先、最正确、最差适应算法*第28页虚拟存放管理分页存放管理地址转换

*第29页例页号01234页架号64320状态11110每页长为32字，现有逻辑地址为：68，180，若能翻译成对应物理地址*第30页处理器管理进程调度：调度算法进程状态及转换*第31页进程同时与互斥进程同时进程互斥临界区P-V操作*第32页*第33页*第34页双向制约

设两个信号量S1和S2，且赋予它们初值S1为1，S2为0，L1:进程AL2:进程BP（S1）P（S2）把信息送入缓冲区从缓冲区取走信息V（S2）V（S1）GOTOL1GOTOL2*第35页死锁死锁定义必要条件死锁预防*第36页设备管理设备分类按使用方法：绝对设备号、相对设备号缓冲技术假脱机系统目标*第37页1）循环测试I/O方式:I/O测试指令不停对该设备进行测试，直到设备空闲为止。

2）程序中止I/O方式:

中止技术及中止处理机构引入，使得CPU与外围设备工作有了相对独立性。

3）通道I/O方式:

引入通道技术，使主机不再干预I/O操作。I/O控制方式改进*第38页*文件管理文件目录第39页*实体间联络

两个实体型之间联络能够分为三类：一对一联络一对多联络多对多联络第40页*概念模型表示方法：实体—联络方法

E–R图：提供了表示实体型、属性和联络方法。第41页*数据模型层次模型网状模