数据结构与算法 - 形考作业四（占比20％）

课程名称：数据结构与算法 发布教师：许小 广东开放大学 媛 作业来源：形考作业专区 作业满分：100.0分 发布时间：2025-06-28 作业要求：按要求完成。

成人学历

单选题

1. 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ） （分值：4.0分）

A. 20

B. 40

C. 30

D. 45

2. 执行一趟快速排序能够得到的序列是（ ） （分值：4.0分）

A. [45，34，12，41] 55 [72，63，27]

国家开放大学 B. [41，12，34，45，27] 55 [72，63]

C. [63，12，34，45，27] 55 [41，72]

D. [12，27，45，41] 55 [34，63，72]

3. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ） 渝粤题库 （分值：4.0分）

A. 任一结点无左孩子

B. 空或只有一个结点

C. 任一结点无右孩子

D. 高度等于其结点数

4. 设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ） （分值：4.0分）

A. 5

B. 6

C. 4

D. 3

5. 顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ） （分值：4.0分）

A. O(n 1/2 )

B. O(n 2 )

C. O(n)

D. O(1og2n)

6. 设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点 （分值：4.0分）

A. 99

B. 102

渝粤文库 C. 101

D. 100

7. 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ） （分值：4.0分）

A. O(n 2 )

B. O(n+e)

C. O(n e )

D. O(n 3 )

8. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ） （分值：4.0分）

A. 第i行0元素的个数之和

B. 第i列非0元素的个数之和

C. 第i列0元素的个数之和

D. 第i行非0元素的个数之和

9. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ） （分值：4.0分）

A. 冒泡排序

B. 希尔排序

C. 快速排序

D. 堆排序

10. 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ） （分值：4.0分）

A. head!=0

B. head->next==0

C. head==0

D. head->next==head

简答题/计算题

1. 设计在顺序有序表中实现二分查找的算法 （分值：20.0分）

2. 设计判断二叉树是否为二叉排序树的算法 （分值：20.0分）

3. 在链式存储结构上设计直接插入排序算法 （分值：20.0分）