2022年南京农业大学信息科学技术学院853计算机专业基础综合之数

目录

2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题库（一） 2 2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题库（二） .............................................................................................................................................. 15 2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题库（三） .............................................................................................................................................. 31 2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题库（四） .............................................................................................................................................. 44 2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题库（五） .............................................................................................................................................. 59

2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研题

库（一）

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

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

一、填空题

1． 假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

2． 已知二维数组

为1000的连续存储区域时，

【答案】1196

【解析】设元素的行标为i，列标为j。则它的存储位置为：

3． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

4． 在循环队列中，队列长度为n，存储位置从0到，

【答案】

编号，以rear指示实际的队尾元素，现

中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

要在此队列中插入一个新元素，新元素的位置是（ ）。

5． 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是_____。

【答案】要加“虚结点”。

设编号为

和

的结点在顺序存储中的下标为

和

。

6． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】

完全二叉树的高度

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

，

则结点

和

在同一层上的条件是

7． 在一个无向图的的邻接表中，若表结点的个数是m,则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n条边，则会有2n个表结点。

8． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

9． 对n个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n（n-1）/2

【解析】第一次需要n-1次比较，第i此需要n-i此比较，所以共需要、n-l+n-2+...+l=n（n-l）/2。

10．外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

二、选择题

11．用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）

A.存储效率 B.数列函数 C.装填（装载）因子 D.平均查找长度 【答案】D

【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。

12．用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。

A.5 B.6 C.8 D.9 【答案】A 6条边 【解析】一共5个结点

13．某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是（ ）

A.-32768 +32767 B.-32767 +32768 C.-65536 +65535

D.-65535 +65536 【答案】A

【解析】寄存器个数指令编址方式如下所示：

16位补码取值范围为-32768 +32767，所以偏移量取值范围为-32768 +32767

14．对任意一棵树，设它有n个结点，这n个结点的度数之和为（ ）。

A.n B. C. D. 【答案】C

【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。

15．TCP/IP参考模型的网络层提供的是（ ）。

A.无连接不可靠的数据报服务 B.无连接可靠的数据报服务 C.有连接不可靠的虚电路服务 D.有连接可靠的虚电路服务 【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A。

16．若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。

I.若该文件的数据不在内存，则该进程进入睡眠等待状态；II.请求read系统调用会导致CPU从用户态切换到核心态；III. read系统调用的参数应包含文件的名称

A.仅 I、II B.仅 I、III C.仅 II、III D.I、II和III 【答案】A

，原进程【解析】对于I，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪进入睡眠等待状态（阻塞状态）

状态。对于II, read系统调 用CPU将从用户态切换到核心态，从而获取操作系统提供的服务。对

偏移量有32-8-4-4=16位

于III，在操作系统中，要读一个文件首先要open系统调用将该文件打开。Open系统调用的参数需要包含文件的路径名与文件名，而read系统调用只需使用open返回的文件描述符，并不使用Read系统调用要求用户提供三个输入参数：文件名作为参数。①文件描述 符；②buf缓冲区首址；③传送的字节数n。read系统调用的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至由指针buf所指示的缓冲区中。

17．—

组记录的关键码为

准得到的一次划分结果为（ ）。

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为

一次划分结束。

18．相对于微程序控制器， …… 此处隐藏：2803字，全部文档内容请下载后查看。喜欢就下载吧 ……