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

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

1、判断哪个表结构是逻辑结构（ ）。

A、顺序表

B、哈希表

C、有序表

D、单链表

2、关于算法的优越性判断，以下正确的是（ ）。

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

B、健壮性是指程序不因为奇怪的输出而产生奇怪的状态

C、若算法的时间复杂度是O(n²)，表示它的问题规模是n²

D、算法的输入是指至少要有一个输入，这些输入取自于某个特定对象的集合

3、如果要在最后一个元素之后插入一个元素和删除第一个元素， 那么哪种存储方式最省时间（ ）。

A、单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

4、顺序表中每个元素是占2个存储单元，若第一个元素a0的地址100，则a5在内存中的存储地址是（ ）。

A、105

B、110

C、115

D、120

5、6545321顺序进栈判断不合法的出栈的序列（ ）。

A、1235456

B、6545321

C、6545123

D、2545631

6、根据一个式子a* (b+c)-d写出后缀表达式（ ）。

A、abcd*+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

7、100*90的稀疏矩阵中，有非0元素10个，每个类型占2个字节，求用三元组存储该矩阵时所需要字节数（ ）。

A、60

B、66

C、20

D、10

8、对稀疏矩阵进行的压缩的目的是（ ）。

A、表达变得简单

B、对矩阵元素的存取变得更加简单

C、去掉矩阵中的多余元素

D、减少不必要的存储空间

1、试题答案：C

试题解析：

顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，也描述存储结构和数据运算。而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述了元素之间的逻辑关系，属于逻辑结构。故本题选C。

2、试题答案：B

试题解析：

A：算法原地工作是指所需要的额外辅助空间是常量级，所以选项A中说法错误。
B：算法的健壮性指输入非法数据，会适当做出反应和处理，不会出现奇怪的输出，故选项B中说法正确。
C：算法的时间复杂度是O(n²)，这是设定问题规模为n的分析结果，它不表示问题规模是n²，故选项C中说法错误。
D：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合；一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。故选项C中说法错误。
综上所述，本题选B。

3、试题答案：D

试题解析：

单链表、仅有头指针的单循环链表和双链表查找最后一个元素时，都需要遍历整个链表，而仅有尾指针的单循环链表在O(1)的时间复杂度内就可以找到最后一个结点和第一个结点，便于在最后一个元素之后插入一个元素和删除第一个元素。故本题选D。

4、试题答案：B

试题解析：

a5前面有5个元素，所以其在内存中的地址为100+2*5=110。故本题选B。

5、试题答案：D

试题解析：

A：6545321依次入栈，再依次出栈即可得到出栈序列1235456。
B：每个元素入栈后即刻出栈，则可以得到出栈序列6545321。
C：6入栈并出栈，5入栈并出栈，4入栈并出栈，5再入栈并出栈，321依次入栈再依次出栈，则可以得到出栈序列6545123。
D：出栈的第一个元素是2，说明此时栈中的元素序列依次是65453，接着只能是3出栈或者1入栈并出栈，即2的后面只能是3或1。因此，2545631不是一个合法的出栈序列。
综上所述，本题选D。

6、试题答案：B

试题解析：

首先明确表达式中各个运算符的运算顺序，接着按照运算符的先后顺序将运算符提到其对应的两个操作数的后面，即可得到后缀表达式为abc+*d-。故本题选B。

7、试题答案：B

试题解析：

稀疏矩阵采用三元组压缩存储时，非零元素所在行、列、非零元素的值构成一个三元组（i，j，v），因而每个非零元素占3*2=6个字节，共有10个非零元素，故需要60个字节。此外，一般需要用三个整型数据存储矩阵的行数、列数和总元素个数，所以还需要6个字节。因此，共需要66个字节。故本题选B。

8、试题答案：D

试题解析：

稀疏矩阵中许多零元素，它们占用了大量的存储空间。若对稀疏矩阵进行压缩存储，只存储非零元素，这样可以减少不必要的存储空间。故本题选D。