20172323 2018-2019-1 《程序设计与数据结构》课堂作业报告

20172323 2018-2019-1 《程序设计与数据结构》课堂作业报告

课程:《程序设计与数据结构》
班级: 1723
姓名: 王禹涵
学号: 20172323
实验教师:王志强老师
测试日期:2018年10月
必修/选修: 必修

1.测试内容

ASL测试
已知线性表具有元素{5,13,19,21,37,56,64,75,80,88,92},如果使用折半查找法,ASL是多少?

2. 解题原理及过程

  • 二分查找(折半查找):当查找池中的项目组是已排序的,那么利用二分查找将会更有效率。

    • 二分查找的思路: 二分查找从排序列表的中间开始查找,如果中间元素不是目标元素,根据两个元素的大小关系,再判断从列表的前一半或是后一般进行查找。每次的查找都是从当前一串数字的中间元素开始的。直到最后找到该元素或是没有找到抛出一个信息。
    • 二分查找的每次比较都会删除一半的可行候选项,当查找池中有偶数个待查找值时,选择的是两个中间值的第一个。
  • ASL: 所谓ASL是指在查找过程中,为确定记录在查找表中的位置,需和给定值进行比较的记录关键字个数的平均值。

    • 折半查找的过程可以用二叉树来描述,树中的每个结点对应有序表中的一个记录,结点的值为该记录在表中的位置。
  • 解题:在本题中,线性表具有元素{5,13,19,21,37,56,64,75,80,88,92},可以画出计算机执行折半查找的顺序

位置 0 1 2 3 4 5 6 7 8 9 10 11
元素 ... 05 13 19 21 37 56 64 75 80 88 92
顺序 ... 3 4 2 3 4 1 3 4 2 3 4

二叉树如图所示

所以顺序为1的结点一个,2有两个,3有四个,4有四个。
ASL=(1+2x2+3x4+4x4) / 11 = 33/11= 3

PS:查阅折半查找ASL的算法时,文章给出了另一种ASL的算法

这种算法适用于n较大时的情况

原文地址:https://www.cnblogs.com/Lewandodoski/p/9785110.html