【考研题库】2021年南京大学845数据结构和算法、操作系统、计算机系统基础、计算机网络之数据结构考

版权声明

本书根据历年考研大纲要求并结合历年考研真题按照考研题型进行了整理编写，涵盖了这一考研科目重点试题及高频试题并给出了详细参考答案，针对性强，有的放矢，提高复习效率，是考研复习首选资料。

青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。

因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。

特别说明

本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。

一、单项选择题

1．下述__________是顺序存储结构的优点。

A.插入运算方便

B.可方便地用于各种逻辑结构的存储表示

C.存储密度大

D.删除运算方便

【答案】C

2．在n个节点的线索二叉树中，线索的数目为__________。

A.n-1

B.n

C.n+1

D.2n

【答案】C

3．两个栈S1和S2及一个输入序列ABCD，每个输入元素只能选择其中一个栈入栈，则不可能的输出序列为__________。

A.ABCD;

B.BADC;

C.CABD;

D.DABC;

【答案】

4

．广义表，则下面式子的值为__________。(Head与Tail分别是取表头和表尾的函数。)

A.

B.d

C.f

D.

【答案】A

5．关键路径是AOE网中__________。

A.从始点到终点的最短路径

B.从始点到终点的最长路径

C.从始点到终点的边数最多的路径

D.从始点到终点的边数最少的路径

【答案】B

6．堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列(50,70,40,80,90,30,60,10,20)，若在堆排序的第一阶段将该序列建成一个堆(堆顶元素为最大值)，那么交换元素的次数为__________。

A.3

B.4

C.5

D.6

E.7

【答案】B

7．以下不属于存储结构是__________。

A.栈

B.线索树

C.哈希表

D.双链表

【答案】A

【解析】桟属于一种逻辑结构，通常有顺序栈和链栈两种存储结构。

8．将一个的三对角矩阵，按行优先存入一维数组中，A中元素(即该元素下标i=66，j=65)在B数组中的位置k为__________。

A.198

B.195

C.197

【答案】B

9

．有一个100阶的三对角矩阵M，其元素按行优先次序压缩存入下标从0开始的一维数组N中，元素在N中的下标是__________。

A.86

B.87

C.88

D.89

【答案】B

【解析】在三对角矩阵中，除了第一行和最后一行是每行2个元素外，中间的每行都是3个元素。所以，对于，就是2+3×28+2=88,这是从1开始编号的，那么从0开始编号就是87号。故本题答案为B。

10．对于广义表中的节点g，判断为空表的条件是__________。

A.

B.

C.且

D.

【答案】A

11．对初始状态为递增序列的表按递增顺序排序，最省时间的是__________算法，最费时间的是__________算法。

A.堆排序

B.快速排序

C.插入排序

D.归并排序

【答案】C、B

12．快速排序算法在最好的情况下的时间复杂度是__________。

A.

B.

C.

D.

【答案】C

【解析】快速排序的最好时间复杂度为。

13．以下排序方法中，稳定的排序方法是__________。

A.快速排序

B.堆排序

C.希尔排序

D.基数排序

【答案】D

【解析】基数排序是一种稳定的排序方法。本题答案为D。

14．无向图，其中：，。对该图进行深度优先遍历，得到的顶点序列正确的是__________。

A.abecdf

B.acfebd

C.aebcfd

D.aedfcb

【答案】D

15．在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是__________。

A.直接插入排序

B.冒泡排序

C.简单选择排序

D.归并排序

【答案】A