[数据结构与算法]Day36~Day42

Day36

数据结构

1. 其中n为正整数，则最后一行的语句频度在最坏情况下是_____ （南京理工大学考研真题)

A．D（n）

B．O（nlogn）

C．O（n3）

D．O（n2）

• 答案: D
• 解析:这个是冒泡排序，最坏的情况下需要进行1+2+…+n-1次交换，即时间复杂度是O（n²）。

计算机网络

2. 公用电话交换网（PSTN）采用了_____ 交换方式（2015年 中科院真题）

A. 分组 B.报文 C.信元 D.电路

• 答案: D
• 解析:电路交换在通信之前要在通信双方之间建立一条被双方独占的物理通路。公用电话网络正是最早使用电路交换传输方式的网络。

计算机操作系统

3. 下列说法中_____ 不是创建进程必须的（上海交通大学考研真题)

A．建立一个进程的进程表项

B．为进程分配内存

C．为进程分配CPU

D．将进程表项放入就绪队列

• 答案: C
• 解析: 进程刚被创建后，实际上是处于就绪状态的，所以不许为进程分配CPU。

计算机组成原理

4. 计算机的字长取决于_____ (华中科技大学 2005年)

A．控制器的种类

B．运算器一次运算二进制数的位数

C．存储器的大小

D．主机与外设一次交换信息的长度

• 答案: B
• 解析: 机器字长定义为CPU一次能处理的二进制数的位数，也即运算器中一次运算二进制数的位数。

Day37

数据结构

1. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用_____ 最节省时间 (江苏大学考研真题)

A．带头结点的双循环链表

B．单循环链表

C．带尾指针的单循环链表

D．单链表

• 答案：A
• 解析：要快速地在末尾插入元素，需要能立马得到末尾元素结点，故最好是循环链表。要快速地在末尾删除元素，需要立马得到末尾元素结点的前继结点，故最好是双向链表。综上可见为双循环链表。

计算机网络

2. 在连续ARQ协议中，当滑动窗口序号位数为n时，则发送窗口最大尺寸为_____ （2015年 中科院真题）

A. 2^（n-1）

B. 2ⁿ-1

C. 2n

D. 2ⁿ

• 答案：B
• 解析：连续ARQ协议包括后退N帧和选择重传两种协议，对于后退N帧来说,当帧序号位数为n时，发送窗口大小有1<发送窗口≤2ⁿ-1，接收窗口大小为1；对于选择重传来说，当帧序号位数为n时，发送窗口大小≤2^{（n-1），发送窗口取最大值时，接收商口=发送窗口=2}（n-1）,综上，当采用GBN协议时，发送窗口的取值更大，为2ⁿ - 1，选B。

计算机操作系统

3._____ 不是操作系统的功能（2015年 中科院真题）

A.CPU管理

B.存储管理

C.网络管理

D.数据管理

• 答案：C
• 解析：操作系统的主要功能包括处理器（CPU）管理、存储器管理、文件管理和设备管理。数据管理履于文件管理的范畴。网络管理不是操作系统的功能，故选C。

计算机组成原理

4. 在定点数运算中，产生溢出的原因是_____ (哈尔滨工程大学 2005年)

A．运算过程中最高位产生了进位或借位

B．运算的结果超出了机器的表示范围

C．参加运算的操作数超出了机器的表示范围

D．寄存器的位数太少，不得不舍弃最低有效位

• 答案：B
• 解析：参与运算的操作数若超出了机器的表示范围，则会报错，或者截断，不是溢出的概念。

Day38

数据结构

1. 下面关于线性表的叙述中，错误的是哪一个?_____ （北京交通大学考研真题）

A．线性表采用顺序存储，必须占用一片连续的存储单元

B．线性表采用顺序存储，便于进行插入和删除操作

C．线性表采用链接存储，不必占用一片连续的存储单元

D．线性表采用链接存储，便于插入和删除操作

• 答案：B
• 解析：顺序存储，插入删除时会移动大量的元素，效率相对较低。

计算机网络

2. 以下哪个是快速以太网的介质访问控制方法_____ （2015年 中科院真题）

A. CSMA/CD

B. 令牌总线

C. 令牌环

D. 100VG-AnyLan

• 答案: A
• 解析: CSMA/CD协议是广泛应用于快速以太网的介质访问控制方式。令牌总线方式已经很少使用，令牌环访问控制主要应用于令牌环局域网中。

计算机操作系统

3.下面叙述中，错误的是_____ （2015年 中科院真题）

A.操作系统既能进行多任务处理，又能进行多重处理

B.多重处理是多任务处理的子集

C.多任务是指同一时间内在同一系统中同时运行多个进程

D. 一个CPU的计算机上也可以进行多重处理

• 答案: B
• 解析: 考查并行和并发的概念，多重处理即并行执行，多任务处理即多个进程并发执行。操作系统既可以支持并发执行也可以支持并行执行，A正确。并行应该是并发的真子集，B错误。在同一时间间隔内，系统中同时运行多个进程是并发执行的基本概念。C正确。一个CPU可以采用多核架构，可以实现并行执行，D正确。

计算机组成原理

4. 数位每左移1位相当于原数乘以2，为防止左移操作造成溢出，补码左移的前提条件是：其原最高有效位_____ (哈尔滨工程大学 2005年)

A．为0

B．为1

C．与原符号位相同

D．与原符号位相异

• 答案: C
• 解析: 补码表示时，最高数位为“0”时是有效位、为“1”时是无效位，故算术左移时，最高数位丢“0”，结果出错，而丢“1”，则不对结果产生负面影响。最低数位为“1”时是有效位、为“0”时是无效位，故算术右移时，最低数位丢“1”，影响精度，而丢“0”，则不对结果产生负面影响。

Day39

数据结构

1. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_____ 存储方式最节省时间（哈尔滨工业大学考研真题）

A．顺序表

B．双链表

C．带头结点的双循环链表

D．单循环链表

• 答案：A
• 解析：线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。

计算机网络

2. 决定局域网特性有3个主要技术，它们是_____ （2015年 中科院真题）

A. 传输介质、差错检测方法和网络操作系统

B. 通信方式、同步方式和拓朴结构

C. 传输介质、拓扑结构和介质访问控制方法

D. 数据编码技术、介质访问控制方法和数据交换技术

• 答案：C
• 解析：传输介质、拓扑结构和介质访问控制方法是决定局域网特性的3个主要技术。

计算机操作系统

3. 不会产生内部碎片的存储管理是_____ （2007年 西安电子科技大学）

A.分页式存储管理

B.分段式存储管理

C.固定分区式存储管理

D.段页式存储管理

• 答案：B
• 解析：只要是固定大小的分配就会产生内部碎片，其余的部分都会产生外部碎片。如果固定和不固定同时存在（如段页式），物理本质还是固定的，解释如下：

分段虚拟存储管理：每一段的长度都不一样（对应不固定），所以会产生外部碎片，但不会产生内部碎片；
分页虚拟存储管理：每一页的长度都一样（对应固定），所以会产生内部碎片，但不会产生外部碎片；
段页式分区管理：地址空间首先被分成若干个逻辑分段（这里的分段只是逻辑上的，而我们所说的碎片都是物理上真实存在的，是否有碎片还是要看每个段的存储方式，所以才是物理单位），每段都有自己的段号，然后再将每个段分成若干个固定的页。所以其仍然是固定分配，会产生内部碎片；
固定式分区管理：很明显是固定的大小，会产生内部碎片。
综上分析，本题选B。

计算机组成原理

4. 实现N位（不包括符号位）补码一位乘时，乘积为_____ 位（2007年 西安电子科技大学）

A．N

B．N+1

C．2N

D．2N+1

• 答案：C
• 解析：补码一位乘法运算过程中一共向右移位N次，加上原先的N位，一共是2N位数值位。

Day40

数据结构

1. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与_____量级相当。(南京邮电大学 2010)

A．顺序查找

B．折半查找

C．分块查找

D．前面都不正确

• 答案：B
• 解析：在随机的情况下，二叉排序树的平均查找长度的数据量级为O(log2n)，与折半查找同数量级。

计算机网络

2. 无法隔离冲突域的网络互连设备是_____ （2015年中科院真题）

A.路由器

B.交换机

C.集线器

D.网桥

• 答案: C
• 解析: 数据链路层设备（交换机、网桥）可隔离冲突域，而不能隔离广播域；网络层设备（路由器）既可隔离冲突域，又可隔离广播域；物理层设备（中继器、集线器）则无法隔离冲突域和广播域。故选C。

计算机操作系统

3. 在空白表中，空白区按其长度由小到大进行查找的算法称为_____ 算法（西安电子科技大学,2007年）

A.最佳适应

B.景差适应

C.最先适应

D.先进先出

• 答案: A
• 解析: 所谓最佳是指每次为作业分配内存时，总是把能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。

计算机组成原理

4. 若阶码为三位，用补码表示；尾数7位，用原码表示，其中一位为符号位；以2为底，则十进制数27／64的浮点规格化数是_____ (东部名校考研题)

A．0101011011

B．1100110110

C．1110110110

D．0001011011

• 答案: C
• 解析: 首先排除A、D，它们非规格化，因为规格化的原码，最高数值位为1。27／64的原码表示：0．0110110=0．110110×2-1。左移一位成规格化数。阶码用补码：111。

Day41

数据结构

1. 对于双向循环链表，在p指针所指的结点之后插入s指针所指结点的操作应为_____ (北京工业大学考研真题)

A．p->right=s；s->left=p；p->right->left=s；s->right=p->right；

B．p->right=s；p->right->left=s；s->left=p；s->right=p->right；

C．s->left=p；s->right=p->right；p->right=s；P->right->left=s；

D．s->left=p；s->right=p->right；P->right->left=s；P->right=s；

• 答案：D
• 解析：先建立好s指向p和p的后继节点的链接，即s->left=p；s->right=p->right；然后建立p的后继节点指向s的链接，即p->right->left=s；最后，断开p与后继节点的链接，将p指向s，即p->right=s。

计算机网络

2. 成帧、差错控制、流量控制和传输管理是_____ 的主要功能(华东理工大学2005年)

A．物理层

B．数据链路层

C．网络层

D．传输层

• 答案：B
• 解析：数据链路层在不可靠的物理介质上提供可靠的传输，其作用包括物理地址寻址，数据封装成帧，流量控制，差错校验，数据的检错、重发等。

计算机操作系统

3. 在虚拟页式存储管理方案中，_____ 完成页面调入内存的工作(中国科学技术大学,2005年）

A.缺页中断处理

B.页面淘汰过程

C.工作集模型应用

D.紧缩技术利用

• 答案：A
• 解析：A正确，缺页中断就是要访问的页不在主存中，缺页中断处理就是操作系统将缺失页面调入主存后再进行访问；B错误，页面淘汰就是当内存空间被占满而又要调入新页时，必须淘汰已在内存的某一页面，如果被淘汰的页面曾经被修改过，还要将此页写回到外存，再换进新的页面；C错误，工作集模型用于处理抖动问题，一个进程当前使用的页的集合叫作它的工作集(Working Set).如果整个工作集都在内存中，在进入下一个运行阶段之前进程的运行不会引起很多页面故障；D错误，紧缩技术是将空闲小分区整合，移动拼接成大分区的过程。

计算机组成原理

4. 为使虚拟存储系统有效地发挥其预期的作用，所运行的程序应具有的特性是_____ (西部名校考研真题)

A．该程序不应含有过多的I／O操作

B．该程序的大小不应超过实际的内存容量

C．该程序应具有较好的局部性

D．该程序的指令间相关不应过多

• 答案：C
• 解析：Cache和虚存都是基于程序的局部性原理——程序访问在时间、空间和顺序上都有一定的范围。

Day42

数据结构

1. 向一个栈顶指针为h的带头结点的链栈中插入指针S所指的结点时，应执行_____ (北京理工大学考研真题)

A．h->next=s；

B．s->next=h；

C．s->next=h；h->next=s；

D．s->next=h-next；h->next=s；

• 答案：D
• 解析：本题是向一个链栈中插入结点，可从头结点后插入。先将s结点指向第一个头结点之后的结点之前，再将头结点指向s结点。

计算机网络

2._____ 是数据链路层的功能(重庆邮电大学 2007年)

A．线路控制

B．流量控制

C．差错控制

D．以上都是

• 答案：D
• 解析：数据链路层在不可靠的物理介质上提供可靠的传输，其作用包括物理地址寻址，数据封装成帧，流量控制，差错校验，数据的检错、重发等。

计算机操作系统

3. 通常对文件系统来说，文件名及属性可以集中在_____ 中以便查询（浙江大学 2006年）

A. 目录 B.索引 C.字典 D.作业控制块

• 答案：A
• 解析：文件与文件控制块一一对应，人们把文件控制块的有序集合称为文件目录,即一个文件控制块就是一个文件目录项。而文件控制块中包含的信息有文件名、文件的结构、文件的物理位置、存取控制信息和管理信息。

计算机组成原理

4. 某一SRAM芯片，其容量为1024×8位，除电源和接地端外，该芯片引脚的最小数目为_____ (东部名校经典试题）

A．20

B．22

C．25

D．30

• 答案：A
• 解析：芯片容量为1024×8位：1024说明芯片容量为1024，故地址线为10根才能译码出1024个单元1024B=210B；8位说明数据线是8位，再加上片选端和读写控制线（因这里为RAM），所以要读写控制。故引脚最小引脚数为：10+8+1+1=20，选A项。