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

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

试卷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，V7，D.V1V2，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、文件可按其记录的类型不同而分成两类，即______和______文件。

14、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则

删除一个元素平均需要移动元素的个数是______。

15、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的

次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用

以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。

16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结

点和______个叶子，该满二叉树的深度为______。

17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A9.9在B中的存储位置k=______