2005年数据结构考研真题答案及解析

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

2、设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是（）。

A、(n-1)/2

B、n/2

C、(n-1)n/2

D、(n+1)n/2

3、如果只保存一个n阶对称矩阵a的下三角元素（含对角线元素），并采用行主序存储在一维数组b中，a[i][j]（或a[i，j]）存于b[k]，则对i<j，下标k与i，j的关系是（）。设一维数组和矩阵元素的行列下标取值均从0开始。

A、i（i+1）/2+j

B、j（j+1）/2+i

C、i（i-1）/2+j

D、j（j-1）/2+i

4、一棵三叉树中，已知度为3的结点个数等于度为2的节点数，且树中叶子结点的数目为13，则度为2的结点数目为（）。

A、4

B、2

C、3

D、5

6、已知一棵由关键字集合{18，43，27，77，44，36，39} 所构造的二叉搜索树（也称为二叉排序树），对该树进行中序遍历得到的节点序列为（）。

A、树形未定，无法确定

B、18，43，27，77，44，36，39

C、18，27，36，39，43，44，77

D、77，44，43，39，36，27，18

7、一个索引文件，如果经常需要插入和删除元素，宜采用（）做索引。

A、二叉排序树

B、二叉平衡树

C、B-树

D、B+树

8、均匀的散列函数应当使关键字集合中的元素，经过散列函数映射到散列表中任何位置的概率（）。

A、相等

B、最小

C、最大

D、一定

9、关键路径是指AOE（Activity On Edge）网中（）。

A、任意两顶点间的最长路径

B、任意两顶点间的最短路径

C、从源点到汇点的最长路径

D、从源点到汇点的最短路径

10、堆可以是最大堆，也可以是最小堆。下列序列中（）既不是最大堆，也不是最小堆。

A、（90，85，78，67，56，42，35，24，18）

B、（18，35，56，24，42，78，67，85，90）

C、（90，78，85，56，67，35，42，48，24）

D、（18，35，24，56，42，78，67，85，90）

2、试题答案：A

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的顺序存储结构--顺序表--顺序表的基本操作--顺序表的删除。
【解析】在长度为n的顺序表中，共有n个元素可供删除。若删除第一个元素，则需要移动n-1个元素；若删除第二个元素，需要移动n-2个元素；…；若删除第n-1个元素，需要移动1个元素；若删除第n个元素，需要移动0个元素。因此，在顺序表中插入一个新元素平均需要移动（n+n-1+…+1+0）/n=（n-1）/2个元素。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查数据结构--数组与广义表--矩阵的压缩存储--特殊矩阵的压缩存储--对称矩阵的压缩存储。
【解析】当i<j，说明a[i][j]位于上三角部分，其对应下三角元素a[j][i]。对称矩阵a的下三角部分中，第一行有1个元素，第二行有2个元素，…，第i行有i个元素。矩阵元素的行列下标取值均从0开始，那么a[j][i]位于第j+1行第i+1列，则它是第1+2+…+j+i+1= j（j+1）/2+i+1个元素，又因为一维数组下标取值是从0开始的，所以需要减一。因此，a[i][j]存于b[k]中，其下标k与i，j的关系是k= j（j+1）/2+i。故本题选B。

4、试题答案：A

试题解析：

【考点】本题考查数据结构--树与二叉树。
【解析】在任意一棵树中，结点总数等于总度数加一。因此，在三叉树中，有n0+n1+n2+n3=n1+2n2+3n3+1，化简得n0=n2+2n3+1。由题干知n3=n2，n0=13，则有13=3n2+1，解得 n2=4。故本题选A。

6、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树--二叉排序树的性质。
【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
由二叉排序树的性质可知，其中序遍历结果是一个有序递增的序列。选项中只有C中序列有序递增，故本题选C。 

7、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B+树--B+树的性质。
【解析】由于B+树的叶子结点只包含数据，因此在进行插入和删除操作时，只需要修改叶子结点，不需要修改非叶子结点，这样可以减少修改操作的开销。而且，B+树可以通过调整树的结构来保持平衡，从而保证查询性能。因此，一个索引文件，如果经常需要插入和删除元素，宜采用B+树做索引。故本题选D。

8、试题答案：A

试题解析：

【考点】本题考查数据结构--查找--散列/哈希表--哈希表的构造--哈希函数--选择哈希函数的考虑因素。
【解析】均匀的散列函数应当将关键字映射到散列表中任何位置的概率都相等，这样可以最大程度地避免散列冲突，使得散列表中的关键字分布均匀，提高散列表的查找效率。如果某些关键字映射到散列表中的某些位置的概率更大，那么这些位置就容易发生冲突，影响查找效率。故本题选A。

9、试题答案：C

试题解析：

【考点】本题考查数据结构--图--有向无环图--关键路径--AOE网。
【解析】在AOE网中，从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径。故本题选C。

10、试题答案：B

试题解析：

【考点】本题考查数据结构--排序--内部排序--选择排序--堆排序--堆--堆的性质。
【解析】
A中所有结点均满足“任意结点值大于等于其左右孩子值”这一特点，故其是一棵大根堆。
B中除了结点35满足大根堆的特点，而其余结点满足小根堆的特点，故其既不是最大堆，也不是最小堆。
C中所有结点均满足“任意结点值大于等于其左右孩子值”这一特点，故其是一棵大根堆。
D中所有结点均满足“任意结点值小于等于其左右孩子值”这一特点，故其是一棵小根堆。
综上所述，本题选B。