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

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

1、以下属于逻辑结构的是（ ）。

A、顺序表

B、哈希表

C、有序表

D、单链表

2、在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（ ）操作与链表的表长有关。

A、删除单链表中的第一个元素

B、删除单链表中的最后一个元素

C、在单链表第一个元素前插入一个元素

D、在单链表最后一个元素后插入一个元素

3、二叉树在线索化后，仍不能有效求解的问题是（ ）。

A、先序线索二叉树中求先序后继

B、中序线索二叉树中求中序后继

C、中序线索二叉树中求中序前驱

D、后序线索二叉树中求后序后继

4、下面说法错误的是（ ）。

A、算法原地工作的含义是指不需要任何额外的辅助空间

B、在相同的规模n下，复杂度O (n)的算法在时间上总优于复杂度O(n²)的算法

C、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

D、同一个算法，实现语言的级别越高，执行效率越低

5、以下是线性表的是（ ）。

A、由n个实数组成的集合

B、由500个字符组成的序列

C、由所有整数组成的序列

D、邻接表

6、设二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占用1个空间，A[3][3]存放在（ ）。

A、678

B、688

C、696

D、692

7、设线性表有n个元素，严格说来，以下操作中（ ）在顺序表上实现要比链表上实现的效率高。I.输出第i个元素值(1≤i≤n) II.交换第3个元素与第4个元素的值III.顺序输出这n个元素的值

A、I

B、I，III

C、I，II

D、II，III

8、关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。I.线性表的顺序存储结构优于其链式存储结构II.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构III.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构IV.顺序存储结构和链式存储结构可以进行顺序存取

A、I、II、III

B、II、IV

C、II、III

D、II、IV

9、一个带头结点的循环单链表L，若L->next->next=L，则表中的元素个数为（ ）。

A、0

B、1

C、2

D、可能为0或1

10、设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链式表的是（ ）。

A、只有表头结点指针，没有表尾指针的双向循环链表

B、只有表尾结点指针，没有表头指针的双向循环链表

C、只有表头结点指针，没有表尾指针的单向循环链表

D、只有表尾结点指针，没有表头指针的单向循环链表

1、试题答案：C

试题解析：

数据的存储结构：顺序存储、链式存储、索引存储、哈希存储。顺序表属于顺序存储，哈希表属于哈希存储，单链表属于链式存储，所以顺序表、哈希表和单链表都不是逻辑结构。有序表属于逻辑结构，且是线性结构，既可以顺序存储结构存储，也可以用链式存储结构存储。故本题选C。

2、试题答案：B

试题解析：

删除单链表中的最后一个元素时，需要遍历整个链表找到最后一个元素的前驱结点。而选项A、C、D中的操作不需要遍历链表即可完成。因此，只有执行删除单链表中的最后一个元素的操作与链表的表长有关。故本题选B。

3、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--线索二叉树--线索二叉树的性质。
【解析】后序线索二叉树不能有效解决求后序后继的问题。查找后序后继也必须知道该结点的双亲结点，二叉链表中没有存放双亲的指针，故本题选D。

4、试题答案：A;D

试题解析：

【考点】本题考查数据结构--绪论--算法和算法分析。
【解析】
A：算法原地工作是指所需要的临时空间对于问题规模来说是一个常数，并非不需要额外的辅助空间。故A中说法错误。
B：O(n)的算法的运行时间是线性的，而O(n²)的算法的运行时间是二次方级别的，随着输入规模的增加，O(n²)算法的运行时间会迅速增加，而O(n)算法的运行时间相对较低。因此，一般情况下，规模n相同时，复杂度O(n)的算法在时间上总优于复杂度O(n²)的算法。故B中说法正确。
C：时间复杂度是用来衡量算法执行时间随输入规模增长的增长率，常用大O符号表示。而所谓的时间复杂度的上界，指的是在最坏情况下，算法执行时间的一个上限。故C中说法正确。
D：说法过于绝对，且执行效率主要取决于算法的优化程度和底层硬件的性能等因素。故D中说法错误。
综上所述，本题选A和D。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的基本概念。
【解析】线性表是具有相同特性的数据元素的一个有限序列。由n个实数组成的集合是集合，并非序列，所以不是线性表。由500个字符组成的序列符合线性表的定义，所以它是线性表。由所有整数组成的序列并不是有限的序列，所以它也不是线性表。邻接表是图的一种存储结构，并不是线性表。综上所述，本题由500个字符组成的序列是线性表。故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查数据结构--数组与广义表--数组--数组的存储--二维数组的存储。
【解析】由题意知，每行元素个数为n，A[2][2]存放位置在676，假设二维数组A[m][n]按行优存储，则644+2*n+2=676，解得每行元素个数n=15，那么A[3][3]存放在644+3*15+3=692的位置。故本题选D。

7、试题答案：C

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构。
【解析】对于顺序表而言，每个元素在内存中的地址是连续的，因此可以通过下标直接访问元素，时间复杂度为O(1)。而对于链表而言，需要从头结点开始遍历链表，找到第i个元素，时间复杂度为O(n)。对于输出第i个元素值和交换第3个元素与第4个元素的值这两个操作而言，首先都需要找到对应的元素。因此，这两个操作在顺序表上的实现要比链表上的实现效率高。对于顺序输出这n个元素的值这一操作而言，在顺序表上实现和链表上实现的效率差不多，都需要遍历整个线性表，时间复杂度均为O(n)。综上所述，本题选C。

8、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构。
【解析】
I：线性表的顺序存储结构和其链式存储结构各有优缺点。在未明确使用场合时，无法明确线性表的顺序存储结构和其链式存储结构的好坏。
II：链式存储结构既能表示线性结构，例如线性表，又能表示非线性结构，例如树和图。因此，链式存储结构比顺序存储结构能更方便地表示各种逻辑结构。
III：频繁使用插入和删除结点操作，链式存储结构更优于顺序存储结构。因为在链式存储结构中，只需要修改结点指针即可完成操作，而在顺序存储结构中可能需要移动大量的元素。
IV：顺序存储结构和链式存储结构都可以从第一个结点开始，顺序访问表中的任意一个元素。因此，顺序存储结构和链式存储结构可以进行顺序存取。
综上所述，II、IV说法正确。故本题选B。

9、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--单循环链表。
【解析】一个带头结点的循环单链表L，若L->next->next=L，则链表有两种情况，如下所示。故本题选D。

10、试题答案：C

试题解析：

【考点】本题考查
1、数据结构--线性表--线性表的存储结构--线性表的链式存储结构--单循环链表的特点；
2、数据结构--线性表--线性表的存储结构--线性表的链式存储结构--双循环链表--双循环链表的特点。
【解析】在只有表头结点指针，没有表尾指针的单向循环链表的表头进行删除操作时，总需要遍历整个链表以找到表尾元素，再修改表尾元素的指针，使整个链表保持是一个单向循环的状态，时间复杂度为O(n)。因此，若所有操作均在表头进行时，有表头结点指针，没有表尾指针的单向循环链表最不适合作为链式表。故本题选C。