1、计算机专业（基础综合）模拟试卷 36 及答案与解析一、单项选择题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=h1（D）n=2 h 一 14 关于哈夫曼树，下列说法正确的是( ).（A）在哈夫曼树中。权值相同的叶子结点都在同一层上（B）在哈夫曼树中，权值较大的叶子结点一般离根结点较远（C）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（D）在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊处理5 每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点N 的左孩子是它在原树对应结点的( )。（A）最左孩子（B）最右孩子（C）右邻兄弟（D）左邻兄弟
3、6 已知 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 路查找树是 23 树(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，3
5、5，80，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=72932，Y=2 558，则用浮点加法计算 X+Y 的最终结果是( )。（A）001111100010（B） 001110100010（C） 010000010001（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 帧的数据中，如果出现了 000111111011 这样的流，请问发送到信道上它将会变成( ) 。（A）0001111110110（B） 0001111111011（C） 0001111101011（D）000011111101136 以太网交换机进行转发决策时使用的 PDU 地址是 ( )。（A）目的物理地址（B）目的 IP 地址（C）源物理地址（D）源 IP 地址37 一台路由器的路由表中有以
13、下几项(CIDR)：请问当目的地址为 13814663127的分组将会被发给( ) 。（A）接口 0（B）接口 1（C）接口 2（D）接口 0 和接口 138 假设一个连接的最大数据段长度为 2KB，一个 TCP 的阀值为 64KB，如果这时候传输发生了超时，那么新的阀值为( )。（A）32KB（B） 63KB（C） 128KB（D）2KB39 如果在 TCP 连接中有一方发送了 F1N 分组，并且收到了回复，那么它将 ( )。（A）不可以发送数据，也不可以接收数据（B）可以发送数据，不可以接收数据（C）不可以发送数据，可以接收数据（D）连接马上断开40 下列的应用层协议中，( )是采用 UD
14、P 传输的。（A）SMTP（B） DNS（C） HTTP（D）FTP二、综合应用题41-47 小题，共 70 分。41 已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序遍历访问的第一个结点，是否可不用递归且不用栈来完成?请简述原因。42 设有一个双向链表 h，每个结点中除有 prior，data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，每个结点中的 freq 域都被初始化为零。每当进行 LocateNode(h，x)运算时，令元素值为 x 的结点中 freq 域中的值加一，并调整表中结点的次序，使其按访问频度的递减序列排序，以便使被频繁访问的结点总靠近
15、表头，试写一符合上述要求的 LocateNode 运算的算法。43 写出单总线结构计算机中指令 M( )VER1，R2(含义是将寄存器 R1 中内容写入寄存器 R2 中)的操作步骤。43 某计算机系统的内存储器由(2ache 和主存构成，Cache 的存取周期为 45 纳秒，主存的存取周期为 200 纳秒。已知在一段给定的时间内，CPU 共访问内存 4500 次，其中 340 次访问主存。问：44 Cache 的命中率是多少?45 CPU 访问内存的平均时间是多少纳秒?46 Cache 一主存系统的效率是多少?47 如果 Cache 为 8 行，主存 16 块，分别采用三种方式映射主存的第 9
16、 块到 Cache中什么位置(写出 tag 值)?48 用 PV 操作实现写优先读者一写者问题。48 (某系统有三个进程 P1，P2，P3 并发工作，其中 P1 执行过程中需要使用资源S3，S1；P2 需要使用资源 S1，S2；P3 需要使用资源 S2，S3。49 如果进程推进过程中对资源分配不加以限制，会导致什么结果，为什么?50 如何避免这种后果，列出所有可能的方法。51 描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退 N 帧协议，多帧滑动窗口与选择重传协议的区别。计算机专业（基础综合）模拟试卷 36 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。
17、下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 执行 B 时需要找到尾结点的前一个结点的指针 P，因此需遍历该单链表，因此与链表的长度有关。2 【正确答案】 B【试题解析】 设尾指针为 TAIL，则通过 TAIL 可访问队尾，通过 TAII-next 可访问队头。3 【正确答案】 D【试题解析】 对于深度为 h 的满二叉树，n 一 20+21+2h-1，m=2 h-1。4 【正确答案】 C【试题解析】 哈夫曼编码中不允许出现两个字符编码相同的情况，故 D 错。5 【正确答案】 A6 【正确答案】 B【试题解析】 根据二叉排序树插入结点算法，将上述 8
18、 个数据元素按照依次插入结点的方法构造出一棵二叉排序树后，该树的最大层次为 5，故该树的深度：勾5。7 【正确答案】 D【试题解析】 参见 B-树定义。8 【正确答案】 B【试题解析】 拓扑排序的结果不一定是唯一的；在 AOE 网中，关键路径可以不止一条，故选 B。9 【正确答案】 C【试题解析】 任何一个借助于“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为：ceil(10g(n!)。10 【正确答案】 A【试题解析】 对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一个长度为 2 的有序表。故选 A。11 【正确答案】 D【试题解析】 完整的计算机系统由配
19、套的硬件系统和软件系统组成。12 【正确答案】 D【试题解析】 真值 0 在原码、反码机器数形式下都有正 0、负 0 两种形式，而在补码机器数形式下只有一种形式。13 【正确答案】 B【试题解析】 虽然题中未给出机器数形式是原码、反码还是补码，但由于寄存器中数据的符号位为 0，即表示一个正数，故仍可进行判断；算术左移 1 位时，符号位为 0 不变，最高数值位 1 移丢，结果出错；算术右移 1 位时，符号位为 0 不变，数值位最高位补 0，结果为 21H。14 【正确答案】 D【试题解析】 根据题意，X 可记为 00，111；00 ，11101(分号前为阶码，分号后为尾数)，Y 可记为 00，1
20、01；00，10100；首先对阶，X、Y 阶码相减，即00，11100，101=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，说明发生溢出。15 【正确答案】 A【试题解析】 半导体随机存储器的访问速度与存储芯片的容
21、量和存储单元的位置无关，只取决于存储芯片的存取周期，选 A。16 【正确答案】 C【试题解析】 写直达法指写操作数时既写入 Cache 又写入主存；写回法指写操作数时写入 Cache 而不写入主存，仅当数据被替换出 Cache 时才写回主存。17 【正确答案】 B【试题解析】 主存地址寄存器 MAR 和程序计数器 PC 的位数都取决于主存储器的容量，二者位数相等，选 B。18 【正确答案】 B【试题解析】 采用 EPROM 作为控制存储器，可以通过改变微指令和微程序来改变机器的指令系统，此时控制器又称为动态微程序控制器，选 B。19 【正确答案】 B【试题解析】 PCI 总线是一种 32 位或
22、 64 位的并行总线。20 【正确答案】 A【试题解析】 链式请求方式下，为实现总线判优控制，需要 1 根总线请求线、1根总线忙线、1 根总线同意线，共 3 根控制线。21 【正确答案】 C【试题解析】 统一编址方式下不需要专门的 I O 指令，因而简化了指令系统，其指令系统的实现比单独编址方式简单。22 【正确答案】 D【试题解析】 寻道时间又叫平均寻道时间，是指磁盘最大寻道时间和最小寻道时间的平均值。23 【正确答案】 D【试题解析】 D 不是操作系统的功能。24 【正确答案】 B【试题解析】 分段式存储管理会产生外部碎片。25 【正确答案】 C【试题解析】 为了相互协调的顺序进程访问共享
23、资源，必须提供同步和互斥机制。26 【正确答案】 D【试题解析】 D 分页虚拟存储管理也有此功能。27 【正确答案】 A【试题解析】 进程 A 在临界去访问是可以被 B 打断的，但是由于互斥机制， B是进不了临界区的。28 【正确答案】 A【试题解析】 根据文件物理结构的不同，文件可以被随机和顺序访问。29 【正确答案】 A【试题解析】 文件的访问控制信息存储在 FCB 里。30 【正确答案】 D【试题解析】 P，V 操作是原子操作。31 【正确答案】 C【试题解析】 中断系统是操作系统运行所需的硬件支撑，所以必须提供。32 【正确答案】 D【试题解析】 本题主要考查磁盘和磁带的工作方式的区别
24、。33 【正确答案】 B【试题解析】 网桥是数据链路层设备。34 【正确答案】 D【试题解析】 为了纠正 d 个错误，需要使用距离为 2d+1 的编码方案，所以答案是 3 个。35 【正确答案】 C【试题解析】 HDLC 采用了比特填充法来实现链路层的透明传输，如果在数据流中发现了连续的 5 个“1”就在其后面加一个“0”，所以 C 是正确答案。36 【正确答案】 A【试题解析】 以太网交换机是数据链路层设备，它的转发决策是依据 PDU 的目的物理地址。37 【正确答案】 B【试题解析】 从掩码上看第一项和第二项都可以，而路由器会选择匹配位数最多的项目发送，所以这里应当选择第二项的端口来发送分
25、组，即接口 1。38 【正确答案】 A【试题解析】 当发生了超时的情况下，TCP 的阀值将会减半。39 【正确答案】 C【试题解析】 TCP 提供了一个全双工的连接，当一方希望断开连接时需要发送FIN 的分组，而另一方仍然可以发送数据。40 【正确答案】 B【试题解析】 DNS 是采用 UDP 传输的，而其他的三项都使用了 TCP。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 可以。原因：后序遍历的顺序是“左子树一右子树一根结点” 。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。 if(p!一 null)whil
26、e(p 一lchild!=nuUllp 一rchild!=null)while(p 一lehild!=null)p=p 一lchild；if(p-rehild!=null)p=p 一 rehild；return(p)；返回后序序列第一个结点的指针42 【正确答案】 在 DLinkList 类型的定义中添加 freq 域(int 类型)，给该域初始化为 0。在每次查找到一个结点*P 时，使其 freq 域增 1，再在*P 结点的前面找到一个结点*q，它或是头结点或是满足 q-freq=p-freq，然后删除*P 结点，使其插入到*q 结点之后。算法描述如下： int LocateNode(DLi
27、nkList*h，ElemType x)DLinkList *p=h 一 b-next，*q；while(p!=NULLp-data!=x)p=p 一43 【正确答案】 操作步骤如下：第一步，送指令地址。将 PC 的值送MAR。PCMAR 第二步，计算下一条指令的地址。PC 加 1 送回 PC。PC+1PC第三步，读人指令。把存储器中读出来的指令经过 MDR 送入 IR 中。DBUSMDRIR 第四步，送数据。R1R244 【正确答案】 C Cache 的命中率 h=Nc(Nc+Nm)=(4500-340)4500=092=929545 【正确答案】 C CPU 访存的平均时间 Ta=h*Tc
28、+(1-h)*Tm=09245+(1 一092)200=574ns46 【正确答案】 C Cache 一主存系统的效率 e=TcTa=45574=078=78 47 【正确答案】 全 相联方式：8 行中的任意行，tag=1001 直接方式：8 行中的第1 行，tag=1 组相联方式：第 1 组的任意行，tag=1048 【正确答案】 Semaphore mutex=1 ； 读文件计数的互斥Semaphore write=1； 写互斥Semaphore s=1； 用于实现“写优先”int count=0；Reader()while(1)p(s)；p(mutex)；if(count=0)p(wri
29、te)；当第一个读者读文件时，阻止写者写count+：v(mutex)：v(s)；读文件49 【正确答案】 可 能会发生死锁。例如，进程 P1，P2 和 P3 分别占有了资源S3，S1 和 S2，若各进程再申请资源会导致循环等待，即发生了死锁。50 【正确答案】 可 以采用静态分配、按序分配、分配前检测、强行剥夺资源或采用银行家算法等方法消除死锁。51 【正确答案】 滑动窗口是数据链路控制的一个重要机制，滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的帧的序号，称为接收窗口。发送方窗口内的序列号代表了那些已经被发送，但是还没有被确认的帧，或者是那些可以被发送的帧。滑动窗口机制在发送方和接收方分别设置发送窗口和接收窗口，在数据传输过程中受控地向前滑动，控制数据传输的过程。发送窗口用来对发方进行流量控制，其大小指明在收到对方 ACK 之前发送方最多可以发送多少个数据帧，只有序号在窗口覆盖范
