七,如图所示的有向网图,利用Dijkstra算法求从顶点v1到 其他各顶点的最短路径.
【解答】从源点v1到其他各顶点的最短路径如下表所示. 源点 终点 最短路径 最短路径长度 v1 v3 v1→v3 15 v1 v5 v1→v5 15 v1 v2 v1→v3→v2 25 v1 v6 v1→v3→v2→v6 40 v1 v4 v1→v3→v2→v4 45
四,已知数据序列为(12,5,9,20,6,31,24),对该数据序列进 行排序,写出插入排序,起泡排序,快速排序,简单选择排序, 堆排序每趟的结果. 【解答】用上述排序方法的每趟结果如下:
五,判别下列序列是否为堆,如不是,按照堆排序思想把它调,8,8,42) ⑵(3,9,5,8,4,17,21,6) 【解答】序列⑴是堆,序列⑵不是堆,调整为堆(假设为大根堆) 的过程如图所示.
⑹评价基于比较的排序算法的时间性能,主要标准是( )和( ). 【解答】关键码的比较次数,记录的移动次数 ⑺对n个记录组成的任意序列进行简单选择排序,所需进行的关键 码间的比较次数总共为( ). 【解答】比较次数=(n-1)+(n-2)+ … +2+1=n×(n-1)/2
二,选择题 ⑴下列序列中,( )是执行第一趟快速排序的结果. A [da,ax,eb,de,bb] ff [ha,gc] B [cd,eb,ax,da] ff [ha,gc,bb] C [gc,ax,eb,cd,bb] ff [da,ha] D [ax,bb,cd,da] ff [eb,gc,ha] 【解答】A 【分析】此题需要按字典序比较,前半区间中的所有元素都应小于ff,后半区 间中的所有元素都应大于ff. ⑵ 堆的形状是一棵( ). A二叉排序树 B满二叉树 C完全二叉树 D 判定树 【解答】C 【分析】从逻辑结构的角度来看,堆实际上是一种完全二叉树的结构. ⑶对数列(25, 84, 21, 47, 15, 27, 68, 35, 20)进行排序,元素序列的变化情况如下: ⑴ 25, 84, 21, 47, 15, 27, 68, 35, 20 ⑵ 20, 15, 21, 25, 47, 27, 68, 35, 84 ⑶ 15, 20, 21, 25, 35, 27, 47, 68, 84 ⑷ 15, 20, 21, 25, 27, 35, 47, 68, 84 则采用的排序方法是( ). A 希尔排序 B 简单选择排序 C 快速排序 D 归并排序 【解答】C
