1、计算机专业（基础综合）模拟试卷 13 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在一个长度为 n(n1)的带头结点的单链表 h 上，设有尾指针 r(指向尾结点) ，则执行( )操作与链表的长度有关。（A）删除单链表中的第一个元素（B）删除单链表中的最后一个元素（C）在单链表第一个元素前插入一个新元素（D）在单链表最后一个元素后插入一个新元素2 若用单链表来表示队列，则应该选用( )。（A）带尾指针的非循环链表（B）带尾指针的循环链表（C）带头指针的非循环链表（D）带头指针的循环链表3 对于一个满二叉树，
2、共有 n 个结点和 m 个叶子结点，深度为 h，则( )。（A）n=h+m（B） h+m=2n（C） m=h-1（D）n=2 h-14 关于哈夫曼树，下列说法正确的是( )。（A）在哈夫曼树中，权值相同的叶子结点都在同一层上（B）在哈夫曼树中，权值较大的叶子结点一般离根结点较远（C）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（D）在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊处理5 每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点N 的左孩子是它在原树对应结点的( )。（A）最左孩子（B）最右孩子（C）右邻兄弟（D）左邻兄弟6
3、 已知 8 个数据元素为(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )。（A）4（B） 5（C） 6（D）77 下列叙述正确的个数是( )。(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-树（A）3（B） 4（C） 5（D）68 下列说法正确的是( ) 。（A）任何有向网络(AOV-网) 拓扑排序的结果是唯一
4、的（B）有回路的图不能进行拓扑排序（C）在 AOE 网中一定只有一条关键路径（D）一个正常的 AOE 网中只能有一个源点、一小汇点和一条关键路径9 对任意 7 个关键字进行排序，至少要进行( )次关键字之间的两两比较。（A）13（B） 14（C） 15（D）1610 一组记录的关键字为25，50，15，35，80，85，20，40，36，70)，其中含有5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（A）15，25，35，50，20，40，80，85，36，70（B） 15，25，35，50，80，20，85，40，70，36（C） 15，25，50，35，8
5、0，85，20，36，40，70（D）15，25，35，50，80，20，36，40，70，8511 完整的计算机系统由( )组成。（A）运算器和控制器（B） CPU 和主存储器（C）主机和外部设备（D）硬件系统和软件系统12 真值 0 在原码、反码和补码机器数形式下( )。（A）都有正 0、负 0 两种形式（B）仅在原码中有两种形式，而在反码、补码机器数形式下只有一种形式（C）仅在反码中有两种形式，而在原码、补码机器数形式下只有一种形式（D）仅在补码中有一种形式，而在反码、原码机器数形式下均有两种形式13 某定点机字长 8 位(含 1 位符号位)，现该机中一个寄存器的内容为 43H，则将其算
6、术左移一位、算术右移一位的结果分别为( )。（A）86H，21H（B）结果出错，21H（C）结果出错，A1H（D）未给出机器数形式，无法判断14 浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位(均含 2 位符号位)。若有两个数 X=272932，Y= 558，则用浮点加法计算 X+Y 的最终结果是( )。（A）00111 1100010（B） 00111 0100010（C） 01000 0010001（D）发生溢出15 半导体随机存储器的访问速度与( )有关。（A）存储芯片的存取周期（B）存储芯片的容
7、量大小（C）所访问存储单元的位置（D）以上都包括16 Cache 常用的写回策略有写直达法和写回法。当采用写回法时，一个 Cache 数据块在( ) 时写回主存。（A）任何一次写操作数时（B）第一次写操作数时（C）数据块被换出时（D）以上都有可能17 主存地址寄存器 MAR 的位数与下列哪个寄存器相同?( )。（A）主存数据寄存器 MDR（B）程序计数器 PC（C）指令寄存器 IR（D）累加器 AC18 控制存储器使用 EPROM 构成的控制器是( )。（A）静态微程序控制器（B）动态微程序控制器（C）毫微程序控制器（D）以上都不对19 下列关于 PCI 总线的说法中错误的是 ( )。（A）P
8、CI 总线采用集中式总线判优控制方式（B） PCI 总线是一种 16 位的并行总线（C） PCI 总线具有自动配置能力（D）PCI 总线在 PC 机中得到了广泛的使用20 某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（A）3（B） 5（C） 16（D）无法确定21 下列说法中错误的是( )。（A）统一编址方式即把 IO 端口当作主存储器的单元来分配地址（B）统一编址方式下不需要专门的 IO 指令（C）统一编址方式下指令系统的实现比单独编址方式复杂（D）采用统一编址方式会减少主存的编址空间22 活动头磁盘的寻道时间是指
9、( )。（A）最大寻道时间（B）最小寻道时间（C） A、B 之和（D）A、B 的平均值23 下列选择中，( ) 不是操作系统关心的主要问题。（A）管理计算机裸机（B）设计、提供用户程序与计算机硬件资源的接口（C）管理计算机系统资源（D）高级程序设计语言的编译器24 采用( ) 不会产生内部碎片。（A）分页式存储管理（B）分段式存储管理（C）固定分区式存储管理（D）段页式存储管理25 在操作系统中，要对并发进程进行同步的原因是( )。（A）进程必须在有限的时间内完成（B）进程具有动态性（C）并发进程访问共享资源（D）进程具有结构性26 ( )不是分段式虚拟存储管理优于分页式虚拟存储管理的方面。（
10、A）没有内零头（B）便于处理在进程执行过程中堆栈尺寸的增长问题（C）便于共享内存中数据（D）只需将进程的一部分调入内存，进程即可运行27 在下面四段描述中( )是错误的。（A）若进程 A 和进程 B 在临界区上互斥，那么当进程 A 处于该临界区时，它不能被进程 B 打断（B）虚拟存储管理中采用对换策略后，用户进程可使用的存储空间似乎增加了（C）虚拟存储管理中的抖动现象是指页面置换时用于换页的时间远多于执行程序的时间（D）进程可以由程序、数据和进程控制块(PCB)描述28 存放在磁盘上的文件( )。（A）既可随机访问，又可顺序访问（B）只能随机访问（C）只能顺序访问（D）必须通过操作系统访问29
11、 文件系统中，文件访问控制信息存储的合理位置是( )。（A）文件控制块（B）文件分配表（C）用户口令表（D）系统注册表30 在操作系统中，P ，V 操作是一种( )。（A）机器指令（B）系统调用命令（C）作业控制命令（D）低级进程通信原语31 ( )是操作系统必须提供的功能。（A）GUI( 图形用户界面)（B）为进程提供系统调用命令（C）处理中断（D）编译源程序32 磁盘和磁带是两种存储介质，他们的特点是( )。（A）二者都是顺序执行的（B）二者都是随机存取的（C）磁盘是顺序存取的，磁带是随机存取的（D）磁带是顺序存取的，磁盘是随机存取的33 网桥是在以下( ) 层上实现不同网络互联的设备。（
12、A）物理层（B）数据链路层（C）网络层（D）传输层34 一种数据编码的海明距是 7，那么使用这种编码最多可以纠正( )个错误。（A）0 个（B） 1 个（C） 2 个（D）3 个35 在一个 HDLC 帧的数据中，如果出现了 0001 1111 1011 这样的流，请问发送到信道上它将会变成( ) 。（A）0001 1111 1011 0（B） 0001 1111 1101 1（C） 0001 1111 0101 1（D）0000 1111 1101 136 以太网交换机进行转发决策时使用的 PDU 地址是 ( )。（A）目的物理地址（B）目的 IP 地址（C）源物理地址（D）源 IP 地址3
13、7 请问当目的地址为 13814663127 的分组将会被发给( )。（A）接口 0（B）接口 1（C）接口 2（D）接口 0 和接口 138 假设一个连接的最大数据段长度为 2 KB，一个 TCP 的阀值为 64 KB，如果这时候传输发生了超时，那么新的阀值为( )。（A）32 KB（B） 63 KB（C） 128 KB（D）2 KB39 如果在 TCP 连接中有一方发送了 FIN 分组，并且收到了回复，那么它将( )。（A）不可以发送数据，也不可以接收数据（B）可以发送数据，不可以接收数据（C）不可以发送数据，可以接收数据（D）连接马上断开40 下列的应用层协议中，( )是采用 UDP 传
14、输的。（A）SMTP（B） DNS（C） HTTP（D）FTP二、综合应用题41-47 小题，共 70 分。41 试编写一个非递归算法，实现求以二叉链表存储的二叉树中 q 结点的祖先。42 设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为：MAX从 w 到 v 的最短距离 w 属于 V(G)如果 v 是有向图 G 中具有的最小偏心度的顶点，则称顶点 v 是 G 的中心点。43 在一个 8 级中断的系统中，硬件中断响应从高到低的优先顺序是12345678，通过中断屏蔽技术，将中断处理优先顺序设置为13572468，如果 CPU 在执行一个应用程序时有 5、6、7
15、、8 级的四个中断同时到达，CPU 在按优先顺序处理到第 3 个中断请求的过程中又有一个 3级中断请求到达 CPU，试画出 CPU 响应这些中断的顺序示意图。44 某计算机有 8 个主设备需要竞争总线的使用权，其设备号为 07。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，该计算机为实现判优控制所需的控制线种类及数量分别为多少?45 三个进程 P1、P2 、P3 互斥使用一个包含 N(NO)个单元的缓冲区。P1 每次用produce()生成一个正整数并用 put()
16、送入缓冲区某一空单元中； P2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数； P3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。46 在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为 m。试分别计算 m=3 和 m=4 时， FIFO 和 LRU 两种替换算法的缺页(页故障)数，并给出：结果说明了什么?47 如下图所示为一个网络连接的
17、示意图，主机 1 到主机 2 采用了 SLIP 网络连接，SLIP 网络可以传输的最大数据段是 296 字节，主机 2 和主机 3 使用了以太网连接。请问：(1)为了使 IP 不分片，主机 1 可以在 TCP 包中承载多少数据 ?(2)主机 3 可以在 TCP 包中承载多少数据?(3) 先在主机 1 和主机 3 建立起了一条 CP 连接，请问这条 TCP 连接的 mss 值是多少?计算机专业（基础综合）模拟试卷 13 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 执行 B 时需要
18、找到尾结点的前一个结点的指针 P，因此需遍历该单链表，因此与链表的长度有关。2 【正确答案】 B【试题解析】 设尾指针为 TAIL，则通过 TAIL 可访问队尾，通过 TAIL-next可访问队头。3 【正确答案】 D【试题解析】 对于深度为 h 的满二叉树，n=2 0+21+2h-1=2h-1，m=2 h-1。4 【正确答案】 C【试题解析】 哈夫曼编码中不允许出现两个字符编码相同的情况，故 D 错。5 【正确答案】 A6 【正确答案】 B【试题解析】 根据二叉排序树插入结点算法，将上述 8 个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为 5，故该树的深度为 5。7
19、 【正确答案】 D【试题解析】 参见 B-树定义。8 【正确答案】 B【试题解析】 拓扑排序的结果不一定是唯一的；在 AOE 网中，关键路径可以不止一条，故选 B。9 【正确答案】 C【试题解析】 任何一个借助于“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为：ceil(log(n!) 。10 【正确答案】 A【试题解析】 对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一个长度为 2 的有序表。故选 A。11 【正确答案】 D【试题解析】 完整的计算机系统由配套的硬件系统和软件系统组成。12 【正确答案】 D【试题解析】 真值 0 在原码、反码机器数形式下都
20、有正 0、负 0 两种形式，而在补码机器数形式下只有一种形式。13 【正确答案】 B【试题解析】 虽然题中未给出机器数形式是原码、反码还是补码，但由于寄存器中数据的符号位为 0，即表示一个正数，故仍可进行判断；算术左移 1 位时，符号位为 0 不变，最高数值位 1 移丢，结果出错；算术右移 1 位时，符号位为 0 不变，数值位最高位补 0，结果为 21H。14 【正确答案】 D【试题解析】 根据题意，X 可记为 00，111；00 ，11101(分号前为阶码，分号后为尾数)，Y 可记为 00，101；00，10100；首先对阶，X、Y 阶码相减，即00，111-00，101=00，111+11
21、，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，说明发生溢出。15 【正确答案】 A【试题解析】 半导体随机存储器的访问速度与存储芯片的容量和存储单元的位置无关，只取决于存储芯片的存取周期，选 A。16 【正确答案】 C【试题解析】
22、 写直达法指写操作数时既写入 Cache 又写入主存；写回法指写操作数时写入 Cache 而不写入主存，仅当数据被替换出 Cache 时才写回主存。17 【正确答案】 B【试题解析】 主存地址寄存器 MAR 和程序计数器 PC 的位数都取决于主存储器的容量，二者位数相等，选 B。18 【正确答案】 B【试题解析】 采用 EPROM 作为控制存储器，可以通过改变微指令和微程序来改变机器的指令系统，此时控制器又称为动态微程序控制器，选 B。19 【正确答案】 B【试题解析】 PCI 总线是一种 32 位或 64 位的并行总线。20 【正确答案】 A【试题解析】 链式请求方式下，为实现总线判优控制，
23、需要 1 根总线请求线、1根总线忙线、1 根总线同意线，共 3 根控制线。21 【正确答案】 C【试题解析】 统一编址方式下不需要专门的 I O 指令，因而简化了指令系统，其指令系统的实现比单独编址方式简单。22 【正确答案】 D【试题解析】 寻道时间又叫平均寻道时间，是指磁盘最大寻道时间和最小寻道时间的平均值。23 【正确答案】 D【试题解析】 D 不是操作系统的功能。24 【正确答案】 B【试题解析】 分段式存储管理会产生外部碎片。25 【正确答案】 C【试题解析】 为了相互协调的顺序进程访问共享资源，必须提供同步和互斥机制。26 【正确答案】 D【试题解析】 D 分页虚拟存储管理也有此功
24、能。27 【正确答案】 A【试题解析】 进程 A 在临界去访问是可以被 B 打断的，但是由于互斥机制， B是进不了临界区的。28 【正确答案】 A【试题解析】 根据文件物理结构的不同，文件可以被随机和顺序访问。29 【正确答案】 A【试题解析】 文件的访问控制信息存储在 FCB 里。30 【正确答案】 D【试题解析】 P，V 操作是原子操作。31 【正确答案】 C【试题解析】 中断系统是操作系统运行所需的硬件支撑，所以必须提供。32 【正确答案】 D【试题解析】 本题主要考查磁盘和磁带的工作方式的区别。33 【正确答案】 B【试题解析】 网桥是数据链路层设备。34 【正确答案】 D【试题解析】
25、 为了纠正 d 个错误，需要使用距离为 2d+1 的编码方案，所以答案是 3 个。35 【正确答案】 C【试题解析】 HDLC 采用了比特填充法来实现链路层的透明传输，如果在数据流中发现了连续的 5 个“1”就在其后面加一个“0”，所以 C 是正确答案。36 【正确答案】 A【试题解析】 以太网交换机是数据链路层设备，它的转发决策是依据 PDU 的目的物理地址。37 【正确答案】 B【试题解析】 从掩码上看第一项和第二项都可以，而路由器会选择匹配位数最多的项目发送，所以这里应当选择第二项的端口来发送分组，即接口 1。38 【正确答案】 A【试题解析】 当发生了超时的情况下，TCP 的阀值将会减
26、半。39 【正确答案】 C【试题解析】 TCP 提供了一个全双工的连接，当一方希望断开连接时需要发送FIN 的分组，而另一方仍然可以发送数据。40 【正确答案】 B【试题解析】 DNS 是采用 UDP 传输的，而其他的三项都使用了 TCP。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 该题可采用按后序遍历二叉树的非递归算法，当访问 q 结点时，结点栈中所有栈元素均为 q 结点的祖先。#define MAX 1000void Ancestor(BTTree*T，BTNode*q)BTNode*sMAX；栈实现非递归BTNode*p=T；int bMAX；int top=-1：
27、dowhile(p)s+top=p；btop=0；P=p-lchild；if(top-1&btop=1)p=stop；if(p=q)printf(“q 结点的祖先是：n“)；for(int i=0； i=top；i+)printf(“c“，si-data)；return；elsetop-；if(top-1)p=stop-rchild；btop=1；while(top-1)；42 【正确答案】 设 C 是有向图 G 的邻接矩阵，求最小偏心度的顶点的步骤如下：(1)利用 Floyd 算法求出每对顶点之间的最短路径矩阵 A；(2)对矩阵 A 求出每列 i 的最大值，得到顶点 i 的偏心度；(3)在这
28、 n 个顶点的偏心度中，求出最小偏心度的顶点 k，即为图 G 的中心点对应的算法如下：int Center(MGraph&G)int AMAXVMAXV， BMAXV；int i，j，k，m；for(i=0；i Gn；i+)将邻接矩阵赋给 Afor(j=0；j Gn；j+)Aij=Gedgesij；for(k=0；kGn；k+)实现()功能for(i=0；i Gn；i+)for(j=0；j Gn；j+)if(Aik+AkjAij)Aij=Aik+Akj；for(j=0；j Gn；j+)实现()功能，结果放在 B 数组中Bj=A0j；for(i=1；i Gn；i+)if(BjAij)Bj=Aij
29、；k=0；m=Bj；实现() 功能，结果放在 k 中for(i=1；i Gn；i+)if(Bim)m=Bi；k=i；return k；返回 k 值43 【正确答案】 硬件中断响应的优先顺序称为响应优先级，设置中断屏蔽字后实际处理中断的优先顺序称为处理优先级，分析如下：CPU 在执行现行程序时，有5、6、7、8 级的四个中断请求同时到达，根据响应优先级，CPU 首先响应 5 级中断，设置中断屏蔽字后，由于 5 级中断的处理优先级高于 6、7、8 级中断，故CPU 执行 5 级中断服务程序直至结束，返回原应用程序；此时仍有 6、7、8 级三个中断请求，根据响应优先级，CPU 首先响应 6 级中断，
30、保护现场、设置中断屏蔽字后开中断，由于 7 级中断的处理优先级高于 6 级中断，故 CPU 转而去执行 7级中断服务程序；7 级中断服务程序设置中断屏蔽字后，屏蔽了 6、8 级中断请求，故 7 级中断服务程序执行直至结束，返回到 6 级中断服务程序；6 级中断服务程序执行的过程中，有一个 3 级中断请求到达，由于 6 级中断的处理优先级低于 3 级中断，故 CPU 将转而去执行 3 级中断服务程序，3 级中断服务程序设置中断屏蔽字后，将屏蔽 6、8 级中断请求，故 3 级中断服务程序将执行直至结束，返回到 6 级中断服务程序； 6 级中断服务程序执行直至结束，返回到原应用程序，此时尚有一个 8
31、 级中断请求，故 PU 将转向 8 级中断服务程序直至执行结束返回原应用程序。上述过程的示意图如下：44 【正确答案】 (1)集中式总线判优控制的仲裁逻辑集中在一处，如 CPU 中，而分布式判优控制的仲裁逻辑分散在与总线连接的各主设备上。 (2)三种集中仲裁方式下，为实现判优控制所需的控制线种类和数量分别为：链式查询方式下需要 1 根总线请求线、1 根总线忙线和 1 根总线同意线；计数器定时查询方式下需要 1 根总线请求线、1 根总线忙线和 log28=3 根设备地址线；独立请求方式下需要 8 根总线请求线和 8 根总线同意线。45 【正确答案】 定义信号量 S1 控制 P1 与 P2 之间的
32、同步；S2 控制 P1 与 P3 之间的同步；：empty 控制生产者与消费者之间的同步； mutex 控制进程间互斥使用缓冲区。程序如下：Var s1=0， s2=0，empty=N ，mutex=1 ；ParbeginP1：beginX=produce()； *生成一个数*P(empty)； *判断缓冲区是否有空单元*P(mutex)； *缓冲区是否被占用*Put()；If x2=0V(s2)； *如果是偶数，向 P3 发出信号*elseV(s1)； *如果是奇数，向 P2 发出信号*V(mutex)； *使用完缓冲区，释放 *endP2：beginP(s1)； *收到 P1 发来的信号，
33、已产生一个奇数*P(mutex)； *缓冲区是否被占用*Getodd()；Countodd()：=countodd()+1；V(mutex)； *释放缓冲区 *V(empty)； *向 P1 发信号，多出一个空单元*endP3：beginP(s2) *收到 P1 发来的信号，已产生一个偶数*P(mutex)； *缓冲区是否被占用*Geteven()；Counteven()：=counteven()+1 ；V(mutex)； *释放缓冲区 *V(empty)； *向 P1 发信号，多出一个空单元*endParend46 【正确答案】 (1)m=3 LRU：10 次 FIFO ：9 次m=4 LRU：8 次 FIFO：10 次(2)说明两点：FIFO 存在奇异现象，即存储块增加，缺页次数反而增加；LRU 并非总是优于 FIFO。47 【正确答案】 (1)TCP 头部长 20，IP 头部长 20，为了使 IP 数据报不分片，主机 1 不能在 TCP 的数据中添加超过 256 字节的数据。(2)同理主机 3 不可以在数据中添加超过 1 460 字节的数据。(3)在 TCP 连接建立的过程中，双方协商 mss，由于主机 1 的 mss 为 256，主机3 的 mss 为 1 460，所以为了使 IP 不分片，整个 TCP 连接的 mss 应该为 256。
