1、计算机专业（基础综合）模拟试卷 35 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。void fun(int n)int i，k；for(i1；iBCD。下表列出了执行每级中断服务程序所需的时间。 如果以执行中断服务程序的时间作为确定中断优先级的尺度：时间越短优先级越高。 (1)请指出如何为各级中断服务程序设置屏蔽码? (2) 如果 A、B 、C、D 分别在6s、8s、10s、0s 时刻发出中断请求，请画出 CPU 执行中断服务程序的序列。
2、 (3)基于上题，请计算上述四个中断服务程序的平均执行时间。45 某大学的阅览室共有 300 个座位，同学进入时必须先在管理处用学生证换取座位牌，若座位满了，同学就要在阅览室外等候。当有同学离开时，要到管理处用座位牌换回学生证。请画出流程图，试用一种类语言，利用信号量和 P、V 操作，描述同学进入和离开阅读室的过程。46 某虚拟存储系统中有一个进程共有 6 页(05)，其中代码占 3 页(02)，数据占1 页(3)，数据堆占 1 页(4)，用户栈占 1 页(5)。它们依次存放在外存的22，23，25，26 存储块。当前，代码页已经分配在物理内存的 66，67，87 页，数据页为 31，并已经进
3、行了修改。数据堆页还没有分配内存，用户栈分配在 01 页。请问：(1)页表中应该包含哪些项目? 请填写此页表(见下表)。(2)若内存堆申请内存，因无分配物理内存而产生缺页中断，此时内存无空闲页面，则采用 LRU 页面淘汰算法选中内存的那个页面?操作系统作何处理? 页表又如何变化 ?设当前时刻为虚拟时间 1256。47 主机 A 向主机 B 连续发送了两个 TCP 报文段，其序号分别为 70 和 100。试问：(1)第一个报文段携带了多少个字节的数据?(2)主机 B 收到第一个报文段后发回的确认中的确认号应当是多少?(3)如果主机 B 收到第二个报文段后发回的确认中的确认号是 180，试问 A
4、发送的第二个报文段中的数据有多少字节?(4)如果 A 发送的第一个报文段丢失了，但第二个报文段到达了 B。B 在第二个报文段到达后向 A 发送确认。试问这个确认号应为多少 ?计算机专业（基础综合）模拟试卷 35 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 基本运算语句是 k5*k ，设其执行时间为 T(n)。对于 j 每循环一次，该语句的执行次数为 m，有：5 mn，即 mlog5n。所以：2 【正确答案】 B【试题解析】 利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及
5、进行后缀表达式求值这两步操作可以和在一起进行，需要设立运算符栈 OPTR 和运算数栈 OPND 两个栈。例如求选项 A 的表达式 AB*(CD)的过程如下表所示：按照上述过程可知，选项 A 求值时，运算数栈 OPND 的大小至少为 4。例如求选项 B 的表达式(AB)*CD 的过程如下表所示： 按照上述过程可知，选项 B 求值时，运算数栈 OPND 的大小至少为 2。类似地，选项 C、D 求值时，运算数栈 OPND 的大小至少为 3、3。因此本题答案为 B。3 【正确答案】 B【试题解析】 输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项 A，输入序列为 abcd
6、，输出序列为 dacb，由输出受限性质可知以 da开头的结果只有 dabc，选项 A 为错误答案。分析选项 B，输入序列为 abcd，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输入 b，这时队列中的序列为 ba，再在输出端输入c，这时队列中的序列为 bac；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。分析选项 C，输入序列为 abcd，输出序列为 dbca，由输出受限性质可知以 db开头的结果只有 dbac，选项 C 为错误答案。4 【正确答案】 C【试题解析】 一棵二叉树每层只有 1
7、个结点，则具有 1025 个结点的二叉树的最大高度为 1025。一个具有 1025 个结点的完全二叉树的高度为 11。这一个具有1025 个结点的二叉树的高 h 为 11 至 1025 之间。5 【正确答案】 D【试题解析】 对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵
8、二叉排序树的平均查找长度的值不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n 成正比。6 【正确答案】 D【试题解析】 简单无向图的邻接矩阵是对称的，且对角线元素均是 0，故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式)： k (n1)(n2)10n 2(12n)n(n 1)2。7 【正确答案】 A【试题解析】 邻接矩阵的空间复杂度为 O(n2)，与边的个数无关。邻接表的空间复杂度为 O(ne)，与图中的结点个数和边的个数都有关。8 【正确答案】 D【试题解析】 根据折半查找的过程，由于需要栈结构实现递归算法，栈
9、的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。 第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n4；依次类推，当所确定的查找区间中的元素为 0 时，递归调用该算法的次数为 log 2n1 次，查找结束。 归纳总结折半查找法在查找成功时和给定值进行比较的关键字个数至多是log 2n1；在查找不成功时和给定值进行比较的关键字个数最多也不超过log 2n1。9 【正确答案】
10、C【试题解析】 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。10 【正确答案】 D【试题解析】 按照所有中国人的生日(月、日)排序，一方面待排序记录个数 n 是非常大的，另一方面关键字所含的排序码为 2，且一个排序码基数为 12，另一个为31，都是较小的常数值，采用基数排序可以在 O(n)内完成排序过程。11 【正确答案】 D【试题解析】 本题主要考查各种排序的手工排序过程。选择排序在每趟结束后可以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递增，直到最后的一个有序的完整序列；希尔排
11、序也是形成部分有序的序列；快速排序以某个元素为界将大于它和小于它的关键字划分为两个子序列，再将该元素放在中间。观察题中的元素排序过程，可知是快速排序。12 【正确答案】 B【试题解析】 本题图中所示为冯.诺依曼计算机硬件系统的五大基本部件，包括运算器、控制器、存储器、输入设备和输出设备五大基本部件。归纳总结 运算器用来进行各种运算和数据转换；控制器则为计算机的工作提供统一的时钟和各种命令，协调计算机的各部件自动地工作；存储器用来存放程序、数据；输入设备和输出设备用来接收用户提供的外部信息或向用户提供输出信息。解题技巧 图中虚线框内是 CPU 部分，CPU 包括运算器和控制器，据此可排除选项 C
12、；与其他 4 个部件均有联系，可以确定是控制器，据此可排除选项 A；最后根据信息的传送方向可确定为输入设备，为输出设备。13 【正确答案】 C【试题解析】 A 选项为7，B 选项为7 的原码， D 选项为7 的补码。归纳总结 正数的原码、补码和反码的表示形式是相同的，都等于真值本身，而负数的原码、补码和反码各有不同的表示，其中反码表示法是将真值的数值部分按位取反。解题技巧 因为这是一个负数，所以可以首先排除掉选项 A。然后可以看出选项B、C、D 分别代表7 的原码、反码和补码。14 【正确答案】 C【试题解析】 如果仅考虑纠正 1 位错的情况，只要满足 2knk 1 就可以了(设校验位的位数为
13、 k，信息位的位数为 n)。此题中因为 n8，所以 k4。如果在纠正 1 位错的同时还要能发现 2 位错，则满足 2k1 nk 1。 归纳总结海明码实现原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。15 【正确答案】 D【试题解析】 X 补被称为 X朴的机器负数，由 X补求X补的过程称为对X补变补(求补)，这是做减法运算时必须要完成的操作。 归纳总结不管 X 的真值为正或为负，已知X 朴求 X 补的方法是：
14、将 X补连同符号位一起求反，末尾加“1”。 X 补 表示的真值如果是正数，则变补后X 补所表示的真值变为负数；反过来，X 补表示的真值如果是负数，则变补后X 朴所表示的真值变为正数。 解题技巧 此题容易错选选项 C。如果除符号位外，各位变反，末位加 1，得到的是x原而不是 X补，且只有 x 为负数时成立。16 【正确答案】 B【试题解析】 DRAM 的集成度高于 SRAM，SRAM 的速度高于 DRAM，可以推出 DRAM 的成本低于 SRAM，sRAM 芯片工作时不需要刷新，DRAM 芯片工作时需要刷新。归纳总结 随机存储器 RAM 又可分为静态 RAM(SRAM)和动态 RAM(DRAM)
15、两种。SRAM 由 6 个 MOS 管组成一个记忆单元，它的存取速度快，但集成度低，功耗也较大；DRAM 由 4 个 MOS 管或单个 MOS 管组成一个记忆单元，它的集成度高，功耗小，但存取速度慢。DRAM 是靠 MoS 电路中的栅极电容来存储信息的，栅极电容上的电荷数目会随着时间推移逐步泄漏，因此每隔一定的时间必须向棚极电容补充一次电荷，这个过程称为“刷新”。解题技巧 这类选择题是由多选题改造而来的单选题，其难度高于普通的单选题。在解题时需要首先判断多段叙述中各自的正确性，然后再在四个选项中挑选正确的选项。17 【正确答案】 A【试题解析】 对某个寄存器中的某几位清零又称为按位清，将此寄存
16、器的内容和一个特定的源操作数做“与”运算，即可得到。归纳总结 一般计算机都具有与、或、非和异或等逻辑运算指令。这类指令在没有设置专门的位操作指令的计算机中常用于对数据字(字节)中某些位(一位或多位)进行操作。如利用“与”指令还可以使目的操作数的某些位置“0”。只要源操作数的相应位为“0”，其余位为“1”，然后执行“与”指令即可。利用“或”指令可以使目的操作数的某些位置“1”。只要源操作数的相应位为“1”，其余位为“0”，然后执行“或”指令即可。解题技巧 此题容易错选选项 D，XOR 指令可以实现对整个寄存器的全部位清零的功能，但不能实现对指定的某几位清零的功能。18 【正确答案】 C【试题解析
17、】 具有 3 个功能段的流水线连续执行 IO 条指令共需时间3t9t12t。归纳总结 流水线在开始时总要有一段建立时间，结束时又需要有排空的时间，设一 m 段流水线的各段经过时间均为 t，则需要 T。mt 的流水建立时间，之后每隔 t 就可流出一条指令，完成 n 个任务共需时间 Tmt(n1)t。19 【正确答案】 B【试题解析】 除去 101 条机器指令所对应的 101 个微程序外，至少还有一个取指微程序，所以至少有 102 个微程序。归纳总结 通常，一条机器指令对应一个微程序。由于任何一条机器指令的取指令操作都是相同的，因此可以将取指令操作抽出来编成一个独立的微程序，这个微程序只负责将指令
18、从主存中取出送至指令寄存器。此外，也可以编出对应间址周期的微程序和中断周期的微程序。这样，控制存储器中的微程序个数应等于指令系统中的机器指令数再加上对应的取指、间址和中断周期等公用的微程序数。若指令系统中具有 n 种机器指令，则控制存储器中的微程序数至少有 n1 个。20 【正确答案】 C【试题解析】 在总线的 104 根信号线中，数据总线占 32 根，也就是 4 个字节，由于总线工作频率为 33MHz，所以理论的最大数据传输率4B33MHz132MB s。归纳总结 总线的最大数据传输率又称总线带宽，即每秒传输的字节数。总线带宽一总线宽度总线频率。21 【正确答案】 C【试题解析】 RGB8：
19、8：8 是指红、绿、蓝 3 种颜色都各有 8 位，总共的颜色深度为 24 位，所以颜色数为 2 孔种。归纳总结 颜色深度与颜色数的对应关系是：颜色数2 颜色深度。22 【正确答案】 C【试题解析】 中断和 DMA 方式是 IO 设备与主机间交换数据常采用的传送控制方式，在这两种控制方式下，CPU 和 IO 设备可以并行工作，由于中断方式需要执行中断服务程序，并且完成一次程序中断还需要许多辅助操作，所以它主要适用于中、低速外设。归纳总结 中断方式下，外设在做好输入输出准备时，向主机发中断请求，主机接到请求后就暂时中止原来执行的程序，转去执行中断服务程序对外部请求进行处理，在中断处理完毕后返回原来
20、的程序继续执行。DMA 方式是在主存和外设之间开辟直接的数据通路，可以进行基本上不需要 CPU 介入的主存和外设之间的信息传送，这样不仅能保证 CPU 的高效率，而且能满足高速外设的需要。中断方式和 DMA 方式的主要区别为：(1)中断方式是程序切换，需要保护和恢复现场；而 DMA 方式除了开始和结尾时，不占用 CPU 的任何资源。(2)对中断请求的响应时间只能发生在每条指令执行完毕时；而对 DMA 请求的响应时间可以发生在每个机器周期结束时。(3)中断传送过程需要 CPU 的干预；而 DMA 传送过程不需要 CPU 的干预，故数据传输速率非常高，适合于高速外设的成组数据传送。(4)DMA 请
21、求的优先级高于中断请求。(5)中断方式具有对：异常事件的处理能力，而 DMA 方式仅局限于完成传送数据块的 IO 操作。23 【正确答案】 C【试题解析】 交互式操作系统有时又称为分时操作系统，它将时间分成一个个的片段，轮流分给每个用户，用户将分到的时间片段用于本进程的运行。交互式系统强调交互，所以，对用户的输入及时响应就显得非常重要，而分时方式最能够及时地响应用户的请求，因为分时系统能够频繁地给多个用户分配时间。因此如何保证操作系统能及时地接收多个用户的输入就成了交互式操作系统设计的目标，也是交互式系统需要解决的关键问题。24 【正确答案】 C【试题解析】 本题考查并发进程的特点，并结合信号
22、量进行同步的原理。由于进程并发，所以，进程的执行具有不确定性，在 P1、P2 执行到第一个 PV 操作前，应该是相互无关的。现在考虑第一个对 s1 的 PV 操作，由于进程 P2 是 P(s1)操作，所以，它必须等待 P1 执行完 V(s1)操作以后才可继续运行，此时的 xyz 值分别为11，21，22，当进程 P1 执行完 V(s1)以后便在 P(s2)上阻塞，此时 P2 可以运行直到 V(s2)，此时的 xyz 值分别为 33，21，55，进程 P1 继续运行直到结束，最终的xyz 值分别为 33，76，55 。在此需注意，xyz 应该是共享变量，若是私有变量，则进程 P1、P2 就各自独
23、立对：xyz 操作。25 【正确答案】 D【试题解析】 本题考查对临界区的理解。所谓临界区，并不是指临界资源，临界资源是指共享的数据、代码或硬件设备等，而临界区是指访问这些临界资源的那段代码程序，例如 PV 操作，加减锁等。操作系统中对临界区的访问关心的就是临界区的操作过程，具体对临界资源作何操作是应用程序的事，操作系统并不关心。26 【正确答案】 C【试题解析】 进程进入临界区必须满足互斥条件，当进程进入临界区但是尚未离开时就被迫进入阻塞是可以的，系统中经常有这样的情形。在此状态下，只要其它进程在运行过程中不寻求进入该进程的临界区，就应该允许其运行。该进程所锁定的 l 临界区是不允许其它进程
24、访问的，其它进程若要访问，必定会在临界区的 “锁”上阻塞，期待该进程下次运行时可以离开并将临界区交给它。所以正确选项为 C。27 【正确答案】 D【试题解析】 本题考查分区保护的主要措施。在分区分配内存管理方法中，最常采用的方法是界地址保护法和基址、限长寄存器保护法。界地址保护法将每一个进程在内存中的物理位置的上界和下界值存放到上下界地址寄存器中，进程的每一条指令或数据的物理地址均与这两个上下界寄存器比较，一旦低于下界寄存器或大于上界寄存器均发生越界中断，从而起到保护作用。基址、限长寄存器保护法是上述方法的改进。将进程的逻辑地址与限长寄存器比较，一旦越界就发出中断，从而保护内存。基址寄存器主要
25、是用来进行逻辑地址到物理地址的转换。28 【正确答案】 A【试题解析】 本题考查段页式地址转换的计算。根据题目给出的条件，地址(1，8228)应该位于第二段，对应段号为 l(段号从 0 开始计算)，因此找到第二段(即编号为 1 的段表)的页表，该段段长为 3，可以看到有 3 个页面。8228 按页分822840962 余 36，因此应该在第三页，没有越界。第三页的页号为 2(从 0 开始编址)，页号 2 对应的页框号为 118，所以，物理地址为 118409636483364。29 【正确答案】 C【试题解析】 在分页存储管理系统中，页面的大小是由计算机系统的地址结构所决定的，一般由软硬件共同
26、决定。对于某一种系统一般采用一种大小的页面(也有部分现代操作系统采用双页面系统的)。在确定地址结构时，若选择的页面较小，一方面可使内碎片减小，并减少了内碎片的总空间，有利于提高内存利用率。另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外还会降低页面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但却又会使页内碎片增大。由于内存的大小是固定的，所以无论页面是大是小，可以进入内存的作业大小也是固定的，最多不超过内存的大小。实际上，分页的大小并不影响进入内存作业的数量。从宏观上看，进入内存的页面内容是没有变化的。所以分页式虚拟存储管理系统中，页面的
27、大小与可能产生的缺页中断次数并没有确定的关系。正确答案为 C。30 【正确答案】 C【试题解析】 本题考查磁盘的结构。磁盘的存储是按照磁头(或盘面)，磁道(或柱面)和扇区三要素唯一确定的，但是，在具体的使用时，是将所有的可用存储块按一维编号来进行分配的，称为逻辑地址。由于多盘面的磁盘系统中所有的磁头装在同一个转动轴上，是同步一起移动的，所以选择高效的编址方式能够提高磁盘的读写时间。不同于按磁头、磁道、扇区的顺序编址，多盘组磁盘的编址首先是按磁道来编，从磁盘外边缘到磁盘中心从 0 开始编号，本题中是 O 到 29999。确定了磁道，接下去随着磁盘的转动，所有磁头一起从某一起始点开始，寻找扇区，扇
28、区的编号也是从 0 开始，本题中是 0 到 249。找到扇区后再按磁头寻找，磁头从上到下从 0 开始编号，本题中是 0 到 15。在了解了盘组磁盘的编址方式后，下面的计算就比较简单了。首先确定磁道，1002578(25016) 并下取整(即舍去小数部分)得250，得到磁道号，余下逻辑块编号的偏移量是 2578，接下去确定扇区号，257816 并下取整得 161，得到扇区号，余下逻辑块编号的偏移量是 2，此号便是磁头号了，所以，其对应的三要素单位为 2，250，161。31 【正确答案】 D【试题解析】 本题考查文件系统重名问题的解决。树形目录的引入将文件重名的问题得到解决。树形文件目录是多级目
29、录，最初的目录称为根目录，其余目录称为子目录。每一个目录下可以存放不同的文件，相同文件名的文件(可能内容是不同的)，可以存放在不同的目录下，从而解决了文件重名问题。32 【正确答案】 D【试题解析】 本题考查设备管理中重要的数据结构的作用。既然是映射关系，必定有源和目标，能说明存在这关系的只有 D 选项。33 【正确答案】 B【试题解析】 本题主要考查 OSI 参考模型各个层次的作用，这里二进制信息块其实就是数据链路层所封装的数据帧，传输层虽然也提供可靠的数据传输，但不能保证系统间直接的二进制信息块的可靠性，因此答案是 B。归纳总结OSI 参考模型的各层功能如下：1物理层：保证二进制位流在物理
30、介质上传输，而不是这些位流的信息含义。2数据链路层：保证数据在相邻的节点之间透明传输。3网络层：保证报文分组在源一目的节点之间透明传输。4传输层：保正报文在源主机进程目的主机进程之间的透明传输。5会话层：为两个会话建立通信伙伴关系。通信方向控制(单工，半双工，全双工)谁是发送者?谁是接收者?谁付费?如何进行故障点恢复等。6表示层：进行数据格式转化(不同操作系统间)，数据加密解密，数据压缩解压等。7应用层：为用户提供各种网络服务。包括文件服务，电子邮件服务，数据库服务，WWW，BBS，News，DNS 等。在这七层中，14 层完成网络通信，57 层完成数据处理。34 【正确答案】 D【试题解析】
31、 本题考查物理层介质，单模光纤芯径小(10mm 左右)，仅允许一个模式传输，色散小，工作在长波长(1310nm 和 1550nm)，与光器件的耦合相对困难，而多模光纤芯径大(625mm 或 50mm)，允许上百个模式传输，色散大，工作在850nm 或 1310nm。与光器件的耦合相对容易，也就是主要区别在于直径的粗细，两者在数据传输速率，传输距离和价格方面并没有太大的区别，因此答案是 D。35 【正确答案】 D【试题解析】 本题考查零比特填充，为了避免其它字段中出现“0111110”，产生误解，HDLC 采用零比特填充技术，即在发送时，除标志字段外，如果连续发现 5个“1”，则在其后自动插入一
32、个“0”。接收方收到连续 5 个“1”后，如果其后为“0”，则自动将该“0”位删除，如果其后为“1”，则继续检查下一位，如果为“0”，则为标志位，为“1”则出错。即： 核心点就是只要出现连续的 5 个 0 之后，添加一个 0，因此位串 011111 11011111 0，经过填充后是 01111101101111100，因此答案为 D。36 【正确答案】 B【试题解析】 本题考查交换机的工作原理，注意本题前提是以太网交换机，因此属于数据链路层的范畴，故可以排除选项 A 和 D，因为 IP 地址属于网络层，而PORT 地址，即端口地址属于传输层，这里要明确以太网中 MAC 和 LLC 的功能，L
33、LC 子层负责向其上层提供服务，MAC 子层的主要功能包括数据帧的封装卸装，帧的寻址和识别，帧的接收与发送，链路的管理，帧的差错控制等，因此，交换机在转发数据包时所依据的是 MAc 地址，答案是 B。37 【正确答案】 B【试题解析】 本题考查 CRC 校验的计算方法，设信息位串为 ala2a3am，则信息编码多项式为 M(x)alx m1 a2x m2 a3x m 3a m，选择一个 r 次多项式 G(x)作为生成多项式，再按下面步骤生成校验串： (1)在信息位串后补 r 个0，对应的多项式为 xrM(x)， (2) 用模 2 又不借位除法，计算 xrM(x)G(x)的余数R(x)，R(x)
34、就是校验位串对应的多项式。 设要发送的码字多项式为 T(x)，则：T(x)x rM(x)R(x) 本题中该字符串为 1010001，G(x)一 x4x 2x1，因此 M(x)x 6x 41，r 4 x rM(x)x 10x 8x 410100010000 计算 R(x)x rM(x)G(x) 的过程如下： R(x)为 1101，因此 R(x)x rM(x)G(x)x 3x 21，T(x)x rM(x)G(x) R(x)x 10x 8x 4x 3x 21，也就是1010001(信息位串)1101( 校验位串) ，因此答案为 B。38 【正确答案】 C【试题解析】 主要考查网络设备与参考模型的关系
35、，主机作为终端设备，需要实现整个五层协议，而路由器作为网络层设备，仅实现物理层，数据链路层和网络层三个层次的协议，这里 TCP 是传输层协议，路由器不需要管理传输层的内容，仅完成网络层的数据包传输，选项排除，因此答案为 C。39 【正确答案】 B【试题解析】 本题主要考查 TCP 报文段和 UDP 报文段结构，TCP 数据报和UDP 数据报都包含目标端口、源端口、校验号。但是由于 UDP 是不可靠的传输，故数据报不需要编号，所以不会有序号这一字段，而 TCP 是可靠的传输，故需要设置序号这一字段，答案是 B。归纳总结 注意 UDP 数据报有两个字段：数据字段和首部字段。首部字段有 8 个字节，
36、由 4 个字段组成，每个字段都是两个字节(牢记)：(1)源端口，即源端口号(端口号用 16bit 来表示，故需要 2 字节长度)。(2)目的端口，即目的端口号。(3)长度，即 UDP 用户数据报的长度 (尽管有 2 字节来描述 UDP 数据报的长度，但是一般来说 UDP 协议限制其应用程序数据为 512 字节或更小)。(4)检验和，即检测 UDP 用户数据报在传输中是否有错(既检验首部又检验数据部分)。而 TCP 报文段也分为首部和数据两部分，TCP 的全部功能也都体现在首部的各个字段中，其中源端口和目的端口的意义和 UDP 是一致的。40 【正确答案】 C【试题解析】 本题考查 DNS 域名
37、解析的工作过程，具体步骤如下： (1)客户机提交域名解析请求，并将该请求发送给本地的域名服务器；(2)当本地的域名服务器收到请求后，就先查询本地的缓存。如果有查询的 DNS信息记录，则直接返回查询的结果。如果没有该记录，本地域名服务器就把请求发给根域名服务器；(3)根域名服务器再返回给本地域名服务器一个所查询域的顶级域名服务器的地址；(4)本地服务器再向返回的域名服务器发送请求；(5)接收到该查询请求的域名服务器查询其缓存和记录，如果有相关信息则返回本地域名服务器查询结果，否则通知本地域名服务器下级的域名服务器的地址；(6)本地域名服务器将查询请求发送给下级的域名服务器的地址，直到获取查询结果
38、；(7)本地域名服务器将返回的结果保存到缓存，并且将结果返回给客户机，完成解析过程。因此本题答案是 C。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 由 a0 75，得表长 m1107515。 (1)在一般情况下，H(K) K MOD P 中，P 取质数或者不包含小于 20 的质因数的和数，因此选择P13。散列函数 H(K)K MOD13。 (2)散列表：(3)等概率情况下查找成功的平均查找长度：ASI(172231 41)111811。 (4)等概率情况下查找不成功的平均查找长度：ASI(152141) 131113。【试题解析】 本题是对散列表的一种常见考查方式，题目的
39、难点是求查找成功和不成功的平均查找长度。用链地址法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下。归纳总结 散列表的查找效率(比较次数) 取决于：散列函数、处理冲突的方法和散列表的装填因子。当具体给出散列表的长度 m、元素个数 n，以及散列函数和解决冲突方式后，可以在求出散列表的基础上计算查找成功时的平均查找长度和查找不成功的平均查找长度。查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列到的位置上要插入新元素时为找到空位
40、置的探查次数的平均值。42 【正确答案】 void OneToThree(LinkList&L，&la，&ld，&lo)*L 是无头结点的单链表第一个结点的指针，链表中的数据域存放字符。本算法将链表 L 分解成含有英文字母字符、数字字符和其它字符的带头结点的三个循环链表*la：(LinkList)malloc(sizeof(LNode)； 建立三个链表的头结点ld(LinkList)malloc(sizeof(LNode) ；lo(LinkList)malloc(sizeof(LNode)；lanext la； 置三个循环链表为空表ldnextld；lonextlo；while(L! NULL) 分解原链表rL；LLnext； L 指向待处理结点的后继if(rdataa&rdatadataA&rdatanext lanext； 处理字母字符lanext r；else if(rdata0&rdatanext ldnext； 处理数字字符ldnextr；else rnext lonext ； 处理其它符号lonextr；
