2022年新疆师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年新疆师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年新疆师范大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈

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

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

3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构

C.索引存取的存储结构D.Hash存取的存储结构

4、已知串S=aaab，其next数组值为（）。

A.0123B.1123C.1231D.1211

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、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180B．500，450，200，180

C．180，500，200，450D．180，200，500，450

8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码

字。

2022年新疆师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年新疆师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页

A.107B.108C.214D.215

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是

（）。

A.每次分区后，先处理较短的部分

B.每次分区后，先处理较长的部分

C.与算法每次分区后的处理顺序无关

D.以上三者都不对

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排

序树检索时，平均比较次数为______。

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

13、建立索引文件的目的是______。

14、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输

出。

15、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用

______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。