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

2022年甘肃政法大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年甘肃政法大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

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

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

3、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点B.标识表结点中首结点的位置

C.方便运算的实现D.说明单链表是线性表的链式存储

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

5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定

7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180B．500，450，200，180

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

8、有n（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

2022年甘肃政法大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年甘肃政法大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结

果为（）。

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果

为（）。

A.（2，5，12，16）26（60，32，72）

B.（5，16，2，12）28（60，32，72）

C.（2，16，12，5）28（60，32，72）

D.（5，16，2，12）28（32，60，72）

二、填空题

11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当

使用监视哨时，若查找