《习题讲解678(计算机概论).ppt》由会员分享，可在线阅读，更多相关《习题讲解678(计算机概论).ppt（40页珍藏版）》请在金锄头文库上搜索。
1、计算机概论第二次习题课6、7、8 KeyPoints Explanation六章oOSI模型和TCP/IP协议OSI模型七层结构及其功能TCP/IP协议中协议类型及其应用互联网上文档分类o网络分类:LAN、MAN、WANo连接设备：中继器、网桥、路由器和网关OSI模型和TCP/IP协议(1)o模型：由标准化组织制定的用于网络设计的指南OSI(Open Systems Interconnection)模型：由国际标准化组织ISO设计，理论上允许任意两个不同系统之间可以相互通信而无需考虑它们的底层体系结构。o协议：用于控制网络或者交互式网络中不同设备间交互的一系列规则。TCP/IP (Transm
2、ission control/Internet protocol)协议：TCP/IP协议是互联网上正式使用的协议组。所以TCP/IP协议中的层并不完全与OSI模型中的层相同。OSI模型和TCP/IP协议(2)OSI模型编号：层次 功能1 物理层(phsical )负责在物理介质中传输流，先将位编码和解码成位组，接着把位流转换为信号； 数据单元：位2 数据链路层（Data Link）通过加入报头和报尾，将位组成帧；负责两个相邻站点间帧的点对点传递 数据单元：帧3 网络层(NetWork)负责源站点和目的站点之间包的传递；数据单元：包4 传输层(Transport)负责整个消息的源至目的地（端到端
3、）的传送；消息由一个或者多个包组成 数据单元：消息5 会话层(Session) 负责控制用户间的会话；不单独实现，通常包括在应用层6 表示层(presentation)基于不同系统使用不同的编码（ASCII、Unicode），关注信息的语法和语义；压缩和解压缩；加密和解密7 应用层(Application)使得用户（不管是人还是软件）都可以访问网络，定义了通用的应用程序OSI模型例子49.下面动作包含在OSI模型中的哪个层？a 发送数据帧给下一个站点b 从源至目的地发送数据包 c 从源至目的地发送长消息 d 登录远程计算机 e 加密和解密数据 f 将数据的机器码转换成统一字符编码标准(Unic
4、ode)Data LinkNetworkTransportApplicationPresentationPresentationTCP/IP(1)分类协议名称描述对应OSI模型层IP不可靠的协议，但提供最大限度的传输服务 ； 数据单元：IP数据报(交互式)网络层TCP可靠的传输协议，为应用程序提供完整的传输层服务传输层UDP简单协议，只提供端到端发送的基本传输需要FTP用于从一台机器向另一台传送文件的标准协议；用来解决不同编码系统和文件格式的问题应用层（会话层和表示层的功能集中到这一层）SMTP最流行的应用是电子邮件；TELNET互联网上允许远程登录的一个通用的客户-服务器程序；通过将本地终端
5、作为远程系统的终端来实现本地系统同远程系统建立连接HTTP用来在万维网上访问和传输文档的客户端-服务器程序WWW多媒体文档的集合TCP/IP(2)oIP地址：IPv4地址由4个字节（32位）组成；通常用点分十进制来表示o客户端-服务器模型：客户向服务器请求服务客户：本地计算机上运行的应用程序；需要时运行服务器：在远程计算机上运行的应用程序；一直运行p邮件地址：唯一的标示Internet上的一个邮箱本地部分：定义了特殊文件的名称，即用户邮箱域名：定义了作为SMTP服务器的计算机名URLpURL(统一资源定位器)：HTTP所用的特殊地址，它是互联网上用于指定任何一种信息的标准。方法：用来传输文档的
6、客户-服务程序，HTTP既是方法主机：存储信息的计算机，通常为计算机赋予www.开头的别名端口：定义了服务器的端口数量，可选路径：存储信息的文件的路径名例如：使用http协议，路径为：/user/general，计算机别名为：www.hadb,则其URL地址为：http：/www.hadb/user/general文档类型o静态文档(static documents)：在服务器端生成，只能被复制；如用户用浏览器下载文档o动态文档(dynamic documents)：驻留在服务器端的程序，当浏览器发送请求，服务器就运行该程序并将结果返回给浏览器；如浏览器向服务器发出运行日期的请求o活动文档(a
7、ctive documents)：程序，不能在服务器端运行，浏览器需要请求程序的传输，传输后这个程序会在浏览器中运行；如用户用浏览器下载游戏网络分类oLAN局域网：oMAN城域网oWAN广域网例子o如果有一个每个角落有一台计算机的正方形房间，哪种拓扑结构需要较少的电缆？a 总线局域网 b 环形局域网c 在房间中央有一个集线器的星形LAN解答：假设正方形边长为Lcm， 则总线局域网需要3Lcm的电缆； 环形局域网需要4Lcm的电缆； 星形局域网需要2 * sqrt(2) * Lcm or 2.828Lcm的电缆。 故需要较少电缆的为C 连接设备连接设备比较连接设备OSI模型中所处的层功能中继器物
8、理层延伸了网络的物理长度，再生信号并将其发送给网络的其余部分网桥物理层和数据链路层通信控制器：长总线分成小段，每小段都是独立的通信段，根据帧的物理地址来过滤帧；再生帧；可以连接属于同一局域网内的两个段或者属于同一组织的两局域网路由器物理层、数据链路层、网络层根据数据包的逻辑地址(网络层)为其选择路由；可以连接两个独立的网络：局域网、城域网、广域网；互联网既通过路由器形成网关全部七层充当协议转换器；允许两个网络相互通信，而两个网络的协议可以不同；常与路由器这个术语交替使用七章：操作系统oOS定义与组成部分o内存管理系统单道程序多道程序虚拟内存p进程管理器程序、作业和进程状态图进程同步：死锁(de
9、adlock)和饿死(starvation)p主流操作系统：windows、Unix和LinuxOS (operation system)定义o操作系统是计算机硬件和用户(程序和人)的接口，它使得其他程序更加方便有效地执行，并能方便地对计算机硬件和软件资源进行管理。o操作系统组成部分内存管理系统单道程序和多道程序o单道程序中，大多数内存专用于单一的程序，仅仅一小部分用来装载操作系统。o多道程序中，同一时刻可以装入多个程序并能够同时执行这些程序，CPU轮流为它们服务。例子o计算机装有一个单道程序的操作系统，如果内存容量为64MB，操作系统需要4MB，那么该计算机可以执行程序的最大内存是多少？若操
10、作系统自动分配10MB内存给数据，则可以执行程序的最大内存又是多少？解答： 64MB-4MB=60MB 64MB-4MB-10MB=50MB多道程序分区调度o内存被分成不定长度的几个分区，每个分区保存一个程序。o此技术中，每个程序需完全载入内存，并占用连续的地址。o执行模式：CPU在各程序之间交替服务。1.由一个程序开始，执行一些指令直到有输入/输出或者分配给当前程序的时间片结束2.CPU保存现场并转入下一个程序；重复1步骤3.所有程序执行完之后，CPU转回第一个程序例子o多道程序的操作系统将60MB内存分为10MB、12MB、18MB、20MB；第一个程序运行需要17MB使用第三分区，第二个
11、需要8MB使用了第一分区，第三个需要10.5MB，使用了第二分区；第四个需要20MB使用第四分区。问总共使用多少内存？总共浪费了多少内存？内存浪费率是多少？解答：总共使用的内存： 17+8+10.5+20=55.5（MB） 浪费的内存： 60MB-55.5MB=4.5MB 内存浪费率： 4.5/60=7.5%10MB12MB18MB20MB多道程序分页调度o内存被分成大小相同的帧；程序则分成大小相等的页；页和帧的大小一样；o此技术下，程序在运行前全部载入内存，但在内存中不必是连续的；例子o多道程序的操作系统使用分页调度，将可用内存60MB内存分为15页，每一页大小为4MB；第一个程序运行需要1
12、7MB，第二个需要8MB，第三个需要10.5MB，；第四个需要20MB。问总共使用多少内存？总共浪费了多少内存？内存浪费率是多少？解答：第一个程序需要5页 4MB*5=20MB17MB 第二个程序需要2页 4MB*2=8MB 第三个程序需要3页 4MB*3=12MB10.5MB 第四个程序需要5页 4MB*5=20MB 总共使用了60MB； 浪费内存为：3+1.5=4.5MB；内存浪费率为7.5%虚拟内存o微软的官方定义是:计算机使用的临时存储器，用来运行所需内存大于计算机具有的物理内存的程序；虚拟内存用部分硬盘空间做内存来弥补计算机RAM空间的不足。o例1：内存空间为10MB，而我们需要运行
13、10个程序，每个程序3MB；若同时运行10个这样的程序，则至少需要30MB的内存空间，这时候，虚拟内存大小就是至少20MB。例子：o例2：一OS执行时需要所有的程序驻留在物理内存中。物理内存大小为100MB，虚拟内存为1GB；有多少10MB大小的程序可以同时运行？它们之中有多少可以随时驻留在内存中？多少则必须要存在磁盘里？o解答：100MB/10MB=10 1GB/10MB=102.4 可以同时运行112个10MB大小的程序 有10个可以随时驻留在内存中 有102个必须存在磁盘中进程管理器程序、作业和进程名称描述联系程序由程序员编写的一组稳定的指令，存储在硬盘(磁盘)上可能会也可能不会成为作业
14、作业从程序中被选中执行，到其运行结束并再次程序的这段过程中，称为作业每个作业都是程序，并不是所有程序都是作业进程进程是执行中的程序；换句话说，进程是驻留在内存中的作业；只要作业被装入内存就成为进程每个进程都是作业，而每个作业未必都是进程状态图例子o进程在下面的情况下处于什么状态？a 进程在使用CPU b 进程结束打印，等待CPU又一次调用c 进程因为时间片用尽而被终止d 进程从键盘读取数据e 进程打印数据运行就绪就绪等待等待死锁(Deadlock)o死锁：是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统
15、产生了死锁,这些永远在互相等待的进程称为死锁进程. o死锁发生需要四个必要条件：互斥：一个资源只能被一个进程调用占有资源占有：虽然不使用资源，但进程仍然占用直到有其他可用的资源先到先得：操作系统不能临时对资源重新分配循环等待：所有的进程和资源包含在一个环里例子：o例1：三个进程(A、B、C)同时运行，进程A占用File1但需要File2，进程B占用File3需要File1，进程C占用File2需要File3.画出资源与进程之间的关系框图，并判断是否是死锁？o例1：三个进程(A、B、C)同时运行，进程A占用File1，进程B占用File2需要File1，进程C占用File3需要File2.画出资
16、源与进程之间的关系框图，并判断是否是死锁File1File2File3ACB分配请求分配请求请求分配请求File1File2File3ACB分配请求分配分配第八章：算法o算法定义算法的三种结构：顺序、判断、循环算法的表示：流程图、伪代码o基本算法排序：选择排序、冒泡排序、插入排序查找：顺序查找、折半查找p递归算法定义、结构o算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。o三种结构算法的表示(1)o流程图：只显示算法从开始到结束的整个流程，而无细节o规则：椭圆或者圆角表示“开始”或者“终止”菱形表示“判断”长方形表示“处理”平行四边形表示“输入输出”算法的表示(2)o伪代码：类似
17、英语的表示法，现在还无相应标准基本算法排序(1)o选择排序算法：该算法将列表分为两个子列表：已排序的和未排序的。使用两重循环，外层循环每次扫描时迭代一次，内层循环在未排序列表中寻找最小的元素并把它和未排序数据中第一个元素进行交换。Select sortInput：unsorted list1. Set wall at the beginning；2. While there are more elments in the unsorted list2.1 Find smallest elment in unsorted list2.2 Swap (Smallest, First)2.3 Adv
18、ance wallEnd loop3. Return listEnd基本算法排序(2)o冒泡排序：两重循环，外层循环每次扫描过程中迭代一次，每次内层循环则将一个元素冒泡至顶部(左部)。基本算法排序(3)o插入排序：双层循环，外层循环每次扫描迭代一次，内层循环则寻找插入的位置。例子o例1：分别使用选择排序、冒泡排序和插入排序算法，手工排序下列数据并给出每次扫描所做的工作； 14 7 23 31 40 56 78 9 2选择排序冒泡排序插入排序原始14 7 23 31 40 56 78 9 214 7 23 31 40 56 78 9 214 7 23 31 40 56 78 9 212/7 23
19、 31 40 56 78 9 14 2/14 7 23 31 40 56 78 914/7 23 31 40 56 78 9 222 7/23 31 40 56 78 9 142 7/14 9 23 31 40 56 787 14/23 31 40 56 78 9 232 7 9/31 40 56 78 23 142 7 9/14 23 31 40 56 787 14 23/31 40 56 78 9 242 7 9 14/40 56 78 23 312 7 9 14/23 31 40 56 787 14 23 31/40 56 78 9 252 7 9 14 23/56 78 40 312
20、7 9 14 23/31 40 56 787 14 23 31 40/56 78 9 262 7 9 14 23 31/78 40 562 7 9 14 23 31/40 56 787 14 23 31 40 56/78 9 272 7 9 14 23 31 40/78 562 7 9 14 23 31 40/56 787 14 23 31 40 56 78/9 282 7 9 14 23 31 40 56/782 7 9 14 23 31 40 56/787 9 14 23 31 40 56 78/292 7 9 14 23 31 40 56 782 7 9 14 23 31 40 56 7
21、8基本算法查找o顺序查找：从表头开始查找，若当前元素不是目标元素，右移指针，直到找到目标值或者确信查找目标不在列表中。一般用于查找无序列表，针对较小的列表或者是不常用的列表，效率低。o折半查找：从测试列表的中间元素开始查找，判别目标值是在前半部分还是后半部分；若在前半部分，则无需查找后半部分；重复此过程直至找到目标值。用于有序列表查找，效率比较高。o递归算法包含了算法本身，则为递归；换句话说，递归是算法自我调用的过程例子o一个列表包含以下元素。使用折半查找法，跟踪查找88的步骤，要求给出每一步中first、mid和last的值。 8 13 17 26 44 56 88 97目标：88037FirstMidLast8131726445688970123456781317264456889701234567457FirstMidLast667FirstMidLast81317264456889701234567例子o使用如下定义编写一个寻找两个整数最大公约数(gcd)的递归算法。 GCDInput: 2 integers (X and Y)1. If X Y1.1 Return GCD(Y, X)2. Else if Y equals 02.2 Return X3. Else3.3 Return GCD(Y, X % Y )End ifEnd
