2016年数据结构考研真题答案及解析（七）

本文提供2016年数据结构考研真题答案及解析，以下为具体内容

1、设一个链表最常用操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。

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

B、单循环链表

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

D、单链表

2、下列数据结构中，（ ）是非线性数据结构。

A、栈

B、队列

C、完全二叉树

D、字符串

3、判定一个循环队列qu（最多元素为MaxSize）为空的条件是（ ）。

A、qu→rear-qu→front==MaxSize

B、qu→rear-qu→front-1==MaxSize

C、qu→rear==qu→front

D、qu→rear=qu→front-1

4、图G是n个顶点的无向完全图，则下列说法错误的有（ ）。

A、G的邻接多重表需要n(n-1)个边节点和n个顶点节点

B、G的连通分量个数最少

C、G为连通图

D、G所用顶点的度的总和为n(n-1)

5、采用开放定址法解决冲突的散列查找中，发生聚集的主要原因是（ ）。

A、数据元素过多

B、负载因子过大

C、散列函数选择不当

D、解决冲突的方法选择不当

6、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A、二叉查找树

B、哈夫曼树

C、AVL树

D、堆

7、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序。

A、冒泡排序

B、希尔排序

C、快速排序

D、堆排序

8、程序段for(i=n-1; i<1; i--) for(j=1; j<n; j++) if(A[j]> A[j+1]) swap(A[j]，A[j+1]);其中n为正整数，则最后一行语句执行，在最坏情况下是（ ）。

A、

B、

C、

D、

1、试题答案：A

试题解析：

【考点】本题考查链表的选取。
【解析】
A带头结点的双循环链表：插入和删除都不需要遍历链表，较为容易。
B单循环链表：在末尾不管是插入还是删除元素，都需要从头遍历整个链表找到尾结点，比较费时。
C带尾指针的单循环链表：在末尾插入元素可以，但是在末尾删除元素时，需要从头到尾遍历获取要删除结点的前驱结点，比较费时。
D单链表：和单循环链表一样，在单链表中的末尾不管是插入还是删除元素，都需要从头遍历整个链表找到尾结点，比较费时。
综上所述，本题选A。

2、试题答案：C

试题解析：

【考点】本题考查非线性结构。
【解析】数据的逻辑结构分为线性结构和非线性结构。
① 常用的线性结构有：线性表，栈，队列，数组，串。
② 常见的非线性结构有：二维数组，多维数组，广义表，树（二叉树等），图，堆。
综上所述，完全二叉树是非线性结构。故本题选C。

3、试题答案：C

试题解析：

【考点】本题考查判定一个循环队列的队空条件。
【解析】为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时：front=rear；当队满时：front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志（front指向队首元素，rear指向队尾元素的下一个元素）。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选C。

4、试题答案：A

试题解析：

【考点】本题考查无向完全图的特点。
【解析】本题涉及的概念如下：
（1）完全图：假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。
（2）连通图：从顶点v到w有路径，就称顶点v和w连通。如果图中任意两个顶点都连通，则该图为连通图。
（3）连通分量：无向图中的极大连通子图称为连通分量 。
A：n个顶点的无向完全图，其有n(n-1)/2条边，所以G的邻接多重表需要n(n-1) /2个边节点。因此，选项A说法错误。
B：G是完全图则其一定是连通图，所以它的连通图只有其本身。
C：G 是完全图，则其一定是连通图。
D n个顶点的无向完全图，其有n(n-1)/2条边。而一条边对应一个出度和一个入度，所以G所用顶点的度的总和为n(n-1)。
综上所述，本题选A。

5、试题答案：D

试题解析：

【考点】本题考查发生聚集的主要原因。
【解析】散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积。采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是解决冲突的方法选择不当。故本题选D。

6、试题答案：D

试题解析：

【考点】本题考查满二叉树的特点。
【解析】
A：二叉排序树只有中序遍历结果是一个有序序列。
B：在哈夫曼树中，所有关键字只会出现在叶子结点上，其非叶子结点上并没有关键字。
C：AVL树（平衡二叉树）本质上是带了平衡功能的二叉排序树，所以也不满足题干性质。
D：大根堆的特点是任意结点满足“该结点值≥左右孩子结点值”；小根堆的特点是任意结点满足“该结点值≤左右孩子结点值”。因此，在大根堆中，从任一结点出发到根的路径上所经过的结点序列按其关键字有序递减；在小根堆中，从任一结点出发到根的路径上所经过的结点序列按其关键字有序递增。因此对满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
综上所述，本题选D。

7、试题答案：C

试题解析：

【考点】本题考查排序算法的综合比较。
【解析】分析如下：
A：若序列已有序时，选择冒泡排序进行一趟后，发现两两元素比较并未发生交换，即可确定此时序列已经有序，排序结束。
B：若序列已有序时，选择排序每一趟排序过程中都没有元素交换，直到步长为1时，整个排序过程结束。
C：在快速排序中，通过基准元素把序列分成两个部分，一般选择第一个元素为基准元素。若序列已经有序，进行第一趟排序时，第一个元素（最小元素）作为基准会将整个序列分成两部分，左部分为空，右部分为剩余元素。第一趟排序时，左部分无需排序，右部分继续进行快速排序，选取右部分第一个元素作为基准将整个序列分成两部分，左部分为空，右部分为剩余元素。这一过程中，每次分块只减少一个元素，n个元素需要进行n-1次分块才能结束整个快速排序，浪费时间耗时更长。这是快速排序最糟糕的情况，时间复杂度为O(n²)。
D：堆排序的最好、最坏、平均时间复杂度都是O(nlogn)。
综上所述，在待排序数据已有序时，花费时间反而最多的是快速排序。故本题选C。

8、试题答案：C

试题解析：