1、计算机专业（基础综合）模拟试卷 71 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 对任意 n 个关键字进行排序，两两关键字进行比较的时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(log(n!)（D）O(nlogn)2 某顺序表的表长为 n 表，删除一个元素所需移动元素的平均个数为( )，假设在任何位置上删除一个元素的概率相等时。（A）n（B） n2（C） (n-1) 2（D）(n+1) 23 有 A，B，C ，D ，E 5 个元素按次序入栈，在各种可能的出栈次序中，以元素C，D 最先出栈
2、的序列中，下列正确的一组是( )。（A）CDBAE CDABE（B） CDEBA CDBEA（C） CDEAB CDABE（D）CEBAE CDAEB4 某二叉树中有 100 个叶结点，那么这棵：二叉树中有( )个度为 2 的结点。（A）89（B） 99（C） 101（D）1025 设结点 x 和 y 是二叉树中任意的两个结点，在该二叉树的先序遍历序列中 x 在 y之前，而在其后序遍历序列中 x 在 y 之后，则 x 和 y 的关系是( )。（A）x 是 y 的左兄弟（B） x 是 y 的右兄弟（C） x 是 y 的祖先（D）x 是 y 的后裔6 下面一系列编码中，不是哈夫曼编码的是( )。（
3、A）1 1 1，1 10，10，01，00（B） 000，001，010，011，1（C） 100，11，10，1，0（D）001，000，01，11，107 设图的邻接矩阵 A 如下所示。各顶点的度依次是 ( )。（A）1，2，1，2（B） 2，2，1，1（C） 3，4，2，3（D）4，4，2，28 如下所示带权图 G，其最小生成树各边权的总和为 ( )。（A）14 （B） 19（C） 21（D）269 对 N 个记录的索引顺序表(分块表)进行查找，平均查找长度最小时，块长为 ( )。（A）（B）（C） NlogN（D）logN10 下列排序算法中，( )每一趟都能选出一个元素放在最终位置上
4、，并且是不稳定的。（A）冒泡排序（B）希尔排序（C）直接选择排序（D）直接插入排序11 最佳归并树在外排序中的作用是( )。（A）完成 m 路归并排序（B）设计 m 路归并排序的优化方案（C）产生初始归并段（D）与竞标赛树的作用类似12 关于冯.诺依曼计算机，下列说法正确的是( )。（A）冯.诺依曼计算机的程序和数据是靠输入设备送入计算机的寄存器保存的（B）冯 .诺依曼计算机工作是由数据流驱动控制流工作的（C）冯 .诺依曼计算机的基本特点可以用“存储程序 ”和“程序控制” 来高度概括（D）随着计算机技术的发展，冯.诺依曼计算机目前已经被淘汰13 16 位二进制补码所能表示的有符号整数的范围是(
5、 )。（A）065 535（B） -32 76832 767（C） -11-2 15（D）-32 76832 76814 在大量数据的传送过程中，常用且有效的检验法是( )。（A）海明码校验（B）偶校验（C）奇校验（D）CRC15 某 8 位机的地址码为 16 位，主存按字节编址，其中最高 8 KB 主存空间为系统BIOS 程序一区，其余为用户程序区。现有 4 K4 的 ROM 芯片和 18 K4 的 SRAM芯片。构建该机所允许的最大空间的主存，需用上述规格的 ROM 芯片和 SRAM芯片各为( )。（A）4，4（B） 14，14（C） 14，4（D）4，1416 设机器字长为 32 位，一
6、个容量为 16 MB 的存储器，CPU 按半字寻址，其可寻址的单元数是( ) 。（A）2 24（B） 223（C） 2222（D）22 2117 零地址的运算类指令在格式中不给出操作数的地址，参加的两个操作数来自( )。（A）累加器和寄存器（B）累加器和暂存器（C）堆栈的栈顶和次栈顶（D）堆栈的栈顶和累加器18 某机主存容量 64 KB，按字节编址。主存地址。 100H 处有一条相对转移指令，指令字长 16 位，其中，第一个字节为操作码，第二个字节为相对位移量(用补码表示)，则该指令执行结束后，后继指令的地址范围可能是( )。（A）0000HFFFFH（B） 0080H017FH（C） 008
7、2H0181H（D）0080H01FFH19 多时钟周期 CPU 设计的主要特点中说法错误的是( )。（A）允许共享功能部件（B）每条指令由不同数目的时钟周期完成，减少了指令的平均执行时间（C）多时钟周期 CPU 增加了硬件成本（D）需要设置多个状态部件，控制更加复杂 20 下列关于动态流水线说法正确的是( )。（A）动态流水线是指运算操作的并行流水（B）动态流水线是指在同一时间范围内，当某些段正在实现某种运算时，而另外一些段却在进行另一种运算（C）动态流水线是指指令步骤的并行流水（D）动态流水线是指程序步骤的并行流水 21 某总线有 104 根信号线，其中数据总线(DB)32 根，若总线工作
8、频率为 33 MHz，则其理论最大传输率是( )。（A）33 MBs（B） 64 MBs（C） 132 MBs（D）1 64 MBs 22 关于 DMA 方式和通道方式，下列说法中错误的是( )。（A）DMA 的数据传送全部由硬件控制，而通道方式通过执行通道程序来传送数据（B）一个 DMA 控制器连接多台外设时，这些外设只能串行工作（C）一个通道可连接多台外设，且可使这些外设并行工作（D）DMA 控制器和通道都可以连接各种高低速设备23 操作系统为用户提供了多种接口，它们是( )。I计算机高级指令；终端命令；图标菜单；汇编语言；VC 语言；系统调用（A）I，V（B） ，VI （C） ，V（D）
9、，24 在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长短是( )。（A）进程相应的代码长度（B）进程总共需要运行的时间（C）进程特点和进程调度策略（D）进程完成什么功能25 进程处于下列哪个等待状态时，它是处于非阻塞状态( )。（A）等待从键盘输入数据（B）等待协作进程的一个信号（C）等待操作系统分配 CPU 时间（D）等待网络数据进入内存26 分页管理方式中的页面是为( )。（A）用户所感知的（B）操作系统所感知的（C）编译系统所感知的（D）连接装配系统程序所感知的27 虚拟页式存储管理中，CPU 必须具备必要的物理硬件的支持，而不是必需的单元是( )。（A）缺页中断机
10、构（B）地址加法器（C） Cache（D）地址寄存器28 在一个虚拟存储系统中，假设主存的容量是 256 MB，辅存的容量为 8 GB，处理机地址寄存器以及地址线位宽 32 位，在这样的系统中，虚存的空间最大为( )。（A）8 GB（B） 256 MB（C） 256 MB+8 GB（D）4 GB29 某操作系统中对文件的删除和增加操作十分频繁，那么系统不适宜采用( )。（A）索引文件（B）连续文件（C） Hash 文件（D）串联文件30 文件系统采用两级索引分配方式。如果每个磁盘块的大小为 2KB，每个盘块号占 4B，则该系统中单个文件的最大长度是( )。（A）64 MB（B） 128 MB（
11、C） 256 MB（D）5 12 MB31 磁臂驱动调度算法中，能够随时改变磁头运动方向的算法是( )。（A）电梯调度算法（B）扫描算法（C）循环查看算法（D）最短寻道距离优先算法32 通过硬件和软件的功能扩充，把原来独占的设备改造成若干用户共享的设备，这种设备称为( ) 。（A）系统设备（B）存储设备（C）用户设备（D）虚拟设备33 在 OSI 的层次模型中，( )是控制对等实体间进行通信的规则的集合。（A）协议（B）服务（C）接口（D）原语34 已知某信道的信号传输速率为 64 kbs，一个载波信号码元有 4 个有效离散值，则该信道的波特率为( )k Baud。（A）16（B） 32（C）
12、 64（D）12835 利用海明码纠正 2 比特的错误，那么海明距为( )。（A）2（B） 3（C） 4（D）536 路由器收到的分组的 TTL 值为 0，那么路由器将( )。（A）把该分组返回发送方（B）丢弃该分组（C）继续转发（D）本地提交37 假设一个 NAT 服务器其公网地址为 205567935，并且有如下的表项，那么当一个 IP 地址为 1921683256 端口为 21 分组进入公网的时候，转换后的端口号和源 IP 地址是( )。（A）205567935：2056（B） 1921683256：2056（C） 205567935：1 892（D）205567935：225638 一
13、台主机正在通过一条 10 G bits 的信道发送 65 535 字节的满窗口数据，信道的往返延迟为 1 ms，不考虑数据处理时间。TCP 连接可达到的堆大数据吞吐量是( )。(假设用于标记字节的序号位为 32 位，报文的生存时间 120 s)（A）2 M bits（B） 4 M bits（C） 8 M bits（D）16 M bits 39 一个 TCP 连接下面使用 256 kbits 的链路，其端到端时延为 128 ms。经测试，发现吞吐量只有 120 kbitso 试问发送窗口是( )。（A）7 348 字节 （B） 7 338 字节（C） 7 228 字节（D）7 224 字节40
14、在 HTIP 协议中，一个以 2 开头的响应报文表示 ( )。（A）暂时性失败（B）永久性失败（C）重定向（D）成功二、综合应用题41-47 小题，共 70 分。41 设一段正文由字符集A，B，C ，D，E ，F中的字母组成，这 6 个字母在正文中出现的次数分别为12， 1 8，26，6，4，34 。(1)为这 6 个编码设计哈夫曼编码；(2)设每个字节由 8 位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节；(3)若这段正文开始部分的二进制编码序列为：0110001001011010100，请按(1)的哈夫曼编码将其译为正文。42 已知一个线性表，其中的数据元素类型均为整型。
15、现有两个单链表 La 和 Lb，其中 La 只能存储偶数而 Lb 只能存储奇数。现想利用 La 和 Lb 来存储此线性表。请完成以下问题：(1)给出算法的主要思想；(2)写出算法的实现函数；(3)总结所用算法的时间和空间复杂度。43 已知 4 位有效信息为 1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式 G(x)=1011。44 一台计算机有分离的数据和指令 Cache。同时该计算机还采用了页式虚拟存储器技术。这里假定页面和(；ache 块具有大小相同。已知 Cache 的存取速度为 10 ns
16、，主存的存取速度为 60 ns，磁盘的存取速度为 12 ms。该计算机的时钟周期为10 ns。如果指令和数据的提取均命中 Cache，指令的执行需要 1 个时钟周期。Cache 采用的是直接映射并使用写回策略。在 Cache 中平均 50的块是修改过的。对于主存，同样采用写回策略，主存中平均 30的页面已经被修改。我们假定指令在 Cache 和主存中的命中率均为 95，而数据在 Cache 和主存中的命中率为 90，我们还知道一般情况下 35的指令存取数据，求这种情况下的最大 CPI。该题必须写出计算过程，并对每一步作必要的说明，否则不给分。45 关于分页系统，回答下列问题：(1)在页表中，哪
17、些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配 3 个内存块，某作业进程在运行访问中的轨迹为1，4，3，1，6，8，1，且每一页都是按请求装入的。问：先进先出页面置换算法(FIFO)和最近未使用页面置换算法(LRU)下，产生缺页的次数各是多少 ?(画出必要的数据图)(3)在什么情况下，上述两种页面淘汰算法执行效果是一样的?为什么?46 现有 A，B 两队人要过河，河上有船，但是每次只能乘坐 4 个人，并且每次乘客满员才能开船，到河对岸后空船返回。由于某种原因，过河时船上不能同时有三个 A 队人员、一个 B 队人员或者一个 A 队人员、三个 B 队人员的组合(即其他组合是安全的)
18、。请编写程序，用 PV 操作正确解决 A，B 两队人过河的问题，并说明所设置的信号量及其初值。47 已知一个局域网连接图如下图： 主机 A 的 IP 地址为 1921684819，物理地址为 DE24E4EFC5 B2；主机 B 的 IP 地址为 1921684812，主机 C 的 IP 地址为 1921684821。 请回答下列问题：(1)主机 A 如何得知主机 B 的物理地址(指出所使用的协议名称和协议工作原理 )?(2)一个 IP 包的源地址和目的地址分别是 1921684819 和1921684821，为了发送该 IP 包，源主机应该先发送什么帧 ?(3)该分组的以太网帧的源地址、目的
19、地址和协议类型域各是什么?(用 16 进制表示)计算机专业（基础综合）模拟试卷 71 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 任何一个借助于“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为：O(log(n!) 。2 【正确答案】 C【试题解析】 顺序表的删除运算的时间主要消耗在了移动表中元素上，删除第 i个元素时，其后面的元素 ai+1a n 都要向上移动一个位置，共移动了 n 一 i 个元素。在等概率情况下，即 pi=1n，则： 3 【正确答案】 B【试题解析
20、】 要使得 C，D 作为第一、二个元素出栈，应是 A，B ，C 先入栈，C 出栈，D 入栈，D 出栈；接着就剩下 A，B 在栈中，E 未入栈，共 3 个元素，此三者序列为 BAE，BEA ， EBA。4 【正确答案】 B【试题解析】 根据二叉树的性质 n0=n2+1，可知度为 2 的结点个数为 99。5 【正确答案】 C【试题解析】 先序遍历是“根一左子树一右子树”，而后序遍历是“左子树一右子树一根”，题目中二叉树的先序遍历序列中 x 在 y 之前，而在其后序遍历序列中 x在 y 之后，则 x 一定是 y 的祖先。6 【正确答案】 C【试题解析】 C 中 100 和 10 冲突，即一个结点既是
21、叶子结点又是内部结点，哈夫曼树中不可能出现这种情况。7 【正确答案】 C【试题解析】 各顶点的度是矩阵中，此结点对应的横行和纵列非零元素之和。8 【正确答案】 C【试题解析】 由上述建立最小生成树的过程可知，最小生成树个边权的总和为 21。9 【正确答案】 A【试题解析】 设块长为 B，索引表中包含 NB 项，索引表的 ASL=(NB+1)2，块内的 ASL=(B+1)2，总的 ASL=(NB+1)2+(B+1)2，根据均值不等式 B=NB 时有最小值，因此 B= ，答案为 A。10 【正确答案】 C【试题解析】 本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。11 【正确答案】
22、B【试题解析】 最佳归并树在外排序中的作用是设计 m 路归并排序的优化方案，仿照构造哈夫曼树的方法，以初始归并段的长度为权值，构造具有最小带权路径长度的 m 叉哈夫曼树，可以有效地减少归并过程中的读写记录数，加快外排序的速度。12 【正确答案】 C【试题解析】 根据冯.诺依曼计算机的特点排除错误选项。冯.诺依曼计算机的程序和数据是靠输入设备送入计算机的存储器保存的，而不是寄存器，因此选项 A不正确；冯.诺依曼计算机属于指令流驱动控制的，因此选项 B 不正确；从计算机体系结构的角度来看，到目前为止绝大多数计算机仍属于冯.诺依曼计算机，因此选项 D 不正确。只有选项 C 是正确的。13 【正确答案
23、】 B【试题解析】 补码表示的有符号整数范围(用十进制表示)：一 32 76832 767。对应的二进制代码 1000 0000 0000 00000111 1111 1111 1111。14 【正确答案】 D【试题解析】 CRC 适合对大量数据进行校验。15 【正确答案】 D【试题解析】 内存空间为：2 168=64 KB。去掉主存空间里的前 8 K，还有 56 K的用户空间。使用 4 K4 的 ROM 芯片数为：8 K4 K84=4。使用 8 K4 位的SRAM 芯片为 56K8 K84=14。16 【正确答案】 B【试题解析】 16 MB=2 24，由=F 字长为 32 位，现在按半字(
24、16 位)寻址，相当于有8 M 个存储单元， 8 MB=223。每个存储单元中存放 16 位二进制数。17 【正确答案】 C【试题解析】 零地址指令的运算属于堆栈的运算指令，参与操作的数据来自堆栈的栈顶和次栈顶。18 【正确答案】 C【试题解析】 该指令取指结束后，PC 值自动加 2，即(PC)=0102H；相对位移量用 8 位补码表示，故其范围为 80H7FH，扩展到 16 位为 FF80H007FH，与PC 值相加就可得后继指令的地址范围为 0082H 0181H。19 【正确答案】 C【试题解析】 多时钟周期 CPU 设计的主要特点有： 每条指令由不同数目的时钟周期完成，可以减少指令的平
25、均执行时间。允许共享功能部件，降低硬件成本，但需要设置多个状态部件。控制更加复杂。20 【正确答案】 A【试题解析】 A 符合动态流水线的定义。静态流水线和动态流水线的不同之处在于静态流水的上下段连接疗式阎定，而动态流水线的上下连接方式可变。21 【正确答案】 C【试题解析】 在总线的 104 根信号线中，数据总线占 32 根，也就是 4 个字节，由于总线工作频率为 33MHz，所以理论的最大数据传输率=4 B33MHz=132 MBs。总线的最大数据传输率又称总线带宽，即每秒传输的字节数。总线带宽=总线宽度总线频率。22 【正确答案】 D【试题解析】 通道可连接各种高低速外设，而 DMA 控
26、制器只用于高速外设成组数据的传送，D 为错误选项。23 【正确答案】 B【试题解析】 本题考查操作系统的接门。操作系统有两种接口：命令输入和系统调用。而命令输入又可以分为命令行和图形用户界面。命令行是在终端或命令输入窗口中输入操作和控制计算机的规定的命令，既可以一条一条输入，也可以组织成一批命令，逐条自动执行，称为批处理命令。图形用户接口是我们熟知的图标和菜单形式。系统调用是我们编写程序过程中，需要计算机所做的操作，一般要按同定格式来调用。24 【正确答案】 C【试题解析】 本题考查进程调度的时机和进程调度的策略。进程调度的时机与进程特点有关，例如进程是 CPU 繁忙型还是 IO 繁忙型，自身
27、的优先级等。但是仅有这些特点是不够的，能否得到调度还取决于进程调度策略，若采用优先级调度算法，则进程的优先级才起作用。至于占用处理机运行时间的长短，则要看进程自身。若进程是 IO 繁忙型，运行过程中要频繁访问 IO，也就是说，可能会频繁主动放弃 CPU，所以，占用 CPU 的时间就不会长，一旦放弃 CPU，则必须等待下次调度。若进程是 CPU 繁忙型，则一旦占有 CPU 就可能会运行很长时间，但是，运行时间还取决于进程调度策略。大部分情况下，交互式系统为改善用户的响应时间，大多采用时间片轮转的算法，这种算法在进程长期占用 CPU 到一定时间后，会强制将其换下，以保证其他进程的 CPU 使用权。
28、所以，本题的正确答案应为选项 C，其他都不是。25 【正确答案】 C【试题解析】 等待操作系统分配 CPU 时间是处于就绪状态。26 【正确答案】 B【试题解析】 页面信息是由操作系统管理的。27 【正确答案】 C【试题解析】 在虚拟页式存储管理中，除了有主存和辅存以外，为满足虚拟技术，CPU 还需要有缺页中断机制；为满足页式存储管理，CPU 中需要有地址加法器和地址寄存器来计算贝表到页框的映射，而 Cache 并不是必需的，因为 Cache 的存在只是提高了 CPU 寻址的效率，并不是虚拟页式存储技术的重要单元，缺少Cache，CPU 每次执行一个双字的指令 (以 32 位为例)或取一个数据
29、均需要二次访问内存，当然这是很不利的，可能会实际上造成虚拟页式的使用障碍。增加了Cache，为虚拟页式存储技术的实际使用提供了方便。28 【正确答案】 D【试题解析】 本题考查虚拟存储器的最大容量。虚拟存储器空间的最大值与实际存储容量没有关系，仅与其地址系统的位宽有关，32 位的系统其最大虚存都是 4 GB。但是若要问虚存的实际容量是多少，则要考虑主存和辅存的大小。若主存和辅存之和小于 4 CB(对于 32 位系统)，则应是主存和虚存的实际容量之和。若大于4 GB，则多余的部分没有用，虚存的实际容量的大小还是 4 GB。29 【正确答案】 B【试题解析】 因为连续文件是线性存储，每次增、删都要
30、移动元素，代价较大。30 【正确答案】 D【试题解析】 每个磁盘块中最多呵以有 2 KB4 B=512 个索引项，则两级索引分配方式下，单个文件的最大长度为 5125122 KB=512 MB。31 【正确答案】 D【试题解析】 本题考查磁臂调度算法。(1)最短寻道时间优先算法是找离得最近的磁道去服务，那么它随时会改变方向；(2)电梯调度算法在一次单向运动过程中服务所有经过的磁道的请求，直到该方向没有磁道需要访问了才改变方向，到达另一个方向的最远的需要服务的磁道后在返回；(3)扫描调度算法非常类似电梯调度算法，区别是扫描算法不管有没有用户请求访问磁道，均会移到磁道两端的终点；(4)循环电梯调度
31、算法只进行单向服务，到最远端的服务磁道结束后立即返回另一端的第一个需要服务的磁道，返程途中不寻道，以保证对不同分布磁道的访问具有公平性。32 【正确答案】 D【试题解析】 本题考查虚拟设备的概念。33 【正确答案】 A【试题解析】 协议是控制两个对等实体进行通信的规则的集合，而服务是指某一层向它上一层提供的一组原语。服务是由下层向上层通过层问接口提供的，而原语则是用来描述操作的。 服务和协议的关系可以由下图来描述：34 【正确答案】 B【试题解析】 一个码元若取 2n 个不同离散值，则含有 n bit 的信息量。在本题中，一个码元含有的信息量为 2 bit，由于在数值上波特率=比特率每符号含的
32、比特数，因此波特率为(642)k=32 k Baud。35 【正确答案】 D【试题解析】 为了纠正 d 个错误，需要一个距离为 2d+1 的编码方案，因为在这样的编码方案中，合法码字之间的距离足够远，因而即使发生了 d 位变化，还是原来的码字离它最近，从而可以唯一确定原来的码字，达到纠错的目的。36 【正确答案】 B【试题解析】 本题考查 IP 报头字段以及路由转发。路由器对 TTL 为零的数据分组进行丢弃处理，并向源主机返回时间超时的 ICMP 报文，因此答案是 B。37 【正确答案】 A【试题解析】 NAT 协议利用端口号来解决内网到外网的地址映射问题。任何时候当一个向外发送的分组进入 N
33、AT 服务器的时候，源地址被真实的公网地址所取代，端口也被转换为其他索引值。38 【正确答案】 A【试题解析】 TCP 协议分组中携带的数据量最大为 65 53520 一 20=65 495 字节，所以要发送 65 535 字节的数据需要 2 个 TCP 报文，将 65 535 字节的数据发送完毕，无形中多出了两个 IP 分组+TCP 分组的头部为(20+20)2=80 字节一共发送的 bit 数为 n=(65 535+80)8。发送的时间为两个分组需要两个响应，所以发送时间为数据的实际发送时间+信道延时，所以 t=(65 535+80)810G+1 ms2，则这条连接的吞吐量为：n t=2
34、Mbits。39 【正确答案】 C【试题解析】 来回路程的时延=1282=256 ms 。设发送窗口为 X 字节，假定一次最大发送量等于窗口值，那么，每发送一次都得停下来等待得到本窗口的确认，以得到新的发送许可，这样：40 【正确答案】 D【试题解析】 HTTP 协议中以 2 开头的响应报文表示请求成功。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)构造哈犬曼树的过程，如下图所示： 根据题目中给出的序列，依此选取其中最小的两个组成一棵二叉树。(2)各个字母对应的编码为：A 011 B 00 C 10 D 0101 E 0100 F 11(3)要进行压缩存储，B，F，C
35、 只需要 2 位，出现的次数分别为 18，26，34；A 只需要 3 位，出现的次数分别为 1 2；D，E 只需要 4 位，出现的次数分别为 4，6。压缩后，共需字节数为： (2(18+26+34)+312+4(4+6)8=232 8=29(4)给出的序列是：0110001001011010100，将其拆分成字母对应的编码。011：A；00：B；0100：E；10：E；11：F；0101：D ；00：B。泽文序列为：ABECFDB42 【正确答案】 (1)依次遍历线性表，如果线性表中的数据是偶数则插入 La 中，如果是奇数，那么就插入 Lb 中。(2)算法的函数如下：void decompos
36、e(LinkList&L，LinkList&La ，LinkList &Lb) 含头结点LNode*p，*q；p=L-next；La=L：La-next=La：Lb-next=Lb；空的循环链表while(p!=NULL)q=p-ilext；if(p-data 2=0)偶数则插入 La 中p-next=La-next；La-next=p；else奇数则插入 Lb 中p-next=Lb-next；Lb-next=p；p=q；(3)遍历链表的时间复杂度为 O(n)，算法实现过程中使用的辅助空间为常量，空间复杂度为 O(1)。43 【正确答案】 (1)题目要求能够发现两位错并纠正一位错，故需要在海明
37、码的基础上增加 1 位全局的奇偶校验位，此时的编码方式称为“扩展的海明码” 。 普通海明码编码计算如下：首先计算所需校验位的位数 k，根据 2k4+k+1，可知应取 3位校验位，数据位与校验位的位置安排如下：各校验位的数值计算如下： C 1 校验的比特位包含 1，3，5，7 位，按配偶原则： C1= =0 C2 校验的比特位包含 2，3，6，7 位，按配偶原则：C 2=1 C4 校验的比特位包含 4，5，6，7 位，按配偶原则： C4= =0 综上所述，将 1010 编码扩展为海明码为 1010010，为了能够发现两位错并纠正一位错，在最左端增加 1 位全局偶校验位 C8。 C 8=1 故，将
38、有效信息 1010 编码扩展的海明码为11010010。 (2)将待编码的有效信息 1010 表示为多项式 M(x)： M(x)=x 3+x=1010 由于生成多项式 G(x)为 4 位，故将 M(x)左移 3 位，得 M(x)x3，目的是空出 3 位，以便拼装余数(校验位) ： M(x)x 3=x6+x4=1010000 用 M(x)x3 模 2 除生成多项式G(x)： 将左移后的待编码有效信息与余数R(X)作模 2 加，即形成循环冗余校验码： M(x)x 3+R(x)=1010000+011=1010011 即用生成多项式 G(x)=101 1 将有效信息 1010 编码，得循环冗余校验码
39、 1010011。44 【正确答案】 分成两种指令算：一种是需要存取数据的指令；另一种是不需要存取数据的指令。不需要存取数据的指令：不需要考虑数据的命中和写回。65(95501+955060 ns10 ns+5957060 ns 10 ns+595 3012 ms60 ns+5512 ms10 as)=6 。需要存取数据的指令：需要存取数据的指令本身的 CPI 为：A=(95501+955060 ns10 ns+5957060 ns10 ns+595 30 12 ms60 ns+5512 ms10ns)。指令需要存取的数据所耗费的 CPI：B=(90501+905060 nslO ns+109
40、07060 ns 10 ns+1090 301 2 ms60 ns+1010 12 ms10 as)。最后结果为：A35+B35 =11 。45 【正确答案】 (1)在页表中，访问位和修改位是为请求页面调度设置的。访问位来跟踪页的使用，修改位来跟踪页的写入。 (2)FIFO 算法：缺页次数是 6，具体如下表所示：(3)当最先进入内存的页面又是最近最久没有使用的页面时，上述两种页面淘汰算法执行的效果一样。46 【正确答案】 int m=4； 信号量，初始值为 4Embark(A) 登船函数P(m)；Aembark()；Sail() 开船go()；V(m)；V(m)；V(m)；V(m)；while
41、(true)if(t=0)int t=4； 记录已经登船人数int i：0； 记录 A 登船人数，4 时不允许同类再登船int j=0； 记录 B 登船人数，4 时不允许同类再登船while(teamhasNext()ready=teamnext()；if(ready= =A)if(i= =4)continue； 防止 3 和 1 的情况elset-：j+；Embark(ready)； if(i= =3 Il(i= =2&j= =1)j=4； 防止 3 和 1 的情况if(j= =3 lI(j= =2&i= =1)i=4； 防止 3 和 1 的情况if(t= =0)Sail()；break；t
42、eamrelnit()； 整理等候队列47 【正确答案】 (1)采用 ARP 协议来实现。首先在本地的高速缓存中查找目标主机的 IP 地址，通常高速缓存中保存着一些主机的 IP 与物理地址的对应关系。若找到，则直接获得 B 的物理地址；否则，将在本地网络上发送一个广播，此时本地网络上的主机接收到该请求后都会检查是否与自己的 IP 地址相同，若相同则产生一个应答消息，里面包含了对应的物理地址，并发送给请求主机，请求主机便得到了 IP 对应的物理地址，并将 IP 与物理地址的对应关系添加到本地高速缓存中。(2)在以太网中发送数据，首先要知道对方的以太网地址。所以主机 A 需要先发送ARP 帧来获得主机 C 的物理地址。(3)ARP 采用了以太网的广播功能，使用全“1”的地址作为目的地址，即：FFFFFFFFFFFF，源地址为主机 A 的地址：DE24 E4EF C5B2，类型为 ARP 的类型值：0806。
