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

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

1、下列说法中，（ ）是不正确的。

A、数据元素是数据的基本单位

B、数据项是数据中不可分割的最小标识单位

C、数据可由若千个数据元素构成

D、数据项可由若千个数据元素构成

2、在顺序存储的线性表（a1，a2，...an）中，删除任意一个结点时所需移动结点的平均次数为（ ）。

A、n

B、n/2

C、(n-1)/2

D、(n+1)/2

3、设输入序列1、2、3、...、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。

A、n-i

B、n-1-i

C、n+1-i

D、不能确定

4、设n阶方阵A是对称矩阵，为节省存储空间，将其下三角（包括对角线）以行序为主序存储在一维数组B[k]（1≤k≤n(n+1)/2）中，则对任一上三角元素aij（i<j，1≤i≤n，1≤j≤n），在一维数组B中的下标位置k是（ ）。

A、i(i-1)/2+j

B、j(j-1)/2+i

C、(i+1)i/2+j+1

D、(j+1)j/2+i+1

5、下列程序段的时间复杂度为（ ）。for(i=0；i<m；i++) for(j=0；j<t；j++) c[i][j]=0；for(i=0；i<m；i++) for(j=0；j<t；j++)for(k=0；k<n；k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；

A、O(m*n*t)

B、O(m+n+t)

C、O(m+n*t)

D、O(m*t+n)

6、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。

A、N1-1

B、N2-1

C、N2+N3

D、N1+N3

7、在顺序表中，只要知道（ ），就可以求出任一结点的存储地址。

A、基地址

B、结点大小

C、向量大小

D、基地址和结点大小

8、在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ ）。

A、已固定

B、不固定

C、可以改变

D、不确定

9、设计一个判别表达式中左右括号是否配对的算法，采用（ ） 数据结构最佳。

A、顺序表

B、栈

C、队列

D、链表

10、广义表(a,b,(c,(d)))的表尾是（ ）。

A、(d)

B、(c,(d))

C、d

D、(b,(c,(d)))

1、试题答案：D

试题解析：

本题考查数据结构中的基本概念。
一个数据元素可以由若干个数据项组成，所以D说法错误。故本题选D。

2、试题答案：C

试题解析：

本题考查顺序表删除操作结点的平均移动次数。
当对n个元素进行删除操作时，有n个位置可以删除。1，2，3，4...n每个位置需要移动的元素个数分别为n-1，n-2，n-3...1，0个。所以平均需要移动的元素个数为(n-1)n/2n=(n-1)/2个。

3、试题答案：C

试题解析：

本题考查栈的输出。
输出序列中的第一个元素是n，说明1、2、3已经全部入栈，输出时必定是按照n、n-1、...、2、1的顺序出栈的，所以输出序列中的第i个输出元素是n-i+1。故本题选C。

4、试题答案：B

试题解析：

本题考查对称矩阵的压缩存储。
若将下三角以行序为主序存储在一维数组中，下三角元素aji前面有j-1行，共j(j-1)/2个元素，aji是第j行的第i个元素，所以aji是第j(j-1)/2+i个元素。又因为数组B[k]的下标是从1开始的，所以aji在一维数组B中的下标位置k是j(j-1)/2+i。在对称矩阵中，上三角元素aij对应元素下三角元素aji，所以aij在一维数组B中的下标位置k也是j(j-1)/2+i。故本题选B。

5、试题答案：A

试题解析：

本题考查时间复杂度的计算。
本程序段主要耗时在于三层for循环，该三层for循环共执行m*n*t次，所以程序段的时间复杂度为O(m*n*t)。故本题选A

6、试题答案：A

试题解析：

本题考查森林转化为二叉树。
森林转化为二叉树的过程：首先，T1、T2和T3先分别转化为二叉树，除根结点以外，其它结点都转化为根结点的左孩子。接着，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子。最终实现森林到二叉树的转化。根据此过程易知，二叉树B的根结点的左子树的结点数为N1-1。故本题选A。 

7、试题答案：D

试题解析：

本题考查顺序表存储地址计算。
顺序表是一组地址连续的存储单元依次存储表中的元素，所以可以根据首元素的地址和结点所占空间大小，直接访问顺序表中任一结点。故本题选D。

8、试题答案：A

试题解析：

本题考查顺序栈的特点。
 顺序栈是指利用顺序存储结构实现的栈，采用地址连续的存储空间（数组）依次存储栈中数据元素。而数组的容量一旦被声明就固定了，所以一个顺序栈一旦被声明，其占用空间的大小则已固定。故本题选A。

9、试题答案：B

试题解析：

本题考查栈的应用。
利用栈“先进后出”的特点。首先扫描整个判别表达式，碰到左括号将其入栈，碰到右括号则出栈一个左括号。最后，如果整个表达式扫描完成且栈为空，则说明判别表达式中左右括号配对。故本题选B。

10、试题答案：D

试题解析：

本题考查广义表。
表头：当广义表LS非空时，称第一个元素为LS的表头；表尾：称广义表LS中除去表头后其余元素组成的广义表为LS的表尾。表头是元素，表尾是广义表。