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

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

1、计算机算法必具备输入、输出和(  )等五个特性。

A、 有效性、可移植性和可扩充性

B、 有效性、确定性和有穷性

C、 确定性、稳定性和有穷性

D、 易读性、稳定性和安全性

2、链表不具有的特点是(  )。

A、 插入、删除不需要移动元素

B、 可随机访问任一元素

C、 不必事先估计存储空间

D、 所需空间与线性长度成正比

3、设head是带头结点的单循环链表的头指针，结点的指针域为next，数据域为data，则指针p是指向链表尾结点的条件是(  )。

A、 p->next==head

B、 p->next==head->next

C、 p==head

D、 p==head->next

4、针对下述结论，正确答案是(  )。①两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端②队列逻辑上是一个下端和上端既能增加又能减少的线性表

A、 只有①正确

B、 只有②正确

C、 ①②都正确

D、 ①②都不正确

5、己知广义表LS=（（a，b），c，d，（e， f）），运用head和tail函数取出LS中原子e的运算是(  )。

A、 head（tail（LS））

B、 tail（tail（head（LS）））

C、 head（tail（head（tail（LS）））

D、 head（head（tail（tail（ tail （LS）））））

6、在下述结论中，正确的是（ ）。①只有一个结点的二叉树的度为0②二叉树的度为2③二叉树的左右孩子可任意调换④具有n个结点的二叉链表具有n+1个空指针域

A、 ④

B、 ②③

C、 ②④

D、 ①④

7、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序(  )。

A、 都不相同

B、 完全相同

C、 先序和中序相同，而与后序不同

D、 中序和后序相同，而与先序不同

8、对具有n个顶点、e条边的无向网用邻接矩阵为存储结构时，求最小生成树的Prim 算法的时间复杂度为(  )。

A、 O（n）

B、 O）（n+e）

C、 O（n²）

D、 O（eloge）

9、当采用折半查找法查找一个数据时，要求数据存储结构(  )。

A、 一定采用顺序存储结构

B、 一定采用链式存储结构

C、 一定采用三元组存储结构

D、 既可采用链式又可采用顺序存储结构

10、下列排序算法中，在关键字基本无序的情况下，经第一趟排序完毕后，其最大或最小关键字的元素一定在其最终位置上的算法是(  )。

A、 直接插入排序

B、 归并排序

C、 直接选择排序

D、 快速排序

1、试题答案：B

试题解析：

【考点】本题考查算法的特性。
【解析】

故本题选B。

2、试题答案：B

试题解析：

【考点】本题考查链式存储的特点。
【解析】线性表有两种存储结构，一种是顺序结构，一种是链式结构。链表属于链式结构。对于A，链表的插入和删除仅需修改指针不需要移动元素，A是链表的特点。对于B，顺序存储结构是一种随机存取的结构，而链式存储结构非随机存取结构，链表访问某元素需要从头指针开始，B不是链表的特点而是顺序存储的特点。对于C，链表不必事先估计存储空间，其存储单元不必连续，C是链表的特点。链表每个结点都需要开辟存储空间，因此所需空间与线性长度成正比，D是链表的特点。故本题选B。

3、试题答案：A

试题解析：

【考点】本题考查但循环链表的特点。
【解析】单循环链表的尾结点的next指针指向头结点，因此p->next==head。head->next是首元结点而非头结点，因此B错误。p指针指向的是尾结点，因此C和D错误。故本题选A。

4、试题答案：A

试题解析：

【考点】本题考查栈和队列的特性。
【解析】对于①，两个栈共享一片连续内存时，使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，因此①正确。对于②，队列的特性是“先进先出”，这要求队列只能从一端进入从另一端删除，因此②错误。故本题选A。

5、试题答案：D

试题解析：

【考点】本题考查广义表的基本操作。
【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。对上述各个选项从内到外进行分析。对于A，tail（（a，b），c，d，（e， f））=（c，d，（e， f）），head （c，d，（e， f））=c，因此A错误。对于B，head（（a，b），c，d，（e， f））=（a，b），之后无论如何操作均与e无关，因此B错误。对于C，tail（（a，b），c，d，（e， f））=（c，d，（e， f）），head （c，d，（e， f））=c，因此C错误。对于D，tail（（a，b），c，d，（e， f））=（c，d，（e， f）），tail（c，d，（e， f））=（d，（e， f）），tail（d，（e， f））=（（e， f）），head（（e， f））= e， f，head（e， f）=e，故本题选D。

6、试题答案：D

试题解析：

【考点】本题考查二叉树的性质。
【解析】二叉树的度是指二叉树中所有结点的度的最大值，结点的度是指一个结点拥有子树的数目。因此可以说二叉树的度是结点最大分支数，因此①正确，二叉树的度不一定是2，但一定小于等于2，因此②错误。二叉树的左右孩子不可调换，因此③错误。对于④，n个结点的二叉链表有2*n个指针域，n个结点n-1个指针域，因此空指针域为n+1，因此④正确。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查二叉树的性质。
【解析】除单根树的情况外，叶子结点必不是根结点。不管是先序、中序还是后序，其遍历时均为先遍历左子树后遍历右子树，因此叶子结点在三个序列中的相对位置是相同的，其先后顺序均为先左后右。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查最小生成树的时间复杂度。
【解析】构造最小生成树有两种算法，一种是kruskal算法，一种是Prim算法，Kruskal算法的时间复杂度为O（eloge），与边数有关，Prim算法主要对顶点进行操作，与边数无关，因此其时间复杂度为O（n²），故本题选C。

9、试题答案：A

试题解析：

【考点】本题考查折半查找的存储结构。
【解析】折半查找法是针对顺序有序表设计的查找方法，其存储结构只能是顺序存储，因此B和D错误。三元组一般用来存储稀疏矩阵，因此C错误。故本题选A。

10、试题答案：C

试题解析：

【考点】本题考查排序算法的过程。
【解析】对于A，直接插入排序第一趟比较前两个数，然后把第二个数按大小插入到有序表中，无法确定最大或最小关键字的元素的最终位置，因此A错误。对于B，归并排序第一趟排序只能做到分组内的排序有序，而整体序列仍然是无序的，无法确定最大或最小关键字的元素的最终位置，因此B错误。对于C，直接选择排序第一趟排序在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，可以确定最大或最小关键字的元素的最终位置，因此C正确。对于D，快速排序的第一趟排序后其基准值的最终位置可以确定，但基准值并不一定是最大值或最小值，因此D错误。故本题选C。