1、计算机专业（基础综合）模拟试卷 60 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。void fun(int n)int i，k； for(i=1；i =n；i+)for(j=1；j =n；j+)k=1：while(k=n)k=5*k；（A）O(n 2log2n)（B） O(n2log5n)（C） O(n2log5n)（D）O(n 3)2 利用栈求表达式的值时，设立运算数栈 OPND。假设 OPND 只有两个存储单元，在下列表达式中，不发生
2、溢出的是( )。（A）A-B*(C-D)（B） (A-B)*C-D（C） (A-B*C)-D（D）(A-B)*(C-D)3 输入受限的双端队列是指元素只能从队列的一端输入，但可从队列的两端输出。若有 8，1，4，2 依次进入输入受限的双端队列，则得不到的输出序列是( )。（A）2814（B） 1482（C） 4218（D）21484 一个具有 1025 个结点的二叉树的高度为( )。（A）11（B） 10（C） 11 至 1025 之间（D）10 至 1024 之间5 以下关于二叉排序树的说法正确的是( )。在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小每个结点的关键字都
3、比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树在二叉排序树中，新插入的关键字总是处于最底层在二叉排序树中，新结点总是作为叶子结点来插入的二叉排序树的查找效率和二叉排序树的高度有关（A）、（B） 、III 、（C） 、（D）、6 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为 A1n，1n，且压缩存储在 B1k，则 k 的值至少为( )。（A）n(n+1) 2（B） n22（C） (n-1)(n+1)2（D）n(n-1)27 若无向图 G=(V，E)中含 8 个顶点，为保证图 G 在任何情况下都是连通的，则需要的边数最少是( ) 。
4、（A）7（B） 21（C） 22（D）288 用递归算法实现 n 个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( ) 。（A）n（B） n2（C） log2n（D）log 2n+19 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。（A）一定都是同义词（B）一定都不是同义词（C）不一定都是同义词（D）都相同10 如果将中国人按照生日(不考虑年份，只考虑月、E1)来排序，那么使用下列排序算法中最快的是( ) 。（A）归并排序（B）希尔排序（C）快速排序（D）基数排序11 用某种排序方法对线性表(2
5、5，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：(1)25，84， 21，47，15，27，68，35，20(2)20，15， 21，25，47，27，68，35，84(3)15，20， 21，25，35，27，47，68，84(4)15，20， 21，25，27，35，47，68，84则采用的排序方法是( )。（A）选择排序（B）希尔排序（C）二路归并排序（D）快速排序12 若存储周期 100 ns，每次读出一个字节，则该存储器的数据传输率为 ( )。（A）3210 6bs（B） 8106bs（C） 80 Mb s（D）8010 6bs13 假定采用
6、IEEE754 单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（A）(+1125) 10210（B） (+1125) 10211（C） (+0125) 10211（D）(+0125) 1021014 字长相同的两种浮点数，第一种阶码位数多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是 2，则有( )。（A）它们表示的数的范围与精度相同（B）第一种数的范围大，精度低（C）第二种数的范围大，精度高（D）第一种数的范围大，精度高15 以下关于校验码的叙述中，正确的是( )。校验码的码距必须大于 2校验码的码距越大检错纠错能力越强增加奇偶校验位的位数可以提高奇偶校验的
7、正确性采用奇偶校验可检测出一位数据错误的位置并加以纠正采用海明校验可检测出一位数据错误的位置并加以纠正循环冗余校验码是通过除法运算来建立数据和校验位之间的约定关系的（A）、（B） 、（C） 、（D）、16 若内存地址区间为 4000H43FFH，每个存贮单元可存储 16 位二进制数，该内存区域用 4 片存储器芯片构成，则构成该内存所用的存储器芯片的容量是( )。（A）51216bit（B） 2568bit（C） 25616bit（D）10248bit17 数据寻址和指令寻址的不同点在于( )。（A）前者决定操作数地址，后者决定程序转移地址（B）前者决定程序转移地址，后者决定操作数地址（C）前者
8、是短指令，后者是长指令（D）前者是长指令，后者是短指令18 流水计算机中，下列语句发生的数据相关类型是( )。ADD R1，R2，R3 ；(R2)+(R3)R1ADD R4，R1，R5 ；(R1)+(R5)R4（A）写后读（B）读后写（C）写后写（D）读后读19 下列有关控制器的说法正确的是( )。（A）无论是组合逻辑控制器和时序逻辑控制器，都需要有程序计数器（B）微程序控制器不需要程序计数器，只要有微程序计数器（C）都可以不需要程序计数器（D）以上都不对20 下面是关于目前流行的 PC 机主板的叙述：主板上通常包含微处理器插座(或插槽)和芯片组主板上通常包含 ROM BIOS 和存储器(内存
9、条)插座主板上通常包含 PCI 和 AGP 总线插槽主板上通常包含 IDE 连接器其中正确的是( ) 。（A）仅（B）仅 和（C）仅 、和（D）、和21 采用页式内存管理某虚拟存储器，使用 LRU 页面替换算法，假定内存容量为 4个页面，且开始时是空的，考虑下面的页面访问地址流(每次访问在一个时间单位内完成)为 1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7，则页面命中次数是( ) 。（A）24（B） 14（C） 16（D）622 外部设备打印机适合于连接的通道是( )。（A）数组多路通道（B）字节多路通道（C）选择通道（D）任意一种通道23 用户程序在用户态下
10、使用陷入指令而引起的中断是( )。（A）故障中断（B）外部中断（C）不可屏蔽中断（D）访管中断24 下列所示关系中，不是信号量能实现的功能是( )。（A）进程同步（B）进程互斥（C）执行的前趋关系（D）进程的并发执行25 下面是一个并发进程的程序代码，正确的说法是( )。semaphore x1=x2=y=1；int c1=c2=0：cobeginprocedure P1 procedure P2P(x1)； P(x2)if(+c1=1)P(y)； if(+c2=1)P(y) ；V(x1)； V(x2) ；computer(A)； computer(B)；P(x1)； P(x2)；if(-c1
11、=0)V(y)； if(-c2=0)V(y)；V(x1)； V(x2) ；end endcoend（A）进程不会死锁，也不会饥饿（B）进程不会死锁，但是会饥饿（C）进程会死锁，但是不会饥饿（D）进程会死锁，也会饥饿26 在操作系统中，进程 A 与进程 B 共享变量 S1，进程 A 与进程 C 共享变量 S2，则进程 B 和进程 C 之间是( )。（A）必须互斥（B）必须同步（C）同步或互斥（D）无关系27 操作系统中为实现多道程序并发，对内存管理可以有多种方式，其中内存利用率最高的是( ) 。（A）静态分区管理（B）动态分区管理（C）分页管理（D）分段管理28 在一个请求页式的虚拟存储系统中，
12、每个页面的大小分为 4 096 字节。如下某个程序需要将数组赋值，假设，执行代码已经驻留内存，而数据页面尚未分配，数组按先行后列存放。请计算，其缺页中断次数是( )。int a10241024；int i，j；i=0：for(j=0；j1023 ；j+)aij=j；（A）2（B） 1（C） 1 024（D）51229 在页式存储管理系统中选择页面的大小，需要考虑的因素是( )。页面大的好处是页表较小页面小的好处是可以减少由内碎片引起的内存浪费通常，影响磁盘访问时间的主要因素不在于页面的大小，所以使用时可优先考虑较大的页面（A）和（B） 和（C） 和（D）和和30 操作系统中，采用了多种技术改善
13、磁盘输入输出的访问速度，下列不能提高磁盘访问速度的是( ) 。（A）加快盘片转速（B）运用磁臂调度算法（C）采用通道技术（D）添加磁盘缓冲31 有一个文件含有 10000 个文件块，若将其顺序结构存放，则对文件块顺序查找的平均时间为 5000 个。若按索引顺序文件的结构存放，每个索引为 100 个文件块，则顺序查找次数是( ) 。（A）500（B） 100（C） 50（D）1032 计算机系统中，不需要处理机干预，能够在内存中(包括映射的内存)快速搬运数据的控制器是( ) 。（A）通道控制器（B） DMA 控制器（C）中断控制器（D）时钟控制器33 在协议数据单元中，控制信息所不包括的内容是(
14、 )。（A）地划（B）查错码（C）数据（D）协议控制34 通过改变载波信号的相位值来表示数字信号 1、0 的方法是( )。（A）ASK（B） FSK（C） PSK（D）PPP35 假设一个 NAT 服务器其公网地址为 205567935，并且有如表 6-1 的表项，那么当一个 IP 地址为 1921683256 端口为 21 分组进入公网的时候，转换后的端口号和源 IP 地址是( )。（A）205567935：2056（B） 1921683256：2056（C） 205567935：1892（D）205567935：225636 IPv6 协议数据单元由一个固定头部和若干个扩展头部以及上层协议
15、提供的负载组成，其中用于标识松散源路由功能的扩展头是( )。（A）目标头部（B）路由选择头部（C）分段头部（D）安全封装负荷头部37 现有一个长度为 3000B 的 IP 数据报，其 IP 头部的长度为 20B，该 IP 数据报如在最大帧长度为 1518B 的以太网中进行传输，那么为了正确传输，最后一个 IP 数据分片的数据大小是( ) 。（A）20B（B） 30B（C） 40B（D）50B38 传输层用于标识不同的应用的是( )。（A）物理地址（B）端口号（C） IP 地划（D）逻辑地址39 如图 6-1 所示一台路由器连接 3 个以太网，假设主机 C 上要发送一个 IP 分组，使得主机 D
16、 和主机 E 都会接收它，而子网 3 和子网 4 上的主机都不会接收它，那么该 IP 分组的目标 IP 地址是( )。（A）255255255255（B） 13013020255（C） 127001（D）1301301925540 DNS 作为一种分布式系统，所基于的网络应用模式是( ) 。（A）CS 模式（B） BS 模式（C） P2P 模式（D）以上均不正确二、综合应用题41-47 小题，共 70 分。41 已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成?请简述原因。42 设有一个带头结点的循环单链表，其结点值均为正整数。
17、试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。(1)给出算法的基本设计思想；(2)根据设计思想，采用 C 或 C+或 JAVA 语言表述算法，关键之处给出注释。43 图 2-2 所示的 CPU 逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器 IM 最大容量为 16384 字(字长 18 位)，数据存储器 DM 最大容量是65536 字(字长 16 位) 。各寄存器均有“ 打入”(Rin)“送出”(Rout)控制命令，但图中未标出。 (1)指出下列寄存器的位数：程序计数器 PC，指令寄存器 IR，累加器 A
18、C0、AC 1，通用寄存器 R0R 3，指令存储器地址寄存器 IAR，指令存储器数据存储器 IDR，数据存储器地址寄存器 DAR，数据存储器数据寄存器 DDR。(2)设机器指令格式为加法指令可写为“ADD X(R i)”，其功能是(AC 0)+(Ri)+X)AC 1，其中(R i)+X)部分通过寻址方式指向数据存储器 DM。现取 Ri 为 R1。画出 ADD 指令的指令周期流程图，写明“数据通路“ 和相应的微操作控制信号。44 设某计算机有四级中断 A、B、C、D，其硬件排队优先级次序为ABC D。表 21 列出了执行每级中断服务程序所需的时间。如果以执行中断服务程序的时间作为确定中断优先级的
19、尺度，时间越短优先级越高。 (1)指出如何为各级中断服务程序设置屏蔽码； (2)如果 A、B 、C、D 分别在 6s、8s 、10s 、0s 时刻发出中断请求，画出 CPU 执行中断服务程序的序列； (3)基于上题，请计算上述四个中断服务程序的平均执行时间。45 某大学的阅览室共有 300 个座位，同学进入时必须先在管理处用学生证换取座位牌，若座位满了，同学就要在阅览室外等候。当有同学离开时，要到管理处用座位牌换回学生证。请画出流程图，试用一种类语言，利用信号量和 P、V 操作，描述同学进入和离开阅览室的过程。46 一个 32 位的计算机系统中，虚拟存储系统采用了物理地址扩展的三级分页方式，第
20、一级页表占用地址的最高 2 位，第二、三级页表依次占用 9 位地址，最低 12 位用于页内偏移量，如图 23 所示。一个进程的地址空间为 4 GB，每个页表项占用 8 个字节，请问：(1) 一个进程最多有多少个页面?(2)一级、二级以及三级页表各为多大? 一共占用多少存储空间?(3)为提高效率，一级页表和二级页表全部装入内存，三级页表只装入一页，若从OxC8000000 开始顺序映射三级页表、二级页表和一级页表，请计算列出上述三组页表在内存中的地址范围。47 图 24 是三个计算机局域网 A，B 和 C，分别包含 10 台，8 台和 5 台计算机，通过路由器互联，并通过该路由器接口 d 联入因
21、特网。路由器各端口名分别为a、b、c 和 d(假设端口 d 接入 IP 地址为 61602180 的互联网地址)。LAN A和 LAN B 共用一个 C 类 IP 地址(网络地址为 20238600)，并将此 IP 地址中主机地址的高两位作为子网编号。A 网的子网编号为 01，B 网的子网编号为 10。主机号的低 6 位作为子网中的主机编号。C 网的 IP 网络号为 202366 10。请回答如下问题： (1)为每个网络中的计算机和路由器的端口分配 IP 地址； (2)写出三个网段的子网掩码；(3)列出路由器的路由表；(4)IAN B 上的一台主机要向 B 网段广播一个分组，请填写此分组的目的
22、地址；(5)LAN B 上的一台主机要向 C 网段广播一个分组，请填写此分组的目的地址。计算机专业（基础综合）模拟试卷 60 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 基本运算语句是 k=5*k，设其执行时间为 T(n)。对于 j 每循环一次，该语句的执行次数为 m，有：5 mn，即 mlog5n。所以：2 【正确答案】 B【试题解析】 利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及进行后缀表达式求值这两步操作可以一起进行，需要设立运算符栈 OPTR 和运算数栈oPN
23、D 两个栈。例如求选项 A 的表达式 AB*(CD)的过程如表 65 所列：按照上述过程可知，选项 A 求值时，运算数栈 OPND 的大小至少为 4。例如求选项 B 的表达式(AB)*CD 的过程如表 66 所列：按照上述过程可知，选项 B 求值时，运算数栈 OPND 的大小至少为 2。 类似地，选项 C、D 求值时，运算数栈 OPND 的大小分别至少为 3、3。因此本题答案为B。3 【正确答案】 D【试题解析】 设 e1 端可输人可输出， e2 端仅能输出；且设某元素 x 从 e1 端进队为 xe1 进 进，从 e1 端出队为 xe1 出 ，从 e2 端出队为 xe2 出 ；，则各选项出队情
24、况如下表 67 所列。4 【正确答案】 C【试题解析】 一棵二叉树每层只有 1 个结点，则具有 1 025 个结点的二叉树的最大高度为 1 025。一个具有 1 025 个结点的完全二叉树的高度为 11。这一个具有 1 025 个结点的二叉树的高 h 为 11 至 1 025 之间。5 【正确答案】 D【试题解析】 对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字，右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于每一棵特定的二叉排序树，均可按照平均查找
25、长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和 log2n 成正比。6 【正确答案】 D【试题解析】 简单无向图的邻接矩阵是对称的，且对角线元素均是 0，故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式)： k=(n-1)+(n-2)+1+0=n2-(1+2+n)=n(n-1)2。7 【正确答案】 C【试题解析】 本题考查图的基本概念。 要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G
26、始终保持连通。首先需要图 G 的任意 7 个结点构成完全连通子图 G1，需 n(n-1)2=7(7-1)2=21 条边，然后再添加一条边将第 8 个结点与 G1 连接起来，共需 22 条边。 本题非常容易错误地选择选项 A，主要原因是对“保证图 G 在任何情况下都是连通的”的理解，分析选项 A，在图 G 中，具有 8个顶点 7 条边并不能保证其一定是连通图，即有 n-1 条边的图不一定是连通图。 分析选项 D，图 G 有 8 个顶点 28 条边，那么图 G 一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。8 【正确答案】 D【试题解析】 根据折
27、半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。 第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n4；依次类推，当所确定的查找区间中的元素为 0 时，递归调用该算法的次数为log 2n+1 次，查找结束。 折半查找法在查找成功时和给定值进行比较的关键字个数至多是log 2n+1；在查找不成功时和给定值进行比较的关键字个数最多也不
28、超过log 2n+1。9 【正确答案】 C【试题解析】 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。10 【正确答案】 D【试题解析】 按照所有中国人的生日(月、日)排序，一方面待排序记录个数 n 是非常大的，另一方面关键字所含的排序码为 2，且一个排序码基数为 12，另一个为31，都是较小的常数值，采用基数排序可以在 O(n)内完成排序过程。11 【正确答案】 D【试题解析】 本题主要考查各种排序的手工排序过程。选择排序在每趟结束后可以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递
29、增，直到最后的一个有序的完整序列；希尔排序也是形成部分有序的序列；快速排序以某个元素为界将大于它和小于它的关键字划分为两个子序列，再将该元素放在中间。观察题中的元素排序过程，可知是快速排序。12 【正确答案】 D【试题解析】 由于存储周期 100ns，每次读出一个字节，则数据传输率=8 (10010-9)= 80106 位秒。选项 C 的错误在于存在误差，1 M=10241024 。13 【正确答案】 B【试题解析】 45100000H=0100 0101 0001 0000 0000 0000 0000 0000，符号位=0，阶码=10001010，尾数=001000000000000000
30、00000。阶码真值=10001010-1111111=1011B=11。因为隐含了尾数最高数位，尾数为 1001，所以其真值为(+1125) 10211。14 【正确答案】 B【试题解析】 字长相同的两种浮点数，阶码位数较多表示的数范围越大，尾数越多表示的精度越高。15 【正确答案】 D【试题解析】 码距大于等于 2 的数据校验码，开始具有检错的能力。码距越大，检、纠错能力就越强；奇偶校验码的码距等于 2，可以检测出一位错误(或奇数位错误)，但不能确定出错的位置，也不能检测出偶数位错误；海明码的码距大于2，不仅可以发现错误，还能指出错误的位置，为自动纠错提供了依据；循环冗余校验码则通过除法运
31、算来建立数据和校验位之间的约定关系。16 【正确答案】 C【试题解析】 43FF-4000+1=400，即内存区域为 1K 个单元，总容量为 1K1 6。现有 4 片存储芯片构成，则芯片容量为 25616bit。17 【正确答案】 A【试题解析】 数据寻址寻找的是操作数的地址，指令寻址寻找的是下条指令的地址，它决定于程序转移地址。18 【正确答案】 A【试题解析】 数据相关包括写后读相关(RAW)、写后写相关(WAW)、读后写相关(WAR)。在这两条指令中，都对 R1 进行操作，其中前面对 R1 写操作，后面对R1 读操作，因此发生写后读相关。19 【正确答案】 A【试题解析】 无论控制器的硬
32、件实现方法有何不同，都需要程序计数器。对于微程序控制器可能同时还有微程序计数器，这两者并不矛盾。20 【正确答案】 D【试题解析】 关于 PC 机主板的四个描述都是正确的。21 【正确答案】 B【试题解析】 LRU 算法是堆栈型算法，按照页面访问地址流可以容易地得到命中次数，如表 68 所列。共命中 14 次。22 【正确答案】 B【试题解析】 打印设备属于低速设备，它适合于连接到字节多路通道上，一个字节多路通道上连接多台相同或不相同的低速设备，当通道为一个设备传送完一个字节后，就转去为另一个设备服务。23 【正确答案】 D【试题解析】 本题考查用户态和内核态及其转换的概念。在操作系统管理下的
33、计算机中，为保护系统的安全，对一部分处理机的指令限定使用对象，即只有操作系统才可以执行。而当用户需要使用这些特权指令时，必须调用特定的访管指令，也称陷入指令，顾名思义由用户态陷入到内核态，从而从用户态转入内核态，继而可以执行特权指令；访管指令引起的中断称为访管中断，它是用户使用特权指令的唯一人口。24 【正确答案】 D【试题解析】 本题考查信号量的功能，在多道程序技术系统中，信号量机制是一种有效的实现进程同步与互斥的工具。信号量可以实现的功能有：进程的同步与互斥，进程执行的前趋关系，进程执行的前趋关系实质上是指进程的同步关系。除此以外，只有进程的并发执行不需要信号量来控制，因此正确答案为 D。
34、25 【正确答案】 B【试题解析】 本题考查 PV 操作与死锁以及饥饿的关系。仔细考察程序代码，我们似曾相识，可以看出是一个扩展的“单行线”的问题。也就是说，某单行线只允许单方向的车辆通过，在单行线的人口设置信号量 y，在告示牌上显示某一时刻各方向来车的数量 c1 和 c2，要修改告示牌上的车辆数量必须互斥进行，为此设置信号量 x1 和 x2。若某方向的车辆需要通过时，首先要将该方向来车数量 c1 或 c2 增加1，并查看自己是否是第一个进入单行线的车辆，若是，则获取单行线的信号量y，进入单行线。通过此路段以后出单行线时，将该方向的车辆数 c1 或 c2 减 1(当然是利用 x1 或 x2 来
35、互斥修改)，并察看自己是否是最后一辆车，若是，则释放单行线的互斥量 y，否则，保留信号量 y，让后继车辆继续通过。双方的操作如出一辙。考虑出现一个极端情况，即当某方向的车辆首先占据单行线并后来者络绎不绝时，另一个方向的车辆就再没有机会通过该单行线了。从而造成饥饿。由于有信号量的控制，死锁的可能性没有了(即双方同时进入单行线，在中间相遇，造成双方均无法通过的情景)。26 【正确答案】 D【试题解析】 进程同步和进程互斥是指多个相关进程在执行次序上的协调，保证对共享变量操作的正确性。这些进程会互相竞争以及相互合作，在一些关键时刻点上可能需要前后顺序操作。这种顺序操作必须有一个共同的操作对象，例如共
36、享变量等，当不同的进程对该共享变量进行读写时，则必须互斥；只要双方任何一方是只读的，则不存在互斥关系。若二个进程互相之间无任何共享变量的话，就不存在同步或互斥关系，本题中，进程 A 与进程 B 有关系，进程 A 与进程 C 有关系，进程 B 与进程 C 并不存在递延关系。27 【正确答案】 C【试题解析】 本题考查实现各种多道程序的存储管理的方法。为实现多道程序并发，系统必须将多个程序调人内存，让多个进程竞争 CPU 和外设，使得计算机能高效地运转。多个程序调人内存会存在越界，溢出等多种问题。为解决这些问题，存储管理采用了分区法、分页法、分段法和段页式等多种技术。静态分区方法平均对内存的利用率
37、是分区大小的 50，利用率较低。动态分区在经过多次分配和回收以后会出现大量的外碎片(外零头)，这些外碎片很难利用，需要经过内存紧缩来合并，综合起来能比静态分区的利用率稍高。分段技术与动态分区技术类似，内存利用率较动态分区低，因为其进程分段数量大于单个进程的数量，外碎片会增加。分页技术的内存利用率最高，每个进程只在最后一页有 50概率的浪费，页面大小比分区大小要小得多，因此，被浪费的内存数量最少，从而内存的利用率最高。当然，分页需要额外增加页表，分段需要增加段表，会增加系统开销，但是对内存的利用率来讲却是最高的。28 【正确答案】 D【试题解析】 本题考查 C 语言程序在使用内存时的分配机制。采
38、用请求页式虚拟存储管理的基本点是按需分配内存，仅当使用到该页时才通过缺页中断分配内存。C 语言对数组的存放是先行后列的，整型数组每个占用 2 个字节，据此，我们可以计算，4096 字节可以存放 2 行数组，由于程序中并非按行赋值，而是按列赋值，所以一页只赋值 2 个数组(是跳跃地赋值)，若每申请一页产生 1 次缺页中断，那么总共要产生 10242=512 次缺页中断。29 【正确答案】 C【试题解析】 在确定地址结构时，若选择的页面较小，一方面可使内碎片减小，从而减少了内碎片的总空间、有利于提高内存利用。但另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外，还会降低页
39、面换进换出的效率。若选择的页面较大，虽然可减少页表长度，提高换进换出效率，但却又会使内碎片增大。因此。页面的大小应选得适中，通常页面的大小是 2 的幂，即在512B 4096B 之间。页面大小与磁盘调度的关系不大，磁盘调度与扇区有关。故正确答案为 C。30 【正确答案】 C【试题解析】 本题考查对磁盘电气结构的理解。磁盘访问时间是由磁盘片旋转延时、寻道延时、处理延时和数据内部传输延时组成。加快盘片转速可以减少旋转延时，运用磁臂调度算法可以降低寻道时间，添加缓冲区可以降低内部传输延时(例如串并转换，预读写等)，而通道技术是与计算机接口总线和内存速度有关，与磁盘的性能无关。31 【正确答案】 B【
40、试题解析】 本题考查的是文件的逻辑结构。顺序文件在按顺序查找文件内容时，必须按顺序一个一个去读取，最快在第一个就读取到，最慢一直读到最后一个文件块，所以平均为一半，计算结果是 100002=5000。(若采用二分法不会有这么多次)。当采用索引顺序文件时，文件的内容已经按照索引的关键词排好了序(例如按字母顺序等)。并建立了索引表，索引表一般将一定数量的文件块组织成一组，本题中以 100 个一组，所以分成 10 000100=100 组，按顺序查找法，查找这 100 组平均需要 1002=50 次，找到以后在组内继续查找，平均需要 1002=50 次，所以共需要 50+50=100 次。32 【正
41、确答案】 B【试题解析】 本题考查 IO 设备中各种控制器的特点。通道控制器主要用于外设与内存的数据搬运，不需要处理机干预；DMA 控制器用于内存到内存 (包括将外设的存储器映射到内存空间的部分，例如显存空间)的快速数据搬运，且不需要处理机干预；中断控制器用于接收中断信号，对中断信号进行优先级别排列并产生中断码(中断号 )等工作，时钟控制器管理计算机系统的所有时序和定时器，与数据搬运无关。33 【正确答案】 C【试题解析】 本题考查协议的基本概念，为保证网络中的计算机之间有条不紊的进行数据交换，合理的共享资源，各独立的计算机系统必须严格的遵循事先约定好的一套套的通信规程，包括严格规定要交换的数
42、据形式。控制信息的格式和控制功能，以及通信过程中事件执行的次序等，这里地址、查错码和协议控制都是控制信息必须包括的，但具体的数据是由上层协议所决定，因此答案是 C。34 【正确答案】 C【试题解析】 本题考查数字调制的基本概念，使用某个频率的正弦载波，使其的振幅、频率或相位随着数字信号的变化而变化，称为调制；相反的过程称为解调；数字调制具有三种基本形式即移幅键控法 ASK、移频键控法 FSK 和移相键控法PSK 。在 ASK 方式下，用载波的两种不同幅度来表示二进制的两种状态。在FSK 方式下，用载波频率附近的两种不同频率来表示二进制的两种状态。在 PSK方式下，用载波信号相位移动来表示数据。
43、因此答案为 C。35 【正确答案】 A【试题解析】 本题考查地址转换技术 NAT 的工作原理，NAT 协议利用端口域来解决内网到外网的地址映射问题。任何时候当一个向外发送的分组进入到 NAT 服务器的时候，源地址被真实的公网地址所取代，而端口域被转换为一个索引值(21被转换成 2056)。因此答案是 A。36 【正确答案】 B【试题解析】 本题考查 IPv6 地址的基本概念，IPv6 首部的固定部分被简称为IPv6 首部，其大小是 40 字节，而 IPv4 首部中的必要部分为 20 字节。IPv6 已经定义了以下扩展首部：逐跳选项首部(H0p-by-Hop Options header)：定义
44、需要逐跳处理的特殊选项；路由首部(Routing header) ：提供扩展路由，类似于 IPv4 的源路由；片段首部(Fragment header)：包含分片和重组信息；认证首部(Authentication header)：提供数据完整性和认证；封装安全负载首部(Encapsulation Security Payload header)：提供秘密性；目标选项首部(Destination Options header)：包含要在目标节点检查的可选信息。因此答案是 B。37 【正确答案】 C【试题解析】 分片目的：当到来的数据报长度超过其输出线路所属网络的 MTU时，路由器将数据报分成许多
45、较小的片段。每个片段被封装成数据报，独立传输。封装片段使用的报头取自原始数据报的报头。分片原理：路由器利用 MTU 和报头长度计算每一报片允许包含的最大数据字节数(必须是 8 字节的整倍数)，并对原始数据报的数据部分进行分片。在每个报片前使用原始报头的拷贝，修改原始头部中的某些字段，如总长度、标志位、片偏移(以字节为单位的偏移量除以 8)等，重新计算头校验，然后发送。当一个片段到达一个具有更小 MTU 的网络时，需要进一步分片，所有分片都在目的主机重组，中间路由器不做重组的工作。分片重组：将到来的报片重新组装一个完整数据报的过程称为重组，重组是在目的主机中进行的。目的主机使用源地址和分组标识来
46、确定属于同一个数据报的片段，根据 MF 标志判断是否最后一个报片已经到达。当MF=0 的报片到达时，根据该报片的片偏移字段和总长度字段可以计算出原始数据报的总长度。当所有报片都已到达时，按照各报片在原始数据报中的偏移量进行组装。本题考查 IP 分片的原理和应用，这里以太网帧头为 18B，IP 头为 20B，因此最大数据载荷是 1 480B，3 020B 的 IP 数据的数据部分是 3 020-20=3 000B，因此必须进行分片，3000=1480+1480+40 共 3 片，最后一片的数据部分是 40B，因此答案是 C。38 【正确答案】 B【试题解析】 本题考查端口号的作用，端口号是传输层
47、的服务访问点，让应用层的应用进程通过端口来交付数据给传输层，是标志应用层的进程，因此答案是 B。39 【正确答案】 A【试题解析】 本题考查路由器的功能和 IPv4 地址的特点，主机 D 属于子网130130190，主机 E 属于 130130200，分别属于不同的网络，可以同时接收的 IP 分组必定是广播报文，题目又要求该广播报文不能转发到子网 3，和子网 4，则这个广播报文必定是有限广播地址 255255255255，路由器可以割断广播报，因此答案是 A。40 【正确答案】 A【试题解析】 本题考查网络应用模型，DNS 作为分布式应用，是一种典型的CS 模式。B S 模式又称 BS 结构，
48、是随着 Internet 技术的兴起，对 CS 模式应用的扩展。因此答案为 A。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 可以。原因：后序遍历的顺序是“左子树-右子树- 根结点” 。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。if(p!=NULL)while(p-ichild!=NULLP- rchild!=NULL)while(p-Ichild!=NULL)P：P- ichild ；if(p-rchild!=NULL)P=P-rchild；return(p)； 返回后序序列第一个结点的指针42 【正确答案】 用 C 语言算法描述如下：void delall(LinkList&L)LNode*p，*pre，*minp，*minpre；while(L- next!=L) 循环单链表不空时循环p=L-next：pre=L；minp=p；minpre=pre；while(p!=L) 从头开始查找最小值的结点if(p-dataminp-data)
