计算机专业(基础综合)模拟试卷87(题后含答案及解析)

计算机专业（基础综合）模拟试卷87(题后含答案及解析)题型有：1.单项选择题2.综合应用题单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1．以下关于图的说法正确的是()。Ⅰ图G的生成树是该图的一个极小连通子图Ⅱ生成树中最长路径的起点和终点的度均为1Ⅲ对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点A．Ⅰ、ⅡB．Ⅱ、ⅢC．Ⅰ、ⅢD．仅有Ⅱ正确答案：D解析：说法Ⅰ是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。说法Ⅱ是正确的，可用反证法证明。设v1，v2，…vk是生成树的一条最长路径，其中，v1为起点，vk为终点，若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路。所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。2．下列陈述中正确的是()。A．在DMA周期内，CPU能执行程序。B．中断发生时，CPU首先执行人栈指令将程序计数器的内容保护起来。C．DMA传送方式中，DMAC每传送一个数据就窃取一个指令周期。D．输入输出操作的最终目的是要实现CPU与外设之间的数据传输。正确答案：D解析：A错，DMA周期内CPU仍然可以执行程序。B错，对于单重中断发生时首先执行中断周期，其顺序为中断响应、关中断、程序断点(PC)进栈、向量地址送PC。3．下面关于PCI总线的描述中，错误的有()。Ⅰ．PCI总线是一个与处理器性能相关的高速外围总线Ⅱ．PCI总线可对传输信息进行奇偶校验Ⅲ．PCI设备一定是主设备Ⅳ．系统中允许有多条PCI总线A．仅Ⅰ、ⅢB．仅Ⅱ、ⅢC．仅Ⅲ和ⅣD．仅Ⅰ、Ⅲ正确答案：D解析：PCI总线与CPU及时钟频率都无关，故Ⅰ错误；PCI总线支持即插即用并且可对数据和地址进行奇偶校验，并且PCI总线采用猝发传送方式，故Ⅱ正确；主设备指获得总线控制权的设备，所以PCI设备不一定都是主设备，故Ⅲ错误；系统中肯定允许有多条PCI总线，以此来提升计算机的效率，故Ⅳ正确。4．在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过一段时间，发送窗口的后沿的变化情况可能为()。Ⅰ．原地不动Ⅱ．向前移动Ⅲ．向后移动A．Ⅰ、ⅢB．Ⅰ、ⅡC．Ⅱ、ⅢD．都有可能正确答案：B解析：发送窗口的后沿的变化情况只能有两种：(1)原地不动(没有收到新的确认)。(2)向前移动(收到了新的确认)。发送窗口不可能向后移动，因为不可能撤销已收到的确认帧。5．DNS服务器在名称解析过程中正确的查询顺序是()。A．本地缓存记录→区域记录→转发域名服务器→根域名服务器B．区域记录→本地缓存记录→转发域名服务器→根域名服务器C．本地缓存记录→区域记录→根域名服务器→转发域名服务器D．区域记录→本地缓存记录→根域名服务器→转发域名服务器正确答案：C解析：本题考查DNS域名解析的工作过程，具体步骤如下：(1)客户机提交域名解析请求，并将该请求发送给本地的域名服务器；(2)当本地的域名服务器收到请求后，就先查询本地的缓存。如果有查询的DNS信息记录，则直接返回查询的结果。如果没有该记录，本地域名服务器就把请求发给根域名服务器；(3)根域名服务器再返回给本地域名服务器一个所查询域的顶级域名服务器的地址；(4)本地服务器再向返回的域名服务器发送请求；(5)接收到该查询请求的域名服务器查询其缓存和记录，如果有相关信息则返回本地域名服务器查询结果，否则通知本地域名服务器下级的域名服务器的地址；(6)本地域名服务器将查询请求发送给下级的域名服务器的地址，直到获取查询结果；(7)本地域名服务器将返回的结果保存到缓存，并且将结果返回给客户机，完成解析过程。因此本题答案是C。6．假设有k个关键字互为同义词，若用线性探查法把这k个关键字存人，至少要进行的探查次数是()。A．k--1B．kC．k+1D．k(k+1)／2正确答案：D解析：假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入，…，第k个关键字通过k次比较后插入。总的比较次数=1+2+…+k=k(k+1)／2。7．栈S和队列Q的初始状态皆为空，元素a1、a2、a3、a4、a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3、a4、a2、a1、a5、a6，则栈S至少应该容纳()个元素。A．6B．4C．3D．2正确答案：C解析：模拟一下入栈、出栈过程，如表2-5所示。选取模拟过程中栈内元素个数最大的值，便为该题答案，因此本题选C。8．由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。A．27B．38C．51D．75正确答案：D解析：二叉排序树的构造方法如下：每读入一个数据，建立一个新结点，若二叉排序树为空，则新结点为二叉排序树的根结点；若二叉排序树非空，则新结点的值和根结点比较，若小于根结点，则插入左子树；否则插入右子树。结点的平衡因子是指结点的左子树的深度减去它的右子树的深度。由数据(27，16，75，38，51)构造平衡二叉树，插入51后首次出现不平衡子树，易知最小不平衡子树的结点为75。9．以下IP地址中，路由器不进行转发的有()。Ⅰ．10．1．32．7Ⅱ．192．168．32．2Ⅲ．172．30．1．3Ⅳ．172．35．32．244A．仅Ⅰ、Ⅱ、ⅢB．仅Ⅱ、ⅢC．仅Ⅰ、Ⅲ、ⅣD．仅Ⅳ正确答案：A解析：路由器对于专用网地址(私有地址)是不进行转发的。私有地址总结如下：A类10．0．0．0～10．255．255．255(记住10开头即可)B类172．16．0．0～172．31．255．255(这个死记)C类192．168．0．0～192．168．255．255(记住192．168开头即可)10．在DMA方式下，数据从内存传送到外设经过的路径是()。A．内存→数据总线→外设B．内存→DMAC→外设C．内存→CPU→总线→外设D．外设→内存正确答案：B解析：在DMA方式下，数据从主存传送到外设需要通过DMA控制器中的数据缓冲寄存器。11．某计算机采用虚拟页式存储技术，系统为每一个进程提供65536B的地址空间，含内外存。页面大小为4096B，某一个进程的代码段有32768B，数据段16396B，堆栈段在进程创建时为1024B，运行中最大会增涨到15284B。那么这个进程()。A．能够创建到内存，运行正常B．能够创建到内存，运行过程中出错C．不能创建到内存D．能够创建到内存，可能会死锁正确答案：B解析：本题考查页式存储的基本概念。页内只能存放同一个段的信息，不能容纳不同段的内容。根据题意，系统给每个进程最多分配有65536÷4096＝16个页面，进程创建时需要代码段32768÷4096＝8页；数据段16396÷4096＝4页余12，占用5页；堆栈段1024÷4096＝0页余3072，占用l页。8＋5＋1＝14<16，因此进程可以创建。当运行中堆栈段增涨到最大15284时，需要页面15284÷4096＝3页余2996，需占用4页，那么8＋5＋4＝17>16，超出了系统分配给一个进程的最大地址空间，因此将会在申请第17个页面时出现一个致命的错误，进程退出。死锁的发生一定是二个或二个以上的进程之间发生的时间和空间上的竞争，本题没有涉及其它进程，因此不会死锁。12．通道是一种IO设备，它主要用于传输的数据是位于()。A．主存与IO设备B．CPU与IO设备C．主存与外存D．CPU与外存正确答案：A解析：本题考查通道的作用与功能。通道主要是连接IO设备与内存的一个硬件设施，又称为IO处理机，是一个独立于CPU的专门管理IO的控制器，它可以控制设备与内存直接进行数据交换，所以它与CPU是并行的。通道具有执行IO指令的能力，并通过执行通道程序来控制IO操作。但是，通道又和一般的处理机不同，他的结构简单，指令较少且单一，这些指令一般均与IO操作有关。同时，通道一般没有自己独立的内存，它的程序大多是放在主存中的，与CPU共享。13．对于设计实时操作系统，不是其设计目标的是()。A．安全可靠B．处理机效率C．及时响应输入D．快速处理请求正确答案：B解析：本题考查实时操作系统的设计目标。实时操作系统要求能对用户的请求在规定的时间内完成，同时需要保证进程运行的安全性和高可靠性。而处理机的效率不是实时操作系统设计所关心的。14．一种数据编码的海明距是7，那么使用这种编码最多可以纠正()个错误。A．0个B．1个C．2个D．3个正确答案：D解析：为了纠正d个错误，需要使用距离为2d+1的编码方案，所以答案是3个。15．一个B类网络的子网掩码为255．255．252．0，则该B类网络的主机数目是()。A．2046B．1022C．510D．128正确答案：D解析：本题考查IPv4字网划分，首先明确B类网络的掩码是255．255．0．0，而192的二进制是11111100，由此可知可划分26＝64个子网，每个子网的主机数为22－2＝2，因此该B类网络的主机数目是64×2＝128，因此答案是D。16．内存按字节编址，地址从90000H到CFFFFH，若用存储容量为16K×8bit芯片构成该内存，至少需要的芯片数是()。A．2B．4C．8D．16正确答案：D解析：CFFFF－90000＋1＝40000，即256KB，若用存储容量为16K×8bit芯片则需芯片数＝(256K×8)／(16K×8)＝16(片)。[归纳总结]采用字扩展的方法，用若干存储芯片构成一个存储器。[解题技巧]用地址范围的末地址减去首地址再加1，就可以方便的计算出存储空间的大小。17．在IP数据报的传递过程中，IP数据报报头中保持不变的域是()。A．标识和片偏移B．标志和头部校验和C．标识和目的地址D．标志和生存周期正确答案：C解析：本题考查IPv4报文格式和传输特性。在数据报传递过程中，如果遇到长度超过网络MTU的时候，必须分片。因此，片偏移和标志是变化的，生存时间是随着数据报传递发生变化的。对于校验和，每经过一个结点都要进行重新计算，因此只有目的地址和标识是不变的。注意：标识是一个计算器，即使发生分片的情况下，其会把这个值复制到分片后的标识字段，因此答案为C。18．以下关于路由器的路由表说法正确的是()。I．路由表包含目的网络和到达该目的网络的完整路径Ⅱ．路由表必须包含子网掩码Ⅲ．目的网络和到达该目的网络路径上的下一个路由器的IP地址Ⅳ．目的网络和到达该目的网络路径上的下一个路由器的MAC地址A．Ⅱ、ⅢB．只有ⅢC．I、ⅢD．Ⅱ、Ⅲ、Ⅳ正确答案：B解析：本题考查网络设备中路由器的作用结构和工作原理，路由器是网络互连的关键设备，其任务是转发分组。每个路由器都维护着一个路由表以决定分组的传输路径。当目的主机与源主机不在同一个网络中，则应将数据报发送给源主机所在网络上的某个路由器，由该路由器按照转发表(由路由表构造的)指出的路由将数据报转发给下一个路由器，这种交付方式称为间接交付。I：为了提高路由器的查询效率和减少路由表的内容，路由表只保留到达目的主机的下一个路由器的地址，而不是保留通向目的主机的传输路径上的所有路由信息，故I错误。Ⅱ：路由表并不一定包含子网掩码，一般只在划分了子网的网络中，路由器的路由表才使用子网掩码，如果不使用就根本不能得到网络号。而没有划分子网的网络，使用默认的就可以，不需要在路由表上显示，故Ⅱ错误。Ⅲ：路由器的路由表的表项通常包含目的网络和到达该目的网络的下一个路由器的IP地址，因为路由器是工作在网络层，网络层使用的是IP地址，故Ⅲ正确，Ⅳ：路由器是工作在网络层的设备，对数据链路层是透明的，故IV错误。综上，只有Ⅲ正确，因此答案是B19．一0．5表示为IEEE754标准短实数的机器数形式为()。A．11000000010000000000000000000000B．11000000000000000000000000000000C．10111111000000000000000000000000D．01111111100000000000000000000000正确答案：C解析：1EEE754标准的短实数阶码长8位，采用偏移值为7FH的移码；尾数采用原码规格化形式，隐藏第一个数值位；格式顺序为数符、阶码、尾数。一0．510=一1．0×2-1，表示为IEEE754标准短实数为10111111000000000000000000000000，其中，第一位1为数符，表示负数，接下来8位01111110为阶码，表示阶码为一1，最右23个0为尾数，其中第一数值位1隐藏。20．设结点x和y是二叉树中任意的两个结点，在该二叉树的先序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是()。A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后裔正确答案：C解析：由于先序遍历是“根…左子树一一右子树”，而后序遍历是“左子树_——右子树——根”，题目中二叉树的先序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x一定是y的祖先。[归纳总结]假设M、N分别是一棵二叉树中的两个结点，关于各个结点的关系如下：表中“1”、“0”或“φ”分别表示肯定、恰恰相反或者不一定。注：如果(1)离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中，则称a在b的左方(即b在a的右方)。21．某机器指令字长12位，有零地址、一地址、二地址3种指令，地址码长4位，采用扩展操作码技术。若二地址指令和一地址指令条数都取最大值，则该机指令条数最多为()。A．16B．46C．48D．4366正确答案：B解析：根据题意，二地址指令的操作码长度为12-4×2=4，留一个编码用于扩展，故最多可定义15条二地址指令；一地址指令扩展长度为4位，留一个编码用于扩展，故最多可定义15条一地址指令；零地址指令可在一地址指令的基础上扩展4位，故最多可定义16条零地址指令。根据题意，该机指令条数最多为15+15+16=46条。22．页面置换算法()可能会产生Belady异常现象。A．先进先出算法FIFOB．最近最少使用算法LRUC．利用referencebit的近似的LRUD．最优算法optimal正确答案：A解析：先进先出算法会出现Belady异常。23．下列关于机器字长与指令字长的说法正确的是()。A．指令字长等于机器字长B．指令字长一定是机器字长的整数倍C．两者长度没有必然关系D．以上说法都不对正确答案：C解析：指令字长取决于操作码的长度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系；但为了硬件设计方便，指令字长一般取字节或存储字长的整数倍。24．页面置换算法()可能会产生Belady异常现象。A．先进先出算法FIFOB．最近最少使用算法LRUC．利用referencebit的近似的LRUD．最优算法optimal正确答案：A解析：先进先出算法会出现Belady异常。25．一个广域网信道的比特率是4Kbps，传播延迟为20ms，若确保停一等协议才至少50％效率，那么帧的大小在至少是()。A．大于160bitB．大于150bitC．大于140bitD．大于130bit正确答案：A解析：当发送一帧的时间等于信道传播延迟的2倍时，信道利用率是50％。或者说，当发送一帧的时间等于来回路程的传播延迟时，效率将是50％。本题中，往返传播时间为20毫秒×2＝40毫秒，发送速率是每秒4000位，即发送1位需0．25毫秒。40毫秒÷0．25毫秒／位＝160位。所以，帧大于160位时，采用停一等协议才有至少50％的效率，答案是A。26．请求分页存储管理方案中，如果所需的页面不在内存中，则产生缺页中断，它属于()中断。A．硬件故障B．I／OC．外D．程序中断正确答案：D27．某文件占100个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为200μs将缓冲区的数据传送到用户区的时间是100μs，CPU对一块数据进行分析的时间为100μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是()。A．30000μs、20000μs。B．30100μs、20200μsC．30100μs、30100μsD．20200μs、20200μs正确答案：B解析：这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的；所以对单一缓冲区，从磁盘写入和读出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU对数据的分析与从用户区读数据也是需要互斥操作，但是CPU分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入缓冲区的时间，因此，CPU会空闲。单缓冲区的总时间＝(磁盘写入缓冲区时间＋缓冲区读出时间)×100＋CPU处理最后一块数据的时间＝(200＋100)×100＋100＝30100μs。当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU的数据分析。读出操作和数据分析必须互斥进行，故，从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间＝(磁盘写入缓冲区时间)×100＋读出最后一块数据时间＋CPU分析最后一块数据时间＝(200)×100＋100＋100＝20200μs。28．局域网交换机首先完整地接收数据帧，并进行差错检测。如果正确，则根据帧目的，则根据目的地址确定输出端口号再转发出去。这种交换方式是()。A．直接交换B．改进直接交换C．存储转发交换D．查询交换正确答案：C解析：本题考查交换机的三种交换方式，直接交换在输入端口检测到数据帧时，检查帧头地址，把数据帧直通到相应的端口，实现交换功能。存储转发交换把输入端口的数据帧先存储起来，然后进行CRC(循环冗余码校验)检查，在对错误包处理后才取出数据帧的目的地址，通过查找表转换成输出端口送出帧。碎片隔离交换检查数据包的长度是否够64个字节，如果小于64字节，说明是假包，则丢弃该包；如果大于64字节，则发送该包。因此答案是C。29．为了限制路由信息传播的范围，OSPF协议把网络划分成4种区域(Area)，其中连接各个区域的传输网络是()。A．不完全存根区域B．标准区域C．主干区域D．存根区域正确答案：C解析：本题考查层次路由与OSPF、路由协议，如果将区域看成一个节点，则OSPF是以主干区域(area0．0．0．0)为顶点，其他区域为终端的星形拓扑结构。标准区域可以接收链路更新信息和路由总结。存根区域是不接受自治系统以外的路由信息的区域。如果需要自治系统以外的路由，它使用默认路由0．0．0．0。完全存根区域不接受外部自治系统的路由以及自治系统内其他区域的路由总结，需要发送到区域外的报文则使用默认路由0．0．0．0。不完全存根区域类似于存根区域，但是允许接收以LSAType7发送的外部路由信息，并且要把LSAType7转换成LSAType5。因此答案是C。30．有m个叶子结点的哈夫曼树所具有的结点数为()。A．mB．m+1C．2mD．2m-1正确答案：D解析：由哈夫曼树的特点易知哈夫曼树结点总数=2m-1，m为叶子节点个数。31．用直接插入排序方法对下列4个表进行(由小到大)的排序，比较次数最少的是()。A．94，32，40，90，80，46，21，69B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80D．90，69，80，46，21，32，94，40正确答案：C32．临界区是指并发进程中访问共享变量的()段。A．管理信息B．信息存储C．数据D．程序正确答案：D33．文件系统采用树形目录结构后，对于不同用户的文件，其文件名()。A．应该不同B．由操作系统类型决定C．可以相同也可以不同D．受系统约束正确答案：C解析：树形目录的引入提高了检索的效率，解决了文件的重名问题，即允许不同的用户使用相同的文件名。因此，对于不同用户文件而言其文件名既可以相同也可以不同。34．IEEE的802委员会已经标准化了很多种类的LAN，其中无线LAN标准是()。A．1EEES02．3B．1EEE802．5C．IEEE802．11D．IEEE802．17正确答案：C解析：1EEE802．11是无线LAN的标准。35．系统“抖动”现象的发生是由()引起的。A．置换算法选择不当B．交换的信息量过大C．内存容量不足D．请求页式管理方案正确答案：A解析：在请求分页存储管理中，从主存中刚刚移走某一页面后，根据请求马上又调进该页，这种反复调进调出的现象，称为系统抖动。原因是调度的算法不科学。系统抖动大大降低系统效率。36．对地址转换协议(ARP)描述正确的是()。A．ARP封装在IP数据报的数据部分B．ARP是采用广播方式发送的C．ARP是用于IP地址到域名的转换D．发送ARP包需要知道对方的MAC地址正确答案：B解析：以主机A(192．168．1．5)向主机B(192．168．1．1)发送数据为例。当发送数据时，主机A会在自己的ARP缓存表中寻找足否有目标IP地址。如果找到了，也就知道了目标MAC地址，直接把目标MAc地址写入帧里面发送就可以了；如果在ARP缓存表中没有找到目标IP地址，主机A就会在网络上发送一个广播，A主机MAC地址是“主机A的MAC地址”，这表示向同一网段内的所有主机发出这样的询问：“我是192．168．1．5，我的硬件地址是‘主机A的MAC地址’。请问IP地址为192．168．1．1的MAC地址是什么?”网络上其他主机并不响应ARP询问，只有主机B接收到这个帧时，才向主机A做出这样的回应：“192．168．1．1的MAC地址是OO—aa_-00—62一c6—09”。这样，主机A就知道了主机B的MAC地址，它就可以向主机B发送信息了。同时A和B都更新了自己的ARP缓存表(因为A在询问的时候把自己的IP和MAC地址一起告诉了B)，下次A再向主机B或者B向A发送信息时，直接从各自的ARP缓存表里查找就可以了。37．某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB(快表)采用全相联映射，有4个页表项，内容如下表所示。则对虚拟地址03FFF180H进行虚实地址变换的结果是A．0153180HB．0035180HC．TLB缺失D．缺页正确答案：A解析：虚拟地址为03FFF180H，其中页号为03FFFH，页内地址为180H，根据题目中给出的页表项可知页标记为03FFFH所对应的页框号为0153H，页框号与页内地址之和即为物理地址0153180H。38．某CPU主频为1．03GHz，采用4级指令流水线，每个流水段的执行需要1个时钟周期。假定CPU执行了100条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为A．0．25×109条指令／秒B．0．97×109条指令／秒C．1．0×109条指令／秒D．1．03×109条指令／秒正确答案：C解析：采用4级流水执行100条指令，在执行过程中共用4+(100—1)=103个时钟周期。CPU的主频是1．03GHz，也就是说每秒钟有1．03G个时钟周期。流水线的吞吐率为1．03G×100／103=1．0×109条指令／秒。39．A．B．C．D．正确答案：D40．A．B．C．D．正确答案：A综合应用题41-47小题，共70分。41．已知数组A[1．．n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。(1)给出算法的基本设计思想；(2)根据设计思想，采用C或C++或Java语言表述算法，关键之处给出注释；(3)说明你所设计算法的时间复杂度和空间复杂度。正确答案：用C语言算法描述如下：voildAdjust(intA[]){／／调整数组A，使得A的左边为负整数，右边为正整数inti=1，j=n，temp；while(i＜j)(while(A[i]＜0&&i＜j)i++；／／A[i]为负整数时，i增1while(A[j]＞0&&i＜j)j--；／／A[j]为正整数时，j减1if(i＜＜j){Letup：A[i]；A[i]：A[j]；A[j]：temp；／／A[i]为正整数、A[j]为负整数时，交换i++：j--；}}}(3)算法的时间复杂度为O(n)；算法的空间复杂度为O(1)。42．下面是给出的一段IP数据包头所包含的数据，OO00305252400080062C23COA80101D803E215，请根据IPv4头部格式回答如下问题：(1)该IP包的发送主机和接收主机的地址分别是什么?(2)该IP包的总长度是多少?头部长度是多少?(3)该IP分组有分片吗?如果有分片它的分片偏移量是多少?(4)该IP包是由什么传输层协议发出的?正确答案：(1)该IP包的发送主机和接收主机的地址分别是192．168．1．1和216．3．226．21。(2)该IP包的总长度是48，头部长度是20。(3)该IP分组没有分片。(4)该IP包是由TCP协议发出的。解析：本题考查IP数据报的格式，首先我们先列出IP头部的格式，然后按照这个格式来解析题目给出的头部数据。IPv4的头部格式如下图所示：版本(4位)：目前的协议版本号是4，因此IP有时也称作IPv4。首部长度(4位)：首部长度指的是IP层头部占32bit字的数目(也就是IP层头部包含多少个4字节一32位)，包括任何选项。由于它是一个4比特字段，因此首部最长为60个字节。普通IP数据报(没有任何选择项)字段的值是5，也就是5×32／8＝5×4＝20个字节。服务类型字段(8位)：服务类型(TOs)字段包括一个3bit的优先权子字段(现在已被忽略)，4bit的TOS子字段和1bit未用位但必须置0。总长度字段(16位)：整个IP数据报的长度，以字节为单位。利用首部长度字段和总长度字段，就可以知道IP数据报中数据内容的起始位置和长度。由于该字段长16比特，所以IP数据报最长可达65535字节总长度字段是IP首部中必要的内容。标识字段(16位)：唯一地标识主机发送的每一份数据报。通常每发送一份报文它的值就会加1。frag＿off域的低13位中分段偏移(Fragmentoffset)域指明了该分段在当前数据报中的什么位置上。除了一个数据报的最后一个分段以外，其他所有的分段(分片)必须是8字节的倍数。这是8字节是基本分段单位。由于该域有13个位，所以，每个数据报最多有8192个分段。frag—off的高3位：(1)比特0是保留的，必须为0；(2)比特1是“更多分片”(MF－MoreFragment)标志。除了最后一片外，其他每个组成数据报的片都要把该比特置1。(3)比特2是“不分片”(DF－Don’tFragment)标志，如果将这一比特置1，IP将不对数据报进行分片。这时如果有需要进行分片的数据报到来，会丢弃此数据报并发送一个ICMP差错报文给起始端。TTL(time—to—live)：生存时间字段设置了数据报可以经过的最多路由器数。它指定了数据报的生存时间。TTL的初始值由源主机设置(通常为32或64)，一旦经过一个处理它的路由器，它的值就减去1。协议字段(8位)：根据它可以识别是哪个协议向IP传送数据。当网络层组装完成一个完整的数据报之后，它需要知道该如何对它进行处理。协议(Protocol)域指明了该将它交给哪个传输进程。TCP是一种可能，但是UDP或者其他的协议也是可能的。首部检验和字段(16位)：根据IP首部计算的检验和码。它不对首部后面的数据进行计算。后面就是32位源IP地址和32位目的IP地址。(1)根据以上的分析，可以得出源IP地址是第13，14，15，16字节，也就是C0A80101，转换为十进制点分表示得到源IP地址为：192．168．1．1。目标IP地址是第17，18，19，20字节即D803E215，转换为十进制点分表示得到目标IP地址为：216．3．226．21。(2)IP包的总长度域是IP头部的第3，4字节，即0030。转换为十进制得到该IP包的长度是48。而头部长度为IHL域，是第一字节的后4个位表示，根据题目的数据IHL值是5，再将IHL的值乘以4，即得到头部的长度为20。(3)是否分片的标识在IP包头的第7字节的第7位表示，那么该分组的第7字节为40，对应第7位是‘1’，即DF位置为‘1’表示没有分片。(4)协议域是第10字节，值为06，用于表示传输层的协议，根据RFC标准，数值6表示的是TCP协议。43．某一计算机系统采用“主存—Cache”存储层次结构，主存容量有8个块，Cache容量有4个块，采用直接地址映像。(1)如果主存块地址流为0，1，2，5，4，6，4，7，1，2，4，1，3，7，2，主存内容一开始未装入Cache中，列出每次访问后Cache中各块的分配情况；(2)指出块命中的时刻；(3)求出此期间Cache的命中率。正确答案：(1)主存块地址流为0，1，2，5，4，6，4，7，1，2，4，1，3，7，2，主存内容一开始未装入Cache中，每次访问后Cache中各块的分配情况如下：(2)命中时刻的时刻为装入第二个4、第三个4以及第三个1和第三个2的时刻。(3)命中率=4／15×100％=26．67％。44．正确答案：(1)算法基本思想如下：从头至尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。(2)详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点，如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少个结点，当i＞k时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。(3)算法描述：intLocateElement(Linklistlist，intk){p1=list-＞link；p=list；i=1；while(p1){p1=p1-＞link；i++；if(i＞k)p=p-＞next；／／如果i＞k，则p也往后移}if(p==list)return0；／／说明链表没有k个结点else{printf(“％d＼