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

2022年重庆交通大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

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

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

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

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

A.下一元素的地址

B.内存储器的地址

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

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

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

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

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．500，200，450，180B．500，450，200，180

C．180，500，200，450D．180，200，500，450

8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中

有（）个叶子。

A.lognB.（n－1）/2C.logn+1D.（n＋1）/2

22

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、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表

示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，

1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f（6，4）=______。

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

13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从

左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，

指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使

用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。

试填充算法中的空格，使算法完整。

14、设单链表的结点结构为（data，next）