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

2022年海南大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

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

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

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

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

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

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

A.下一元素的地址

B.内存储器的地址

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

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

4、已知有向图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，V7，V3B.V1，V2，V6，V4，V5，V7

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

5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、Ⅳ．仅BⅠ、Ⅱ、Ⅲ．C仅Ⅱ、Ⅲ、Ⅳ．仅DⅢ、Ⅳ、Ⅴ

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

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

A．只有e．有Be、b．有Ce、c．无法确定D

8、有n（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

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

A.11B.10至1025之间C.11至1024之间D.10

10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A.（100，80，90，60，120，110，130）

B.（100，120，110，130，80，60，90）

C.（100，60，80，90，20，110，130）

D.（100，80，60，90，120，130，110）

二、填空题

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

12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

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

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

定不成功。

14、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义

相应的______，设计出相应的______。

15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂

度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。

16、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V