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

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

试卷A（有答案）

一、选择题

1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)

2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈

3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构

C.索引存取的存储结构D.Hash存取的存储结构

4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.234156

5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，

则在进行出队操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三

次进行退栈操作，则不可能得到的出栈序列是（）。

7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

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

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

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

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

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

C.其中只有一个叶结点

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

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

（）。

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

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

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

D.以上三者都不对

二、填空题

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

12、阅读下列程序，指出其功能，并写出空格处应填上的语句。

13、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，

free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；

delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别

进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A

的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查

找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

14、建立索引文件的目的是______。

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

16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点

为______。

17、模式串P=‘abaabcac’的next函数值序列为______