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

一、选择题

1、下述文件中适合于磁带存储的是（　　）。

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

2、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（　　）。

A.head（tail（LS）） （head（LS））

C.head（tail（head（tail（LS）））） （tail（tail（head（LS））））

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（　　）存储方式最节省时间。

A.顺序表  B.双链表  C.带头结点的双循环链表 D.单循环链表

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

A.（rear+1）MOD n=front

B.rear=front

C.rear+1=front

D.（rear-1）MOD n=front

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

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

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。

A．只有e  B．有e、b．有e、c．无法确定

7、下列叙述中，不符合m阶B树定义要求的是（　　）。

A．根结点最多有m棵子树 ．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列  D．叶结点之间通过指针链接

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

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

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

A.log2n（n－1）/2n+1  D.（n＋1）/2

10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（　　）。

A.选择排序法  B.插入排序法  C.快速排序法  D.堆排序法

二、填空题

11、在有n个顶点的有向图中，每个顶点的度最大可达______。

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

13、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需要执行以下语句：______

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

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

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

17、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。

18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。

三、判断题

19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（　　）

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

21、一个广义表可以为其他广义表所共享。（　　）

22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　）

23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（　　）

24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　）

25、顺序存储结构的主要缺点是不利于插入或删除操作。（　　）

26、归并排序辅助存储为O（1）。（　　）

27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（　　）

28、无环有向图才能进行拓扑排序。（　　）

四、简答题

29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。

30、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。

31、设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循左移P（0＜P＜ n）个位置，即将R中的数据由（X0，X1，…，Xn－1）变换为（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：

（1） 给出算法的基本设计思想。

（2） 根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。

五、算法设计题

32、已知二叉树丁的结点形式为（llink，data，count，rlink），在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

33、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。

34、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法delete（Linklist&L）。

35、已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O（m）。

参

一、选择题

1、【答案】A

2、【答案】C

3、【答案】A

4、【答案】B

5、【答案】C

6、【答案】A

7、【答案】D

8、【答案】C

9、【答案】D

10、【答案】A

二、填空题

11、【答案】2(n-1)

12、【答案】n(n-1)/2 

13、【答案】py->next=px->next；px->next=py

14、【答案】生成有序归并段（顺串）；归并

15、【答案】记录；数据项

16、【答案】模式匹配；模式串

17、【答案】9174；8788 

18、【答案】FEGHDCB；BEF

【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。

三、判断题

19、【答案】×

20、【答案】×

21、【答案】√

22、【答案】×

23、【答案】√

24、【答案】×

25、【答案】√

26、【答案】×

27、【答案】√

28、【答案】√

四、简答题

29、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个

栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：

30、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。

31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…， xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中的前n－P个数和后P个数分别原地逆置，最终得到结果xp，xp＋1，…，xn－1，x0，x1，…，xp－1。

（2）用C语言算法描述如下：

（3）说明算法的复杂性：上述算法中3个Reverse函数的时间复杂度分别为O（p/2）、O（（p－2）/2）为O（n/2），故算法的时间复杂度为O（n），算法的空间复杂度为O（1）。

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：