操作系统每日一题 2020 Nov #

1. Week 1 #

1.1. 分页与分段的区别 #

以下关于分页系统与分段系统区别的描述，错误的是［华中科技大学］

A. 页是信息的物理单位，段是信息的逻辑单位

B. 页的大小固定，段的大小动态变化

C. 分页系统中的逻辑地址空间是一维的，分段系统中的是二维的

D. 分页系统比分段系统更方便信息的共享和保护

答案

答案：D
解析：ABC都是正确的，D是错误的，说法刚好反了：分段系统比分页系统更方便信息的共享和保护。分页管理方式是从计算机的角度考虑的，目的是提高内存的利用率，提升计算机的性能，并且分页通过硬件机制实现，对用户完全透明；而分段管理方式的提出则是考虑了用户和程序员，目的是满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

1.2. B-树 #

m阶B-树任一个结点最多有个关键字[南京航空航天大学]

A. m

B. m-1

C. m+1

D. 任意

答案

答案：B
解析：对于一个m阶B-树，结点关键字个数最多有m-1个。
总结如下：
(1)对于根节点，子树(孩子或者称为分支)个数取值范围[2,m]，关键字个数范围[1,m-1]
(2)对于内结点，分支数范围[ceil(m/2),m]，关键字个数的范围是ceil(m/2)-1,m-1]
(3)对于最小度数为t>=2的结点，根节点关键字的个数范围: [1, 2*t - 1]，非根节点关键字的个数范围: [t-1, 2*t - 1]，分支的个数范围：[t, 2*t]

1.3. 基数排序 #

下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是 [湖南大学]

A．直接插入排序

B. 起泡排序

C. 基数排序

D. 快速排序

答案

答案：C
解析：元素的移动次数与关键字的初始排列次序无关的是：基数排序
元素的比较次数与初始序列无关是：选择排序
算法的时间复杂度与初始序列无关的是：选择排序，堆排序，归并排序

1.4. 完全二叉树 #

已知一棵完全二叉树共有999个结点,则树高为，叶子结点数为 [南京航空航天大学 2015年]

A． 10 500

B． 9 500

C． 10 499

D． 9 499

答案

答案：A
解析：树高度为 log2n + 1，向下取整得10，完全二叉树具有999结点可知该树9层满，10层未满。得第10层有488个结点，可知第9层有244个结点度为2。综上所述叶子结点数为 488+(256 - 244) = 500。此题对于求结点的部分也可以这么解决：由于是完全二叉树，则N1（度为1的点的个数）为0或者1，若N1为1，则N0+N2+N1=N0+N0-1+1=999，此时N0为非整数，不符合题意，舍去。故N1为0，我们有2N0=1000，得N0=500。

1.5. 哈夫曼树 #

若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为 [武汉大学2014年改编]

A. ⌊(n(m-1)+1)/m⌋

B. ⌊(n-1)/m⌋

C. ⌊(n-1)/(m-1)⌋

D. ⌊n/(m-1)⌋-1

答案

答案：C
解析：设非叶子结点数量为x，则总结点个数为x+n；度为m的哈曼夫树，每个非叶结点都有m个分叉，故结点总数为x*m+1（加1是为了加上根节点）；x+n=x*m+1，解得x=（n-1）/（m-1）。

1.6. 堆栈的顺序存储结构 #

若用STACK[n]表示某堆栈采用顺序存储结构，则下列关于堆栈及堆栈操作的叙述中正确的是。[北京航空航天大学2015年]

A．堆栈的大小为n；

B．堆栈为空时n=0;

C．最多只能进行n次进栈和出栈操作；

D．n各元素依次进栈后，它们的出栈顺序与进栈顺序反。

答案

答案：A
解析：B选项，堆栈为空时n=-1，C 选项，应该是可以进行无限次进栈出栈，D选项，每个元素进栈后又立马出栈，就可以保证元素依次进栈，且进栈顺序与出栈一致。

1.7. 栈的操作 #

对于一个初始为空的栈s执行操作push(s,5)，push(s,2)，push(s,4)，pop(s,x)，getTop(s,x)后，x的值应是（中国科学院大学 2016）

A. 5

B. 2

C. 4

D. 0

答案

答案：B
解析：栈的储存顺序是先进后出,所以pop出栈操作将4出栈后,栈顶元素就是2。

2. Week 2 #

2.1. 2.1.完全二叉树 #

一棵深度为4的完全二叉树，最少有个结点。（华南理工大学 2005年）

A．4

B．8

C．15

D．6

答案

答案: B
解析:深度为4的完全二叉树，前3层结点总数为23-1=7。第4层只有一个结点时，完全二叉树结点数最少。即8个。

2.2. 矩阵的存储 #

将一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行的对角元素A[i][i]在B中的存放位置是（中国科学院大学 2016）

A. (i+3)×i/2

B. (i+1)×i/2

C. (2n-i+1)×i/2

D.(2n-i-1)×i/2

答案

答案: A
解析: 第0行只有1个元素,第1行有2个元素…….第i-1行需要存储i个元素。第i行前的元素数为1+2+3….+i。第i行第i个元素,所以1+2+3+…+i+i。

2.3. RIP协议 #

RIP协议采用的路由选择算法是____（重庆邮电大学2007）

A. 距离向量算法

B. 链路状态算法

C. 邻机测试报文对算法

D. 以上都不是

答案

答案：A
解析：RIP基于距离向量算法，OSPF基于链路状态算法。

2.4. 曼彻斯特编码 #

传统以太网发送的数据采用曼彻斯特编码，所占的频带宽度_____。

A. 与原始基带信号相同

B. 是原始基带信号的一半

C. 是原始基带信号的二倍

D. 是原始基带信号的四倍

答案

答案：C
曼彻斯特编码的特点是，在每个码元的中间出现电平跳变，位中间的跳变既作为时钟信号，又作为数据信号，由于曼彻斯特编码每一个码元的正中间时刻出现一次电平的转换，可从曼彻斯特编码的波形图看出其它所占的频带宽度比原始的基带信号增加了一倍。

2.5. 链路状态路由算法 #

下列哪个协议是采用了链路状态（LinkState）路由算法_____（北京邮电大学2011）

A. RAP

B. HTTP

C. OSPF

D. BGP

答案

答案：C
解析：RAP采用的是距离向量协议，BGP采用的是路径向量路由选择协议，OSPF采用的链路状态协议。

2.6. TCP 段 #

主机甲向主机乙发送一个 (SYN=1, seq=1000) 的 TCP 段，期望与主机乙建立 TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的 TCP 段可能是____（北京航空航天大学2015）

A. ( SYN = 1, ACK = 0, seq = 1001, ack = 1001 )

B. ( SYN = 1, ACK = 1, seq = 1000, ack = 1000 )

C. ( SYN = 1, ACK = 1, seq = 1001, ack = 1001 )

D. ( SYN = 0, ACK = 1, seq = 1000, ack = 1000 )

答案

答案：C
解析：确认序号：仅当ACK标志为1时有效。确认号表示期望收到的下一个字节的序号。详见TCP协议3次握手建立过程图解。

2.7. 网络分类 #

一座大楼内的一个计算机网络系统，属于。（中国科学院大学 2017）

A. PAN

B. LAN

C. MAN

D. WAN

答案

答案：B
解析：LAN是局域网的编写，是按照网络的事业范围划分的，比如学校、工厂、企业一般都是局域网。

3. Week 3 #

3.1. BASE标示 #

10BASE-T中，T通常是指。（重庆大学 2005年）

A．细缆

B．粗缆

C．双绞线

D．以太网

答案

答案：C
解析：BASE前的10表示数据率为10Mbit/s，T表示双绞线。因此选C。

3.2. CSMA/CA网络 #

在一个CSMA/CA网络上，计算机A有一个2时槽的帧间间隔，计算机B的帧间间隔是4时槽。下述关于优先级的表述哪个是正确的？（中国科学院大学 2017）

A. 计算机A具有最高的优先级

B. 计算机B具有最高的优先级

C. 帧间间隔同CSMA/CA网络的优先级无关

D. 在CSMA/CA网络中不能够分配优先级

答案

答案：A
解析：CSMA/CA协议是无线局域网中为了尽可能避免沖突的介质访问控制协议。协议釆用二进制指数退避算法。当一个设备检测到传输介质空闲时，该设备在它可以竞争访问介质之前必须等待一个指定的帧间间隔时间。帧间间隔也可以用于优先级传输，如果一个设备被分配一个较小的帧间间隔值，那么它就有更多的机会得到对传输介质的访问。题目中A是2个时间间隔，B是4个时间间隔，因此计算机A具有最高优先级。

3.3. PPP协议 #

以下对PPP协议的说法中错误的是。（北京理工大学 2004年）

A．具有差错控制能力

B．仅支持IP协议

C．支持动态分配IP地址

D．支持身份验证

答案

答案：B
解析：PPP协议两端的网络层可以运行不同的网络层协议，但仍然可使用同一个PPP协议进行通信。因此B错误。PPP协议提供差错检测但不提供纠错功能，它是不可靠的传输协议，因此也不使用序号和确认机制，A正确。PPP支持两种认证，一种是PAP，一种是CHAP。相对来说PAP的认证方式安全性没有CHAP高。PAP在传输Password时是明文的，而CHAP在传输过程中不传输密码，取代密码的是Hash（散列值）。PAP认证是通过两次握手实现的，而CHAP则是通过三次握手实现的。PAP认证是被叫提出连接请求，主叫响应；而CHAP则是主叫发出请求，被叫回复一个数据包，这个包里面有主叫发送的随机的散列值，主叫在数据库中确认无误后发送一个连接成功的数据包连接，因此D正确。PPP协议可用于拨号连接，因此支持动态分配IP地址，C正确。

3.4. 网桥 #

下面关于网桥的描述，错误的是。（重庆大学 2005年）

A．网桥工作在数据链路层，可以对网络进行过滤和分段

B．网桥可以对不需要传递的数据进行过滤并有效地阻止广播数据

C．网桥传递所有的广播信息，因此难以避免广播风暴

D．网桥与集线器相比，需要处理接收到的数据，因此增加了时延

答案

答案: B
解析: 网桥只适合于用户数不多和通信量不太大的局域网，否则有时还会因传播过多的广播信息而产生网络拥塞。这就是所谓的广播风暴。因此选B。

3.5. 隔离网络错误 #

下面哪种设备不可以隔离网络错误或冲突域？（中央财经大学 2004年）

A．中继器

B．网桥

C．交换机

D．路由器

答案

答案: A
解析: 在同一个网络上两个比特同时进行传输则会产生冲突；在网络内部数据分组所产生与发生冲突的这样一个区域称为冲突域。数据链路层以上的设备都可以隔离冲突域，中继器是物理层设备，不能隔离冲突域，因此选A。

3.6. 计算机网络 #

下列有关计算机网络叙述借误的是。（中国科学院大学 2017）

A. 利用Internet网可以使用远程的超级计算中心的计算机资源

B. 计算机网络是在通信协议控制下实现的计算机互联

C. 建立计算机网络的最主要目的是实现资源共享

D. 以接入的计算机多少可以将网络划分为广域网、城域网和局域网

答案

答案：D
解析：计算机网络是按照分布范围或者说是按照网络的覆盖范围，将网络划分为广域网（几十-几千米）、城域网（城市、街区）以及局域网（工厂、学校）。

3.7. CSMA/CA网络 #