以下为《计算机算法基础－一学期试卷A》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

XX轻工大学 2017 –2018 学年第 1 学期

期末考试试卷（本科A卷）

课程名称 计算机算法基础 课程编号

注：考生须在上答题，答题时注明大、小题号

-------------------------------------------------------------------------------------------------------------------------------------

指出下列每个函数属于哪一种Θ（g(n)）类型（尽量使用最简单的函数g(n)），然后将这些函数按照增长的数量级从低到高的顺序进行排序。（15分）

a.
b.

c.
d.

e.

（1）有如下代码所示的迭代算法：

分析该算法的时间效率类型（5分）。

（2）有如下代码所示的递归算法：

a. 建立函数F(n)的递推式，分析该算法计算的是什么； 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 , log3=0.477, log5=0.699)（5分）

使用基于比较的排序算法，对输入数组A[n]={5, 3, 1, 9, 8, 2, 4, 7}按数值从小到大的顺序进行排序。

若采用选择排序算法（伪代码如下），画出该算法排序的过程，计算比较操作的执行次数。指出选择排序算法的平均时间效率。（10分）

若采用归并排序算法（伪代码如下），画出该算法排序的过程，计算比较操作的执行次数。指出归并排序算法的平均时间效率。（10分）

有如下的无向带权图：

应用Dijkstra算法求解该图的单起点最短路径问题，设顶点A为起点。给出算法求解过程、A到各点的最短路径和路径长度。（10分）

若该图改为无权图，顶点和边的连接关系均不改变，以A为起点，应用广度优先查找（BFS）算法遍历该图，画出该图的广度优先查找树，指出每个节点被访问到的顺序（设节点默认按字典顺序访问，不在广度优先查找树中的边用虚线表示）。（10分）





[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

1. 新冠肺炎疫情防控消毒、通风情况记录表
2. XX中学九则学习法曝光
3. 数据结构课程设计报告模板-排序算法的实现 (1)
4. 《队列表演（二）》说课内容
5. 干部人事档案材料排序方法
6. 1.算法及应用复杂度
7. 7的乘法口诀教案
8. 细破反接通知单
9. 二年级上册数学《认识时间》教学设计
10. 餐具消毒记录表
11. 认识实习总结
12. 整式的乘法教学设计
13. 整理与复习（教案）
14. 笔算乘法两位数乘两位数进位教学设计
15. 《儿童乐园》教学设计

以上为《计算机算法基础－一学期试卷A》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。