软考在线  |  计算机技术与软件专业技术资格（水平）考试   |   [请选择科目]
[ 成为 VIP会员 ]        登录  |  注册      我的  购物车
件 
科目切换  联系我们 
    
  |   [请选择科目]
VIP：有效提升20分！  真题  历年真题 (可免费开通)/  百科全书/ 机考模拟平台/  最难真题榜/  自测/  攻打黄金十二宫/  真题检索/  真题下载/  真题词库
知识   必会知识榜/  最难知识榜/  知识点查询/      文档   学习计划/  精华笔记/  试题文档     纸质图书   《百科全书》HOT！！/         /        首页/  2025年上半年专区/  手机版/ 
免费智能真题库 > 历年试卷 > 软件设计师 > 2023年上半年 软件设计师 上午试卷 综合知识
  第60题      
  知识点：   折半查找   查找
  关键词：   二分查找        章/节：   计算机软件知识       

 
对某有序概序表进行折率查找《二分查找》时，进行比较的关键字序列不可能是（）.
 
 
  A.  42,61,90,85,77
 
  B.  42,90,85,61,77
 
  C.  90,85,61,77,42
 
  D.  90,85,77,61,42
 
 
 

 
  第33题    2024年下半年  
   0%
实现二分查找（折半查找）时，要求查找表 (61) 。
  第34题    2011年下半年  
   60%
下图所示的逻辑流实现折半查找功能，最少需要（34)个测试用例可以覆盖所有的可能路径。
  第57题    2010年上半年  
   49%
对n个元素的有序表A[1..n]进行二分（折半）查找（除2取商时向下取整)，查找元素A[i] 时，最多与A中的（57)个元素进行比较。
   知识点讲解    
   · 折半查找    · 查找
 
       折半查找
        折半查找的基本思想是：设查找表的元素存储在一维数组r[1…n]中，那么在表中的元素已经按关键字递增（或递减）的方式排序的情况下，可进行折半查找。其方法是：首先将待查的key值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等则查找成功；若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n]中，下一步应在后半个子表中再进行折半查找；若key<r[mid].key，说明待查记录只可能在前半个子表r[1…mid-1]中，下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
        折半查找的性能分析：折半查找的过程可以用一棵二叉树描述，不妨设节点总数为n=2h-1，则判定树是深度为h=log2(n+1)的满二叉树。在等概率情况下，折半查找的平均查找长度为。
        当n值较大时，ASLbs≈log2(n+1)-1。
        折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。
 
       查找
        1）顺序查找
        顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
        2）折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3）分块查找
        在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
        4）哈希表及其查找
        根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
   题号导航      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 /
 
第60题    在手机中做本题
    在线人数   共计 14916人 在线 
    dongjianta..     hs1295@hf-..     bfmso.luji..     837850688@..     zhangzhime..     zhangya031..
    suxianjun1..     zdwndjb@si..     alyssa196@..     shaoqinliu..     likaigreat..     jixiezheng..
    wwtld@qq.c..     lxyxxp@hot..     476756927@..     sunweimin@..     nuijiashen..     dzh9610@12..
    469820555@..     tanting121..     tanhanbiao..     huicong.li..     gll1986127..     616670365@..
    szqfzxy123..     limingren1..     gsxdyx@sin..     ylsmagic20..     dadola@163..     liyuweitop..
    xumeizhou2..     gao2008po@..     xujianchun..     fenger1112..     wenchongro..     daiqimao@1..
    luoyiyangz..     zhangya031..     bes80@163...     543548433@..     zengfei369..     liyashi998..

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2025 All Rights Reserved 软考在线版权所有