说明

$\color{green}{\text{绿色}}$ 答案代表没做错， $\color{red}{\text{红色}}$ 代表做错

教训中的 $\color{green}{\text{warning}}$ tag代表需要回过头再看看

一些常用记号

Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
Ⅵ
Ⅶ


2010计算机考研

# 2009

1

1．为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是

A．栈

B．队列

C．树

D．图

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、栈和队列			nan

2．设栈S和队列Q的初始状态均为空，元素a, b, c, d, e,f, g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b, d,c,f,e,a,g，则栈S的容量至少是

A. 1

B.2

C．3

D.4

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、栈和队列			nan

3.给定二叉树如右图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2,4，则其遍历方式是___。

A. LRN

B．NRL

C．RLN

D．RNL

图片详情

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树和二叉树、二叉树的遍历			nan

4.下列二叉排序树中，满足平衡二叉树定义的是

图片详情

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树和二叉树、平衡二叉树			nan

5．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是_

A．39

B.52

C.111

D.119

解析

$\color{red}{\text{C}}$

以三层的情况为例，可知如果第6层有叶子节点，那么这棵树最高为7层，所以节点最多有 $2^7-1-8\times2=111$

三层的情况

$\color{green}{\text{完全二叉树}}$ ：高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树和二叉树、完全二叉树			nan

6．将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是_-

I．父子关系

II．兄弟关系

III.u的父结点与v的父结点是兄弟关系

A．只有II

B．I和II

C.I和III

D．I、II和III

解析

$\color{red}{\text{B}}$

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树和二叉树、树、森林			nan

7.下列关于无向连通图特性的叙述中,正确的是

I．所有顶点的度之和为偶数

II．边数大于顶点个数减

III．至少有一个顶点的度为1

解析

$\color{green}{\text{A}}$

考虑环型，排除2、3

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、图、无向图的性质			nan

8．下列叙述中，不符合m阶B树定义要求的是

A．根结点最多有m棵子树

B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列

D.叶结点之间通过指针链接

解析

$\color{green}{\text{D}}$

叶结点之间通过指针链接是 $\color{green}{\text{B+}}$ 树的性质

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、查找、B+树的基本概念			nan

9.已知关键字序列5,8,12,19,28,20,15,22是小根堆（最小堆)，插入关键字3，调整后得到的小根堆是―___。

A.3,5,12,8,28,20,15,22,19

B.3,5,12,19,20,15,22,8,28

C. 3,8,12,5,20,15,22,28,19

D.3,12,5,8,28,20,15,22,19

解析

$\color{green}{\text{A}}$

画图解之

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、排序、堆排序			nan

10．若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是_

A．冒泡排序

B．插入排序

c．选择排序

D.二路归并排序

解析

$\color{green}{\text{B}}$

排序默认 $\color{green}{\text{由小到大}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、排序、排序算法的分析和应用			nan

11．冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是。

A．指令操作码的译码结果

B.指令和数据的寻址方式

c．指令周期的不同阶段

D．指令和数据所在的存储单元

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、计算机系统概述、计算机系统的工作原理			nan

12.一个C语言程序在一台32位机器上运行。程序中定义了三个变量x、y和z，其中x和z为int型，y为short型。当x=127，y=-9时，执行赋值语句z=x+y后，x、y和z的值分别是

A. x = 0000007FH，y= FFF9H，z= 00000076H

B. x = 0000007FH，y =FFF9H，z=FFFF0076H

C. x =0000007FH，y =FFF7H，z=FFFF0076H

D. x= 0000007FH，y=FFF7H，z= 00000076H

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、数据的表示和运算、整数的表示和运算			nan

13．浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位)。若有两个数X= $2^7$ ×29/32，Y= $2^5$ x5/8，则用浮点加法计算X＋Y的取终结宋定-—

A. 00111 1100010

B.00111 0100010

C. 01000 0010001

D.发生溢出

解析

$\color{green}{\text{D}}$

小阶向大阶看起

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、数据的表示和运算、浮点数的表示和运算			nan

14．某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32B，按字节编址。主存129号单元所在主存块应装入到的Cache组号是

A. 0

B.1

C.4

D.6

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、存储器层次结构、高速缓冲存储器、Cache和主存之间的映射方式			nan

15．某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2K×8位的ROM芯片和4K×4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和 RAM芯片数分别是

A.1、15

B.2、15

C. 1、30

D.2、30

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、存储器层次结构、半导体随机存取存储器			nan

16．某机器字长为16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一个字节为操作码字段，第二个字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是。

A. 2006H

B.2007H

C.2008H

D.2009H

解析

$\color{green}{\text{C}}$

读完内存地址

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、指令系统、寻址方式			nan

17．下列关于RISC的叙述中，错误的是

A. RISC普遍采用微程序控制器

B.RISC大多数指令在一个时钟周期内完成

C. RISC的内部通用寄存器数量相对CISC多

D. RISC的指令数、寻址方式和指令格式种类相对CISC少

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、指令系统、CISC和RISC的基本概念			nan

18．某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间)分别为90ns、80ns、70ns、和60ns,则该计算机的CPU时钟周期至少是

A. 90ns

B. 80ns

c.70ns

D. 60ns

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、中央处理器、指令流水线		warning	nan

19．相对于微程序控制器，硬布线控制器的特点是_

A．指令执行速度慢，指令功能的修改和扩展容易

B．指令执行速度慢，指令功能的修改和扩展难

C．指令执行速度快，指令功能的修改和扩展容易

D.指令执行速度快，指令功能的修改和扩展难

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、中央处理器、控制器的功能和工作原理			nan

20．假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是_

A.10MB/s

B.20MB/s

C.40MB/s

D.80MB/s

解析

$\color{green}{\text{B}}$

$4B \times 10MHz / 2= 20MB/s$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、总线、			nan

21．假设某计算机的存储系统由Cache和主存组成，某程序执行过程中访存1000 次，其中访问Cache缺失（未命中）50次，则Cache的命中率是_

A.5%

B. 9.5%

c. 50%

D. 95%

解析

$\color{green}{\text{D}}$

(1000-50)/1000=95%

题目tag详情

总结

题型	错因	教训	视频讲解
cache			nan

22.下列选项中，能引起外部中断的事件是_

A．键盘输入

B．除数为О

c．浮点运算下溢

D．访存缺页

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、输入/输出系统、I/O 方式、程序中断方式、异常和中断、外部中断			nan

23．单处理机系统中，可并行的是_

Ⅰ进程与进程

Ⅱ处理机与设备

Ⅲ处理机与通道

Ⅳ设备与设备

A. I、II和III

B. I、II和IV

c. I、III和IV

D. II、III和IV

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、计算机系统概论、			nan

24．下列进程调度算法中，综合考虑进程等待时间和执行时间的是_

A．时间片轮转调度算法

B．短进程优先调度算法

C．先来先服务调度算法

D．高响应比优先调度算法

解析

$\color{green}{\text{D}}$

$\color{red}{\text{响应比}}$ 的变化规律可描述为

$\text{响应比}R_p=\dfrac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、处理机调度、典型的调度算法、			nan

25.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是_….__。

A.2

B.3

C.4

D. 5

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、死锁、			nan

26．分区分配内存管理方式的主要保护措施是_

A．界地址保护

B．程序代码保护

C．数据保护

D．栈保护

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理、连续分配管理方式、			nan

27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是_

A. $2^8$ B

B. $2^{16}$ B

c. $2^{24}$ B

D． $2^{32}$ B

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理、非连续分配管理方式、			nan

28．下列文件物理结构中，适合随机访问且易于文件扩展的是_

A.连续结构

B．索引结构

C．链式结构且磁盘块定长

D．链式结构且磁盘块变长

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理、非连续分配管理方式、			nan

29．假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45,12, 68,110,180,170,195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是

A. 110,170,180,195,68,45,35,12

B. 110,68,45,35,12,170,180,195

C. 110,170,180,195,12,35,45,68

D. 12,35,45,68,110,170,180,195

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、文件管理、磁盘组织与管理、			nan

30．文件系统中，文件访问控制信息存储的合理位置是_

A．文件控制块

B．文件分配表

c．用户口令表

D．系统注册表

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、文件管理、文件系统基础、			nan

31．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是。

A.0、1

B.1、1

C. 1、2

D.2、1

解析

$\color{red}}{\text{B}}$

建立符号链接时，引用计数值直接复制;建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接;但对于硬链接则不可直接删除，引用计数值减1，若值不为0，
则不能删除此文件，因为还有其他硬链接指向此文件。

当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2一1=1，F2的引用计数值不变。

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、文件管理、文件系统基础、文件共享、			nan

32．程序员利用系统调用打开IO设备时，通常使用的设备标识是__

A．逻辑设备名

B．物理设备名

c．主设备号

D.从设备号

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、输入/输出(I/O)管理、设备分配、			nan

33．在OSI参考模型中，自下而上第一个提供端到端服务的层次是.

A.数据链路层

B．传输层

c．会话层

D.应用层

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
传输层			nan

34.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是_

A. 12kbps

B.24kbps

C. 48kbps

D. 96kbps

解析

$\color{red}{\text{B}}$

采用4个相位，每个相位有4种幅度的QAM调制方法，每个信号可以有16种变化，传输4比特的数据。根据奈奎斯特定理，信息的最大传输速率为2W $log_2V$= 2x3k×4=24kb/s。

题目tag详情

总结

题型	错因	教训	视频讲解
物理层、奈奎斯特定理			nan

35．数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是

A.2

B.3

C.4

D.5

解析

$\color{red}{\text{C}}$

重传4、5、6、7，帧数为4

$\color{green}{\text{注意}}$ 数据链路层的序号和传输层中tcp的序号不同

数据链路层的序号是 $\color{green}{\text{已经}}$ 收到该序号对应的帧
传输层中tcp的序号是 $\color{green}{\text{期望}}$ 收到该序号对应的报文段

题目tag详情

总结

题型	错因	教训	视频讲解
数据链路层、GBN			nan

36．以太网交换机进行转发决策时使用的PDU地址是

A.目的物理地址

B.目的IP地址

C．源物理地址

D.源IP地址

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据链路层、局域网、以太网、交换机			nan

37.在一个采用CSMA/CD协议的网络中,传输介质是一根完整的电缆,传输速率为1Gbps电缆中的信号传播速度为200000km/s。若最小数据帧长度减少800bit，则最远的两个站点之间的距离至少需要_

A.增加160m

B．增加80m

C．减少160m

D．减少80m

解析

$\color{red}{\text{D}}$

最小帧长=总线传播时延×数据传输速率×2
$\dfrac{帧长}{数据传输速率}=总线传播时延×2$

设x为减少的距离，则下面的等式成立

$\text{原来右边的值}-\dfrac{800bit}{1Gbps}=(\dfrac{\text{原来右边的值}}{2}-\dfrac{x}{200000km/s}) \times 2$

题目tag详情

总结

题型	错因	教训	视频讲解
数据链路层、介质访问控制、随机访问介质访问控制、			nan

38．主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300B和500B的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是

A. 500

B.700

c. 800

D. 1000

解析

$\color{green}{\text{D}}$

TCP是面向字节流的(即TCP传送时是逐个字节传送的)，所以TCP连接传送的字节流中的每个 $\color{green}{\text{字节}}$ 都按顺序编号

题目tag详情

总结

题型	错因	教训	视频讲解
传输层、TCP协议、TCP可靠传输、			nan

39．一个TCP连接总是以1KB的最大段长发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的，那么当第.4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是_

A.7KB

B.8KB

C．9KB

D.16KB

解析

$\color{green}{\text{C}}$

1,2,4,8,9

题目tag详情

总结

题型	错因	教训	视频讲解
传输层、TCP协议、TCP拥塞控制、网络拥塞的处理、			nan

40.FTP客户和服务器间传递FTP命令时，使用的连接是_

A．建立在TCP之上的控制连接

B．建立在TCP之上的数据连接

c．建立在UDP之上的控制连接

D.建立在UDP之上的数据连接

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
应用层、FTP			nan

41.(10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法:

${\textstyle\unicode{x2460}}$ 设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;

${\textstyle\unicode{x2461}}$ 选择离u最近且尚未在最短路径中的一个顶点v,加入最短路径中,修改当前顶点u=v;

${\textstyle\unicode{x2462}}$ 重复步骤${\textstyle\unicode{x2461}}$,直到u是目标顶点时为止。

请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。

解析

我的答案

参考答案

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、图、最短路径			nan

42.（15分）已知一个带有表头结点的单链表，结点结构为

图片详情

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则，只返回0。要求:

1）描述算法的基本设计思想。

2）描述算法的详细实现步骤。

3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现)，关键之处请给出简要注释。

解析

(1）算法的基本设计思想（5分）:

问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是:定义两个指针变量p和q，初始时均指向头结点的下一个结点(链表的第一个结点)。p指针沿链表移动;当p 指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。

(2）算法的详细实现步骤（5分）:

count=0，p和q指向链表表头结点的下一个结点;②若p为空，转⑤;

若count等于k，则q指向下一个结点;否则，count=count+1;p指向下一个结点，转②;

若count等于k，则查找成功，输出该结点的data域的值，返回 l;否则，说明k值超过了线性表的长度，查找失败，返回0;

⑥算法结束。

(3）算法实现（5分）:

代码详情

typedef int ElemType;//链表数据的类型定义
typedef struct LNode { //链表结点的结构定义
ElemType data; //结点数据
struct Lnode *link;//结点链接指针
} *LinkList;

int Search_k (LinkList list, int k ) {

//查找链表list倒数第k个结点，并输出该结点data域的值
LinkList p = list->link,q = list->link;//指针p、q指示第一个结点
int count = 0 ;
while(p != NULL){ //遍历链表直到最后一个结点
    if ( count< k) count++; //计数，若count <k只移动p
    else q = q->link; p = p->link;//之后让p、q同步移动
}// while
if (count < k)
    return 0;查找失败返回
else {//否则打印并返回1
    printf ( "%d", q->data) ;
    return 1;
} // search_k

$\color{green}{\text{提示}}$ :算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。

若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分;若采用两遍或多遍扫描才能得到正确结果的，最高分10分。若采用递归算法得到正确结果的，最高给10分;若实现算法的空间复杂度过高(使用了大小与k有关的辅助数组），但结果正确，最高给10分。

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、链表			nan

43.(8分）某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?

2)当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000B，且 DMA预处理和后处理的总开销为500个时钟周期,则CPU用于该外设IO的时间占整个CPU时间的百分比是多少(假设DMA与CPU之间没有访存冲突）?

解析

(1)按题意，外设每秒传送0.5MB，中断时每次传送4B。中断方式下，CPU每次用于数据传送的时钟周期为: 5×18+5×2=100.

为达到外设0.5MB/s 的数据传输率，外设每秒申请的中断次数为:0.5MB/4B=125 000。1秒钟内用于中断的开销:100×125 000=12 500 000=12.5M个时钟周期。

CPU用于外设IO的时间占整个CPU时间的百分比:12.5M/500M=2.5%。

(2)当外设数据传输率提高到5MB/s时改用DMA方式传送，每次 DMA传送5000B，1秒钟内需产生的DMA 次数:5MB/5 000 B=1 000.

CPU 用于DMA处理的总开销:1 000×500=500 000=0.5M个时钟周期。

CPU用于外设IO的时间占整个CPU时间的百分比:0.5M/500M=0.1%。

$5\times 20 \times 0.5 MB /4B/500M$ =2.5%
$10^3 \times 500 / 500 / 10^6$ =0.1%

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、中断			nan

中央处理器、数据通路

图片详情

解析

我的答案

参考答案

记得右边取数的时候需要加括号

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、中央处理器、数据通路			nan

45.(7分）三个进程P、Pz、P,互斥使用一个包含N(N>0)个单元的缓冲区。P每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;Pz每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P;每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述)。

解析

标准答案

semaphore odd = 0, even = 0, empty = N, mutex = 1;
P1( )
{
    x = produce(); //生成一个数
    P(empty); //判断缓冲区是否有空单元
    P(mutex);//缓冲区是否被占用
    Put();
    V(mutex);//释放缓冲区
    if(x%2 == 0)
        V(even); //如果是偶数，向P3发出信号
    else
        V(odd); //如果是奇数，向P2发出信号
}

P2( )
{
    P(odd); //收到P1发来的信号，已产生一个奇数
    P(mutex);//缓冲区是否被占用
    getodd();
    V(mutex);//释放缓冲区
    V(empty); //向P1发信号，多出一个空单元
    countodd();
}
P3( )
{
    P(even); //收到P1发来的信号，已产生一个偶数
    P(mutext); //缓冲区是否被占用
    geteven();
    V(mutex); //释放缓冲区
    V(empty); //向P1发信号，多出一个空单元
    counteven();
}

我的答案，学学注释怎么写

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、信号量			nan

46.(8分）请求分页管理系统中，假设某进程的页表内容见下表。

图片详情

页面大小为4KB，一次内存的访问时间为100ns，一次快表(TLB）的访问时间为10ns处理一次缺页的平均时间为 $10^8$ ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为采用最近最少使用置换算法(（LRU)和局部淘汰策略。假设①TLB初始为空;②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间);③有效位为表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H,请问:

1)依次访问上述三个虚地址，各需多少时间?给出计算过程。

2）基于上述访问序列，虚地址1565H的物理地址是多少?请说明理由。

解析

(1)根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即 $2^{12}$ ，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号Р如下(十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号):

2362H:P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存 10Oms,共计10ns+10Ons+100ns=210ns 。

1565H:P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理10°ns，访问快表10ns，合成物理地址后访问主存100ns，共计10ns+100ns+ $10^8$ ns+10ns+100ns=100 000 220ns 。

25A5H:P=2，访问快表，因第一次访问已将该页号放入快表，因此花费1Ons便可合成物理地址，访问主存100ns，共计 10ns+100ns=110ns 。

(2)当访问虚地址1565H 时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰О号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理			nan

计算机网络、网络编址

图片详情

解析

我的答案

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、网络编址			nan

2010

1

1．若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（)。

A. d，c，e，b， f，a

B. c，b，d，a，e， f

C. b，c，a，e，f，d

D. a，f，e，d，c，b

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、栈			nan

2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素a， b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是（)。

A. b,a，c，d，e

B. d，b,a，c，e

C. d，b，c，a，e

D. e，c，b，a，d

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、栈、队列			nan

3．下列线索二叉树中（用虚线表示线索)，符合后序线索树定义的是（)。

图片详情

解析

$\color{green}{\text{D}}$

$\color{green}{\text{左前右后}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树与二叉树、二叉树的遍历和线索二叉树、线索二叉树、		warning	nan

4.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是()。

图片详情

A. 13、48

B. 24、48

C． 24、53

D. 24、90

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树与二叉树、树与二叉树的应用、平衡二叉树			nan

5．在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（)。

A．41

B.82

C.113

D. 122

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树与二叉树、树的性质、			nan

6.对n (n $\geq$ 2)个权值均不相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是()。

A．该树一定是一棵完全二叉树

B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、树与二叉树、树与二叉树的应用、哈夫曼树和哈夫曼编码、			nan

7．若无向图G=(V，E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是()。

A. 6

B．15

C.16

D.21

解析

$\color{red}{\text{C}}$

$\color{green}{\text{保证图G在任何情况下都是联通的}}$ ，说明要考虑最糟糕的情况而不是选A，只需要6条边

所以是剩下的6个点的构成完全图，然后加一条和第七个点相连的边，即 $6\times 5 / 2 +1=16$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、图、			nan

8．对下图进行拓扑排序，可以得到不同拓扑序列的个数是（)。

图片详情

解析

$\color{green}{\text{B}}$

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、图、图的应用、拓扑排序、			nan

9.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是（)。

A.4

B. 5

C.6

D.7

解析

$\color{green}{\text{B}}$

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、查找、顺序查找和折半查找、折半查找			nan

10.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是。

A．递归次数与初始数据的排列次数无关

B．每次划分后，先处理较长的分区可以减少递归次数

C．每次划分后，先处理较短的分区可以减少递归次数

D．递归次数与每次划分后得到的分区的处理顺序无关

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、排序、交换排序、快速排序			nan

11．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下，则采用的排序方法可能是()。:

第一趟排序结果: 2，12，16，5，10，88，

第二趟排序结果: 2，12，5，10，16，88

第三趟排序结果:2，5，10，12，16，88

A．起泡排序

B．希尔排序

c．归并排序

D.基数排序

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、排序、各种内部排序算法的比较及应用、		warning	nan

12．下列选项中，能缩短程序执行时间的措施是

Ⅰ．提高CPU时钟频率

Ⅱ．优化数据通路结构

Ⅲ．对程序进行编译优化

A．仅Ⅰ和Ⅱ

B．仅Ⅰ和Ⅲ

C．仅Ⅱ和Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理			nan

13．假定有4个整数用8位补码分别表示为r1=FEH，r2=F2H，r3=90H，r4=F8H。若将运算结果存放在一个8位寄存器中，则下列运算中会发生溢出的是（)。

A. r1×r2

B. r2×r3

C. r1×r4

D. r2×r4

解析

$\color{green}{\text{B}}$

有一个快速计算方法，FE+2=0，所以FE=-2

r1=FEH：-2

r2=F2H：-14

r3=90H：144

r4=F8H：-8

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、数据的表示和运算、定点数的表示与运算、			nan

14．假定变量i、f、d数据类型分别为int、float、double ( int用补码表示，float和 double分别用IEEE754单精度和双精度浮点数据格式表示)，已知i=785，f=1.5678e3，d=1.5e100，若在32位机器中执行下列关系表达式，则结果为“真”的是（)。

Ⅰ . i==(int)(float)i

Ⅱ. f==(float)(int)f

Ⅲ. f==(float)(double)f

Ⅳ. (d+f)-d==f

A．仅Ⅰ和Ⅱ

B．仅Ⅰ和Ⅲ

C．仅Ⅱ和Ⅲ

D.仅Ⅲ和Ⅳ

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、数据的表示和运算、			nan

15.假定用若干个2K×4位芯片组成一个8K×8位的存储器，则地址0B1FH所在芯片的最小地址是（)。

A. 0000H

B. 0600H

C.0700H

D. 0800H

解析

$\color{red}{\text{D}}$

第一行芯片的地址范围是2^12-1号

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、存储系统、			nan

16.下列有关RAM 和 ROM 的叙述中，正确的是)。

Ⅰ． RAM是易失性存储器，ROM是非易失性存储器

Ⅱ. RAM和ROM都是采用随机存取方式进行信息访问的

Ⅲ. RAM和 ROM都可用做Cache

Ⅳ. RAM和ROM都需要进行刷新

A．仅Ⅰ和Ⅱ

B．仅Ⅱ和Ⅲ

C．仅Ⅰ、Ⅱ和Ⅲ

D.仅Ⅱ、Ⅲ、Ⅳ

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、存储系统、半导体随机存储器、RAM、ROM			nan

17．下列命中组合情况中，一次访存过程中不可能发生的是

A.TLB未命中，Cache未命中，Page未命中

B. TLB未命中，Cache命中，Page命中

C.TLB命中，Cache未命中，Page命中

D.TLB命中，Cache命中，Page未命中

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、存储系统、半导体随机存储器、高速缓冲存储器、			nan

18．下列寄存器中，汇编语言程序员可见的是（)。

A．存储器地址寄存器(MAR）

B．程序计数器（PC)

C．存储器数据寄存器(MDR）

D.指令寄存器（IR)

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理		warning	nan

19.下列选项中，不会引起指令流水阻塞的是

A．数据旁路（转发)

B．数据相关

C．条件转移

D．资源冲突

解析

$\color{red}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、中央处理器、指令流水线、			nan

20．下列选项中的英文缩写均为总线标准的是（)。

A.PCI、CRT、USB、EISA

B. ISA、CPI、VESA、EISA

C. ISA、SCSI、RAM、MIPS

D. ISA、EISA、PCI、PCI-Express

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、总线、总线标准、			nan

21．单级中断系统中，中断服务程序执行顺序是

Ⅰ．保护现场

Ⅱ．开中断

Ⅲ．关中断

Ⅳ．保存断点

Ⅴ．中断事件处理

Ⅵ．恢复现场

Ⅶ．中断返回

A. Ⅰ->Ⅴ->Ⅵ->Ⅱ->Ⅶ

B．Ⅲ->Ⅰ>Ⅴ->Ⅶ

c. Ⅲ->Ⅳ->Ⅴ->Ⅵ->Ⅶ

D.Ⅳ->Ⅰ->Ⅴ->Ⅵ->Ⅶ

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、输入/输出系统、I/O 方式、程序中断方式、			nan

22．假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200,颜色深度为24位，帧频为85Hz，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为( )。

A. 245Mbit/s

B.979Mbit/s

C. 1958Mbit/s

D. 7834Mbit/s

解析

$\color{green}{\text{D}}$

计算的时候，草稿纸的进位排版要尽可能清晰，不然可能会导致进位出错

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、总线、总线标准、			nan

23．下列选项中，操作系统提供的给应用程序的接口是()。

A．系统调用

B．中断

c．库函数

D.原语

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、计算机系统概论、操作系统的运行环境、系统调用、			nan

24.下列选项中，导致创建新进程的操作是

Ⅰ．用户登录成功

Ⅱ．设备分配

Ⅲ．启动程序执行

A．仅Ⅰ和Ⅱ

B．仅Ⅱ和Ⅲ

C．仅Ⅰ和Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、进程与线程、			nan

25．设与某资源相关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是（)。

A. 0、1

B. 1、0

c. 1、2

D. 2、0

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、进程同步、信号量、			nan

26.下列选项中，降低进程优先级的合理时机是（)。

A．进程的时间片用完

B．进程刚完成1O，进入就绪列队

C．进程长期处于就绪列队

D.进程从就绪状态转为运行态

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、处理机调度、			nan

27．进行p0和p1的共享变量定义及其初值为:

图片详情

A．不能保证进程互斥进入临界区，会出现“饥饿”现象

B．不能保证进程互斥进入临界区，不会出现“饥饿”现象

C．能保证进程互斥进入临界区，会出现“饥饿”现象

D．能保证进程互斥进入临界区，不会出现“饥饿”现象

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、进程管理、实现临界区互斥的基本方法、			nan

28．某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲)，采用最佳适应分配（Best Fit）算法，分配和释放的顺序为:分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是（)。

A.7MB

B.9MB

c.10MB

D. 15MB

解析

$\color{red}{\text{B}}$

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理、内存管理概念、连续分配管理方式、			nan

29．某计算机采用二级页表的分页存储管理方式，按字节编制，页的大小为 $2^{10}$ 字节，页表项大小为2字节，逻辑地址结构为:逻辑地址空间大小为 $2^{16}$ 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（)。

A. 64

B. 128

C.256

D. 512

图片详情

解析

$\color{red}{\text{B}}$

第二级页表可以存放 $2^10B/2B=2^9$ 个页表项

第一级页表需要存放 $2^16/2^9=2^7=128$ 个页表项

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理、内存管理概念、非连续分配管理方式、			nan

30．设文件索引结点中有7个地址项，其中4个地址项为直接地址索引，2个地址项为一级间接地址索引，1个地址项为二级间接地址索引，每个地址项的大小为4B。若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度是()。

A. 33KB

B. 519KB

C. 1057KB

D. 16513KB

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、文件管理、索引节点			nan

31．设置当前工作目录的主要目的是（)。

A．节省外存空间

B．节省内存空间

c．加快文件的检索速度

D.加快文件的读/写速度

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、文件管理、目录结构、			nan

32．本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是

A．命令解释程序

B．中断处理程序

C．系统调用服务程序

D.用户登录程序

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、输入/输出(I/O)管理、I/O子系统的层次结构、		warning	nan

33．下列选项中，不属于网络体系结构所描述的内容是（)。

A．网络的层次

B．每一层使用的协议

C．协议的内部实现细节

D.每一层必须完成的功能

解析

$\color{green}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、计算机网络体系结构与参考模型、			nan

34．在下图所表示的采用“存储-转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbit/s，分组大小为1000B，其中分组头大小为20B。若主机Hl向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是()。

图片详情

A. 80ms

B. 80.08ms

C. 80.16ms

D. 80.24ms

解析

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、物理层、电路交换、报文交换与分组交换、			nan

35．某自治系统内采用RIP协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息<net1，16>，则能得出的结论是（)。

A.R2可以经过R1到达net1，跳数为17

B.R2可以到达net1，跳数为16

C．R1可以经过R2到达net1，跳数为17

D.R1不能经过R2到达net1

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、网络层、RIP		warning	nan

36.若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文类型是（)。

A．路由重定向

B．目的不可达

C．源抑制

D．超时

解析

$\color{red}{\text{C}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、网络层、ICMP			nan

37．某网络的IP地址空间为192.168.5.0/24,采用定长子网划分，子网掩码为255.255.255.248，则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是（ )。

A. 32、8

B. 32、6

c. 8、32

D. 8、30

解析

$\color{green}{\text{B}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、网络层、IPv4、			nan

38.下列网络设备中，能够抑制广播风暴的是（)。

Ⅰ.中继器

Ⅱ.集线器

Ⅲ．网桥

Ⅳ．路由器

A仅Ⅰ和Ⅱ

B．仅Ⅲ

C．仅Ⅲ和Ⅳ

D.仅Ⅳ

解析

$\color{green}{\text{D}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、设备			nan

39．主机甲和主机乙之间已建立一个TCP连接，TCP最大段长度为1000B，若主机甲的当前拥塞窗口为4000B，在主机甲向主机乙连续发送2个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000B，则此时主机甲还可以向主机乙发送的最大字节数是（)。

A. 1000

B.2000

C. 3000

D. 4000

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、应用层、TCP			nan

40．如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为()。

A．一条、一条

B．一条、多条

C．多条、一条

D.多条、多条

解析

$\color{green}{\text{A}}$

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、应用层、DNS			nan

41.(10分）将关键字序列(7、8、30、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从О开始的一维数组，散列函数为H(key)=(key×3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

(1）请画出所构造的散列表。

(2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。

解析

这里的线性探测再散列，就是指线性探测方法

图片详情

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、线性表、			nan

42.(13分）设将n (n > 1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0 < p < n)个位置，即将R中的数据序列由( $X_0$ ， $X_1$ ， $\cdots$ ， $X_{n-1}$ ）变换为( $X_p$ ， $X_{p+1}$ ， $\cdots$ ， $X_{n-1}$ ， $X_0$ ， $X_1$ )， $\cdots$ ， $X_{p-1}$ )。要求:

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

解析

（1）算法的基本设计思想：

可以将这个问题看做是把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到 $a^{-1}$ b，再将b逆置得到 $a^{-1}b^{-1}$ ，最后将整个 $a^{-1}b^{-1}$ 逆置得到 $(a^{-1}b^{-1})^{-1}$ =ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p =3）个位置的过程如下：

Reverse(0,p -1)得到cbadefgh；

Reverse(p,n-1)得到cbahgfed；

Reverse(0,n-1)得到defghabc；

注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。

（2）使用c语言描述算法如下：

代码详情

void Reverse(int R[],int from,int to) {  
    int i,temp;  
    for(i = 0; i < (to - from + 1)/ 2; i++){
        temp = R[from+i]; 
        R[from+i] = R[to-i]; 
        R[to-i] = temp;
    }
}//Reverse

void Converse(int R[],int n,int p){  
    Reverse(R,0,p-1);  
    Reverse(R,p,n-1);  
    Reverse(R,0,n-1);  
}

（3）上述算法中三个Reverse函数的时间复杂度分别为 $O(p/2)$ 、$O((n-p)/2)$ 和 $O(n/2)$ ，故所设计的算法的时间复杂度为 $O(n)$ ,空间复杂度为 $O(1)$ 。

题目tag详情

总结

题型	错因	教训	视频讲解
数据结构、线性表			nan

43.(11分）某计算机字节长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如下:

图片详情

解析

标注答案

我的答案

注意减去1

注意16进制的进位，满16才进1，5678H+1234H = 68ACH $\neq$ 68B2H

注意题目要求的是16进制，

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、指令系统			nan

44.(12分)某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和 B，其伪代码如下所示:

图片详情

解析

标准答案

我的答案

题目tag详情

总结

题型	错因	教训	视频讲解
计算机组成原理、cache			nan

45.(7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB 的内存空间记录16384个磁盘块的空闲状态。

(1）请说明在上述条件如何进行磁盘块空闲状态的管理。

(2）设某单面磁盘的旋转速度为每分钟6000转，每个磁道有100个扇区，相临磁道间的平均移动的时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动(如下图所示)，磁道号的请求队列为50、90、30、120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区共需要多少时间?要求给出计算过程。

(3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等)，
是否有比 CSACN更高效的磁盘调度策略?若有，给出磁盘调度策略的名称并说明理由;若无，请说明理由。

解析

标准答案

我的答案

CSCAN会回到最外层的磁道

直接用先来先服务即可

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、磁盘管理			nan

46.(8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。某进程最多需要6页(Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Frame)。在时刻260前该进程访问情况如下表所示（访问位即使用位)。当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题:

(1)该逻辑地址对应的页号是多少?

(2）若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。

(3）若采用时钟(Clock）置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针按顺时针方向移动,且指向当前2号页框，示意图如下所示)

图片详情

解析

我的答案

标准答案

题目tag详情

总结

题型	错因	教训	视频讲解
操作系统、内存管理			nan

47.(9分）某局域网采用CSMA/CD 协议实现介质访问控制，数据传输率为10Mbit/s，主机甲和主机乙之间的距离为2km，信号传播速度是200000km/s。请回答下列问题，要求说明理由或写出计算过程。

(1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，再到两台主机均检测到冲突时刻为止，最短需经过多长时间?最长经过多长时间?〈假设主机甲和主机乙发送数据过程中，其他主机不发送数据)

(2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太数据帧(1518B）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个 64B.的确认帧，主机甲收到确认帧后立即发送下一个数据帧。此时主机甲的有效数据传输速率是多少?(不考虑以太网帧的前导码)

解析

标准答案

我的答案

题目tag详情

总结

题型	错因	教训	视频讲解
计算机网络、数据链路层、CSMA/CD			nan