《852数据结构真题》

2002年数据结构研究生入学考试试题

一.选择题(30分,每空2分。答案可能不唯一)

1.算法在发生非法操作时可以作出处理的特性称为。

①正确性②可读性③键状性④可靠性

2.指针p所指的元素是双向链表L的尾元素的条件是 A 。若队列

采用链式存储,则该链式队列 B 。

A:① p==L ② p==NULL ③ p->Llink==L ④p->Rlink==L

B:①存在队满的情况②不存在队空的情况

③入队之前必须判断队满否④出队之前必须判断队空否

3.二叉排序树是:。

①中序遍历得到一升序序列的二叉树

②每一分支结点的度均为2的二叉树

③按层次从左到右顺序编号的二叉树

④每一分支结点的值均小于其右子树上所有结点的值(若右子树存

在),又大于其左子树上所有结点的值(若左子树存在)

4.三对角矩阵a[1…n][1…n]以行为主序顺序存储,其存储始址是b,

每个元素占一个存储单元,则元素a[i][j]的存储始址为。

①b+2*j+i-2 ② b+2*i+j-2 ③ b+2*j+i-3 ④ b+2*i+j-3

5.已知一棵二叉树的前序序列和中序序列分别是GFDBHCEA和DFHBGCAE,

则该二叉树的后序序列为 A ,层次序列为 B ,若由森林转

化得到的二叉树是非空的二叉树,则该二叉树是 C ,如果满足

条件 D ,线索二叉树中结点p无右孩子。

A、B:① DBHFEACG ② GFCDBEHA ③ DHBFAECG ④ DFGBCEHA

C:①根结点无右子树②根结点可能有左子树和右子树

③根结点无左子树④各结点只有一个孩子

D:①p->rchild==NULL ②p->rtag==1 p->rtag==0 ④p->rtag==NULL

6.一个加权连通无向图的最小生成树可以使用 A 生成。一项工

程完工所需的最少时间等于某个 B

A:① Hash算法② Dijstra算法③ prim算法④ Huffman算法

B:① AOE网中源点到汇点事件最多的路径的长度

②AOE网中源点到汇点的最长路径的长度

③AOE网中源点到汇点的最短路径的长度

④AOE网中源点到汇点活动最多的路径的长度

7.用冒泡排序的方法对n个记录进行排序,第一趟共要比较 A对

元素。对n个元素进行排序,不稳定的排序是 B ,快速排序是一

种 C ,关键字序列 D 是一个堆。

A:① n-1 ② n/2 ③ n+1 ④ n

B:①直接插入排序②冒泡排序③ shell排序④归并排序

1.下载地址 594.62 KB (需下载币10个)