1、计算机专业（基础综合）模拟试卷 21 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在具有 n 个结点的顺序表，算法的时间复杂度是 O(1)的操作是( )。（A）访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)（B）在第 i 个结点后插入一个新结点(1in)（C）删除第 i 个结点(1in)（D）将 n 个结点从大到小排序2 使用双链表存储线性表，其优点是( )。I 提高查找速度 更方便数据的插入和删除 节约存储空间 很快回收存储空间（A）I、（B） I、（C）仅 （D）、3 若进栈序列为
2、 a，b，c ，则通过出栈操作可能得到 a，b，c 的不同排列个数为( )。（A）4（B） 5（C） 6（D）74 若对 n 阶对称矩阵 A1n，1n以行序为主序方式下将其下三角的元素 (包括主对角线上的所有元素)依次存放于一维数组 B1n(n+1)2中，则在 B 中确定 aij(i（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，1 1（B） 6，9，10，11（C） 6，7，9，1 1（D）6，8，9，118 设散列表表长 m=14，散列函数 H(k)=k MOD 11，表中已有 15，38，61，84 四个元素，如果用线性探测法处理冲突，则元素 49 的存储地址是( )。（A）8（
4、B） 3（C） 5（D）99 以下关于查找方法的说法正确的是( )。I 顺序查找法只能在顺序存储结构上进行折半查找法可以在有序的双向链表上进行分块查找的效率与线性表被分为多少块有关（A）I、（B） 、（C） I、（D）只有10 下述排序方法中，比较次数与待排序记录的初始状态无关的是( )。（A）插入排序和快速排序（B）归并排序和快速排序（C）选择排序和归并排序（D）插入排序和归并排序11 堆排序、快速排序、归并排序就排序算法所用的辅助空间而言，从小到大的关系是( )。（A）堆排序、快速排序、归并排序（B）堆排序、归并排序、快速排序（C）快速排序、归并排序、堆排序（D）归并排序、快速排序、堆排序
5、12 目前的计算机，从原理上讲( )。（A）指令以二进制形式存放，数据以十进制形式存放（B）指令以十进制形式存放，数据以二进制形式存放（C）指令和数据都以二进制形式存放（D）指令和数据都以十进制形式存放13 在 CRC 码中，接收端检查出某一位数据出错后，一般采用的纠正方法是( )。（A）请求重新发送（B）删除数据（C）判断余数值由接收端自行纠（D）以上均可14 表示浮点数时，若要求机器零在计算机中的表示为全“0”，则阶码应采用的编码是( )。（A）原码（B）反码（C）补码（D）移码15 若浮点运算结果尾数不是规格化数，将进行结果规格化。结果规格化有左规和右规之分，下列操作中，属于结果规格化的
6、操作是( )。I尾数左移 1 位，阶码加 1 尾数左移 1 位，阶码减 1尾数右移 1 位，阶码加 1 1V尾数右移 1 位，阶码减 1（A）I、（B） 、（C） I、IV（D）、16 如下图所示，若低位地址(A0A11)接在内存芯片地址引脚上，高位地址(A12 A19)进行片选译码(其中，A14 和 A16 没有参加译码 )，且片选信号低电平有效，则对下图所示的译码电路，不属于此译码空间的地址是( )。 （A）AB000HABFFFH（B） BB000 HBBFFFH（C） EF000HEFFFFH（D）FE000HFEFFFH17 在 32 位处理器上，假设栈顶指针寄存器的当前值为 0x0
7、0FFFFE8，那么在执行完指令 “push eax”(eax 为 32 位寄存器)后，栈指针的当前值为 ( )。（A）0x00FFFFE4（B） 0x00FFFFE6（C） 0x00FFFFEA（D）0x00FFFFEC18 在补码加法运算时，产生溢出的情况是( )。I两个操作数的符号位相同，运算时采用单符号位，结果的符号位与操作数相同两个操作数的符号位相同，运算时采用单符号位，结果的符号位与操作数不同运算时采用单符号位，结果的符号位和最高数位不同时产生进位运算时采用单符号位，结果的符号位和最高数位同时产生进位V运算时采用双符号位，运算结果的两个符号位相同运算时采用双符号位，运算结果的两个符
8、号位不同（A）I、V（B） 、（C） 、（D）I、19 在采用增量计数器法的微指令中，下一条微指令的地址存放的位置是( )。（A）在当前微指令中（B）在微指令地址计数器中（C）在程序计数器中（D）在机器指令的地址码中20 在 32 位总线系统中，若时钟频率为 500MHz，传送一个 32 位字需要 5 个时钟周期，则该总线系统的数据传送速率是( )。（A）200MB/s（B） 400MB/s（C） 600MB/s（D）800MB/s21 计算机要对声音信号进行处理时，必须将它们转换成数字声音信号。最基本的声音信号数字化方法是取样一量化法。若量化后的每个声音样本用 2 个字节表示，则量化分辨率是
9、( ) 。（A）12（B） 11024（C） 165536（D）113107222 在 DMA 方式下，数据从内存传送到外设经过的路径是( )。（A）内存数据总线外设（B）内存 DMAC外设（C）内存 CPU 总线 外设（D）外设内存23 提高单机资源利用率的关键技术是( )。（A）SPOOLing 技术（B）虚拟技术（C）交换技术（D）多道程序设计技术24 一个进程被唤醒意味着( )。（A）该进程可以重新竞争 CPU（B）优先级变大（C） PCB 移到就绪队列之首（D）进程变为运行态25 出现下列的情况可能导致死锁的是( )。（A）进程释放资源（B）一个进程进入死循环（C）多个进程竞争资源出
10、现了循环等待（D）多个进程竞争使用共享型的设备26 进程从运行状态转换为就绪状态的可能原因是( )。（A）被调度程序选中占用处理机（B）等待某一事件（C）等待的事件已经发生（D）时间片用完27 某计算机采用虚拟页式存储技术，系统为每一个进程提供 65536B 的地址空间，含内外存。页面大小为 4096B，某一个进程的代码段有 32768B，数据段：16396B，堆栈段在进程创建时为 1024B，运行中最大会增涨到 15284B。那么这个进程( )。（A）能够创建到内存，运行正常（B）能够创建到内存，运行过程中出错（C）不能创建到内存（D）能够创建到内存，可能会死锁28 虚拟页式存储管理中，CP
11、U 须具备必要的物理硬件的支持，而不是必需的单元是( )。（A）缺页中断机构（B）地址加法器（C） cache（D）地址寄存器29 在文件的逻辑组织中，不属于记录文件的是( )。（A）索引文件（B）分区文件（C）链接文件（D）索引顺序文件30 文件系统可以利用位图实现的是( )。（A）记录图形文件（B）磁盘空间管理（C）磁盘调度（D）目录查找31 文件共享可以有多种方式，下列不是文件共享的方式是( )。（A）绕道法（B）链接法（C）文件映射法（D）基本文件目录表法32 通道是一利 IO 设备，它主要用于传输的数据是位于( )。（A）主存与 IO 设备（B） CPU 与 IO 设备（C）主存与外
12、存（D）CPU 与外存33 计算机网络体系之所以采用层次结构的主要原因是( )。（A）层次结构允许每一层只能同相邻的上下层次发生联系（B）层次结构优于模块化结构（C）使各层次的功能相对独立，使得各层次实现技术的进步不影响相邻层次，从而保持体系结构的稳定性（D）层次结构的方法可以简化计算机网络的实现34 某调制解调器同时使用幅移键控和相移键控，采用 0、2、 和 32 种相位，每种相位又都有 2 个不同的幅值，在波特率为 1200 的情况下数据速率是( )。（A）7200bps（B） 4800bps（C） 2400bps（D）1 200bps35 以太网的 MAC 子层遵守的标准是( )。（A）
13、IEEE8024（B） IEEE8025（C） IEEE8022（D）IEEE802336 一个以太网卡经历 4 次连续冲突后，如果带宽是 10M，那么其最大等待时间是( )。（A）768 微秒（B） 81 92 微秒（C） 71 68 微秒（D）921 微秒37 局域网中访问冲突的根源是( )。（A）独占介质（B）共享介质（C）引入 MAC 子层（D）规则的拓扑结构38 TCP 的滑动窗口协议中规定重传分组的数量最多可以是( )。（A）任意的（B） 1 个（C）大于滑动窗口的大小（D）等于滑动窗口的大小39 下面关于交换机的说法中，正确的是( )。（A）以太网交换机可以连接运行不同网络层协议
14、的网络（B）从工作原理上讲，以太网交换机是一种多端口网桥（C）集线器是一种特殊的交换机（D）通过交换机连接的一组工作站形成一个冲突域40 关于 FTP 的工作过程，下面那种说法错误的是( )。（A）在传输数据前，FTP 服务器用 TCP 21 端口与客户端建立连接（B）建立连接后，FTP 服务器用 TCP 20 端口传输数据（C）数据传输结束后，FTP 服务器同时释放 21 和 20 端口（D）FTP 客户端的端口是动态分配的二、综合应用题41-47 小题，共 70 分。41 现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2 ，em)；i=1；wh
15、ile(所剩边数= 顶点数 )从图中删去 ei；若图不再连通。则恢复 ei；i=i+1；请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举例说明。42 42设有带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。设计在时间和空间上都尽可能高效的算法，将 L 改造成L=(a1，a 2，a n，a 4，a 2)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C 十十或 JAVA 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。43 下图是某存储芯片的引脚图，请回答： (1)这个存储芯片的类型(
16、是 RAM 还是ROM)?这个存储芯片的容量? (2) 若地址线增加一根，存储芯片的容量将变为多少 ? (3)这个芯片是否需要刷新? 为什么?刷新和重写有什么区别。 (4)如果需要刷新，请指出芯片刷新一遍需要的时间(设存取周期为 05s)及你准备选择的刷新方式，需说明理由。 44 磁盘机由 6 个盘片组成，其中专设 1 个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为 61cm，外直径为 1 29cm，道密度为220TPM，位密度为 6000bpm，平均寻道时间为 10ms，磁盘转速为 7200RPM。假定 7=3，试计算：(1)数据盘面数和柱面数。(2)盘组容量是多少字节?(
17、3)数据传输率是多少字节秒?(4)从任一磁道读取 80000 个字节数据的平均存取时间是多少?(5)假定系统配备上述磁盘机 15 台，每个磁道分为 64 个扇区，试为该磁盘系统设计一个地址方案。45 有 n 个生产者进程向 1 个有限的缓冲区不断地发送消息，这些消息通过缓冲区分发到 m 个消费者，缓冲区的大小只可以存放 1 条消息。生产者和消费者的工作遵循如下规则：(1)生产者和消费者对缓冲区的访问互斥；(2)对每 1 条放入缓冲区的消息，所有消费者都必须接收 1 次；(3)缓冲区满时，生产者必须阻塞，缓冲区空时，消费者阻塞。请用信号量和 P、V 操作组织正确的发送和接收。用类 C 语言进行描
18、述。46 并发使得处理机的利用率得到提高，其主要原因是处理机与 IO 可以同时为多个进程服务，也即处理机与 IO 设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计进程并发时的次序。忽略计算机系统的开销，请计算并填写下表以及甘特图的空缺内容： 假设进程创建时间和完全占有 CPU 运行的确切时间如下表所示。已知其IO 繁忙率为 80，处理机的利用率为 20。 请计算并填写下列空格(填百分率)和图表空格处( 填时间) 。 47 下图是三个计算机局域网 A，B
19、和 C，分别包含 10 台，8 台和 5 台计算机，通过路由器互联，并通过该路由器接口 d 联入因特网。路由器各端口名分别为a、b、c 和 d(假设端口 d 接入 IP 地址为 61602180 的互联网地址)。LAN A和 LAN B 公用一个 C 类 IP 地址(网络地址为 20238600)，并将此 IP 地址中主机地址的高两位作为子网编号。A 网的子网编号为 01，B 网的子网编号为 10。主机号的低 6 位作为子网中的主机编号。C 网的 IP 网络号为 20236610。请回答如下问题： (1)为每个网络中的计算机和路由器的端口分配 IP 地址； (2)写出三个网段的子网掩码； (3
20、)列出路由器的路由表； (4)LAN B 上的一台主机要向 B 网段广播一个分组，请填写此分组的目的地址； (5)LAN B 上的一台主机要向 C 网段广播一个分组，请填写此分组的目的地址。计算机专业（基础综合）模拟试卷 21 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A【试题解析】 顺序表是随机存取结构，选项 A 中实质是查找第 i 个结点和第 i 一1 个结点，因此时间复杂度为 O(1)；选项 B 和 C 插入和删除都需要移动元素，时间复杂度为 O(n)；选项 D 是排序问题，时间复杂度
21、是 O(n)O(n 2)。2 【正确答案】 c【试题解析】 在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节省存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以其插入和删除操作更加方便。3 【正确答案】 B【试题解析】 若进栈序列为 a，b，c，可以考虑所有进栈出栈情况，则可能得到a，b，c 的出栈序列是 abc，acb，bac，bca，cba。4 【正确答案】 B【试题解析】 将对称矩阵 A 中的下三角的元素存放于 B 数组中，若求 aij(ij)的位置 k 的关系，答案为 A，即 i(i 一 1)2+j。 但
22、是，本题求 aij(iij(iij(iij 这就需要将备选答案 A 中 i(i 一 1)2+j 的 i 与 j 互换，因此正确答案为 B，即 j(j 一 1)2+i。5 【正确答案】 B【试题解析】 线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为 1。6 【正确答案】 D【试题解析】 由邻接矩阵的定义可知，对于无向图，其邻接矩阵的第 i 行的和即为第 i 个顶点的度。对于有向图，邻接矩阵的第 i 行元素的和即为第 i 个顶点的出度，而邻接矩阵的第 j 列元素的和即为第 j 个顶点的出度。7 【正确答案】 B【试题解析】 由折半查找过程可得，第一次 L(1+
23、11)2 j=6 ，第二次 L(6+1)+11)2 J=9 ，第三次 L(9+1)+11)2 j，第四次 11。 或者由下图所示的折半查找的判定树可求得下标。 8 【正确答案】 A【试题解析】 元素 1 5，38，61，84 分别存储在 4，5，6，7 单元，而元素 49 的散列地址为 5，发生冲突，向后探测 3 个单元，其存储地址为 8。9 【正确答案】 D【试题解析】 I 和的说法都是错误的，顺序查找法可以在顺序存储结构和链式存储结构上进行，而折半查找只能在可以进行随机存取的存储结构上进行，即只能在顺序存储的有序表上进行。10 【正确答案】 C【试题解析】 选择排序在最好、最坏、平均情况下
24、的时间性能均为 0(n2)，归并排序在最好、最坏、平均情况下的时间性能均为 0(nlogn)。11 【正确答案】 A【试题解析】 本题主要考查各种排序的空间复杂度。堆排序只是需要在元素比较进行交换时需要常数个存储空间，它需要的辅助空间为 O(1)；快速排序在递归过程中需要栈结构来保存递归的信息，它需要的辅助空间为 O(log2n)；归并排序需要长度为元素个数的线性空间来保存归并的结果，它需要的辅助空间为 O(n)。12 【正确答案】 C【试题解析】 在计算机中，无论是指令还是数据都以二进制形式存放在存储器中。13 【正确答案】 C【试题解析】 把接收到的 CRC 码用约定的生成多项式 G(X)
25、去除，如果正确，则余数为 0；如果某一位出错，则余数不为 0。14 【正确答案】 D【试题解析】 移码全为 0 时，它所对应的真值最小(绝对值最大的负数)。所以当阶码为全 0，尾数也为全 0 时，表示机器零。15 【正确答案】 B【试题解析】 当浮点运算结果尾数不是规格化数时，执行左规或右规。向左规格化规则：尾数每左移 1 位，阶码减 1。向右规格化规则：尾数右移 1 位，阶码加1。16 【正确答案】 D【试题解析】 这是一个部分译码的片选信号，高 8 位地址中有 2 位(A14 和 A16)没有参与译码，根据译码器电路，译码输出的逻辑表达式应为： 17 【正确答案】 A【试题解析】 “pus
26、h eax”是一条进栈指令，进栈时要先修改栈指针，32 位数据占4 个字节，存储器按字节编址，所以栈指针一 4。18 【正确答案】 C【试题解析】 常用的溢出判断方法主要有三种：采用一个符号位、采用进位位和采用变形补码。19 【正确答案】 B【试题解析】 在增量方式下，下一条微指令的地址应该由微程序计数器形成。20 【正确答案】 B【试题解析】 由于传送 4 个字节的数据需要 5 个时钟周期，4B500MHz5=400MBs。21 【正确答案】 C【试题解析】 量化后的每个声音样本用 2 个字节(16 位)表示，2 16：65536，其倒数就是量化的分辨率。22 【正确答案】 B【试题解析】
27、在 DMA 方式下，数据从主存传送到外设需要通过 DMA 控制器中的数据缓冲寄存器。23 【正确答案】 D【试题解析】 本题考查操作系统的特性。并发性是操作系统的一个最主要的特性，其它特性都是基于该特性的。多道程序设计技术是实现并发性的基础，由于采用了多道技术，系统实现了并发，从而提高了资源利用率。而 SPOOLing 技术是为解决独占设备的问题，虚拟技术主要应用在存储管理中来扩大存储空间，交换技术也是用于存储管理。所以多道技术是正确答案。24 【正确答案】 A【试题解析】 本题考查进程的状态以及状态之间的变换。当一个进程被唤醒时，这个进程就进入了就绪态，等待进程调度而占有 CPU 运行。进程
28、被唤醒在某种情形下优先级可以增大，但是一般不会变为最大，而有固定的算法来计算。也不会唤醒以后位于就绪队列的起首，就绪队列是按照一定的规则来赋予其位置的，例如先来先服务，或高优先级优先，或短进程优先等。更不能直接占有处理机运行。25 【正确答案】 C【试题解析】 本题考查死锁的四个必要条件。死锁的四个必要条件是：互斥、占有并等待、非剥夺、循环等待。本题中，出现了循环等待的现象，意味着可能导致死锁的出现。进程释放资源不会导致死锁，进程自己进入死循环只能产生饥饿，不涉及别的进程。共享型设备允许多个进程申请使用，故也不会造成死锁。26 【正确答案】 D【试题解析】 就绪状态是指一个进程获得了除处理机以
29、外的一切资源，当得到调度时，就由就绪状态转换为运行状态；运行状态就是一个进程在处理机上正在运行。当处于运行状态的进程在运行过程中所分配的时间片用完，则会被强制撤离处理机，以便调度其它进程运行。由于原先运行的进程是非自愿地离开运行状态，所以没有其它的事件相关，只有继续在就绪队列中等候下一次的调度，所以 D 是正确的。A 的情形是由就绪状态转换为运行状态；B 的情形是由运行状态转换为阻塞状态；C 的情形是由阻塞状态转换为就绪状态，均不正确，正确答案应选 D。本题主要考察学生对进程状态以及相互转换的关系，难度也并不高，改变一下问题的问法，ABC 三个答案均会有可能。27 【正确答案】 B【试题解析】
30、 本题考查页式存储的基本概念。页内只能存放同一个段的信息，不能容纳不同段的内容。根据题意，系统给每个进程最多分配有 655364096=1 6 个页面，进程创建时需要代码段 327684096=8 页；数据段 1 63964096=4 页余 12，占用 5 页；堆栈段 10244096=0 页余 3072，占用 1 页。8+5+1=1416，超出了系统分配给一个进程的最大地址空间，因此将会在申请第 1 7 个页面时出现一个致命的错误，进程退出。死锁的发生一定是二个或二个以上的进程之间发生的时间和空间上的竞争，本题没有涉及其它进程，因此不会死锁。28 【正确答案】 C【试题解析】 在虚拟页式存储
31、管理中，除了有主存和辅存以外，为满足虚拟技术，CPU 还需要有缺页中断机制；为满足页式存储管理，CPU 中需要有地址加法器和地址寄存器来计算页表到页框的映射，而 cache 并不是必需的，因为 cache 的存在只是提高了 CPU 寻址的效率，并不是虚拟页式存储技术的重要单元，缺少cache，CPU 每次执行一个双字的指令 (以 32 位为例)或取一个数据均需要二次访问内存，当然这是很不利的，可能会实际上造成虚拟页式的使用障碍。增加了cache，使得虚拟页式存储技术的实际使用提供了方便。29 【正确答案】 B【试题解析】 对于记录型文件，构成文件的基本单位是记录。记录文件是具有符号名并且在逻辑
32、上具有完整意义的记录序列。用户对记录型文件的访问是以记录为基本单位的。一个记录由一组在逻辑上相关的信息项构成。每个文件内部有一个读写指针，通过系统调用可以将读写指针移动到文件的某一位置处，以后的读写将从该指针所确定的位置处开始。因此索引顺序文件、链接文件和索引文件都是记录文件。只有分区文件不是记录文件，故正确答案为 B。30 【正确答案】 B【试题解析】 本题考查位图的功能。位图也称为位示图或示位图。这种题型关键在于平时注意。磁盘调度和目录查找通常是利用指针实现的，和位图无关。而使用位图，可以方便地指示出哪个磁盘块是空闲的，哪个磁盘块已经被使用了(可以利用位图中的位标志为 1 来实现，反之亦然
33、)。31 【正确答案】 C【试题解析】 文件的共享主要有三种方式：绕道法(或称软链接法)，链接法(或称硬链接法)和基本文件目录表法。文件共享可以使得多个用户共同使用同一个文件，不仅是为完成共同任务所必须，而且还节省了大量存储空间，减少重复性劳动，减少实际 IO 文件的个数。其中，绕道法通过文件的路径名来实现共享。链接法直接将文件的指针指向文件所在的目录，并在文件控制块中记录下文件的共享链接数。基本文件目录利用符号文件目录和基本文件目录，用户访问基本文件目录，系统采用符号文件目录，利用指针将基本文件目录映射到符号文件目录，从而实现共享。文件映射不是文件共享的方式，而是进程间进行通信的一种内存共享
34、方式。32 【正确答案】 A【试题解析】 本题考查通道的作用与功能。通道主要是连接 IO 设备与内存的一个硬件设施，又称为 IO 处理机，是一个独立于 CPU 的专门管理 IO 的控制器，它可以控制设备与内存直接进行数据交换，所以它与 CPU 是并行的。通道具有执行IO 指令的能力，并通过执行通道程序来控制 IO 操作。但是，通道又和一般的处理机不同，他的结构简单，指令较少且单一，这些指令一般均与 IO 操作有关。同时，通道一般没有自己独立的内存，它的程序大多是放在主存中的，与 CPU 共享。33 【正确答案】 C【试题解析】 本题考查层次结构，计算机网络分层使各层之间是独立的，灵活性好，结构
35、上可以分开，易于实现和维护，促进标准化工作，这是最主要的原因，选项 A 只涉及一个功能方面，选项 B 层次和模块化各有优缺点，不能相提并论，而选项 D 也是涉及一个方面，因此答案是 C。34 【正确答案】 A【试题解析】 本题考查奈奎斯特定理，注意根据题意有 4 种相位2 个幅值=8 种信号状态，根据共识 C=2Wlog2M=21200log28=21 2003=7200bps，因此答案为A。 35 【正确答案】 D【试题解析】 本题是概念题，考查以太网和 IEEE8023 的关系，IEEE8023描述物理层和数据路层的 MAC 子层的实现方法，在多种物理媒体上以多种速率采用 CSMACD 访
36、问方式，对于快速以太网该标准说明的实现方法有所扩展，是以太网的 MAC 子层遵守的标准，因此答案是 D。 36 【正确答案】 A【试题解析】 本题考查 CSMACD 的二进制指数退避算法，首先每个站点确定一个基本推迟时间 T，然后从整数集合0，1，2，3，2 k-1)中随机抽取一个整数 r，其中 r=min(重发次数， 10)；随机等待时间 TW=rT；注意当某 MAC 帧重发 16 次不能成功，则放弃该帧。并向高层报告。现已知冲突次数为 4，所以k=4，2 k=1 6。由此可得，在下一次重发前最多要等待 15 个时间片。在 10M 以太网的情况下，一个时间片=512 微秒，所以等待的最大时间
37、为 15512=768 微秒，因此答案是 A。37 【正确答案】 B【试题解析】 本题考查以太网 CSMACD 协议的原理，由于采用随机访问和竞争技术，CSMACD 只用于总线拓扑结构网络，因此答案为 B。38 【正确答案】 D【试题解析】 TCP 滑动窗口协议中发送方滑动窗口的大小规定了发送方最多能够传送的分组的数目，只有窗口滑动了，才能往后继续发送。分组的重传也是发送方数据的发送，因而重传分组的数量最多也不超过滑动窗口的大小，答案是 D。39 【正确答案】 B【试题解析】 本题考查交换机和集线器的区别，选项 A，交换机是数据链路层设备，对于网络层来说是透明的，表述有问题，选项 C，集线器是
38、物理层设备，和交换机不在同一个层次，选项 D，交换机的优势就是每个端口是一个冲突域，整个交换机是一个广播域，因此答案是 B。40 【正确答案】 C【试题解析】 本题考查 FTP 的工作原理，FTP 使用两条 TCP 连接完成文件传输，一条是控制连接，另一条是数据连接。平时 FTP 服务器总在端口 21 上等待客户的连接请求，当用户需要传输文件时，FTP 客户与 FTP 服务器的端口 21 建立一个控制连接，用来传送客户的命令和服务器的响应。当客户在控制连接上发出数据传输命令时，服务器在另一个端口上主动与客户建立一条数据连接，然后在数据连接上传输文件。当一个文件传输结束时，关闭数据连接。如果用户
39、请求另一个文件的传输，则服务器和客户再建立一个数据连接，用于传输新的文件。虽然数据连接频繁地建立和释放，但控制连接在整个会话期间一直保持，直到客户与服务器通信结束为止。因此答案为 C。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 题目中方法能求得最小生成树。证明如下：(1)从算法中 while(所剩边数 顶点数)来看，循环到边数比顶点数少 1(即 n 一 1)停止，这符合 n 个顶点的连通图的生成树有 n 一 1 条边的定义；(2)由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；(3)算法中“若图不再连通，则恢复 ei”，含义是必须保留使图连通
40、的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。所以，题目中方法可以求得图的最小生成树。【试题解析】 无向连通图的生成树包含图中全部 n 个顶点，以及足以使图连通的nl 条边。而最小生成树则是各边权值之和最小的生成树。所以要证明题目中的方法正确，需要从以下方面证明，即：n 个顶点的连通图的生成树有 n 一 1 条边；所构成的生成树的边的权值之和最小。42 【正确答案】 (1)算法的基本设计思想如解析所述。(2)用 C 语言算法描述如下：Void split(DLinkListL)DLinkList*p=L 一next，*q，*s=NULL ；L 一next=L；L
41、 一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 ；s 一prior 一next=p；s 一prior=p ；s=p；p=q；s 一prior 一n
42、ext=L； 将 L 和 s 合并起来L 一prior 一next=s；q=L 一prior；L 一prior=s 一prior；s 一prior=q；(3)说明算法的复杂性：上述算法的时间复杂度为 O(n)，算法的空间复杂度为O(1)。【试题解析】 用 p 指针扫描 L 的所有结点，先将 L 构造为只有一个带头结点的循环双链表，而用指针 s 构造不带头结点的循环双链表 (初始时为 NULL)，对于奇数序号的结点*p ，采用尾插法插入到 L 中，对于偶数序号的结点 *p，采用头插法插入到 s 中。最后将 L 和 s 两个循环双链表连接成一个循环双链表，L 为其头结点指针。43 【正确答案】 (
43、1)芯片类型是 RAM，且为动态 RAM(DRAM)，芯片容量64K1。(2)由于地址线是复用的，若地址线增加一根，容量增加 4 倍，芯片的容量变为256K1。(3)需要刷新，因为是 DRAM 是用电容存储信息的。重写是随机的，刷新是定时的。重写按存储单元进行，刷新按存储体一行行地进行。(4)64K1 芯片的内部为 256256 的矩阵，芯片刷新一遍需要的时间=25605s=128s 。采用异步刷新方式最好，死区小，刷新次数少。【试题解析】 第 43 题图中有地址线 8 根，输入输出数据线各 1 根，另有读写控制线丽和行、列选通线。从给出的芯片管脚可以看出，这是一个可读可写的动态随机存储 (D
44、RAM)芯片。44 【正确答案】 (1)由于磁盘机有一个盘面是伺服盘，实际的数据盘面数=621=11(个)柱面数 =(外直径一内直径 )2)道密度=(1 2961)2)220=748( 个) (2)以最内圈磁道的周长当作每条磁道的长度，故该盘组的存储容量(非格式化容量)为：位密度内圈磁道的周长 柱面数数据盘面数=600076174811=903434400b=112929300B (3)数据传输率=转速每一道的容量=120 转 s13725B=1 647000Bs (4)磁盘旋转一圈时间为 6083ms 平均存取时间=平均寻道时间+ 平均等待时间+读取数据的时间=10+832+80000164
45、7000=10+4 15+486=6275ms (5)磁盘系统共 15 台磁盘机，驱动器号(4 位) ；共有 748 个圆柱面，柱面号(10 位)；共有 11 个记录面，记录面号(4 位)；每个磁道有 64 个扇区，扇区号(6 位)。最终的地址方案是： 驱动器号(4 位 )，柱面号 (10 位)，记录面号 (4 位)，扇区号(6 位)。【试题解析】 磁盘机有多个盘片，每个盘片有两个盘面，每个盘面上有若干磁道，各记录面上相同编号(位置)的诸磁道构成一个圆柱面。通常将一条磁道划分为若干个段，每个段称为一个扇区或扇段，每个扇区存放一个定长信息块。45 【正确答案】 本题的解答采用分离的信号量来实现，
46、可以比较清楚地看到操作的过程。typedef int semaphorle； 定义信号量semaphore mutex； 缓冲区互斥信号量用于读写互斥semaphore emptym=1，1，1 ； 当前缓冲区所有格子为空semaphore gridm=0，0，0 ； 缓冲区的每个格子满的信号量void producer() 生产者int i，buffer ；while(1) 并发调度 message=produce()； 生产者生产消息for(i=0，im，i+) 生产者必须P(emptym)； 等待所有格子为空p(mutex)； 取得缓冲区互斥量buffer=write(message)；
47、 将数据写入缓冲区V(murex)； 释放缓冲区互斥量for(i=0，im，i+) 写者写入一次V(gridi)； 所有格子信号量增一void consumer(k，ptr) 第 k 个消费者int i，buffer ；while(1) 并发调度 P(gridk)； 对应第 k 个消费者是否可取数据P(mutex)； 取得缓冲区互斥量ptr=read(buffer)； 消费者读取消息送到本进程空间v(mutex)； 释放缓冲区互斥量V(emptyk)； 将本消费者的空信号量增一consume()； 消费者消费消息【试题解析】 本题是经典的生产者和消费者问题的变形。在经典的生产者和消费者的模型中，生产者和消费者共用一组缓冲区，生产者向缓冲区中写入一次数据，消费者从缓冲区中读出一次数据，即写一次，读一次。本题中，生产者向缓冲区中只写一次，但是每个消费者却都要读一次。对于此类问题，可以把缓冲区看成是m 格的缓冲区阵列，这样一来，生产者每写一次缓冲区，相当于填满了一块 m 格的缓冲区，而消费者只需要读出属于自己格子的消息即可，当所有的格子读空以后，这个缓冲区就可以接纳下一个生产者的写入。分析清楚其工作机制，我们可以从经典的生
