1、计算机专业（基础综合）模拟试卷 59 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在具有 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是( )。（A）访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)（B）在第 i 个结点后插入一个新结点(1in)（C）删除第 i 个结点(1in)（D）将 n 个结点从大到小排序2 使用双链表存储线性表，其优点是( )。提高查找速度更方便数据的插入和删除节约存储空间很快回收存储空间（A）、（B） 、（C）仅 （D）、3 若进栈序列为 a，b，c
2、 ，则通过出栈操作可能得到 a，b，c 的不同排列个数为( )。（A）4（B） 5（C） 6（D）74 若对 n 阶对称矩阵 A1n，1n在以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组 B1n(n+1)2 中，则在 B中确定 aij(ij)的位置 k 的关系是( )。（A）i(i-1)2+j（B） j(j-1)2+i（C） i(i+1)2+j（D）j(j+1)2+i5 在线索化二叉树中，t 所指结点没有左子树的充要条件是 ( )。（A）t- left=NULL（B） t-ltag=1（C） t-ltag=1 且 t-left=NULL（D）以上都不对6 若采
3、用邻接矩阵来存储简单有向图，则其某一个顶点 i 的人度等于该矩阵( )。（A）第 i 行中值为 1 的元素个数（B）所有值为 1 的元素个数（C）第 i 行及第 i 列中值为 1 的元素总个数（D）第 i 列中值为 1 的元素个数7 在有 11 个元素的有序表 A111中进行折半查找，查找元素 A11时，被比较的元素的下标依次是( )。（A）6，8，10，11（B） 6，9，10，11（C） 6，7，9，11（D）6，8，9，118 设散列表的表长 m=14，散列函数 H(k)=k MOD 11，表中已有 15，38，61，84四个元素，如果用线性探测法处理冲突，则元素 49 的存储地址是(
4、)。（A）8（B） 3（C） 5（D）99 以下关于查找方法的说法正确的是( )。顺序查找法只能在顺序存储结构上进行折半查找法可以在有序的双向链表上进行分块查找的效率与线性表被分为多少块有关（A）、（B） 、（C） 、（D）只有10 下述排序方法中，比较次数与待排序记录的初始状态无关的是( )。（A）插入排序和快速排序（B）归并排序和快速排序（C）选择排序和归并排序（D）插入排序和归并排序11 堆排序、快速排序、归并排序就排序算法所用的辅助空间而言，从小到大的关系是( )。（A）堆排序、快速排序、归并排序（B）堆排序、归并排序、快速排序（C）快速排序、归并排序、堆排序（D）归并排序、快速排序、
5、堆排序12 某计算机的时钟频率为 400MHz，测试该计算机的程序使用 4 种类型的指令。每种指令的数量及所需指令时钟数(CPI)如表 7-1 所列，则该计算机的运算速度是( )。（A）106.7（B） 169.5（C） 207.3（D）216.213 在补码表示的机器中，若寄存器 A 中原存的数为 9EH，现存的数为 CFH，则表明执行的一条指令是( )。（A）算术左移（B）逻辑左移（C）算术右移（D）逻辑右移14 计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若 x 的阶码大于 y的阶码，则应将( ) 。（A）x 的阶码缩小至与 y 的阶码相同，且使 x 的尾数部分进行算术左移（B
6、） x 的阶码缩小至与 y 的阶码相同，且使 x 的尾数部分进行算术右移（C） y 的阶码扩大至与 x 的阶码相同，且使 y 的尾数部分进行算术左移（D）y 的阶码扩大至与 x 的阶码相同，且使 y 的尾数部分进行算术右移15 在 4 位有效信息上增加 3 位校验位后得到码长 7 位的海明校验码，它的检、纠错能力是( )。（A）纠一位错或检两位错（B）纠一位错且检两位错（C）只有检错能力，没有纠错能力（D）只有纠错能力，没有检错能力16 某 32 位计算机的 Cache 容量为 16KB，Cache 块的大小为 16B，若主存与Cache 地址映像采用直接映像方式，则主存地址为 0x1234E
7、8F8 的单元装入 Cache的地址是( )。（A）1.0001e+010（B） 1.0001e+012（C） 1.01e+013（D）1.101e+01317 假设变址寄存器 R 的内容为 1000 H，指令中的形式地址为 2000 H；地划 1000 H 中的内容为 2000H，地址 2000H 中的内容为 3000H，地址：3000H 的内容为4000H，则变址寻址方式下访问到的操作数是( )。（A）1000H（B） 2000H（C） 3000H（D）4000H18 以下叙述中，描述正确的是( )。同一 CPU 周期中，可以并行执行的微操作称为兼容性微操作同一 CPU 周期中，不可以并行
8、执行的微操作称为兼容性微操作 同一 CPU 周期中，允许并行执行的微操作称为互斥性微操作同一 CPU 周期中，不允许并行执行的微操作称为互斥性微操作（A）和（B） 和（C） 和（D）和19 下列关于主存储器的描述中，正确的是( )。CPU 访存时间由存储器容量决定ROM 和 RAM 在存储器中是统一编址的ROM 中任意一个单元可以随机访问DRAM 是破坏性读出，因此需要读后重写（A）和（B） 和（C） 和（D）、和20 某数组多路通道最大数据传输率为 1MBs，它有 10 个子通道，则每个子通道的数据传输率为( ) 。（A）100KBs（B） 1MBs（C）介于 A、B 之间（D）小于 100
9、KBs21 若视频图像每帧的数据量为 64MB，帧速率为 30 帧秒，则显示 10 秒的视频信息，其原始数据量是( )。（A）64MB（B） 192MB（C） 640MB（D）1 920MB22 131 的 1 字节、2 字节补码分别是( )。（A）83H，0083H（B） 7DH，FF83H（C）溢出，FF83H（D）溢出，FF7DH23 在操作系统中引入并发可以提高系统效率。若有三个进程 P1、P2 和 P3，按照P1、P2 到 P3 的优先次序运行，采用可抢先式调度，其运行过程如下：P1：计算 6 ms；I O 8 ms；计算 2 ms；P2：计算 12 ms；I O 6 ms；计算 2
10、 ms；P3：计算 4 ms；I O 8 ms；计算 4 ms；不计系统开销，相比单通道顺序运行，多道并发市以节省的时间和 CPU 利用率分别是( )。（A）14 ms；79（B） 16 ms； 83（C） 12 ms； 75（D）22 ms；10024 假设当前计算机并发系统中有一个用户进程，它的工作流程如表 72 所列，再假设系统只有三个基本状态，用户进程具有最高优先级，采用不可抢先时间片轮转调度算法，时间片为 20 ms，其他进程不用磁盘及其他 IO 设备。则该进程运行完成所需时间是( ) 。（A）85ms（B） 140ms（C） 105ms（D）110ms25 下列不是进程调度器被激活
11、的可能时机是( )。（A）时钟中断（B）进程创建完毕（C）处理机空闲（D）程序出错26 下列可能引起 Belady 异常的页面置换算法是( )。（A）LRU（B） Clock（C） LFU（D）FIFO27 某个计算机采用动态分区来分配内存，经过一段时间的运行，现在在内存中依地址从小到大存在 100 KB、450 KB、250 KB、200 KB 和 600 KB 的空闲分区。分配指针现指地址起始点，继续运行还会有 212 KB、417 KB 、112 KB 和 426 KB 的进程申请使用内存，那么，对内存充分利用的分配算法是( )。（A）最先适应算法（B）下次适应算法（C）最佳适应算法（D
12、）最坏适应算法28 在一个采用虚拟存储管理的系统中，计算机的数据位和地址位宽均为 32 位，假设当前系统中存在 10 个进程，主存的容量是 2 GB，辅存的容量为 500 GB，在这样的系统中，所有进程虚存的总空间大小是( )。（A）4 GB（B） 40 GB（C） 2 GB（D）502 GB29 下列文件物理结构中，不适合随机访问且不易于文件扩展的是( )。（A）连续结构（B）索引结构（C）链接结构（D）多级索引结构30 在下列叙述中，正确的是( )。（A）在磁带上的顺序文件中插入新纪录时，必须复制整个文件（B）由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济（C）在磁带上的顺序文件末尾插
13、入新纪录时，不必复制整个文件（D）由于磁带不利于随机存储，故用磁带来作为备份的介质是不合适的31 操作系统为了管理文件，设计了文件控制块(FCB)，文件控制块的建立是( ) 。（A）在调用 create()时（B）在调用 open()时（C）在调用 read()时（D）在调用 write()时32 UNIX 系统中，输入输出设备看作是( ) 。（A）普通文件（B）目录文件（C）索引文件（D）特殊文件33 关于 OSI 参考模型和 TCPIP 模型在传输层提供的服务，正确的说法是( )。（A）OSI 模型在传输层提供面向连接服务（B） TCPIP 模型在传输层仅提供面向连接服务（C） OSI 模
14、型在传输层均可提供无连接和面向连接服务（D）TCP IP 模型在传输层仅提供面向无连接服务34 某信道的信号传输速率为 2 000 波特，若想令其数据传输速率达到 8Kbps，则一个信号码元所取的有效离散值个数至少是( )。（A）2（B） 4（C） 8（D）1635 一个广域网信道的比特率是 4Kbps，传播延迟为 20 毫秒，若确保停等协议至少 50的效率，那么帧的大小至少是( )。（A）大于 160 bit（B）大于 150 bit（C）大于 140 bit（D）大于 130 bit36 在 Internet 上有许多协议，下面的选项中能够正确表示协议层次关系的是( ) 。37 如果子网
15、172632020 再划分为 172632026，则下面的结论中正确的是( )。（A）划分为 1024 个子网（B）每个子网有 64 台主机（C）每个子网有 62 台主机（D）划分为 2044 个子网38 对地址转换协议(ARP)描述正确的是( )。（A）ARP 封装在 IP 数据报的数据部分（B） ARP 是采用广播方式发送的（C） ARP 是用于 IP 地址到域名的转换（D）发送 ARP 包需要知道对方的 MAC 地址39 下列关于 TCP 和 UDP 的说法正确的是( )。（A）两者都是面向无连接的（B）两者都是面向连接的（C） TCP 是面向连接而 UDP 是面向无连接的（D）TCP
16、无连接而 UDP 是面向连接的40 当一台计算机从 FTP 服务器下载文件时，在该 FTP 服务器上对数据进行封装的五个转换步骤是( ) 。（A）比特，数据帧，数据包，数据段，数据（B）数据，数据段，数据包，数据帧，比特（C）数据包，数据段，数据，比特，数据帧（D）数据段，数据包，数据帧，比特，数据二、综合应用题41-47 小题，共 70 分。41 现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2 ，en)；i=1：while(所剩边数= 顶点数 )从图中删去 ei；若图不再连通，则恢复 ei；i=i+1；请问上述方法能否求得原图的最小生成树?若该
17、方法可行，请证明之；否则请举例说明。42 设有带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。设计在时间和空间上都尽可能高效的算法，将 L 改造成 L=(a1，a 3，a n，a 4，a 2)。要求： (1)给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。43 设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，设当前指令的地址码部分为 001AH，正在执行的指令所在地址为 1 F05 H，变址寄存器中的内容为23A0H。 (1)当执行取数指令时，如为变
18、址寻址方式，则取出的数为多少? (2)如为间接寻址，取出的数为多少? (3) 当执行转移指令时，转移地址为多少? 已知存储器的部分地址及相应内容，见表 62。44 四位运算器框图如图 62 所示，ALU 为算术逻辑单元，A 和 B 为三选一多路开关，预先已通过多路开关 A 的 SW 门向寄存器 R1，R2 送入数据如下：R1=0101，R2=1010。寄存器 BR 输出端接四个发光二极管进行显示。其运算过程依次如下： (1)R1(A)+R2(B)BR(显示结果 1010)； (2)R2(A)+R1(B)BR(显示结果 1111)； (3)R1(A)+R1(B)BR(显示结果 1010)； (4
19、)R2(A)+R2(B)BR(显示结果 1111)； (5)R2(A)+BR(B)BR(显示结果 1111)； (6)R1(A)+BR(B)BR(显示结果 1010)。 试分析运算器的故障位置与故障性质(“1”故障还是“0” 故障)，说明理由。45 考虑有三个吸烟者进程和一个经销商进程的系统中，每个吸烟者连续不断地制作烟卷并将其做好的烟卷消费掉(即吸烟)。制烟和吸烟过程需要烟草、烟纸和火柴三种原料。这三个吸烟者自己分别掌握有烟草、烟纸和火柴中的一种。经销商能源源不断地提供上述三种原料，每次经销商会提供上述三种原料中的任意两种，当某个吸烟者发现经销商提供的原料恰好是自己所需的时候，该吸烟者会取走
20、那两种原料，与他自己拥有的原料一起，开始制烟和吸烟。经销商发现原料被取走了就会继续提供任意两种原料，如此反复。试设计一个使经销商和吸烟者同步的算法，并用C 语言编写程序。46 某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下表 63 所列，所有的数字均为十进制，每一项的起始编号是 0，并且所有的地址均按字节计址，每页的大小为 1 024 字节。(1)将下列逻辑地址转换为物理地址，并说明理由。 0793，1197，2099，3320，41 88，5332 (2)假设程序要访问第 2 页，页面置换算法为改进的 Clock 算法，请问该淘汰哪页?页表如何修改? 上述
21、地址的转换结果是否改变?变成多少 ?47 如果表 64 所列是路由器 R1 的路由表，仔细分析各个表项的特点，并回答如下问题。 (1)给出 m0 和 m1 所在的网络号，以及可连接的最大主机数目。 (2)给出接口 m0，m1 和 m2 的合理的 IP 地址(注要求取最小的地址)。 (3)试给出网络的拓扑。计算机专业（基础综合）模拟试卷 59 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A【试题解析】 顺序表是随机存取结构，选项 A 中实质是查找第 i 个结点和第 i-1 个结点，因此时间复杂度
22、为 O(1)；选项 B 和 C 插入和删除都需要移动元素，时间复杂度为 O(n)；选项 D 是排序问题，时间复杂度是 O(n)O(n 2)。2 【正确答案】 C【试题解析】 在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节省存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。3 【正确答案】 B【试题解析】 若进栈序列为 a，b，c，可以考虑所有进栈出栈情况，则可能得到a，b，c 的出栈序列是 abc，acb，bac，bca，cba。4 【正确答案】 B【试题解析】 将对称矩阵 A 中的
23、下三角的元素存放于 B 数组中，若求 aij(ij)的位置 k 的关系，答案为 A，即 i(i-1)2+j。但是，本题求 aii(ij)的位置 k 的关系，aij(ij)这个元素没被存放，也就是说需要找到与 aij(ij)这个元素相等的元素 aij，这就需要将备选答案 A 中 i(i-1)2+j 的 i 与 j 互换，因此正确答案为 B，即 j(j-1)2+i。5 【正确答案】 B【试题解析】 线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为 1。6 【正确答案】 D【试题解析】 由邻接矩阵的定义可知，对于无向图，其邻接矩阵的第 i 行的和即为第 i 个顶点
24、的度。对于有向图，邻接矩阵的第 i 行元素的和即为第 i 个顶点的出度，而邻接矩阵。7 【正确答案】 B【试题解析】 由折半查找过程可得，第一次(1+11)2=6 ，第二次(6+1)+11)2=9，第三次(9+1)+11)2=10，第四次 11。或者由下图 73 所示的折半查找的判定树可求得下标。8 【正确答案】 A【试题解析】 元素 15，38，6 1，84 分别存储在 4，5，6，7 单元，而元素 49 的散列地址为 5，发生冲突，向后探测 3 个单元，其存储地址为 8。9 【正确答案】 D【试题解析】 和的说法都是错误的，顺序查找法可以在顺序存储结构和链式存储结构上进行，而折半查找只能在
25、可以进行随机存取的存储结构上进行，即只能在顺序存储的有序表上进行。10 【正确答案】 C【试题解析】 选择排序在最好、最坏、平均情况下的时间性能均为 O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为 O(nlogn)。11 【正确答案】 A【试题解析】 本题主要考查各种排序的空间复杂度。堆排序只是需要在元素进行比较交换时需要常数个存储空间，它需要的辅助空间为 O(1)；快速排序在递归过程中需要栈结构来保存递归的信息，它需要的辅助空间为 O(log2n)；归并排序需要长度为元素个数的线性空间来保存归并的结果，它需要的辅助空间为 O(n)。12 【正确答案】 C【试题解析】 平均 CPI
26、=(1600001+300002+240004+1 60008)(1 60000+30000+24000+16000)193，4001932073MIPS。13 【正确答案】 C【试题解析】 寄存器 A 中原存内容 10011110，现存内容 11001111，说明执行了一条算术右移指令。14 【正确答案】 D【试题解析】 在浮点数加减运算时，首先要进行对阶，根据对阶的规则，阶码和尾数将进行相应的操作。15 【正确答案】 B【试题解析】 7 位海明码，在 4 位有效信息上增加 3 位校验位，则有 K=3，N=4，则满足 2K-1N+K+1。所以可以纠一位错且检两位错。16 【正确答案】 C【试
27、题解析】 因为 Cache 容量为 16 KB，所以 Cache 地址长 14 位。主存与Cache 地址映像采用直接映像方式，将 32 位的主存地址 0x1234E8F8 写成二进制，取低 14 位就是 Cache 地址。最低。17 【正确答案】 D【试题解析】 变址寻址方式下有效地址 EA=(R)+A=1000H+2000H=3000H，操作数 S=(3000H)=4000H。18 【正确答案】 D【试题解析】 兼容性微操作是指那些可以同时产生，共同完成某一任务的微操作，而互斥性微操作是指在机器中不允许同时出现的微操作。19 【正确答案】 B【试题解析】 CPU 的访存时间与存储容量无关；
28、不是所有的 DRAM 都是破坏性读出，4 管 DRAM 是非破坏性的记忆单元，单管 DRAM 是破坏性的记忆单元。20 【正确答案】 B【试题解析】 数组多路通道以数据块为传输单位，一段时间内只能为一个子通道服务，子通道的数据传输率即为通道的最大数据传输率。21 【正确答案】 D【试题解析】 视频图像每帧的数据量为 64MB，10 秒的视频信息将显示 300 帧，数据的存储量=64MB3010=1920MB 。22 【正确答案】 D【试题解析】 1 字节补码的表示范围为-128127，所以-131 在 1 字节补码表示为溢出；2 字节补码的表示范围为-3276832767，-131 在此范围内
29、，可以正确表示，需要进行符号扩展。-131 的二进制表示为-10000011，用 2 个字节补码表示为1111111101111101。23 【正确答案】 A【试题解析】 本题考查多道程序运行的工作方式，解决此类问题的关键一般根据进程的优先级和时序关系，画出时序图，注意 I O 设备不能抢夺，CPU 可以根据优先级来抢夺。 根据题意，进程运行时序图见表 75：单道运行是需要耗时： 6+8+2+12+6+2+4+8+4=52(ms) 从表中分析，并发运行时需要耗时 6+8+2+4+4+2+2+6+4=38(ms) 节省时间为 52-38=14(ms)，CPU 效率为(6+8+2+4+4+2+4)
30、38=7924 【正确答案】 D【试题解析】 本题考查考生对抢先式和非抢先式，以及时间片轮转调度算法的理解。根据题意，并发系统不止一个进程，所以它们会竞争 CPU，考虑一个简单系统，只有用户进程是使用磁盘的，其他进程不用，所以磁盘的使用可以不用等待，由此，我们画出如下示意图见表 76，其中注意，CPU 是不可抢夺的。由于 CPU 不可抢夺，所以当用户进程从磁盘读写返回时，它不能抢夺其他正在运行的进程，必须等待，到下一个调度时机的时候，由于其优先级最高，所以可以占有 CPU 运行。同理分析，直到该进程运行结束。计算出总时间。注意本题中，进程运行少于 20 ms 而主动出让 CPU 是可以的，并不
31、是一定要到 20 ms 才调度，我们所说的不可抢先是指被迫出让 CPU 的情形是不允许的。25 【正确答案】 B【试题解析】 本题考查进程调度的时机。运行着的进程由于分配的时间到，或者运行结束，或者需要等待事件的发生(例如等待键盘响应)，或者出错，或者自我阻塞等均可以引起激活调度程序进行重新调度，选择一个新的就绪进程占有处理机运行。新的进程加入到就绪队列不是引起调度的直接原因，当 CPU 正在处理其他进程的请求时，该进程仍然需要等待。即使在采用高优先级优先调度算法的系统中，一个最高优先级的进程进入就绪队列，仍旧需要考虑是否允许抢先，当不允许抢先时仍然需要等待。本题中，时钟中断是引起时间片到的触
32、发事件，处理机空闲的原因是进程运行结束或阻塞，程序出错也会出现处理机空闲，此时均可以引起调度器的激活。26 【正确答案】 D【试题解析】 本题考查对 Belady 现象的理解。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，即页面数量由小到大，则发生缺页的次数会由高至低。但是使用 FIFO 算法时，在未给进程或作业分配它所要求的页面数时，有时会出现分配的页面数增大，缺页次数反而增高的现象。这称为。Belady 异常。这种异常只在 FIFO 算法中出现，因为 FIFO 算法忽略了一种现象的存在，就是在内存中停留时间最长的页往往也是经常被访问的页。将这些页淘汰，很可
33、能刚置换出去，又请求调用该页，致使缺页中断较高，严重降低内存的利用率。27 【正确答案】 C【试题解析】 本题考查对计算机动态分区内存分配算法的计算。按照最先适应算法，见表 77。可以分配三个进程，余下 426 KB 的程序需要在外存等候。按照下次适应算法，如下表 78。同样地，余下 426 KB 的程序需要在外存等候。按照最佳适应算法，如表 79。所有进程均可以创建，较合理。按最坏适应算法，如表 710。余下 426 KB 的程序需要在外存等候。 所以，充分利用内存的适应算法是最佳适应算法。28 【正确答案】 B【试题解析】 本题考查虚拟存储器的最大空间的问题。虚拟存储器空间的最大值与实际存
34、储容量没有关系，仅与其地址系统的位宽有关，32 位的系统其最大虚存每个进程都是 4GB。若系统中存在 10 个进程，则总虚拟存储空间是所有进程虚拟存储空间之和。本题中为 40 GB。但是若要问，虚存的实际容量是多少时，则要考虑主存和辅存的大小，若主存和辅存之和小于最大虚拟存储空间 40 GB，则应是主存和虚存的实际容量之和。若大于 40 GB，则多余的部分是没有用的(仅指虚拟存储的外存，因为硬盘的主要作用是存储文件，仅用一部分来作为虚存的外存)。29 【正确答案】 A【试题解析】 本题主要考查文件的物理结构。连续结构，也称为顺序结构，它是把一个逻辑上连续的记录构成的文件分配到连续的物理块中。这
35、种方式管理简单，存储速度快，空间利用率低，文件记录插入或删除操作不方便。索引结构为每个文件建立一个索引表，其中每一个表项指出文件记录所在的物理块号，表项按逻辑记录编写，顺序或按记录内某一关键字顺序排列。对于大文件，为检索方便，可以建立多级索引，还可以把文件索引表也作为一个文件，称为索引表文件。该方式可以满足文件动态增长的要求且存取方便。链接文件把文件信息存放在非连续的物理块中，每个物理块均设有一个指针指向其后续连续的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。所以连续结构是最不利于随机读写和扩展的。30 【正确答案】 A【试题解析】 磁带是顺序访问的存储设备，所以复制文件时必
36、须复制整个文件。由于磁带上文件是顺序文件，所以无法实现索引文件，不管其有多便宜。备份文件时不需要作随机访问，所以用磁带来备份文件是合理的，也是经济的。31 【正确答案】 A【试题解析】 本题考查文件控制块的概念。文件控制块是用于管理文件的一组数据，每个文件均有一个文件控制块，其中包括文件名、文件拥有者、文件创建日期时间等。文件控制块一般在创建该文件时建立，打开文件只是将文件控制块的内容读入内存，读和写文件是对文件内容操作，它们必须依靠文件控制块的指示，例如外存地址，读写权限等。关闭文件只是将文件控制块回写到磁盘，删除文件时将文件控制块清除。32 【正确答案】 D【试题解析】 本题考查有关 UN
37、IX 设备管理的特点。UNIX 中，所有的设备被看作是特殊的文件，因为 UNIX 控制和访问外部设备的方式和访问一个文件的方式是相同的。在 UNIX 同一个外部设备进行通讯之前，这个设备必须首先要有一个设备文件存在。例如，每一个终端都有自己的设备文件来供 UNIX 写数据(出现在终端屏幕上)，和读取数据(用户通过键盘输入)。设备文件又称为特殊文件。设备文件和普通文件不一样，设备文件中并不包含任何数据。33 【正确答案】 A【试题解析】 本题考查 OSI 参考模型和 TCPIP 模型的比较。在 OSI 参考模型中，传输层仅有面向连接的方式。而 TCPIP 模型认为可靠性是端到端的问题，因此它在网
38、络层仅支持无连接的方式，但在传输层支持无连接和面向连接的两种方式。选项 B 和 D 仅说明了 TCPIP 模型在传输层方面的一个服务，选项 C 显然错误，因此答案是 A。34 【正确答案】 D【试题解析】 本题考查波特率与传输速率之间的关系。对于信号传输速率为 2000波特，要使数据传输速率达到 8Kbps，根据奈奎斯特定理 8000=2000Log2N，则一个码元需携带 4bit 的信息，也就是 Log2N=4，所以一个信号码元所能取的离散值的个数为 24=16 个，因此答案是 D。35 【正确答案】 A【试题解析】 本题考查停-等协议的效率计算问题，当发送一帧的时间等于信道传播延迟的 2
39、倍时，信道利用率是 50。或者说，当发送一帧的时间等于来回路程的传播延迟时，效率将是 50。本题中，往返传播时间为 20m2=40m，发送速率是 4000 bs，即发送 1 位需 025m 。40m025m b=160 b。所以，帧大于 160 位时，采用停一等协议才有至少 50的效率，答案是 A。36 【正确答案】 A【试题解析】 本题考查各种协议所处于的层次，选项 B 中 ARP 协议是处于网络层，不是和 TCP 一样处于传输层，选项 C 中 UDP 协议是和 TCP 协议一起处于传输层，选项 D 中 LLC 不是和 IP 一起处于网络层，而是在 MAC 层之上共同组成了数据链路层，因此答
40、案是 A。37 【正确答案】 C【试题解析】 本题考查子网划分的基本算法，首先要明确本题是把现有子网进行了二次划分，注意原子网的网络号是前 20 位，再次划分的网络号是 26 位，也就是从原子网的主机位拿出来 6 位作为子网号，因此可以划分 26=64 个子网，还剩余 6位作为主机号，也就是有效主机位是 26-2=62 台主机，因此答案是 C。38 【正确答案】 B【试题解析】 本题考查 ARP 协议的原理，当主机 A 要向本局域网上的某个主机B 发送 IP 数据报时，如果在其 ARP 高速缓存中查询不到主机 B 的物理地址，这时候 ARP 进程就需要在本局域网上广播发送一个 ARP 请求分组
41、，所以 ARP 协议的请求报文是广播的，不是单播的，此时应该是本局域网上的所有主机都可以收到此 ARP 的请求分组，而主机 B 见到 ARP 分组中的 IP 地址是自己的 IP 时，就向主机 A 发送一个 ARP 响应分组，所以 ARP 响应分组是普通的单播，一定注意ARP 是解决同一局域网上的主机或路由器的 IP 地址和硬件地址的映射问题，如果所要找的主机和源主机不在同一个局域网上，剩下的所有工作都应该由下一跳的路由器来完成。同时 ARP 位于网络层，并没有和 ICMP 一样封装在 IP 数据报中，主要实现 IP 地址和物理地址的转换，因此，ARP 报文在发送的时候并不知道对方的 MAC 地
42、址，因此答案是 B。39 【正确答案】 C【试题解析】 TCPIP 参考模型的传输层上有两个主要的协议，用户数据报协议 UDP(无连接 )和传输控制协议 TCP(面向连接)，主要区别如下：(1)TOP 是基于连接的，UDP 是基于无连接，这是本质的区别，其他区别都是为之服务的。(2)对系统资源的要求：TCP 较多，UDP 少。(3)UDP 数据包结构较简单，而 TCP 为了保证流量控制和拥塞控制，数据包结构较为复杂。(4)TCP 采用流模式，并进行编号，但 UDP 采用数据报模式(5)TCP 保证数据正确性，UDP 可能丢包；TOP 保证数据顺序，UDP 不保证。本题考查 TCP 和 UDP
43、的传输特性，TCP 可靠有连接，UDP 不可靠无连接，因此答案是 C。40 【正确答案】 B【试题解析】 本题考查数据封装的 5 个过程，FTP 服务器的数据要经过应用层、传输层、网络层、链路层才到达物理层，因此对应的封装是数据、数据段、数据包、数据帧，最后是比特，答案是 B。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 题目中方法能求得最小生成树。证明如下：(1)从算法中 while(所剩边数 顶点数)来看，循环到边数比顶点数少 1(即 n-1)停止，这符合 n 个顶点的连通图的生成树有 n-1 条边的定义；(2)由于边是按权值从大到小排序，删去的边是权值大的边，结果的生
44、成树必是最小生成树；(3)算法中“若图不再连通，则恢复 ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。所以，题目中方法可以求得图的最小生成树。42 【正确答案】 (1)用 p 指针扫描 L 的所有结点，先将 L 构造为只有一个带头结点的循环双链表，而用指针 s 构造不带头结点的循环双链表 (初始时为 NULL)，对于奇数序号的结点*p，采用尾插法插入到 L 中，对于偶数序号的结点 *p，采用头插法插入到 S 中。最后将 L 和 S 两个循环双链表连接成一个循环双链表， L 为其头结点指针。(2)用 C 语言算法描述如下：void s
45、plit(DLinkList&L)DLinkList*p=L-next，*q，*s=NULL；L-next=L；L-prior=L； 构造只有一个头结点的循环双链表while(p!=L) 扫描 L 的所有结点q=p-next ：p-next=L；P- prior：L-prior ；将 *p 结点插入到 L 循环双链表的末尾L-prior-next=p；L- prior=p；p=q； q=p-next；if(s=NULL) s 原为空表时，现只含有一个结点S=p；S-next=s；s- prior=s；=else 将*p 插入到 s 的前端p-next=s；p- prior=s- prior ；
46、s-prior-next=P；s-prior=p；s=p：p=q；s-prior-next=L； 将 L 和 S 合并起来L-prior- next=s：q=L-prior；L-prior=S-prior；s-prior=q；(3)说明算法的复杂性：上述算法的时间复杂度为 O(n)，算法的空间复杂度为O(1)。43 【正确答案】 (1)变址寻址时，操作数 S=(Rx)+A)=(23AOH+001AH)=(23BAH)=1748H。 (2) 间接寻址时，操作数 S=(A)=(001AH)=(23AOH)=2600H。 (3)转移指令使用相对寻址，转移地址=(PC)+A=IFOSH+001AH=I
47、FIFH。 因为在本题中没有指出指令的长度，故此题未考虑 PC 值的更新。44 【正确答案】 运算器的故障位置在多路开关 B，其输出始终为 R1 的值。 (1)R1(A)4-R2(B)一 1010，输出结果错； (2)R2(A)+R1(B)=1111，结果正确，说明R2(A)， R1(B)无错； (3)R 1(A)4+R1(B)=1010，结果正确，说明 R1(A)，R 1(B)无错。由此可断定 ALU 和 BR 无错； (4)R 2(A)+R2(B)=1111。结果错。由于 R2(A)正确，且 R2(A)=1010，本应 R2(B)=1010，但此时推知 R：(B)=0101，显然，多路开关
48、 B有问题； (5)R 2(A)+BR(B)=1111，结果错。由于 R2(A)=1010，BR(B)=1111 ，但现在推知 BR(B)=0101，证明开关 B 输出有错； (6)R 1(A)+BR(B)=1010，结果错。由于 R1(A)=0101，本应 BR(B)=1111，但现在推知 BR(B)=0101，再次证明开关 B 出错。 综上所述，多路开关 B 输出有错。故障性质：多路开关 B 输出始终为 0101。这有两种可能：一是控制信号 BS0，BS1 始终为 01，故始终选中寄存器 R1；二是多路开关 B 电平输出始终处于在 0101 上。45 【正确答案】 semaphore Stp=0； 烟草和纸的组合信号量semaphore Spm：0； 烟纸和火柴的组合信号量semaphore Stm=0； 烟草和火柴的组合信号量semaphore buffer=1； 经销商用于放置原料的缓冲区信号量main() 主程序开始cobegin 并发进程示意(不要遗忘)smokert(void) 第一
