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

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

期末试卷A（有答案）

一、选择题

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

排序方法是（）。

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

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

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

3、静态链表中指针表示的是（）。

A.下一元素的地址

B.内存储器的地址

C.下一元素在数组中的位置

D.左链或右链指向的元素的地址

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

A.串是字符的有限序列

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

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

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

5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列

中的元素数是（）。

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

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

A．只有eB．有e、bC．有e、cD．无法确定

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

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

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

8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

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

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

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

C.其中只有一个叶结点

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

10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两

趟排序后的结果。

A.选择排序B.起泡排序C.插入排序D.堆排序

二、填空题

11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当

使用监视哨时，若查找失败，则比较关键字的次数为______。

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放

成321。请填空：

13、外排序的基本操作过程是______和______。

14、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中

data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需

要执行以下语句：______

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

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

16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为

______。

17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。

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

的地址为______。

三、判断题

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

20、对磁带机而言，ISAM是一种方便的文件组织方法（