2011年计算机考研统考真题

2011年计算机考研统考真题 2011201120112011年计算机考研统考真题【1】设 n是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）。 x=2; while(x

2011201120112011年计算机考研统考真题【1】设 n是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）。 x=2; while(x 要求第 1个进入队列的元素存储在 A[0]处，则初始时 front和 rear的值分别是（）。 A.0,0 B.0,n-1 C.n-1,0 D,n-1,n-1 【解析】B。插入元素时，front不变，rear+1.而插入第一个元素后，队尾要指向尾元素，显然，rear初始应该为 n-1，front为 0。【4】若一棵完全二叉树有 768个结点，则该二叉树中叶子结点的个数是（）。 A.257 B.258 C.384 D.385 【解析】C。由完全二叉树的高度和结点个数的关系可得本完全二叉树的高度为 10。第 10层上的结点个数为 768-(29-1)=257（这些全为叶子结点）；第 9层上的非叶结点为 (257-1)/2+1=129；则第 9层上的叶子结点个数为：29-1-129=127；则叶子结点总数为 257+127=384。【5】若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4和 4,3,2,1，则该二叉树的中序遍历序列不会是（）。 A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 【解析】C。满足题干的二叉树必须满足树中不存在双分支结点。则可以画出以下二叉树排除选项：可以看出 A,B,D三项都是可以的。【6】已知一棵有 2011个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点的个数是（）。 A.115 B.116 C.1895 D.1896 【解析】D。可以采用特殊情况法去解。可举以下特例：如上图，则对应的二叉树中仅有前 115个结点有右孩子。【7】对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。 A.95,22,91,24,94,71 B.92,20,91,34,88,35 C.21,89,77,29,36,38 D.12,25,71,68,33,34 【解析】A。由选项 A做出查找路径的一部分，发现在 91的左子树中出现了大于 91的 94，因此 A 选项不可能。【8】下列关于图的叙述中，正确的是（）。 ①回路是简单路径 ②存储稀疏图，用邻接矩阵比邻接表更省空间 ③若有向图中存在拓扑序列，则该图不存在回路 A.仅① B仅①、② C仅③ D仅①、③ 【解析】C。（1）若路径中除了开始点和结束点可以相同以外，其余顶点均不相同，则称这条路径为简单路径。（2）若一条路径中第一个顶点和最后一个顶点相同，则这条路径是一条回路（回路中可能存在既不是起点也不是终点的相同点）。（3）邻接矩阵不图稀疏还是稠密，都取的是最大的存储空间，因此不如邻接表更适合存储稀疏矩阵。（4）用拓扑排序的方法可以判断图中是否存在回路，如果对一个图可以完成拓扑排序，则此图不存在回路。【9】为提高散列（Hash）表的查找效率，可采取的正确措施是（）。 ①增大装填因子 ② 设计冲突少的散列函数 ③处理冲突时避免产证聚集现象 A.仅① B.仅② C.仅①② D.仅②③ 【解析】B。要提高查找效率，就要减少 Hash表的冲突，因此②是正确的措施。对于①装填因子增大，则相应的表中空闲位置就少，更容易发生冲突，因此①不对。聚集现象是不可避免的，因此③不对。【10】为实现快速排序算法，待排序序列宜采用的存储方式是（）。 A.顺序存储 B.散列存储 C链式存储 D索引存储【解析】A。内部排序均采用顺序结构存储。【11】已知序列 25,13,10,12,9是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）。 A.1 B.2 C.4 D.5 【解析】B。在序列尾部插入 18后当前堆如下：可见 10<18(第一次比较)，需要调整，因此交换 10和 10得如下堆：可见 18<25(第二次比较)不需要再次调整，因此只需要调整 2次。【12】下列选项中，描述浮点数操作速度指标的是（）。 A.MIPS B.CPI C.IPC D.MFLOPS 【解析】D。这个不需要解释了，MFLOPS 表示每秒百万次浮点运算。【13】float 型数据通常用 IEEE754 单精度浮点数格式表示。如编译器将 float型变量 x 分配在一个 32 位浮点寄存器 FR1 中，且 x =-8.25，则 FR1 的内容是（）。 A.C104 0000H B.C242 0000H C.C184 0000H D.C1C2 0000H 【解析】A。此题着重考查了 IEEE754 单精度浮点数格式。只要知道格式，基本上就是硬套公式了。首先，将 x表示成二进制，即-1000.01 = -1.00001 112× 。其次应该计算阶码（不妨设为 E），根据 IEEE754单精度浮点数格式有 E-127=3，故 E=130，换成二进制为 1000 0010。最后，要记住最高位“1”是被隐藏的。所以，根据 IEEE754 格式：符号（1 位）+偏移的阶码（8位）+尾数（23 位），即： 1 + 1000 0010 + 0000 1000 0000 0000 000 转换成十六进制：1100 0001 0000 0100 0000 0000 0000 0000，即 C1040000H。【14】下列各类存储器中，不采用随机存取方式的是（）。 A.EPROM B.CDROM C.DRAM D.SRAM 【解析】B。首先，ROM 和 RAM 都是随机存储的。而 EPROM 属于 ROM；SRAM 和 DRAM 属于 RAM，故都是采用随机存取方式。而 CDROM 属于光盘，为非随机存储。【15】某计算机存储器按字节编址，主存地址空间大小为 64MB，现用 4M x 8位的 RAM 芯片组成 32MB 的主存储器，则存储器地址寄存器MAR 的位数至少是（）。 A.22位 B.23 位 C.25 位 D.26位【解析】D。本题有个陷阱，相信不少考生会以 32MB 的实际主存来计算，从而得到答案 25 位，这种解法是错误的。尽管多余的 32MB 没有使用，但是你也得防备以后要用。不能只看眼前呀！知道以 64MB 来计算就很好做了。由于采用字节寻址，所以寻址范围是 64M，而 M64226 = 。故存储器地址寄存器MAR 的位数至少是 26 位。【16】偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（）。 A.间接寻址 B.基址寻址 C.相对寻址 D.变址寻址【解析】A。B、C、D都是某个寄存器内容与一个形式地址相加而生成有效地址，请参考寻址方式总结。各种寻址方式的有效地址和用途总结：寻址方式有效地址计算方式用途及特点立即寻址 —— 通常用于给寄存器赋初值直接寻址 AEA = —— 隐含寻址 —— 缩短指令字长。一次间接寻址 )(AEA = 扩大寻址范围，易于完成子程序返回。寄存器寻址 i REA = 指令字较短；指令执行速度较快。寄存器间接寻址 )( i REA = 扩大寻址范围。基址寻址 )(BRAEA += 扩大操作数寻址范围；适用于多道程序设计，常用于为程序或数据分配存储空间。变址寻址 )(IXAEA += 主要用于处理数组问题。相对寻址 )(PCAEA += 用于转移指令和程序浮动先间接再变址 )()( IXAEA += —— 【17】某机器有一个标志寄存器，其中有进位/借位标志 CF、零标志 ZF、符号标志 SF 和溢出标志 OF，条件转移指令 bgt（无符号整数比较大于时转移）的转移条件是（）。 A. 1=+OFCF B.SF ZF 1+ = C.CF ZF 1+ = D.CF SF 1+ = 【解析】C。假设有两个无符号整数 yx、，bgt 为无符号整数比较大于时转移，不妨设 yx > ，那么 yx − 就肯定大于 0 且不会溢出，故符号标志 SF 和溢出标志 OF用不上。根据排除法答案自然选 C。因为 yx − >0，所以肯定不会借位和进位，且 0≠− yx 。故 CF 和 ZF 标志均为 0。【18】下列给出的指令系统特点中，有利于实现指令流水线的是（）。 I. 指令格式规整且长度一致 II. 指令和数据按边界对齐存放 III. 只有 Load/Store 指令才能对操作数进行存储访问 A.仅 I、II B.仅 II、III C.仅 I、III D.I、II、III 【解析】D。I、II、III均为 RISC 的特性，所以都可以简化流水线的复杂度。 RISCRISCRISCRISC的主要特点总结： � 选取使用频度较高的一些简单指令以及一些很有用但又不复杂的指令，让复杂指令的功能由频度高的简单指令的组合来实现。 � 指令长度固定，指令格式总类少，寻址方式种类少。 � 只有取数/存数指令访问存储器，其余指令的操作都在寄存器内完成。 � CPU中有多个通用寄存器（比 CISC 的多）。 � 采用流水线技术（注意：RISCRISCRISCRISC一定是采用流水线），大部分指令在一个时钟周期内完成。采用超标量和超流水线技术（这两个技术在第五章会详细讲解，这里知道就好），可使每条指令的平均执行时间小于一个时钟周期。 � 控制器采用组合逻辑控制，不用微程序控制（什么是组合逻辑第二章讲过，说白了就是 N多的逻辑电路；微程序控制将会在第五章讲解）。 � 采用优化的编译程序。【19】假定不采用 Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（）。 A. 每个指令周期中 CPU都至少访问内存一次 B. 每个指令周期一定大于或等于一个 CPU时钟周期 C. 空操作指令的指令周期中任何寄存器的内容都不会被改变 D. 当前程序在每条指令执行结束时都可能被外部中断打断【解析】C。由于不采用 Cache 和指令预取技术，所以不可能从 Cache以及在前一个指令执行的时候取指令，所以每个指令周期中 CPU必须访问一次主存取指令，故 A正确。B 是显然正确。至少 PC 寄存器的内容会自加 1，故 C错误。由于机器处于“开中断”状态，所以当前程序在每条指令执行结束时都可能被外部中断打断。【20】在系统总线的数据线上，不可能传输的是（）。 A.指令 B.操作数 C.握手（应答）信号 D.中断类信号【解析】C。指令、操作数、中断类信号都是可以在数据线上传输，而握手（应答）信号必须在通信总线中传输。总结：总线被分为片内总线、系统总线（包括数据总线、控制总线、地址总线）、通信总线。【21】某计算机有五级中断 4 0~L L ，中断屏蔽字为 4 3 2 1 0 , 1(0 4)iM M M M M M i= ≤ ≤ 表示对 i L 级中断进行屏蔽。若中断响应优先级从高到低的顺序是 0 1 2 3 4L L L L L→ → → → ，且要求中断处理优先级从高到低的顺序是 4 0 2 1 3L L L L L→ → → → ，则 1L 的中断处理程序中设置的中断屏蔽字是（）。 A.11110 B.01101 C.00011 D.01010 【解析】D。只要知道做题方法，5秒钟搞定。首先看 1L 所在的位置。后面只有 3L 比自己低，所以把自己和 3L 位置的屏蔽触发器的内容置为 1，其余为 0，即 01010。【22】某计算机处理器主频为 50MHz，采用定时查询方式控制设备 A 的 I/O，查询程序运行一次所用的时钟周期至少为 500。在设备 A工作期间，为保证数据不丢失，每秒需对其查询至少 200 次，则 CPU 用于设备 A的 I/O 的时间占整个 CPU时间的百分比至少是（）。 A.0.02% B.0.05% C.0.20% D.0.50% 【解析】C。由于 CPU 每秒需对其查询至少 200 次，每次 500 个时钟周期。所以 CPU 用于设备 A的 I/O时间每秒最少 500×200=100000个时钟周期。故 CPU用于设备 A的 I/O 的时间占整个 CPU 时间的百分比至少为： %2.0%100 50000000 100000 %100 50 100000 =×=× M 【23】下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（）。 A．先来先服务 B．高响应比优先 C．时间片轮转 D．非抢占式短任务优先【解答】B。这里考察的是多种作业调度算法的特点。响应比=作业响应时间/作业执行时间=（作业执行时间+作业等待时间）/作业执行时间。高响应比算法，在等待时间相同情况下，作业执行的时间越短，响应比越高，满足段任务优先。同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。下面给出几种常见的进程调度算法特点的总结，读者要在理解的基础上识记。先来先服务短作业优先高响应比优先时间片轮转多级反馈队列能否是可抢占否能能能队列内算法不一定能否是不可抢占能能能否队列内算法不一定优点公平，实现简单平均等待时间最少，效率最高兼顾长短作业兼顾长短作业兼顾长短作业，有较好的响应时间，可行性强缺点不利于短作业长作业会饥饿，估计时间不易确定计算响应比的开销大平均等待时间较长，上下文切换浪费时间无尤其适用于无作业调度，批处理系统无分时系统相当通用决策模式非抢占非抢占非抢占抢占抢占【24】下列选项中，在用户态执行的是（）。 A．命令解释程序 B．缺页处理程序 C．进程调度程序 D．时钟中断处理程序【解析】A。CPU 状态分为管态和目态，管态又称特权状态、系统态或核心态。通常，操作系统在管态下运行，CPU 在管态下可以执行指令系统的全集。目态又称常态或用户态，机器处于目态时，程序只能执行非特权指令，用户程序只能在目态下运行。 CPU 将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统及其相关模块使用，普通的应用程序不能使用。缺页处理与时钟中断都属于中断，会对系统造成影响，因此只能在核心态执行。进程调度属于系统的一部分，也只能在核心态执行。命令解释程序属于命令接口，是操作系统提供给用户所使用的接口，因此可以用在用户态执行。补充：常见的特权指令有以下几种（1）有关对 I/O 设备使用的指令。如启动 I/O设备指令、测试 I/O 设备工作状态和控制 I/O设备动作的指令等。（2）有关访问程序状态的指令。如对程序状态字（PSW）的指令等。（3）存取特殊寄存器指令。如存取中断寄存器、时钟寄存器等指令。（4）其他指令本题中 B、D都是要修改中断寄存器，C要修改程序状态字（PSW）。【25】在支持多线程的系统中，进程 P创建的若干个线程不能共享的是（）。 A．进程 P的代码段 B．进程 P中打开的文件 C．进程 P的全局变量 D．进程 P中某线程的栈指针【解析】D。进程是资源分配的基本单元，进程下的各线程可以并行执行，它们共享进程的虚地址空间，但各个进程有自己的栈，各自的栈指针对其他线程是透明的，因此进程 P 中某线程的栈指针是不能共享的。【26】用户程序发出磁盘 I/O 请求后，系统的正确处理流程是（）。 A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序 B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序 C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序 D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序【解析】B。首先用户程序（目态）是不能直接调用设备驱动程序的，有关对 I/O 设备使用的指令是特权指令，通过系统调用，把进程的状态从用户态变为核心态，故 C、D 错误。I/O 软件一般从上到下分为四个层次：用户层、与设备无关软件层、设备驱动程序及中断处理程序。与设备无关软件也就是系统调用的处理程序。因此正确处理流程为 B。【27】某时刻进程的资源使用情况如下表所示：进程已分配资源仍需分配可用资源 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 0 0 0 1 0 2 1 P2 1 2 0 1 3 2 P3 0 1 1 1 3 1 P4 0 0 1 2 0 0 此时的安全序列是（）。 A.P1,P2，P3,P4 B.P1，P3，P2，P4 C.P1，P4，P3，P2 D.不存在【解析】D。使用银行家算法可知，不存在安全序列。由于初始 R1 资源没有剩余，只能分配资源给 P1 执行，P1 完成之后释放资源，这时由于 R2 只有 2 个剩余，因此只能分配对应资源给 P4 执行，P4 完成之后释放资源，但此时 R2 仍然只有 2 个剩余，无法满足 P2、P3 的要求，无法分配。因此产生死锁状态。【28】在缺页处理过程中，操作系统执行的操作可能是（）。 I修改页表 II 磁盘 I/O III 分配页框 A.仅 I,II B.仅 II C.仅 III D.I,II 和 III 【解析】D。这些情况都可能发生，当产生缺页中断时，肯定会修改页表项并分配页框（分配页框出现在有空余页面的情况下），并且会从外存将所缺页调入，产生磁盘 I/O。【29】当系统发生抖动（trashing）时，可以采取的有效措施是（）。 I.撤销部分进程 II.增加磁盘交换区的容量 III.提高用户进程的优先级 A.仅 I B.仅 II C.仅 III D.仅 I,II 【解析】A。在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存中换出的进程。抖动现象是指刚刚被换出的内容又要被访问，因此马上又要换入这种系统频繁置换页面的现象。发生抖动时系统会将大部分时间用于处理页面置换上，降低系统效率。撤销部分进程可以减少系统页面数，可以有效防止系统抖动。改变优先级与增大交换区容量对减少抖动没有帮助。【30】在虚拟内存管理中，地址变换机构将逻辑地址变为物理地址，形成该逻辑地址的阶段是（）。 A.编辑 B.编译 C.链接 D.装载【解析】B。编译过程指编译程序将用户源代码编译成目标模块，在编译源代码的过程中，编译程序会将程序所使用的变量地址信息转化为逻辑地址。编辑过程是指编辑源代码的过程，此时还没有地址的概念。而链接和装载都是对编译好的程序进行处理，包括将逻辑地址转化为物理地址。【31】某文件占 10 个磁盘块，现要把文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为 100μs，将缓冲区的数据传送到用户区的时间是 50μs，CPU 对一块数据进行分析的时间为 50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（）。 A.1500μs，1000μs B.1550μs，1100μs C.1550μs，1550μs D.2000μs，2000μs 【解析】B。单缓冲区当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为 150×10 = 1500，加上处理最后一个磁盘块的时间 50，得 1550。双缓冲区情况下，不存在等待磁盘块从缓冲区读入用户区的问题，因此传输数据全部传输到缓冲区的时间为 100×10 = 1000，再加上将双缓冲区的数据传输到用户区并处理完的时间 2×50 = 100，得 1100。【32】有两个并发执行的进程 P1 和 P2，共享初值为 1的变量 x。P1 对 x 加 1，P2 对 x 减 1。加 1 和减 1 操作的指令序列分别如下所示。 //加 1 操作 //减 1 操作 load R1，x ①//取 x 到寄存器 R1 中 load R2，x ④ inc R1 ② dec R2 ⑤ store x,R1 ③//将 R1 的内容存入 x store x，R2 ⑥ 两个操作完成后，x的值（）。 A.可能为-1 或 3 B.只能为 1 C.可能为 0、1 或 2 D.可能为-1、0、1 或 2 【解答】C。执行①②③④⑤⑥结果为 1，执行①②④⑤⑥③结果为 2，执行④⑤①②③ ⑥结果为 0，结果-1 无法得到。【33】TCP/IP 参考模型的网络层提供的是（）。 A.无连接不可靠的数据报服务 B.无连接可靠的数据报服务 C.有链接不可靠的虚电路服务 D.有链接可靠的虚电路服务【解析】A。首先，网络层的传输采用的是 IP 分组，IP 分组中头部含有源 IP 地址和目的 IP 地址，并不是一个虚电路号，所以网络层采用的是数据报服务；其次，IP 分组的头部也没有对分组进行编号和提供校验字段，所以网络层提供的是不可靠服务；最后， IP 分组首部也没有相关的建立连接的字段，所以网络层属于无连接。【34】若某通信链路的数据传输速率为 2400bps，采用 4 相位调制，则该链路的波特率是（）。 A. 600波特 B. 1200波特 C. 4800 波特 D. 9600 波特【解析】B。题目中说采用 4 个相位，换句话说就是可以表示 4 种状态，故一个码元可以携带 2bit（ 22 =4）的信息。根据比特率（或者称为数据传输率）和波特率的关系。假设每个码元可以携带 n位信息，则比特率=n×码元率，由题意可知，比特率为 2400bps，且 n=2，故码元率为 1200bps。【35】数据链路层采用选择重传协议（SR）传输数据，发送方已发送了 0~3 号数据帧，现已收到 1 号帧的确认，而 0、2 号帧依次超时，则此时需要重传的帧数是（）。 A. 1 B. 2 C. 3 D. 4 【解析】B。此题需要考生很清楚的了解选择重传的工作原理。选择重传协议是不支持累积确认的。何为累积确认？即如果发送方连续发送 0、1、2、3、4号帧。前面 0、1、2、 3号帧的确认都丢失，但是在发送方重发之前却收到了 ACK5，表明前面的 0、1、2、3、4 都已经收到，接收方期待 5 号帧的接收。后退 N 帧协议是支持累积确认的。回到题目，由于只收到 1 号帧的确认，0、2 号帧超时，且由于不支持累积确认，所以需要重传 0、2 号帧。如果此题数据链路层采用后退 N帧协议（GBN）传输数据，由于它具有累积确认的作用，答案就应该选择 A了。可能疑问点：如果不按序的接收，交给主机的话岂不是全部乱套了？解析：如果没有按序，正确的接收帧先存入接收方的缓冲区中，同时要求发送方重传出错帧，一旦收到重传帧后，就和原先存在缓冲区的其余帧一起按正确的顺序送主机。所以说选择重传协议避免了重复传输那些本来已经正确到达接收方的数据帧，进一步提高了信道利用率。但是代价是增加了缓冲空间。【36】下列选项中，对正确接收到的数据帧进行确认的 MAC 协议是（）。 A. CSMA B. CDMA C. CSMA/CD D. CSMA/CA 【解析】D。此题相信大部分考生的情况是对于 A 和 C 比较熟悉，B和 D 完全不知所云。因为在复习的过程中可能不会太在意。CSMA/CD 协议相信考生再熟悉不过，整个过程也能够倒背如流，并没有看到任何需要进行确认的影子，立马可以被排除。其次，CSMA/CD 协议是对 CSMA 协议的改进，既然 CSMA/CD 都没有，那 CSMA协议就必然没有。 CSMA/CA 主要用在无线局域网中，由 IEEE802.11标准定义，它在 CSMA 的基础上增加了冲突避免的功能。冲突避免要求每个结点在发送数据之前监听信道。如果信道空闲，则发送数据。发送结点在发送完一个帧后，必须等待一段称为帧间间隔的时间，检查接收方是否发回帧的确认。如果收到确认，则表明无冲突发生；如果在规定时间内没有收到确认，表明出现冲突，重发该帧。 CDMA被称为码分多路复用，工作在物理层，不存在对数据帧进行确认。【37】某网络拓扑如下图所示，路由器 R1 只有到达子网 192.168.1.0/24的路由。为使 R1 可以将 IP 分组正确地路由到图中所有子网，则在 R1 中需要增加的一条路由（目地网络，子网掩码，下一跳）是（）。【解析】D。很明显本题考察了路由聚合的相关知识点。首先将网络 192.168.2.0/25和网络 192.168.2.128/25 进行聚合。方法如下： 192.168.2.0 换成二进制 11000000110000001100000011000000 10101000101010001010100010101000 00000010000000100000001000000010 00000000 192.168.2.128 换成二进制 11000000110000001100000011000000 10101000101010001010100010101000 00000010000000100000001000000010 10000000 发现前 24 位一样，所以聚合后的超网为：192.168.2.0/24，子网掩码自然就是 24 个 1，后面全为 0，即 11111111 11111111 11111111 00000000（255.255.255.0）。下一跳从图中可以得出为 192.168.1.2。 A. 192.168.2.0, 255.255.255.128, 192.168.1.1 B. 192.168.2.0, 255.255.255.0, 192.168.1.1 C. 192.168.2.0, 255.255.255.128, 192.168.1.2 D. 192.168.2.0, 255.255.255.0, 192.168.1.2 【38】在子网 192.168.4.0/30 中，能接受目的地址为 192.168.4.3 的 IP 分组的最大主机数是（）。 A. 0 B. 1 C.2 D. 4 【解析】C。首先在网络 192.168.4.0/30中只有 2位主机号，取值范围如下（为了简便，二进制和十进制混合用）： 192.168.4.00000000000000 ～ 192.168.4.00000011111111 （ 192.168.4.0 ～ 192.168.4.3 ）发现什么了？192.168.4.3 恰好是其广播地址（广播地址的概念就是主机号全为 1）。既然是广播地址，所以只要是在此网络内的主机，全部都可以接收到广播地址所发出的 IP 分组。而此网络一共有 2 个主机（4-2=2，要去掉全 0 和全 1）。【39】主机甲向主机乙发送一个（SYN=1,seq=11220）的 TCP 段，期望与主机乙建立 TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的 TCP 段可能是（）。 A. (SYN=0,ACK=0,seq=11221，ack=11221) B. (SYN=1,ACK=1,seq=11220，ack=11220) C. (SYN=1,ACK=1,seq=11221，ack=11221) D. (SYN=0,ACK=0,seq=11220，ack=11220) 【解析】C。这个在《计算机网络高分笔记》一书中强调过，不管是连接还是释放，SYN、 ACK、FIN 的值一定是 1，排除 A 和 D选项。并且确认号是甲发送的序列号加 1，ACK 的值应该为 11221（即 11220已经收到，期待接收 11221）。另外需要提醒的一点是，乙的 seq 值是主机随意给的，和甲的 seq值没有任何关系，请参考下面的总结。【40】主机甲与主机乙之间建立了一个 TCP 连接，主机甲向主机乙发送了 3个连续的 TCP 段，分别包含 300字节、400字节和 500字节的有效载荷，第 3个段的序号为 900。若主机乙仅正确收到第 1 和第 3个段，则主机乙发送给主机甲的确认序号是（）。 A. 300 B. 500 C. 1200 D.1400 【解析】B。首先应该计算出第 2 个段的第一个字节的序号。第三个段的第一个字节序号为 900，由于第 2 个段有 400字节，所以第 2 个段的第一个字节的序号为 500。另外，由于确认号就是期待接收下一个 TCP 段的第一个字节序号，所以主机乙发送给主机甲的确认序号是 500。综合题部分【41】已知有一个 6个顶点（顶点编号 0～5）的有向带权图 G，其邻接矩阵 A为上三角矩阵，它的压缩存储如下：要求： (1) 写出图G的邻接矩阵A； (2) 画出有向带权图G； (3) 求图 G的关键路径，并计算关键路径的长度。【解析】本题考察图的存储以及关键路径求解的综合知识。（1）由题可以画出待定上三角矩阵的结构图如下（图中“？”为待定元素）：可以看出，第一行至第五行主对角线上方的元素分别为5,4,3,2,1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：将各元素填入各行即得邻接矩阵：（2 分）（2）根据第一步所得矩阵A 容易做出有向带权图G，如下：（2 分）（3）下图中粗线箭头所标识的4 个活动组成图G 的关键路径。（3 分）由上图容易求得图的关键路径长度为：4+5+4+3=16。【42】一个长度为L（L≥1）的升序序列S，处在第 ⎡ ⎤2/L 个位置的数称为S的中位数。例如，若序列S1 = (11, 13, 15, 17, 19)，则S1 的中位数为15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2 = (2, 4, 6, 8, 10)，则S1 和S2 的中位数为11。现有两个等长的升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：（1）给出算法的基本设计思想；（2）根据设计思想，采用C 或C++或JAVA 语言描述算法，关键之处给出注释；（3）说明你所设计算法的时间复杂度和空间复杂度。【解析】本题考察基本算法的灵活运用。（1）算法的基本设计思想：（5 分） ①笨法：如果考场紧张，无奈之下可以写如下算法（虽然不能得全分，但总比花时间又写错好的多）。算法如下：将两升序序列归并排序，然后求其中位数，时间复杂度为O(n),空间复杂度为O(n)。 ②高效方法：分别求两个升序序列A 和B 的中位数，设为a 和b。 1）若a = b，则a 或b 即为所求的中位数。原因：容易验证，如果将两序列归并排序，则最终序列中，排在子序列ab 前边的元素为先前两序列中排在a 和b 前边的元素；排在子序列ab 后边的元素为先前两序列a 和b 后边的元素。所以子序列ab 一定位于最终序列的中间，又因为a=b，显然a 就是中位数。 2）否则（假设a

                    本文档为【2011年计算机考研统考真题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

2011年计算机考研统考真题

你可能还喜欢