2022年大连工业大学计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年大连工业大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

排序方法是（）。

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

2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序

3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性

B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性

D.易读性、稳定性、安全性

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

A.串是字符的有限序列

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

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

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

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

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

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

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

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

6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行

匹配，第一次出现失配“”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别

（）。

A．i＝1，j＝0B．i＝5，j＝0．Ci＝5，j＝2．Di＝6，j＝2

7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180．B500，450，200，180

C．180，500，200，450．D180，200，500，450

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

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

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

有（）个叶子。

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

22

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

（）。

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

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

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

D.以上三者都不对

二、填空题

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

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

13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并

能较快地______进行查找。

14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、

______、______、______。

15、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查

找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确

定不成功。

16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

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

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

18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85

的地址为______。

三、判断题

19、倒排序文件的优点是维护简单。（）

20、文件系统采用索引结构是为了节省存储空间。（）

21、KMP算法的特点