免费智能真题库
>
历年试卷
>
软件设计师
>
2023年下半年 软件设计师 上午试卷 综合知识
第39题
知识点：
折半查找
章/节：
计算机软件知识
对于有序表(8,15, 19, 23, 26, 31, 40, 65, 91)，用二分法进行查找时，可能的关键字比较顺序为（ ）。
A. 26,40,65
B. 26,8,19
C. 26,23,19
D. 26,31,40
本题目为专供试卷题目。
【如需要，请开通】
您暂时无法使用本功能。
【如需要，请开通】
为保障您的权益，请登录
相关试题：
计算机软件知识
更多>
第61题
2019年下半年
62%
对于如下所示的有向图，其邻接矩阵是一个(60)的矩阵。采用邻接链表存储时，顶点1的表结点个数为2，顶点5的表结点个数为0，顶点2和..
第21题
2018年下半年
13%
下面二叉树表示的简单算术表达式为（ ）。
第52题
2020年下半年
37%
某高校信息系统设计的分E-R图中，人力部门定义的职工实体具有属性：职工号、姓名、性别和出生日期；教学部门定义的教师实体具有属..
知识点讲解
·
折半查找
折半查找
折半查找的基本思想是：设查找表的元素存储在一维数组
r
[1…
n
]中，那么在表中的元素已经按关键字递增（或递减）的方式排序的情况下，可进行折半查找。其方法是：首先将待查的key值与表
r
中间位置上（下标为mid）记录的关键字进行比较，若相等则查找成功；若key>
r
[mid].key，则说明待查记录只可能在后半个子表
r
[mid+1…
n
]中，下一步应在后半个子表中再进行折半查找；若key<
r
[mid].key，说明待查记录只可能在前半个子表
r
[1…mid-1]中，下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
折半查找的性能分析：折半查找的过程可以用一棵二叉树描述，不妨设节点总数为
n
=2
h
-1，则判定树是深度为
h
=log
2
(
n
+1)的满二叉树。在等概率情况下，折半查找的平均查找长度为
。
当
n
值较大时，ASL
bs
≈log
2
(
n
+1)-1。
折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。
题号导航
2023年下半年 软件设计师 上午试卷 综合知识
本试卷我的完整做题情况
1
/
2
/
3
/
4
/
5
/
6
/
7
/
8
/
9
/
10
/
11
/
12
/
13
/
14
/
15
/
16
/
17
/
18
/
19
/
20
/
21
/
22
/
23
/
24
/
25
/
26
/
27
/
28
/
29
/
30
/
31
/
32
/
33
/
34
/
35
/
36
/
37
/
38
/
39
/
40
/
41
/
42
/
43
/
44
/
45
/
46
/
47
/
48
/
49
/
50
/
51
/
52
/
53
/
54
/
55
/
56
/
57
/
58
/
59
/
60
/
61
/
62
/
63
/
64
/
65
/
66
/
67
/
68
/
69
/
70
/
71
/
72
/
73
/
74
/
75
/
第39题 在手机中做本题
