2015(1)年度中国石油大学数据结构试题及答案

A 散列存储 B 顺序存储或链接存储

C 压缩存储 D 索引存储

44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ） A O（n） B O（n log2n） C O（log2n） D O（n）

45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A ) A n B n+1 C n-1 D n+e

46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。 A 求关键路径的方法 B 求最短路径的Dijkstra方法

C 深度优先遍历算法 D 广度优先遍历算法

47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )

2

A 1 B 2 C 9 D 10

48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）

A O（log2n） B O（n） C 不直接依赖于n D 上述都不对 二、 填空题（）

1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种

2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种

3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。

4、 设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配）

5、 栈、队列逻辑上都是（线性存储）结构。

6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。

7、栈中存取数据的原则（ 后进先出），

队列中存取数据的原则（ 先进先出 ）

8、串是由（ 零个或多个）字符组成的序列。（ 长度为零的串 ）称为空串，（ 由一个或多个空格组成的串）称为空格串。

9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。

10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。

11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。 12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ） 13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。

14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。 15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i>=1 ）为（「(i-1)/2 ┐ ）.

16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。 17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。

18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。 19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（ 2h+1 ）个。 20、由一棵二叉树的前序序列和（中序序列）