2022年滁州学院计算机科学与技术专业《数据结构与算法》科目期末试卷.pdfVIP

2022年滁州学院计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

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

排序方法是（）。

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

2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放

在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入选择B.希尔C.二路D.归并

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

A.下一元素的地址

B.内存储器的地址

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

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

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

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

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

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

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

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛V1，V2，

V1，V3，V1，V4，V2，V5，V3，V5，V3，V6，V4，V6，V5，V7，

V6，V7｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7，D.V1V2，V5，V3，V4，V6，V7

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

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

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

7、已知关键字序列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

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

A.二叉树的度为2

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

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

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

9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。

A.直接插入排序B.起泡排序简单选择C.排序D.快速排序

二、填空题

11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。

请填充算法中标出的空白处，完成其功能。

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

13、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，

试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

14、在单链表L中，指针P所指结点有后继结点的条件是______。

15、文件由______组成；记录由______组成。

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

______。

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

【程序说明】本程序完成将二叉树中左、右孩子