免费智能真题库 > 历年试卷 > 软件设计师 > 2009年上半年 软件设计师 上午试卷 综合知识
  第57题      
  知识点:   动态查找表   静态查找表   查找
  章/节:   计算机软件知识       

 
下面关于查找运算及查找表的叙述,错误的是(57) 。
 
 
  A.  哈希表可以动态创建
 
  B.  二叉排序树属于动态查找表
 
  C.  二分查找要求査找表采用顺序存储结构或循环链表结构
 
  D.  顺序査找方法既适用于顺序存储结构,也适用于链表结构
 
 
 

 
  第61题    2015年上半年  
   68%
用某排序方法对一元素序列进行非递减排序时,若该方法可保证在排序前后排序码相同者的相对位置不变,则称该排序方法是稳定的。简..
  第61题    2012年下半年  
   59%
下图所示为一棵M阶B-树,M最有可能的值为(61).
  第62题    2013年下半年  
   55%
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(62);若采用快速排序算法,则时间和空间复杂度分别..
   知识点讲解    
   · 动态查找表    · 静态查找表    · 查找
 
       动态查找表
               二叉排序树
               二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
               (1)若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
               (2)若它的右子树非空,则右子树上所有节点的值均大于根节点的值。
               (3)左、右子树本身就是两棵二叉排序树。
               二叉排序树的查找过程是:若二叉排序树非空,则将给定值与根节点的关键字值相比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到节点的路径;否则查找过程终止于一棵空树。
               二叉排序树中插入节点的操作:每读入一个元素,建立一个新节点,若二叉树非空,则将新节点的值与根节点的值相比较,如果小于根节点的值,则插入到左子树中,否则插入到右子树中;若二叉排序树为空,则新节点作为二叉排序树的根节点。
               二叉排序树中删除节点的操作:在二叉树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性,也就是说,删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*pp指针指向被删除节点),*f为其双亲节点,则删除节点*p的过程可分为以下3种情况。
               ①若*p节点为叶子节点,即p→lchild及p→rchild均为空,则由于删去叶子节点后不破坏整棵树的结构,因此只需修改*p节点的双亲节点*f的相应指针即可,即f→lchild(或f→rchild)=NULL。
               ②若*p节点只有左子树或者只有右子树,此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树,即令f→lchild(或f→rchild)=p→lchild,或f→lchild(或f→rchild)=p→rchild。
               ③若*p节点的左、右子树均不空,则不能像上面那样简单处理,删除*p节点时应将*p的左子树、右子树连接到适当的位置,并保持二叉排序树的特性。可采用以下两种方法进行处理:一是令*p的左子树为*f的左(或右)子树,而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上;二是用*p的中序直接前驱(或后继)节点*s代替*p节点,然后删除*s节点。
               平衡二叉树
               平衡二叉树又称为AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左、右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1;若将二叉树节点的平衡因子定义为该节点的左子树的深度减去其右子树的深度,则平衡树上所有节点的平衡因子只可能是-1、0和1;只要树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
               平衡二叉树上的插入操作。失去平衡后进行调整的规律可归纳为4种情况:①单向右旋平衡处理;②单向左旋平衡处理;③双向旋转(从左到右)平衡处理;④双向旋转(从右到左)平衡处理。
               平衡二叉树上的删除操作:若删除节点的两个子树都不为空,就用该节点左子树上的中序遍历的最后一个节点(或其右子树上的第一个节点)替换该节点,将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后,从被删节点到树根的路径上所有节点的平衡因子都需要更新,对于每一个位于该路径上的平衡因子为±2的节点来说,都要进行平衡处理。
               B-树
               B-树的定义:一棵m阶的B-树,或为空树,或为满足下列特性的m叉树。
               (1)树中每个节点至多有m棵子树。
               (2)若根节点不是叶子节点,则至少有两棵子树。
               (3)除根之外的所有非终端节点至少有棵子树。
               (4)所有的非终端节点中包含下列数据信息,即
               (n,A0,K1,A1,K2A2,…,Kn,An)
               式中,Ki(i=1,2,…,n)为关键字,且Ki<Ki+1(i=1,2,…,n-1);Ai(i=1,2,…,n)为指向子树根节点的指针,且指针Ai-1,所指子树中所有节点的关键字均小于Ki(i=1,2,…,n),An所指子树中所有节点的关键字均大于Kn为节点中关键字的个数。
               (5)所有的叶子节点都出现在同一层次上,并且不带信息(可以看作外部节点或查找失败的节点,实际上这些节点不存在,指向这些节点的指针为空)。
               B-树上进行查找的过程是:首先在根节点所包含的关键字中查找给定的关键字,若找到则成功返回;否则确定待查找的关键字所在的子树并继续进行查找,直到查找成功或查找失败(指针为空)时为止。
               B-树上的插入和删除运算较为复杂,因为要保证运算后节点中关键字的个数大于等于,因此涉及节点的"分裂"及"合并"问题。
               在B-树中插入一个关键字时,不是在树中加一个叶子节点,而是首先在低层的某个终端节点添加一个关键字,若该节点中关键字的个数不超过m-1,则完成插入;否则,要进行节点的"分裂"处理。"分裂"就是把节点中处于中间位置上的关键字取出来插入到其父节点中,并以该关键字为分界线,把原节点分成两个节点,"分裂"过程可能会一直持续到树根。
               在B-树中删除一个节点时,首先找到关键字所在的节点,若该节点在含有信息的最后一层,且其中关键字的数目不少于,则完成删除;否则需进行节点的"合并"运算。若待删除的关键字所在节点不在含有信息的最后一层上,则将该关键字用其在B-树中的后继替代,然后再删除其后继元素,即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
 
       静态查找表
               顺序查找
               顺序查找的基本思想是:从表的一端开始,逐个进行记录的关键字和给定值的比较,若找到一个记录的关键字与给定值相等,则查找成功;若整个表中的记录均比较过,仍未找到关键字等于给定值的记录,则查找失败。
               顺序查找的性能分析如下。
               一般情况下,ci=n-i+1,因此在等概率情况下,顺序查找成功的平均查找长度为
               
               也就是说,成功查找的平均次数约为表长的一半。与其他方法相比,顺序查找方法在n值较大时,其平均查找长度较大,查找效率较低。但这种方法也有优点,就是算法简单且适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可使用。
               折半查找
               折半查找的基本思想是:设查找表的元素存储在一维数组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)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
   题号导航      2009年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第57题    在手机中做本题