1、计算机专业（基础综合）-试卷 14 及答案解析(总分：104.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.在一个长度为 n(n1)的带头结点的单链表 h 上，设有尾指针 r(指向尾结点)，则执行( )操作与链表的长度有关。（分数：2.00）A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素3.若用单链表来表示队列，则应该选用( )。（分数：2.00）A.带尾指针的非
2、循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，深度为 h 则( )。（分数：2.00）A.n=h+mB.h+m=2nC.m=h1D.n=2 h 一 15.关于哈夫曼树，下列说法正确的是( ).（分数：2.00）A.在哈夫曼树中。权值相同的叶子结点都在同一层上B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊处理6.每棵树都能唯一地转换成相对应的二叉树，由树转换成的
3、二叉树中，一个结点 N 的左孩子是它在原树对应结点的( )。（分数：2.00）A.最左孩子B.最右孩子C.右邻兄弟D.左邻兄弟7.已知 8 个数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。（分数：2.00）A.4B.5C.6D.78.下列叙述正确的个数是( )。(1)m=2 的平衡 m 路查找树是 AVL 树(2)m=3 的平衡 m 路查找树是 23 树(3)m=2 的平衡 m 路查找树的叶结点不一定在同一层(4)m 阶 B 一树的叶结点必须在同一层(5)m 阶 B 一树是平衡 m 路查找树(6)平衡 m 路查找树
4、不一定是 B 一树（分数：2.00）A.3B.4C.5D.69.下列说法正确的是( )。（分数：2.00）A.任何有向网络(AOV 一网)拓扑排序的结果是唯一的B.有回路的图不能进行拓扑排序C.在 AOE 网中一定只有一条关键路径D.一个正常的 AOE 网中只能有一个源点、一小汇点和一条关键路径10.对任意 7 个关键字进行排序，至少要进行( )次关键字之间的两两比较。（分数：2.00）A.13B.14C.15D.1611.一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有 5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分
5、数：2.00）A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，50，35，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，8512.完整的计算机系统由( )组成。（分数：2.00）A.运算器和控制器B.CPU 和主存储器C.主机和外部设备D.硬件系统和软件系统13.真值 0 在原码、反码和补码机器数形式下( )。（分数：2.00）A.都有正 0、负 0 两种形式B.仅在原码中有两种形式，而在反码、补码机器数形式下只有一种形式C.仅在反码中有两种形式，而在原码、
6、补码机器数形式下只有一种形式D.仅在补码中有一种形式，而在反码、原码机器数形式下均有两种形式14.某定点机字长 8 位(含 1 位符号位)，现该机中一个寄存器的内容为 43H，则将其算术左移一位、算术右移一位的结果分别为( )。（分数：2.00）A.86H，21HB.结果出错，21HC.结果出错，A1HD.未给出机器数形式，无法判断15.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若有两个数 X= 7 2932，Y=2 5 58，则用浮点加法计算 X+Y 的最终结果是( )。（
7、分数：2.00）A.001111100010B.001110100010C.010000010001D.发生溢出16.半导体随机存储器的访问速度与( )有关。（分数：2.00）A.存储芯片的存取周期B.存储芯片的容量大小C.所访问存储单元的位置D.以上都包括17.Cache 常用的写回策略有写直达法和写回法。当采用写回法时，一个 Cache 数据块在( )时写回主存。（分数：2.00）A.任何一次写操作数时B.第一次写操作数时C.数据块被换出时D.以上都有可能18.主存地址寄存器 MAR 的位数与下列哪个寄存器相同?( )。（分数：2.00）A.主存数据寄存器 MDRB.程序计数器 PCC.指
8、令寄存器 IRD.累加器 AC19.控制存储器使用 EPROM 构成的控制器是( )。（分数：2.00）A.静态微程序控制器B.动态微程序控制器C.毫微程序控制器D.以上都不对20.下列关于 PCI 总线的说法中错误的是( )。（分数：2.00）A.PCI 总线采用集中式总线判优控制方式B.PCI 总线是一种 16 位的并行总线C.PCI 总线具有自动配置能力D.PCI 总线在 PC 机中得到了广泛的使用21.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3B.5C.16D.无法确定22.下列说法
9、中错误的是( )。（分数：2.00）A.统一编址方式即把 IO 端口当作主存储器的单元来分配地址B.统一编址方式下不需要专门的 IO 指令C.统一编址方式下指令系统的实现比单独编址方式复杂D.采用统一编址方式会减少主存的编址空间23.活动头磁盘的寻道时间是指( )。（分数：2.00）A.最大寻道时间B.最小寻道时间C.A、B 之和D.A、B 的平均值24.下列选择中，( )不是操作系统关心的主要问题。（分数：2.00）A.管理计算机裸机B.设计、提供用户程序与计算机硬件资源的接口C.管理计算机系统资源D.高级程序设计语言的编译器25.采用( )不会产生内部碎片。（分数：2.00）A.分页式存储
10、管理B.分段式存储管理C.固定分区式存储管理D.段页式存储管理26.在操作系统中，要对并发进程进行同步的原因是( )。（分数：2.00）A.进程必须在有限的时间内完成B.进程具有动态性C.并发进程访问共享资源D.进程具有结构性27.( )不是分段式虚拟存储管理优于分页式虚拟存储管理的方面。（分数：2.00）A.没有内零头B.便于处理在进程执行过程中堆栈尺寸的增长问题C.便于共享内存中数据D.只需将进程的一部分调入内存，进程即可运行28.在下面四段描述中( )是错误的。（分数：2.00）A.若进程 A 和进程 B 在临界区上互斥，那么当进程 A 处于该临界区时，它不能被进程 B 打断B.虚拟存储
11、管理中采用对换策略后，用户进程可使用的存储空间似乎增加了C.虚拟存储管理中的抖动现象是指页面置换时用于换页的时间远多于执行程序的时间D.进程可以由程序、数据和进程控制块(PCB)描述29.存放在磁盘上的文件( )。（分数：2.00）A.既可随机访问，又可顺序访问B.只能随机访问C.只能顺序访问D.必须通过操作系统访问30.文件系统中，文件访问控制信息存储的合理位置是( )。（分数：2.00）A.文件控制块B.文件分配表C.用户口令表D.系统注册表31.在操作系统中，P，V 操作是一种( )。（分数：2.00）A.机器指令B.系统调用命令C.作业控制命令D.低级进程通信原语32.( )是操作系统
12、必须提供的功能。（分数：2.00）A.GUI(图形用户界面)B.为进程提供系统调用命令C.处理中断D.编译源程序33.磁盘和磁带是两种存储介质，他们的特点是( )。（分数：2.00）A.二者都是顺序执行的B.二者都是随机存取的C.磁盘是顺序存取的，磁带是随机存取的D.磁带是顺序存取的，磁盘是随机存取的34.网桥是在以下( )层上实现不同网络互联的设备。（分数：2.00）A.物理层B.数据链路层C.网络层D.传输层35.一种数据编码的海明距是 7，那么使用这种编码最多可以纠正( )个错误。（分数：2.00）A.0 个B.1 个C.2 个D.3 个36.在一个 HDLC 帧的数据中，如果出现了 0
13、00111111011 这样的流，请问发送到信道上它将会变成( )。（分数：2.00）A.0001111110110B.0001111111011C.0001111101011D.000011111101137.以太网交换机进行转发决策时使用的 PDU 地址是( )。（分数：2.00）A.目的物理地址B.目的 IP 地址C.源物理地址D.源 IP 地址38.一台路由器的路由表中有以下几项(CIDR)： （分数：2.00）A.接口 0B.接口 1C.接口 2D.接口 0 和接口 139.假设一个连接的最大数据段长度为 2KB，一个 TCP 的阀值为 64KB，如果这时候传输发生了超时，那么新的阀
14、值为( )。（分数：2.00）A.32KBB.63KBC.128KBD.2KB40.如果在 TCP 连接中有一方发送了 F1N 分组，并且收到了回复，那么它将( )。（分数：2.00）A.不可以发送数据，也不可以接收数据B.可以发送数据，不可以接收数据C.不可以发送数据，可以接收数据D.连接马上断开41.下列的应用层协议中，( )是采用 UDP 传输的。（分数：2.00）A.SMTPB.DNSC.HTTPD.FTP二、综合应用题(总题数：8，分数：22.00)42.综合应用题 41-47 小题。_43.已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序遍历访问的第一个结点，是否可不用递
15、归且不用栈来完成?请简述原因。（分数：2.00）_44.设有一个双向链表 h，每个结点中除有 prior，data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，每个结点中的 freq 域都被初始化为零。每当进行 LocateNode(h，x)运算时，令元素值为 x 的结点中 freq 域中的值加一，并调整表中结点的次序，使其按访问频度的递减序列排序，以便使被频繁访问的结点总靠近表头，试写一符合上述要求的 LocateNode 运算的算法。（分数：2.00）_45.写出单总线结构计算机中指令 M( )VER1，R2(含义是将寄存器 R1 中内容写入寄存器 R2 中)的
16、操作步骤。（分数：2.00）_某计算机系统的内存储器由(2ache 和主存构成，Cache 的存取周期为 45 纳秒，主存的存取周期为 200 纳秒。已知在一段给定的时间内，CPU 共访问内存 4500 次，其中 340 次访问主存。问：（分数：8.00）(1).Cache 的命中率是多少?（分数：2.00）_(2).CPU 访问内存的平均时间是多少纳秒?（分数：2.00）_(3).Cache 一主存系统的效率是多少?（分数：2.00）_(4).如果 Cache 为 8 行，主存 16 块，分别采用三种方式映射主存的第 9 块到 Cache 中什么位置(写出 tag值)?（分数：2.00）_4
17、6.用 PV 操作实现写优先读者一写者问题。（分数：2.00）_(某系统有三个进程 P1，P2，P3 并发工作，其中 P1 执行过程中需要使用资源 S3，S1；P2 需要使用资源S1，S2；P3 需要使用资源 S2，S3。（分数：4.00）(1).如果进程推进过程中对资源分配不加以限制，会导致什么结果，为什么?（分数：2.00）_(2).如何避免这种后果，列出所有可能的方法。（分数：2.00）_47.描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退 N 帧协议，多帧滑动窗口与选择重传协议的区别。（分数：2.00）_计算机专业（基础综合）-试卷 14 答案解析(总分：104.00
18、，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.在一个长度为 n(n1)的带头结点的单链表 h 上，设有尾指针 r(指向尾结点)，则执行( )操作与链表的长度有关。（分数：2.00）A.删除单链表中的第一个元素B.删除单链表中的最后一个元素 C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素解析：解析：执行 B 时需要找到尾结点的前一个结点的指针 P，因此需遍历该单链表，因此与链表的长度有关。3.若用单链表来表示队列，则应该
19、选用( )。（分数：2.00）A.带尾指针的非循环链表B.带尾指针的循环链表 C.带头指针的非循环链表D.带头指针的循环链表解析：解析：设尾指针为 TAIL，则通过 TAIL 可访问队尾，通过 TAII-next 可访问队头。4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，深度为 h 则( )。（分数：2.00）A.n=h+mB.h+m=2nC.m=h1D.n=2 h 一 1 解析：解析：对于深度为 h 的满二叉树，n 一 2 0 +2 1 +2 h -1，m=2 h-1 。5.关于哈夫曼树，下列说法正确的是( ).（分数：2.00）A.在哈夫曼树中。权值相同的叶子结点都在同一层上B
20、.在哈夫曼树中，权值较大的叶子结点一般离根结点较远C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近 D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊处理解析：解析：哈夫曼编码中不允许出现两个字符编码相同的情况，故 D 错。6.每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点 N 的左孩子是它在原树对应结点的( )。（分数：2.00）A.最左孩子 B.最右孩子C.右邻兄弟D.左邻兄弟解析：7.已知 8 个数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。
21、（分数：2.00）A.4B.5 C.6D.7解析：解析：根据二叉排序树插入结点算法，将上述 8 个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为 5，故该树的深度：勾 5。8.下列叙述正确的个数是( )。(1)m=2 的平衡 m 路查找树是 AVL 树(2)m=3 的平衡 m 路查找树是 23 树(3)m=2 的平衡 m 路查找树的叶结点不一定在同一层(4)m 阶 B 一树的叶结点必须在同一层(5)m 阶 B 一树是平衡 m 路查找树(6)平衡 m 路查找树不一定是 B 一树（分数：2.00）A.3B.4C.5D.6 解析：解析：参见 B-树定义。9.下列说法正确的是(
22、 )。（分数：2.00）A.任何有向网络(AOV 一网)拓扑排序的结果是唯一的B.有回路的图不能进行拓扑排序 C.在 AOE 网中一定只有一条关键路径D.一个正常的 AOE 网中只能有一个源点、一小汇点和一条关键路径解析：解析：拓扑排序的结果不一定是唯一的；在 AOE 网中，关键路径可以不止一条，故选 B。10.对任意 7 个关键字进行排序，至少要进行( )次关键字之间的两两比较。（分数：2.00）A.13B.14C.15 D.16解析：解析：任何一个借助于“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为：ceil(10g(n!)。11.一组记录的关键字为25，50，15，35，8
23、0，85，20，40，36，70，其中含有 5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分数：2.00）A.15，25，35，50，20，40，80，85，36，70 B.15，25，35，50，80，20，85，40，70，36C.15，25，50，35，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，85解析：解析：对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一个长度为 2 的有序表。故选 A。12.完整的计算机系统由( )组成。（分数：2.00）A.运算器和控制器B.CPU 和主存
24、储器C.主机和外部设备D.硬件系统和软件系统 解析：解析：完整的计算机系统由配套的硬件系统和软件系统组成。13.真值 0 在原码、反码和补码机器数形式下( )。（分数：2.00）A.都有正 0、负 0 两种形式B.仅在原码中有两种形式，而在反码、补码机器数形式下只有一种形式C.仅在反码中有两种形式，而在原码、补码机器数形式下只有一种形式D.仅在补码中有一种形式，而在反码、原码机器数形式下均有两种形式 解析：解析：真值 0 在原码、反码机器数形式下都有正 0、负 0 两种形式，而在补码机器数形式下只有一种形式。14.某定点机字长 8 位(含 1 位符号位)，现该机中一个寄存器的内容为 43H，则
25、将其算术左移一位、算术右移一位的结果分别为( )。（分数：2.00）A.86H，21HB.结果出错，21H C.结果出错，A1HD.未给出机器数形式，无法判断解析：解析：虽然题中未给出机器数形式是原码、反码还是补码，但由于寄存器中数据的符号位为 0，即表示一个正数，故仍可进行判断；算术左移 1 位时，符号位为 0 不变，最高数值位 1 移丢，结果出错；算术右移 1 位时，符号位为 0 不变，数值位最高位补 0，结果为 21H。15.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若
26、有两个数 X= 7 2932，Y=2 5 58，则用浮点加法计算 X+Y 的最终结果是( )。（分数：2.00）A.001111100010B.001110100010C.010000010001D.发生溢出 解析：解析：根据题意，X 可记为 00，111；00，11101(分号前为阶码，分号后为尾数)，Y 可记为00，101；00，10100；首先对阶，X、Y 阶码相减，即 00，11100，101=00，111+11，011=00，010(最高位进位自然丢弃)，可知 X 的阶码比 Y 的阶码大 2，根据小阶向大阶看齐的原则，将 Y 的阶码加 2，尾数右移 2 位，得 Y 为 00，111；
27、00，00101；尾数相加，即 00，11101+00，00101=01，00010，尾数相加结果符号位为 01，故需进行右规；规格化，将尾数右移 1 位，阶码加 1，得 X+Y 为 01，000；00，10001，阶码符号位为 01，说明发生溢出。16.半导体随机存储器的访问速度与( )有关。（分数：2.00）A.存储芯片的存取周期 B.存储芯片的容量大小C.所访问存储单元的位置D.以上都包括解析：解析：半导体随机存储器的访问速度与存储芯片的容量和存储单元的位置无关，只取决于存储芯片的存取周期，选 A。17.Cache 常用的写回策略有写直达法和写回法。当采用写回法时，一个 Cache 数据
28、块在( )时写回主存。（分数：2.00）A.任何一次写操作数时B.第一次写操作数时C.数据块被换出时 D.以上都有可能解析：解析：写直达法指写操作数时既写入 Cache 又写入主存；写回法指写操作数时写入 Cache 而不写入主存，仅当数据被替换出 Cache 时才写回主存。18.主存地址寄存器 MAR 的位数与下列哪个寄存器相同?( )。（分数：2.00）A.主存数据寄存器 MDRB.程序计数器 PC C.指令寄存器 IRD.累加器 AC解析：解析：主存地址寄存器 MAR 和程序计数器 PC 的位数都取决于主存储器的容量，二者位数相等，选B。19.控制存储器使用 EPROM 构成的控制器是(
29、 )。（分数：2.00）A.静态微程序控制器B.动态微程序控制器 C.毫微程序控制器D.以上都不对解析：解析：采用 EPROM 作为控制存储器，可以通过改变微指令和微程序来改变机器的指令系统，此时控制器又称为动态微程序控制器，选 B。20.下列关于 PCI 总线的说法中错误的是( )。（分数：2.00）A.PCI 总线采用集中式总线判优控制方式B.PCI 总线是一种 16 位的并行总线 C.PCI 总线具有自动配置能力D.PCI 总线在 PC 机中得到了广泛的使用解析：解析：PCI 总线是一种 32 位或 64 位的并行总线。21.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总
30、线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3 B.5C.16D.无法确定解析：解析：链式请求方式下，为实现总线判优控制，需要 1 根总线请求线、1 根总线忙线、1 根总线同意线，共 3 根控制线。22.下列说法中错误的是( )。（分数：2.00）A.统一编址方式即把 IO 端口当作主存储器的单元来分配地址B.统一编址方式下不需要专门的 IO 指令C.统一编址方式下指令系统的实现比单独编址方式复杂 D.采用统一编址方式会减少主存的编址空间解析：解析：统一编址方式下不需要专门的 IO 指令，因而简化了指令系统，其指令系统的实现比单独编址方式简单。23.活动头
31、磁盘的寻道时间是指( )。（分数：2.00）A.最大寻道时间B.最小寻道时间C.A、B 之和D.A、B 的平均值 解析：解析：寻道时间又叫平均寻道时间，是指磁盘最大寻道时间和最小寻道时间的平均值。24.下列选择中，( )不是操作系统关心的主要问题。（分数：2.00）A.管理计算机裸机B.设计、提供用户程序与计算机硬件资源的接口C.管理计算机系统资源D.高级程序设计语言的编译器 解析：解析：D 不是操作系统的功能。25.采用( )不会产生内部碎片。（分数：2.00）A.分页式存储管理B.分段式存储管理 C.固定分区式存储管理D.段页式存储管理解析：解析：分段式存储管理会产生外部碎片。26.在操作
32、系统中，要对并发进程进行同步的原因是( )。（分数：2.00）A.进程必须在有限的时间内完成B.进程具有动态性C.并发进程访问共享资源 D.进程具有结构性解析：解析：为了相互协调的顺序进程访问共享资源，必须提供同步和互斥机制。27.( )不是分段式虚拟存储管理优于分页式虚拟存储管理的方面。（分数：2.00）A.没有内零头B.便于处理在进程执行过程中堆栈尺寸的增长问题C.便于共享内存中数据D.只需将进程的一部分调入内存，进程即可运行 解析：解析：D 分页虚拟存储管理也有此功能。28.在下面四段描述中( )是错误的。（分数：2.00）A.若进程 A 和进程 B 在临界区上互斥，那么当进程 A 处于
33、该临界区时，它不能被进程 B 打断 B.虚拟存储管理中采用对换策略后，用户进程可使用的存储空间似乎增加了C.虚拟存储管理中的抖动现象是指页面置换时用于换页的时间远多于执行程序的时间D.进程可以由程序、数据和进程控制块(PCB)描述解析：解析：进程 A 在临界去访问是可以被 B 打断的，但是由于互斥机制，B 是进不了临界区的。29.存放在磁盘上的文件( )。（分数：2.00）A.既可随机访问，又可顺序访问 B.只能随机访问C.只能顺序访问D.必须通过操作系统访问解析：解析：根据文件物理结构的不同，文件可以被随机和顺序访问。30.文件系统中，文件访问控制信息存储的合理位置是( )。（分数：2.00
34、）A.文件控制块 B.文件分配表C.用户口令表D.系统注册表解析：解析：文件的访问控制信息存储在 FCB 里。31.在操作系统中，P，V 操作是一种( )。（分数：2.00）A.机器指令B.系统调用命令C.作业控制命令D.低级进程通信原语 解析：解析：P，V 操作是原子操作。32.( )是操作系统必须提供的功能。（分数：2.00）A.GUI(图形用户界面)B.为进程提供系统调用命令C.处理中断 D.编译源程序解析：解析：中断系统是操作系统运行所需的硬件支撑，所以必须提供。33.磁盘和磁带是两种存储介质，他们的特点是( )。（分数：2.00）A.二者都是顺序执行的B.二者都是随机存取的C.磁盘是
35、顺序存取的，磁带是随机存取的D.磁带是顺序存取的，磁盘是随机存取的 解析：解析：本题主要考查磁盘和磁带的工作方式的区别。34.网桥是在以下( )层上实现不同网络互联的设备。（分数：2.00）A.物理层B.数据链路层 C.网络层D.传输层解析：解析：网桥是数据链路层设备。35.一种数据编码的海明距是 7，那么使用这种编码最多可以纠正( )个错误。（分数：2.00）A.0 个B.1 个C.2 个D.3 个 解析：解析：为了纠正 d 个错误，需要使用距离为 2d+1 的编码方案，所以答案是 3 个。36.在一个 HDLC 帧的数据中，如果出现了 000111111011 这样的流，请问发送到信道上它
36、将会变成( )。（分数：2.00）A.0001111110110B.0001111111011C.0001111101011 D.0000111111011解析：解析：HDLC 采用了比特填充法来实现链路层的透明传输，如果在数据流中发现了连续的 5 个“1”就在其后面加一个“0”，所以 C 是正确答案。37.以太网交换机进行转发决策时使用的 PDU 地址是( )。（分数：2.00）A.目的物理地址 B.目的 IP 地址C.源物理地址D.源 IP 地址解析：解析：以太网交换机是数据链路层设备，它的转发决策是依据 PDU 的目的物理地址。38.一台路由器的路由表中有以下几项(CIDR)： （分数：
37、2.00）A.接口 0B.接口 1 C.接口 2D.接口 0 和接口 1解析：解析：从掩码上看第一项和第二项都可以，而路由器会选择匹配位数最多的项目发送，所以这里应当选择第二项的端口来发送分组，即接口 1。39.假设一个连接的最大数据段长度为 2KB，一个 TCP 的阀值为 64KB，如果这时候传输发生了超时，那么新的阀值为( )。（分数：2.00）A.32KB B.63KBC.128KBD.2KB解析：解析：当发生了超时的情况下，TCP 的阀值将会减半。40.如果在 TCP 连接中有一方发送了 F1N 分组，并且收到了回复，那么它将( )。（分数：2.00）A.不可以发送数据，也不可以接收数
38、据B.可以发送数据，不可以接收数据C.不可以发送数据，可以接收数据 D.连接马上断开解析：解析：TCP 提供了一个全双工的连接，当一方希望断开连接时需要发送 FIN 的分组，而另一方仍然可以发送数据。41.下列的应用层协议中，( )是采用 UDP 传输的。（分数：2.00）A.SMTPB.DNS C.HTTPD.FTP解析：解析：DNS 是采用 UDP 传输的，而其他的三项都使用了 TCP。二、综合应用题(总题数：8，分数：22.00)42.综合应用题 41-47 小题。_解析：43.已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序遍历访问的第一个结点，是否可不用递归且不用栈来完成?
39、请简述原因。（分数：2.00）_正确答案：(正确答案：可以。 原因：后序遍历的顺序是“左子树一右子树一根结点”。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。if(p!一null)while(p 一lchild!=nuUllp 一rchild!=null)while(p 一lehild!=null)p=p 一lchild；if(p-rehild!=null)p=p 一rehild；return(p)；返回后序序列第一个结点的指针)解析：44.设有一个双向链表 h，每个结点中除有 prior，data 和 next 三个域外，还有一个
40、访问频度域 freq，在链表被起用之前，每个结点中的 freq 域都被初始化为零。每当进行 LocateNode(h，x)运算时，令元素值为 x 的结点中 freq 域中的值加一，并调整表中结点的次序，使其按访问频度的递减序列排序，以便使被频繁访问的结点总靠近表头，试写一符合上述要求的 LocateNode 运算的算法。（分数：2.00）_正确答案：(正确答案：在 DLinkList 类型的定义中添加 freq 域(int 类型)，给该域初始化为 0。在每次查找到一个结点*P 时，使其 freq 域增 1，再在*P 结点的前面找到一个结点*q，它或是头结点或是满足 q-freq=p-freq，
41、然后删除*P 结点，使其插入到*q 结点之后。算法描述如下： int LocateNode(DLinkList*h，ElemType x) DLinkList *p=h 一 b-next，*q； while(p!=NULLp-data!=x) p=p 一)解析：45.写出单总线结构计算机中指令 M( )VER1，R2(含义是将寄存器 R1 中内容写入寄存器 R2 中)的操作步骤。（分数：2.00）_正确答案：(正确答案：操作步骤如下：第一步，送指令地址。将 PC 的值送 MAR。PCMAR 第二步，计算下一条指令的地址。PC 加 1 送回 PC。PC+1PC 第三步，读人指令。把存储器中读出来
42、的指令经过 MDR 送入 IR 中。DBUSMDRIR 第四步，送数据。R1R2)解析：某计算机系统的内存储器由(2ache 和主存构成，Cache 的存取周期为 45 纳秒，主存的存取周期为 200 纳秒。已知在一段给定的时间内，CPU 共访问内存 4500 次，其中 340 次访问主存。问：（分数：8.00）(1).Cache 的命中率是多少?（分数：2.00）_正确答案：(正确答案：C Cache 的命中率 h=Nc(Nc+Nm)=(4500-340)4500=092=9295)解析：(2).CPU 访问内存的平均时间是多少纳秒?（分数：2.00）_正确答案：(正确答案：C CPU 访存
43、的平均时间 Ta=h*Tc+(1-h)*Tm=09245+(1 一 092)200=574ns)解析：(3).Cache 一主存系统的效率是多少?（分数：2.00）_正确答案：(正确答案：C Cache 一主存系统的效率 e=TcTa=45574=078=78)解析：(4).如果 Cache 为 8 行，主存 16 块，分别采用三种方式映射主存的第 9 块到 Cache 中什么位置(写出 tag值)?（分数：2.00）_正确答案：(正确答案：全 相联方式：8 行中的任意行，tag=1001 直接方式：8 行中的第 1 行，tag=1 组相联方式：第 1 组的任意行，tag=10)解析：46.用 PV 操作实现写优先读者一写者问题。（分数：2.00）_
