2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(3)

【答案】算法如下：

2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（三）

说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。

——————————————————————————————————————————

一、选择题

1． 在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。

【答案】B

【解析】二分查找的时间复杂度为

在一个用N个元素的有序单链表中查找具有给定

关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，

因此时间复杂度为

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

A.1、15 B.2、15 C.1、30 D.2、30 【答案】D

【解析】主存储器包括RAM和ROM两部分，由于ROM区为4KB，则RAM区为60KB。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2Kx8位的ROM芯片，只需/4*2采用2片芯片进行字扩展便可得到4KB的ROM区；选用4Kx4位的RAM芯片，需采用（60）片芯片进行字和位同时扩展便可得60KB的RAM区。

3． 计算机硬件能够直接执行的是（ ）。

I .机器语言程序A.仅B.仅

汇编语言程序

硬件描述语言程序

C.仅

D. 【答案】A

【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言，但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。

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

A.7MB B.9MB C.10MB D.15MB 【答案】B

【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存。故55MB先分配15MB余40MB,再分配30MB后余10MB,释放15MB后出现一个15MB和一个10MB的空闲空间，分配8MB时按最佳适配（BestFit）算法应该使用10MB的空闲块，余2MB的碎片，分配6MB，因此最大空闲区为9MB。 时占用15MB的空间余9MB的碎片（空闲空间）

5． 某磁盘的转速为10,000转/分，平均寻道时间是磁盘传输速率是为

读取一个4KB的扇区所需平均时间约为（ ）

A.9ms B.9.4ms C.12ms D.12.4ms 【答案】B

【解析】磁盘转速是10 000转/分钟，平均转一转的时间是6ms，因此平均查询扇区的时间是3ms，平均寻道时间是6ms，读取4KB扇区信息的时间为0.2ms，信息延迟的时间为0.2ms，总时 间为

6． 在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。

A.1, 2 B.1, 3 C.2, 3 D.2, 4

【答案】B

【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是级索引的偏移量范围是

二级索引访问的偏移量范围是

一

偏移量1234

磁盘控制器延迟

可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在磁盘的位置，需要分别访问存放二级索引的两个索引块以及对应的数据块。

7． 下列关于UDP协议的叙述中，正确的是（ ）

I提供无连接服务 II提供复用/分用服务