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

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

1、下列算法的时间复杂度是（ ）。for(i=0;i<n;i++)c[i][j]=i+j;

A、O(1)

B、O(n)

C、O(log2n)

D、O(n2)

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

A、n

B、n/2

C、(n-1) /2

D、(n+1)/ 2

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

A、顺序表

B、栈

C、队列

D、链表

4、一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为（ ）。

A、1032

B、1028

C、1008

D、8

5、设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

6、广义表（a，b，（C，（d）））的表尾是（ ）。

A、（d）

B、（c，（d））

C、d

D、（b，（c，（d））

7、设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

8、在一个具有n个顶点的无向图中，要连通全部顶点只要需要（ ）条边。

A、n

B、n+1

C、n-1

D、n(n-1) /2

9、对于静态表顺序查找算法，若在表头设置监视哨，则正确的查找方式为（ ）。

A、从第0个元素往后查找该数据元素

B、从第1个元素往后查找该数据元素

C、从第n个元素开始往前查找该数据元素

D、与查找顺序无关

10、常采用下面几种方式解决散列法中出现的冲突问题（ ）。

A、数字分析法、除余法、平方取中法

B、数字分析法、除余法、线性探测法

C、数字分析法、线性探测法、多重散列法

D、线性探测法、多重散列法、链地址法

1、试题答案：B

试题解析：

本题考查时间复杂度。
该循环语句会执行n次，所以算法的时间复杂度为O(n)。故本题选B。

2、试题答案：C

试题解析：

本题考查顺序表。
在顺序表（a1，a2，....，an）中，删除a1需要移动移动个元素，删除a2需要移动个元素，…，删除an-1需要移动1个元素，删除an需要移动0个元素。因此，删除任意一个结点时所需移动结点的平均次数为((n-1)+( n-2)+…+2+1+0)/n=(n-1) /2。故本题选C。

3、试题答案：B

试题解析：

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

4、试题答案：C

试题解析：

本题考查数组地址计算。
loc[8]=(8-6)*4+1000=1008。故本题选C。

5、试题答案：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。

6、试题答案：D

试题解析：

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

7、试题答案：A

试题解析：

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

8、试题答案：C

试题解析：

本题考查无向图的连通性。
在有n个结点的无向图中，某一顶点与其余n-1个顶点有边相连则可成为连通图，即有n-1条边则可成为连通图。故本题选C。

9、试题答案：C

试题解析：

本题考查静态表。
监视哨是将标为0的这个位置的存放的元素值设为Key，其作用是使得我们不用多次判断查找是否越界。因为就算静态表中找不到相应元素，也会在0位置上配对成功，返回0。从后往前查找，碰到监视哨说明查找失败，所以应该从第n个元素开始往前查找数据元素。故本题选C。

10、试题答案：D

试题解析：

本题考查解决冲突的方法。
构造哈希函数的方法：① 数字分析法、② 除留余数法、③ 平方取中法；处理冲突的方法：① 开放地址发（包括线性探测法、二次探测法、伪随机探测法）、② 多重散列法、③ 链地址法。故本题选D。