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

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

1、下面程序段的时间复杂度为（ ）。i=0; s=0; while(s<n){ i++; s=s+i;}

A、

B、

C、O(n)

D、O(n²)

2、若线性表的操作主要是查找，很少涉及到插入、删除操作时，宜采用以下哪种存储结构较为合适（ ）。

A、双链表

B、单链表

C、顺序表

D、循环链表

3、线性表采用链表存储时地址（ ）。

A、必须是连续的

B、连续不连续都可以

C、一定是不连续的

D、部分地址必须是连续的

4、若允许表达式内多种括号混合嵌套，则设计检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（ ）。

A、栈

B、线性表

C、队列

D、二叉排序树

5、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ ）。

A、2，4，3，1，5，6

B、3，2，4，1，6，5

C、4，3，2，1，5，6

D、2，3，5，1，6，4

6、栈和队列的共同点是（ ）。

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

7、在长度为n的顺序表中删除第i（1≤i≤n）个元素时，需要移动元素的次数为（ ）。

A、n-i+1

B、i

C、i+1

D、n-i

8、用链表作为线性表的存储结构的优点是（ ）。

A、便于随机存取

B、花费的存储空间比顺序表少

C、便于插入与删除

D、数据元素的物理顺序与逻辑顺序相同

9、设循环队列中数组的下标范围是0到n-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（ ）。

A、rear-front

B、rear-front+1

C、（rear-front+1）%（n-1）

D、（rear-front+n+1）%n

10、二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为（ ）。

A、429

B、432

C、435

D、438

1、试题答案：A

试题解析：

2、试题答案：C

试题解析：

链式存储结构是非随机存储结构，因此在双链表、单链表、循环链表中查找元素均需要从头开始遍历查找，时间复杂度均为O(n)。在链表中进行插入和删除操作时无需移动元素仅需要改变指针的指向，因此链式结构中插入和删除的时间复杂度为O(1)。而顺序存储结构是随机存储机构，在顺序表中查找元素的时间复杂度为O(1)，插入和删除元素操作需要移动元素，其时间复杂度为O(n)，故本题选C。

3、试题答案：B

试题解析：

线性表的链式存储结构其地址也可以连续也可以不连续，而顺序存储结构其地址是连续的，故本题选B。

4、试题答案：A

试题解析：

栈具有“后进先出”的特点，进行括号匹配检验时，遍历表达式，遇到左括号则进栈，遇到右括号则将栈顶元素出栈，并检验是否与右括号匹配，若匹配则继续遍历；否则判定表达式括号不匹配。遍历结束后检验栈是否为空，若为空，则判定表达式括号匹配，否则括号不匹配。故本题选A。

5、试题答案：D

试题解析：

对于A，经过这样的操作可以得到该出栈序列：push(1)、push(2)、pop(2)、push(3)、push(4)、pop(4)、pop(3)、pop(1)、push(5)、pop(5)、push(6)、pop(6)；对于B，经过这样的操作可以得到该出栈序列：push(1)、push(2)、push(3)、pop(3)、pop(2)、push(4)、pop(4)、pop(1)、push(5)、push(6)、pop(6)、pop(5)；对于C，经过这样的操作可以得到该出栈序列：push(1)、push(2)、push(3)、push(4)、pop(4)、pop(3)、pop(2)、pop(1)、push(5)、pop(5)、push(6)、pop(6)；对于D，4在1之后入栈，因此4应当在1之前出栈，D序列不符合栈“后进先出”的特性，故本题选D。

6、试题答案：C

试题解析：

栈和队列是受限的线性表。栈具有“后进先出”的特性，只能在表的一端进行插入和删除操作的线性表。队列具有“先进先出”的特性，只能在表一端插入在表的另一端删除。故本题选C。

7、试题答案：D

试题解析：

顺序表中删除第i个元素，需要将第i+1至第n个元素依次向前移动一位，共需移动元素的个数为n-i。故本题选D。

8、试题答案：C

试题解析：

对于A，链表不是随机存取结构，顺序表才是，因此A错误；对于B，链表的结点除了值域还有指针域，花费的存储空间比顺序表多，因此B错误；对于C，链表中进行插入和删除操作时无需移动元素，仅需要改变指针的指向，因此C正确；对于D，链表的存储空间不连续，存储地址之间的相互关系依靠指针，因此数据元素的物理顺序与逻辑顺序不同，因此D错误。故本题选C。

9、试题答案：D

试题解析：

在本题中，front指向队首元素，rear指向队尾元素，因此元素个数应当为rear-front+1，因此A错误。再加n是为了保证当rear<front时，计算出的结果是非负数，因此B错误。数组的最大容量为n，因此C错误，故本题选D。

10、试题答案：A

试题解析：

add(A[9][7])=add(A[0][0])+(7*12+9)*3=150+429，故本题选A。