2022年洛阳师范学院计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年洛阳师范学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数

是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

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

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

3、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点标识B.表结点中首结点的位置

C.方便运算的实现说明单链D.表是线性表的链式存储

4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

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、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

则根结点的孩子结点（）。

A．只有eB．有e、b．有Ce、c．无法确定D

8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

9、一个具有1025个结点的二叉树的高h为（）。

A.11B.10至C.111025之间至D.101024之间

10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A.（100，80，90，60，120，110，130）

B.（100，120，110，130，80，60，90）

C.（100，60，80，90，20，110，130）

D.（100，80，60，90，120，130，110）

二、填空题

11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

12、属于不稳定排序的有______。

13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点

中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该

结点中原有的关键字的个数是______。

14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂

度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。

15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，

right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，

right指向其右孩子，rflag=1，right指向其后继。

16、阅读下列程序说明和程序，填充程序中的______。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者

略）。

本程序采用非