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

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

试卷A（有答案）

一、选择题

1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿

链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j-nextD.j=r[j]-next

2、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.9

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

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

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

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，V7B.V1，V3，V2，V6，V4，V5，V7

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

5、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

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

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

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

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

A.二叉树的度为2

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

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

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

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

A.二叉排序树哈夫曼B.树树C.AVL堆D.

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、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步

长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据

的排列次序______。

12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间

的是______算法，最费时间的是______算法。

13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、

______、______、______。

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

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

16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

17、已知链队列的头尾指针分别是f和r，则将值