[研究生入学考试]北航计算机软件技术基础复习课2010.pptx

2010软件技术基础

复习课;1/100;1/100;1/100;1/100;–特点：

编译型语言可进行优化（或多次优化），目标码效率很高，是目前软件开发的最主要编程语言。

用这些语言编写的原程序，都要进行编译，连接，才能生成可执行程序。

C/C++,Pascal,Ada,FORTRAN等都是编译型语言。;1/100;1/100;1/100;1/100;1/100;1/100;迭代法

重复同样步骤，可以逐次求得更精确的值。这一过程即为迭代过程.

使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差，然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差。并认为最后一次迭代得到的近似值为问题的解。这种迭代方法称为逼近迭代。;1/100;1/100;1/100;a1;;栈;栈是限定仅在表尾进行插入和删除运算

的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。表中无元素时称为空栈。在右上图所示的栈中，栈中的元素按a1,

a2,a3,…an的顺序进栈，a1称为栈底元素。新元素进栈要置于an之上，删除或退栈必

须先对an进行，即栈的操作是按先进后出的原则进行。因此，栈又称为LIFO表(LastInFirstOut的缩写)表。栈的物理存储可以用顺序存储结构，也可以用链式存储结构，如右图所示。;树的存储结构

–直观地看，树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定。例如，下图中树的度为3，可以采用含有3个指针域的结点的多重链表作存储结构。但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，再进行处理。;1/100;二叉树的存储结构

–通常使用具有两个指针域的二叉链表作二叉树的存储结构，结点结构如图(a)所示，图中LC为左指针域，指向结点的左子树；RC为右指针域，指向结点的右子树。;二叉树的存储结构

–图(b)所示为一个二叉树的二叉链表。有时亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针，如图(c)所示。用一个结构数组也可以。;1/100;1/100;1/100;对于右图，使用前序遍历，则处理顺序为：ABEFCGDHIJ

对于右图，使用中序遍历，则处理顺序为：EFBGCHIJDA

对于右图，使用后序遍历，则处理顺序为：FEGJIHDCBA;图的存储

–图的结构复杂，应用广泛，因此其存储表示方法也多种多样。下面给出两种最常用的存储表示方法。

图的相邻矩阵表示法

–相邻矩阵是表示结点间的相邻关系的矩阵，若G是一个具有n个结点的图，则G的相邻矩阵是如下定义的n×n矩阵。

1，若（Vi，Vj）是图G的边A[i,j]＝

0，若（Vi，Vj）不是图G的边;1/100;1/100;1/100;1/100;分块查找;分块查找;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;进程的状态;线程－thread;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100; 当某一进程需要使用某种输入输出设备时，首先向“输入输出控制系统”发出请求，该子系统阻塞进程、分析进程发出的请求，并根据进程的请求调用适当的设备驱动程序。设备驱动程序接到“输入输出控制系统”发出的调用请求后，写设备控制器的寄存器，完成设备的初始化，操作设备完成具体的输入输出工作，完成数据传输之后，把设备的状态信息反馈给“输入输出控制系统”。“输入输出控制系统”检验设备状态，唤醒请求进程，并把操作状态信息返回给请求进程。;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/100;1/1;1/100;1/100;1/100;1/100; TCP/IP协议采用分层的体系结构（如图所示），共分为四层：网络接口层，网际层，传输层和应用层。;IP

ARP ARP

硬件协议（链路控制和介质访问）;负责接受IP数据报，并通过网络进行传送。网络的接口有两种：

1、设备驱动程序；

2、使用专用数据链路协议的子系统。

本层的协议标准很多，包括各种逻辑链路控制和介质访问协议。;IP协议提供主机间的数据传送能力。

地址解析协议ARP实现了物理地址和IP地址间的映射，起着屏蔽物理地址细节的作用。

控制协议ICMP。;提供端到端的通信。

传输控制协议TCP，面向连接的协议。

用