2025年同济大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

人人好公，则天下太平；人人营私，则天下大乱。——刘鹗

2025年同济大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

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

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

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

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

3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈

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

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

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

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

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

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

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ

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

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

其关键字有序（）。

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

9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查

找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2

B.n/2

C.(n+1)/2

D.n

二、填空题

11、属于不稳定排序的有______。

12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

13、文件可按其记录的类型不同而分成两类，即______和______文件。