1、考研计算机学科专业基础综合-4-1 及答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，深度为 h，则( )。（分数：2.00）A.n=h+mB.h+m=2nC.m=h-1D.n=2h-12.Cache 常用的写回策略有写直达法和写回法。当采用写回法时，一个 Cahe 数据块在( )时写回主存。（分数：2.00）A.任何一次写操作数时B.第一次写操作数时C.数据块被换出时D.以上都有可能3.对任意 7 个关键字进行排序，至少要进行( )次关键字之间的两两比较。（分数：2.00）A.
2、13B.14C.15D.164.下列关于 PCI 总线的说法中错误的是( )。（分数：2.00）A.PCI 总线采用集中式总线判优控制方式B.PCI 总线是一种 16 位的并行总线C.PCI 总线具有自动配置能力D.PCI 总线在 PC 机中得到了广泛的使用5.半导体随机存储器的访问速度与( )有关。（分数：2.00）A.存储芯片的存取周期B.存储芯片的容量大小C.所访问存储单元的位置D.以上都包括6.在一个 HDLC 帧的数据中，如果出现了 0001 1111 1011 这样的流，请问发送到信道上它将会变成( )。（分数：2.00）A.0001 1111 1011 0B.0001 1111
3、1101 1C.0001 1111 0101 1D.0000 1111 1101 17.在操作系统中，P，V 操作是一种( )。（分数：2.00）A.机器指令B.系统调用命令C.作业控制命令D.低级进程通信原语8.一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有 5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分数：2.00）A.15，25，35，50，2040，8085，36，70B.15，25，35，50，80，20，8540，70，36C.15，25，50，35，80，85，20，36，40，70D.15，25，35
4、，50，80，20，36，40，70，859.下列说法中错误的是( )。（分数：2.00）A.统一编址方式即把 I/O 端口当作主存储器的单元来分配地址B.统一编址方式下不需要专门的 I/0 指令C.统一编址方式下指令系统的实现比单独编址方式复杂D.采用统一编址方式会减少主存的编址空间10.某定点机字长 8 位(含 1 位符号位)，现该机中一个寄存器的内容为 43H，则将其算术左移一位、算术右移一位的结果分别为( )。（分数：2.00）A.86H，21HB.结果出错，21HC.结果出错，A1HD.未给出机器数形式，无法判断11.关于哈夫曼树，下列说法正确的是( )。（分数：2.00）A.在哈夫
5、曼树中，权值相同的叶子结点都在同一层上B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理12.下列的应用层协议中，( )是采用 UDP 传输的。（分数：2.00）A.SMTPB.DNSC.HTTPD.FTP13.完整的计算机系统由( )组成。（分数：2.00）A.运算器和控制器B.CPU 和主存储器C.主机和外部设备D.硬件系统和软件系统14.活动头磁盘的寻道时间是指( )。（分数：2.00）A.最大寻道时间B.最小寻道时间C.A、B 之和D.A
6、、B 的平均值15.在操作系统中，要对并发进程进行同步的原因是( )。（分数：2.00）A.进程必须在有限的时间内完成B.进程具有动态性C.并发进程访问共享资源D.进程具有结构性16.如果在 TCP 连接中有一方发送了 FIN 分组，并且收到了回复，那么它将( )。（分数：2.00）A.不可以发送数据，也不可以接收数据B.可以发送数据，不可以接收数据C.不可以发送数据，可以接收数据D.连接马上断开17.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3B.5C.16D.无法确定18.浮点数加减运算过
7、程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若有两个数X=2729/32，Y=2 55/8，则用浮点加法计算 X+Y 的最终结果是( )。（分数：2.00）A.00111 1100010B.00111 0100010C.01000 0010001D.发生溢出19.已知 8 个数据元素为(34，76，45，1826，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。（分数：2.00）A.4B.5C.6D.720.以太网交换机进行转发决策时使用的 PDU 地址是(
8、 )。（分数：2.00）A.目的物理地址B.目的 IP 地址C.源物理地址D.源 IP 地址21.控制存储器使用 EPROM 构成的控制器是( )。（分数：2.00）A.静态微程序控制器B.动态微程序控制器C.毫微程序控制器D.以上都不对22.主存地址寄存器 MAR 的位数与下列哪个寄存器相同?( )。（分数：2.00）A.主存数据寄存器 MDRB.程序计数器 PCC.指令寄存器 IRD.累加器 AC23.磁盘和磁带是两种存储介质，他们的特点是( )。（分数：2.00）A.二者都是顺序执行的B.二者都是随机存取的C.磁盘是顺序存取的，磁带是随机存取的D.磁带是顺序存取的，磁盘是随机存取的24.
9、真值 0 在原码、反码和补码机器数形式下( )。（分数：2.00）A.都有正 0、负 0 两种形式B.仅在原码中有两种形式，而在反码、补码机器数形式下只有一种形式C.仅在反码中有两种形式，而在原码、补码机器数形式下只有一种形式D.仅在补码中有一种形式，而在反码、原码机器数形式下均有两种形式25.存放在磁盘上的文件( )。（分数：2.00）A.既可随机访问，又可顺序访问B.只能随机访问C.只能顺序访问D.必须通过操作系统访问26.网桥是在以下( )层上实现不同网络互联的设备。（分数：2.00）A.物理层B.数据链路层C.网络层D.传输层27.下列说法正确的是( )。（分数：2.00）A.任何有向
10、网络(AOV-网)拓扑排序的结果是唯一的B.有回路的图不能进行拓扑排序C.在 AOE 网中一定只有一条关键路径D.一个正常的 AOE 网中只能有一个源点、一小汇点和一条关键路径28.采用( )不会产生内部碎片。（分数：2.00）A.分页式存储管理B.分段式存储管理C.固定分区式存储管理D.段页式存储管理29.一种数据编码的海明距是 7，那么使用这种编码最多可以纠正( )个错误。（分数：2.00）A.0 个B.1 个C.2 个D.3 个30.文件系统中，文件访问控制信息存储的合理位置是( )。（分数：2.00）A.文件控制块B.文件分配表C.用户口令表D.系统注册表31.每棵树都能唯一地转换成相
11、对应的二叉树，由树转换成的二叉树中，一个结点 N 的左孩子是它在原树对应结点的( )。（分数：2.00）A.最左孩子B.最右孩子C.右邻兄弟D.左邻兄弟32.下列叙述正确的个数是( )。 (1) m=2 的平衡 m 路查找树是 AVL 树 (2) m=3 的平衡 m 路查找树是 2-3树 (3) m=2 的平衡 m 路查找树的叶结点不一定在同一层 (4) m 阶 B-树的叶结点必须在同一层 (5) m 阶B-树是平衡 m 路查找树 (6) 平衡 m 路查找树不一定是 B-树（分数：2.00）A.3B.4C.5D.633.在一个长度为 n(n1)的带头结点的单链表 h 上，设有尾指针 r(指向尾
12、结点)，则执行( )操作与链表的长度有关。（分数：2.00）A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元紊前插入一个新元素D.在单链表最后一个元素后插入一个新元素34.( )不是分段式虚拟存储管理优于分页式虚拟存储管理的方面。（分数：2.00）A.没有内零头B.便于处理在进程执行过程中堆栈尺寸的增长问题C.便于共享内存中数据D.只需将进程的一部分调入内存，进程即可运行35.若用单链表来表示队列，则应该选用( )。（分数：2.00）A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表36.在下面四段描述中( )是错误的。（
13、分数：2.00）A.若进程 A 和进程 B 在临界区上互斥，那么当进程 A 处于该临界区时，它不能被进程 B 打断B.虚拟存储管理中采用对换策略后，用户进程可使用的存储空间似乎增加了C.虚拟存储管理中的抖动现象是指页面置换时用于换页的时间远多于执行程序的时间D.进程可以由程序、数据和进程控制块(PCB)描述37.下列选择中，( )不是操作系统关心的主要问题。（分数：2.00）A.管理计算机裸机B.设计、提供用户程序与计算机硬件资源的接口C.管理计算机系统资源D.高级程序设计语言的编译器38.一台路由器的路由表中有以下几项(CIDR)：（分数：2.00）A.地址掩码B.下一跳C.138.146.
14、56.021D.接口 0E.138.146.60.022F.接口 1G.默认H.接口 239.( )是操作系统必须提供的功能。（分数：2.00）A.GUI(图形用户界面)B.为进程提供系统调用命令C.处理中断D.编译源程序40.假设一个连接的最大数据段长度为 2KB，一个 TCP 的阀值为 64KB，如果这时候传输发生了超时，那么新的阀值为( )。（分数：2.00）A.32KBB.63KBC.128KBD.2KB二、B综合应用题/B(总题数：5，分数：70.00)41.设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法： (1) 找出最小值结点，且打印该数值。 (2) 若该数
15、值为奇数，则将其与直接后继结点的数值交换。 (3) 若该数值为偶数，则将其直接后继结点删除。（分数：10.00）_给定序列3，5，7，9，11，13，15，17，（分数：35.98）(1).按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。（分数：5.14）_(2).按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。（分数：5.14）_(3).按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。（分数：5.14）_(4).将其编码为循环冗余校验码，生成多项式 G(x)=1011。（分
16、数：5.14）_(5).分别画出寻址方式由操作码指出和寻址方式由专用字段指出时的指令格式。（分数：5.14）_(6).当指令寻址方式由操作码指出时，直接和间接寻址可寻址的主存空间大小为多少?（分数：5.14）_(7).写出 4 种寻址方式下，有效地址 EA 的表达式。（分数：5.14）_42.分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如 32 位地址空间)，会给页表的设计带来什么样的新问题?请给出一种解决方法，分析它的优点和缺点。（分数：8.00）_43.有一个仓库，可以存放 A 和 B 两种产品，但要求： (1) 每次只能存入一种产品(A 或 B)； (2) -NA产
17、品的数量-B 产品的数量M。 其中，N 和 M 是正整数。试用 P，V 操作描述产品 A 与产品 B 的入库过程。（分数：7.00）_某公司的局域网设置如下所示，两个局域网通过路由器连接到 NAT 服务器上，并且通过 NAT 服务器连接到Intrnet 上。局域网 1 的掩码是 192.168.14.0/25，局域网 2 的掩码是 192.168.14.128/25，NAT 服务器的内部 IP 地址为 192.168.13.25，外部 IP 地址为 202.157.85.69，在 NAT 服务器中有如下的表项： 源地址：端口 索引值192.168.14.48:2587 4325192.168.
18、14.175:652 5898192.168.14.145:245 5899请问：（分数：9.00）(1).168.14.175 的主机和地址为 192.168.14.48 的主机分别属于哪个局域网?（分数：2.25）_(2).按照题目的配置，路由器的路由表项应该含有哪几项?（分数：2.25）_(3).现在有一个目的地址为 201.25.68.99，源地址为 192.168.14.175，TCP 端口为652 的 IP 分组到达 NAT 服务器，问 NAT 服务器是否转发该分组?如果转发，分组的 IP 号和端口号分别是多少?（分数：2.25）_(4).当 NAT 服务器收到一个目的地址是 20
19、2.157.85.69，端口号是 4325 的 TCP 数据后，它将转发给哪个主机? （分数：2.25）_考研计算机学科专业基础综合-4-1 答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，深度为 h，则( )。（分数：2.00）A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1 解析：对于深度为 h 的满二叉树，n=2 0+21+2h-1=2h-1，m=2 h-1。2.Cache 常用的写回策略有写直达法和写回法。当采用写回法时，一个 Cahe 数据块在( )时写回主
20、存。（分数：2.00）A.任何一次写操作数时B.第一次写操作数时C.数据块被换出时 D.以上都有可能解析：写直达法指写操作数时既写入 Cache 又写入主存；写回法指写操作数时写入 Cache 而不写入主存，仅当数据被替换出 Cache 时才写回主存。3.对任意 7 个关键字进行排序，至少要进行( )次关键字之间的两两比较。（分数：2.00）A.13B.14C.15 D.16解析：任何一个借助于“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为：ceil(log(n!)。4.下列关于 PCI 总线的说法中错误的是( )。（分数：2.00）A.PCI 总线采用集中式总线判优控制方式B.
21、PCI 总线是一种 16 位的并行总线 C.PCI 总线具有自动配置能力D.PCI 总线在 PC 机中得到了广泛的使用解析：PCI 总线是一种 32 位或 64 位的并行总线。5.半导体随机存储器的访问速度与( )有关。（分数：2.00）A.存储芯片的存取周期 B.存储芯片的容量大小C.所访问存储单元的位置D.以上都包括解析：半导体随机存储器的访问速度与存储芯片的容量和存储单元的位置无关，只取决于存储芯片的存取周期，选 A。6.在一个 HDLC 帧的数据中，如果出现了 0001 1111 1011 这样的流，请问发送到信道上它将会变成( )。（分数：2.00）A.0001 1111 1011
22、0B.0001 1111 1101 1C.0001 1111 0101 1 D.0000 1111 1101 1解析：HDLC 采用了比特填充法来实现链路层的透明传输，如果在数据流中发现了连续的 5 个1就在其后面加一个0，所以 C 是正确答案。7.在操作系统中，P，V 操作是一种( )。（分数：2.00）A.机器指令B.系统调用命令C.作业控制命令D.低级进程通信原语 解析：P，V 操作是原子操作。8.一组记录的关键字为25，50，15，35，80，85，20，40，36，70，其中含有 5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（分数：2.00）A.1
23、5，25，35，50，2040，8085，36，70 B.15，25，35，50，80，20，8540，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。9.下列说法中错误的是( )。（分数：2.00）A.统一编址方式即把 I/O 端口当作主存储器的单元来分配地址B.统一编址方式下不需要专门的 I/0 指令C.统一编址方式下指令系统的实现比单独编址方式复杂 D.采用统一编址方式会减少主存的编址空间解析：
24、统一编址方式下不需要专门的 I/O 指令，因而简化了指令系统，其指令系统的实现比单独编址方式简单。10.某定点机字长 8 位(含 1 位符号位)，现该机中一个寄存器的内容为 43H，则将其算术左移一位、算术右移一位的结果分别为( )。（分数：2.00）A.86H，21HB.结果出错，21H C.结果出错，A1HD.未给出机器数形式，无法判断解析：虽然题中未给出机器数形式是原码、反码还是补码，但由于寄存器中数据的符号位为 0，即表示一个正数，故仍可进行判断；算术左移 1 位时，符号位为 0 不变，最高数值位 1 移丢，结果出错；算术右移1 位时，符号位为 0 不变，数值位最高位补 0，结果为 2
25、1H。11.关于哈夫曼树，下列说法正确的是( )。（分数：2.00）A.在哈夫曼树中，权值相同的叶子结点都在同一层上B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近 D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理解析：哈夫曼编码中不允许出现两个字符编码相同的情况，故 D 错。12.下列的应用层协议中，( )是采用 UDP 传输的。（分数：2.00）A.SMTPB.DNS C.HTTPD.FTP解析：DNS 是采用 UDP 传输的，而其他的三项都使用了 TCP。13.完整的计算机系统由( )
26、组成。（分数：2.00）A.运算器和控制器B.CPU 和主存储器C.主机和外部设备D.硬件系统和软件系统 解析：完整的计算机系统由配套的硬件系统和软件系统组成。14.活动头磁盘的寻道时间是指( )。（分数：2.00）A.最大寻道时间B.最小寻道时间C.A、B 之和D.A、B 的平均值 解析：寻道时间又叫平均寻道时间，是指磁盘最大寻道时间和最小寻道时间的平均值。15.在操作系统中，要对并发进程进行同步的原因是( )。（分数：2.00）A.进程必须在有限的时间内完成B.进程具有动态性C.并发进程访问共享资源 D.进程具有结构性解析：为了相互协调的顺序进程访问共享资源，必须提供同步和互斥机制。16.
27、如果在 TCP 连接中有一方发送了 FIN 分组，并且收到了回复，那么它将( )。（分数：2.00）A.不可以发送数据，也不可以接收数据B.可以发送数据，不可以接收数据C.不可以发送数据，可以接收数据 D.连接马上断开解析：TCP 提供了一个全双工的连接，当一方希望断开连接时需要发送 FIN 的分组，而另一方仍然可以发送数据。17.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3 B.5C.16D.无法确定解析：链式请求方式下，为实现总线判优控制，需要 1 根总线请求线、1 根总线忙线、1 根总线
28、同意线，共 3 根控制线。18.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若有两个数X=2729/32，Y=2 55/8，则用浮点加法计算 X+Y 的最终结果是( )。（分数：2.00）A.00111 1100010B.00111 0100010C.01000 0010001D.发生溢出 解析：根据题意，X 可记为 00，111；00，11101(分号前为阶码，分号后为尾数)，Y 可记为。0，101；00，10100； 首先对阶，X、Y 阶码相减，即 00，111-00，10
29、1=00，111+11，011=00，010(最高位进位自然丢弃)，可知 X 的阶码比 Y 的阶码大 2，根据小阶向大阶看齐的原则，将 Y 的阶码加 2，尾数右移 2 位，得 Y 为 00，111；00，00101； 尾数相加，即 00，11101+00，00101=01，00010，尾数相加结果符号位为 01，故需进行右规； 规格化，将尾数右移 1 位，阶码加 1，得 X+Y 为 01，000；00，10001，阶码符号位为 01，说明发生溢出。19.已知 8 个数据元素为(34，76，45，1826，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。（分数
30、：2.00）A.4B.5 C.6D.7解析：根据二叉排序树插入结点算法，将上述 8 个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为 5，故该树的深度为 5。20.以太网交换机进行转发决策时使用的 PDU 地址是( )。（分数：2.00）A.目的物理地址 B.目的 IP 地址C.源物理地址D.源 IP 地址解析：以太网交换机是数据链路层设备，它的转发决策是依据 PDU 的目的物理地址。21.控制存储器使用 EPROM 构成的控制器是( )。（分数：2.00）A.静态微程序控制器B.动态微程序控制器 C.毫微程序控制器D.以上都不对解析：采用 EPROM 作为控制存储器，
31、可以通过改变微指令和微程序来改变机器的指令系统，此时控制器又称为动态微程序控制器，选 B。22.主存地址寄存器 MAR 的位数与下列哪个寄存器相同?( )。（分数：2.00）A.主存数据寄存器 MDRB.程序计数器 PC C.指令寄存器 IRD.累加器 AC解析：主存地址寄存器 MAR 和程序计数器 PC 的位数都取决于主存储器的容量，二者位数相等，选 B。23.磁盘和磁带是两种存储介质，他们的特点是( )。（分数：2.00）A.二者都是顺序执行的B.二者都是随机存取的C.磁盘是顺序存取的，磁带是随机存取的D.磁带是顺序存取的，磁盘是随机存取的 解析：本题主要考查磁盘和磁带的工作方式的区别。2
32、4.真值 0 在原码、反码和补码机器数形式下( )。（分数：2.00）A.都有正 0、负 0 两种形式B.仅在原码中有两种形式，而在反码、补码机器数形式下只有一种形式C.仅在反码中有两种形式，而在原码、补码机器数形式下只有一种形式D.仅在补码中有一种形式，而在反码、原码机器数形式下均有两种形式 解析：真值 0 在原码、反码机器数形式下都有正 0、负 0 两种形式，而在补码机器数形式下只有一种形式。25.存放在磁盘上的文件( )。（分数：2.00）A.既可随机访问，又可顺序访问 B.只能随机访问C.只能顺序访问D.必须通过操作系统访问解析：根据文件物理结构的不同，文件可以被随机和顺序访问。26.
33、网桥是在以下( )层上实现不同网络互联的设备。（分数：2.00）A.物理层B.数据链路层 C.网络层D.传输层解析：网桥是数据链路层设备。27.下列说法正确的是( )。（分数：2.00）A.任何有向网络(AOV-网)拓扑排序的结果是唯一的B.有回路的图不能进行拓扑排序 C.在 AOE 网中一定只有一条关键路径D.一个正常的 AOE 网中只能有一个源点、一小汇点和一条关键路径解析：拓扑排序的结果不一定是唯一的；在 AOE 网中，关键路径可以不止一条，故选 B。28.采用( )不会产生内部碎片。（分数：2.00）A.分页式存储管理B.分段式存储管理 C.固定分区式存储管理D.段页式存储管理解析：分
34、段式存储管理会产生外部碎片。29.一种数据编码的海明距是 7，那么使用这种编码最多可以纠正( )个错误。（分数：2.00）A.0 个B.1 个C.2 个D.3 个 解析：为了纠正 d 个错误，需要使用距离为 2d+1 的编码方案，所以答案是 3 个。30.文件系统中，文件访问控制信息存储的合理位置是( )。（分数：2.00）A.文件控制块 B.文件分配表C.用户口令表D.系统注册表解析：文件的访问控制信息存储在 FCB 里。31.每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点 N 的左孩子是它在原树对应结点的( )。（分数：2.00）A.最左孩子 B.最右孩子C.右邻兄弟
35、D.左邻兄弟解析：32.下列叙述正确的个数是( )。 (1) m=2 的平衡 m 路查找树是 AVL 树 (2) m=3 的平衡 m 路查找树是 2-3树 (3) m=2 的平衡 m 路查找树的叶结点不一定在同一层 (4) m 阶 B-树的叶结点必须在同一层 (5) m 阶B-树是平衡 m 路查找树 (6) 平衡 m 路查找树不一定是 B-树（分数：2.00）A.3B.4C.5D.6 解析：参见 B-树定义。33.在一个长度为 n(n1)的带头结点的单链表 h 上，设有尾指针 r(指向尾结点)，则执行( )操作与链表的长度有关。（分数：2.00）A.删除单链表中的第一个元素B.删除单链表中的最
36、后一个元素 C.在单链表第一个元紊前插入一个新元素D.在单链表最后一个元素后插入一个新元素解析：执行 B 时需要找到尾结点的前一个结点的指针 P，因此需遍历该单链表，因此与链表的长度有关。34.( )不是分段式虚拟存储管理优于分页式虚拟存储管理的方面。（分数：2.00）A.没有内零头B.便于处理在进程执行过程中堆栈尺寸的增长问题C.便于共享内存中数据D.只需将进程的一部分调入内存，进程即可运行 解析：D 分页虚拟存储管理也有此功能。35.若用单链表来表示队列，则应该选用( )。（分数：2.00）A.带尾指针的非循环链表B.带尾指针的循环链表 C.带头指针的非循环链表D.带头指针的循环链表解析：
37、设尾指针为 TAIL，则通过 TAIL 可访问队尾，通过 TAIL-next 可访问队头。36.在下面四段描述中( )是错误的。（分数：2.00）A.若进程 A 和进程 B 在临界区上互斥，那么当进程 A 处于该临界区时，它不能被进程 B 打断 B.虚拟存储管理中采用对换策略后，用户进程可使用的存储空间似乎增加了C.虚拟存储管理中的抖动现象是指页面置换时用于换页的时间远多于执行程序的时间D.进程可以由程序、数据和进程控制块(PCB)描述解析：进程 A 在临界去访问是可以被 B 打断的，但是由于互斥机制，B 是进不了临界区的。37.下列选择中，( )不是操作系统关心的主要问题。（分数：2.00）
38、A.管理计算机裸机B.设计、提供用户程序与计算机硬件资源的接口C.管理计算机系统资源D.高级程序设计语言的编译器 解析：D 不是操作系统的功能。38.一台路由器的路由表中有以下几项(CIDR)：（分数：2.00）A.地址掩码B.下一跳 C.138.146.56.021D.接口 0E.138.146.60.022F.接口 1G.默认H.接口 2解析：从掩码上看第一项和第二项都可以，而路由器会选择匹配位数最多的项目发送，所以这里应当选择第二项的端口来发送分组，即接口 1。39.( )是操作系统必须提供的功能。（分数：2.00）A.GUI(图形用户界面)B.为进程提供系统调用命令C.处理中断 D.编
39、译源程序解析：中断系统是操作系统运行所需的硬件支撑，所以必须提供。40.假设一个连接的最大数据段长度为 2KB，一个 TCP 的阀值为 64KB，如果这时候传输发生了超时，那么新的阀值为( )。（分数：2.00）A.32KB B.63KBC.128KBD.2KB解析：当发生了超时的情况下，TCP 的阀值将会减半。二、B综合应用题/B(总题数：5，分数：70.00)41.设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法： (1) 找出最小值结点，且打印该数值。 (2) 若该数值为奇数，则将其与直接后继结点的数值交换。 (3) 若该数值为偶数，则将其直接后继结点删除。（分数：1
40、0.00）_正确答案：()解析：算法的思想是：采用从前向后扫描单链表的方法，边扫描边测试，根据测试结点执行相应的操作。算法描述如下： int Function(LinkList* la) int temp； LinkNode* p=L-next；/单链表为空时返回 LinkNode* q=p； if(p=NULL) return 0； /*找到最小值结点*/ while(p!=NULL) if(p-dataq-data) q=P： p=P-next； /*打印最小值结点*/ printf(“Min:%dn“，p-data)； /*功能点：若该数值为奇数，则将其与直接后继结点的数值交换*/ if
41、(q-data%2=1) temp=q-data； if(q-next=NULL)/不存在直接后继结点 return 0； q-data=q-next-data； q-next-data=temp； /*功能点：若该数值为偶数，则将其直接后继结点删除*/ else if(q-next=NULL) return 0； p=P-next； q-next=P-next； free(p)； return 1；给定序列3，5，7，9，11，13，15，17，（分数：35.98）(1).按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。
42、（分数：5.14）_正确答案：()解析：按表中元素的顺序依次插入的二叉排序树如下图所示，其在等概率情况下查找成功的平均查找长度为：ASL:(1+2+3+4+5+6+7+8)/8=9/2。(2).按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。（分数：5.14）_正确答案：()解析：按表中元素的顺序依次插入的平衡二叉树如下图所示，其在等概率情况下查找成功的平均查找长度为：ASI:(1+2*2+3*4+5)/8=11/4。(3).按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。（分数：5.14）_正确答案：()解析：题目要求能够发现两位错并纠正一位错
43、，故需要在海明码的基础上增加 1 位全局的奇偶校验位，此时的编码方式称为“扩展的海明码”。 普通海明码编码计算如下：首先计算所需校验位的位数 k，根据 2k4+k+1，可知应取 3 位校验位，数据位与校验位的位置安排如下： 7 6 5 4 3 2 1D3 D2 D3 C4 D0 C2 C11 0 1 0各校验位的数值计算如下：C1校验的比特位包含 1、3、5、7 位，按配偶原则 C2校验的比特位包含 2、3、6、7 位，按配偶原则 C4校验的比特位包含 4、5、6、7 位，按配偶原则 综上，将 1010 编码扩展为海明码为 1010010，为了能够发现两位错并纠正一位错，在最左端增加 1 位全局偶校验位 C8， 故，将有效信息 1010 编码扩展的海明码为 11010010。(4).将其编码为循环冗余校验码，生成多项式 G(x)=1011。（分数：5.14）_正确答案：()解析：将待编码的有效信息 1010 表示为多项式 M(x)： M(x)=X3+x=1010 由于生成多项式 G(x)为 4 位，故将 M(x)左移 3 位，得 M(x)X3，目的是空出 3 位，以便拼装余数(校验位)：M(x)x3=x6+x4=1010000 用 M(x)x3模 2 除生成多项式 G(x)： 将左移后的待编码有
