2008年大连理工大学考研数据结构试题

大连理工大学2008年考研数据结构试题

一、选择题

1. 线性表的 ———— 运算中，顺序存储结构比例链式存储结构好。

A. 插入

B .删除

C .按号查找

D .按元素值查找

2.此程序的复杂度为 ————

for（int i=0 ； i<m； i++）

for（int j=0；j<n； j++）

A[i][j]=i*j；

A . O（m2）

B . O（n2）

C . O （m*n）

D . O （m+n）

3 .在待排数据已基本有序的情况下， ———— 效率最高。

A . 直接选择排序

B . 直接插入排序

C . 快速排序

D . 归并排序

4 . n 个英文单词，每个单词长度基本相等，为 m ，当 n>>50，m<5 时，时间复杂度最佳的为 ———— ：

A . 快速排序

B .归并排序

C .基数排序

D.直接插入排序

5 .顺序查找长度为 n 的顺序表，查找成功的平均检索长度为 ———— ：

A . n

B . n/2

C.（n-1）/2

D . （n+1）/2

6 .一颗二叉树，头序序列为 ABCDEFG ，中序序列为 CBDAEGF ，后序为 ————

A . CDBGFEA

B . CDBFGEA

C . CDBAGFE

D . BCDAGFE

7 .一颗度为 3 的树，度为 3 的节点为三个，度为 2 的节点为 1 个，度为 1 的节点 1 个，度为 0 的节点 ———— 个。

A . 6

B . 7

C . 8

D . 9

8 .m 阶 B— 树中，某一节点插入一个新关键字引起破裂，则该节点原有关键字 ———— 个。

A.|—m/2—|

B.|—m/2—|-1

C.m

D.m-1

E.|—m/2—|

F.|—m/2—|-1

9 .两个长度为 n 的递增有序表，合并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 ———— 次。

A . 1

B . n-1

C . n

D . 2n

10 .有向图 G， n 个顶点，邻接矩阵存储于二维数组中，顶点 i 的度为 ———— .

A.（i=0 n-1）∑A[i][j]

B.（j=0 n-1）∑A[i][j]

C.（i=0 n-1）∑A[i][j]+（j=0 n-1）∑A[i][j]

D.（j=0 n-1）∑（A[i][j]+A[j][i]）

二、问答题

1. （ 6 ） n 阶对称阵（ aij ） n × n ，采用压缩存储存放于一维数组 F[m] 中，从 F[0] 开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij （ 0<=i，j<=n-1 ）的地址计算公式，并求算 m .

2. （ 5 ）顺序队列如何解决假溢出问题。

3. （ 8 ）已知一组关键字（ 10 ， 26 ， 14 ， 25 ， 17 ， 36 ， 37 ， 44 ， 27 ， 34 ， 60 ）设哈希函数 H （ x ） =x%13 ，表长 m=13 ，请写出用线性探测法处理冲突构造所得的哈希表。并求出在等概率情况下，查找成功时的平均检索长度。

4. （ 6 ）给定一个由 n 个关键字不同的记录构成的序列，你能否用比 2n-3 少的比较次数找出 n 个元素中的最大值和最小值？如果有，请描述你的方法。最快需要多少次比较？（无需写算法）

三 、用类 C 语言完成设计

1.（ 15 ）什么是堆？设计算法判定给定的存于数组 r[] 中的 n 个数据是否为堆。

2.（ 15 ）设 u 、 v 是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。

3. （ 10 ）设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。