2022年宜宾学院计算机科学与技术专业《数据结构与算法》科目期末试卷.pdfVIP

2022年宜宾学院计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

1、下述文件中适合于磁带存储的是（）。

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

3、算法的计算量的大小称为计算的（）。

A.效率复B.杂性现实C.性D.难度

4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)

5、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.4

6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字

3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树．所B有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

A.二叉排序树哈夫曼B.树树C.AVL堆D.

10、下列二叉排序树中查找效率最高的是（）。

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

二、填空题

11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。

12、在哈希函数H（key）=key%p中，p值最好取______。

13、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则

删除一个元素平均需要移动元素的个数是______。

14、VSAM系统是由______、______、______构成的。

15、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用

______的排序方法。

16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址

2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是______。

（2）存放数组的第8列的所有元素至少需要的单元数______。

（3）数组按列存储时，元素A[5，8]的起始地址是______。

17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）

18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点

为______。

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）

20、倒排文件的目的是为了多关键字查找。（）

21、串是一种数据对象和操作都特殊的线性表。（）