免费智能真题库 > 历年试卷 > 软件设计师 > 2020年下半年 软件设计师 上午试卷 综合知识
  第59题      
  知识点:   线性表   查找
  章/节:   计算机软件知识       

 
线性表L中进行二分查找,要求L( )。
 
 
  A.  顺序存储,元素随机排列
 
  B.  双向链表存储,元素随机排列
 
  C.  顺序存储,元素有序排列
 
  D.  双向链表存储,元素有序排列
 
 
 

  相关试题:链表          更多>  
 
  第57题    2014年上半年  
   37%
若对线性表的最常用操作是访问任意指定序号的元素,并在表尾加入和删除元素,则适宜采用 (57) 存储。
  第65题    2010年上半年  
   60%
若对一个链表最常用的操作是在末尾插入结点和删除尾结点,则采用仅设尾指针的单向循环链表(不含头结点)时,(65)。
  第58题    2016年下半年  
   23%
设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素,若采用顺序存储结构,则平均需要移动(58)个元素;若采用..
   知识点讲解    
   · 线性表    · 查找
 
       线性表
               线性表的定义
               线性表是n个元素的有限序列,通常记为(a1,a2,…,an)。其特点如下。
               .存在唯一的一个称为"第一个"的元素。
               .存在唯一的一个称为"最后一个"的元素。
               .除了表头外,表中的每一个元素均只有唯一的直接前驱。
               .除了表尾外,表中的每一个元素均只有唯一的直接后继。
               线性表的存储结构
               1)顺序存储
               线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下,存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动大量的元素。
               一般地,在线性表的顺序存储结构中,第i个元素ai的存储位置为
               LOC(ai)=LOC(a1)+(i-1)×L
               式中,LOC(a1)为表中第一个元素的存储位置;L为表中每个元素所占空间的大小。
               2)链式存储
               线性表的链式存储是指用节点来存储数据元素,节点的空间可以是连续的,也可以是不连续的,因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请,无须事先分配。最基本的节点结构如下图所示。
               
               最基本的节点结构
               其中,数据域用于存储数据元素的值,指针域则存储当前元素的直接前驱或直接后继信息,指针域中的信息称为指针(链)。n个节点通过指针连成一个链表,若节点中只有一个指针域,则称为线性链表(单链表)。
               线性表采用链表作为存储结构时,不能进行数据元素的随机访问,但其优点是插入和删除操作不需要移动元素。以下是几种其他链表结构。
               (1)双向链表。每个节点包含两个指针,指明直接前驱和直接后继元素,可在两个方向上遍历链表。
               (2)循环链表。表尾节点的指针指向表中的第一个节点,可在任何位置上开始遍历整个链表。
               (3)静态链表。借助数组来描述线性表的链式存储结构。
               在链式存储结构中,只需要一个指针(头指针)指向第一个节点,就可以顺序访问到表中的任意一个元素。为了简化对链表状态的判定和处理,特别引入一个不存储数据元素的节点,称为头节点,将其作为链表的第一个节点并令头指针指向该节点。
               线性表的插入和删除运算
               1)基于顺序存储结构的运算
               插入元素前要移动元素以挪出空的存储单元,然后再插入元素;删除元素时同样需要移动元素,以填充被删除的存储单元。在等概率下平均移动元素的次数分别是
               
               2)基于链式存储结构的运算
               在链式存储结构下进行插入和删除,其实质都是对相关指针的修改。
               (1)在单向链表中插入节点时,指针的变化情况如下图所示。
               
               单向链表插入节点时的指针变化情况
               (2)在单向链表中删除节点时,指针的变化情况如下图所示。
               
               单向链表删除节点时的指针变化情况
               (3)在双向链表中插入节点时,指针的变化情况如下图所示。
               
               双向链表插入节点时的指针变化情况
               (4)在双向链表中删除节点时,指针的变化情况如下图所示。
               
               双向链表删除节点时的指针变化情况
               注意:以上3图中①为插入运算前的指针走向;②为插入运算后的指针走向;虚线为插入后的指针指向。
 
       查找
        1)顺序查找
        顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        2)折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3)分块查找
        在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
        4)哈希表及其查找
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
   题号导航      2020年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第59题    在手机中做本题