2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构

与算法》科目期末试卷A（有答案）

一、选择题

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

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

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的

排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序

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

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

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

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

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

5、在下列表述中，正确的是（）

A.含有一个或多个空格字符的串称为空格串

B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过l

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

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

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

2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页

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、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ

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

其关键字有序（）。

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

9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中

有（）个叶子。

A.lognB.（n－1）/2C.logn+1D.（n＋1）/2

22

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

A.平衡二叉树

B.二叉查找树

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

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

二、填空题

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

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

12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步

长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据

的排列次序______。

13、VSAM系统是由______