2. 计算机
  3. 阅读下列函数说明、图和C代码，将应填入(n)处的字句。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有 m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放

阅读下列函数说明、图和C代码，将应填入(n)处的字句。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有 m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放

admin2008-01-15  65
问题 阅读下列函数说明、图和C代码，将应填入(n)处的字句。
[说明]
   散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有 m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
例如：设散列函数为Hash(Key)=Key mod 7，记录的关键字序列为15,14,21,87,97,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453，建立的散列文件内容如图4-1所示。
[图4-1]
   
   为简化起见，散列文件的存储单位以内存单元表示。
   函数InsertToHashTable(int NewElemKey)的功能是：将元素NewEIemKey插入散列桶中，若插入成功则返回0，否则返回-1。
   采用的散列函数为Hash(NewElemKey)=NewElemKey % P，其中P为设定的基桶数目。
   函数中使用的预定义符号如下：
   #define NULLKEY  -1           /*散列桶的空闲单元标识*/
   #define P   7                 /*散列文件中基桶的数目*/
   #define ITEMS  3              /*基桶和溢出桶的容量*/
   typedef struct BucketNode{    /*基桶和溢出桶的类型定义*/
           int KcyData[ITEMS];
           struct BucketNode *Link;
   }BUCKET;
   BUCKET Bucket[P];             /*基桶空间定义*/
[函数]
   int lnsertToHashTable(int NewElemKey){
   /*将元素NewElemKey插入散列桶中，若插入成功则返回0，否则返回-1*/
   /*设插入第一个元素前基桶的所有KeyData[]、Link域已分别初始化为NULLKEY、
     NULL*/
       int Index;    /*基桶编号*/
   int i,k;
         BUCKET *s,*front,*t;
         (1)  ;
        for(i=0; i＜ITEMS;i++)/*在基桶查找空闲单元，若找到则将元素存入*/
          if(Bucket[Index].KeyData=NULLKEY){
              Bucket[Index].KeyData=NewElemKey;  break;
          }
        if(  (2)  ) return 0;
   /*若基桶已满，则在溢出桶中查找空闲单元，若找不到则申请新的溢出桶*/
         (3)  ;        t=Bucket[Index].Link;
        if(t!=NULL)   {/*有溢出桶*/
            while (t!=NULL){
              for(k=0; k＜ITEMS; k++)
                  if(t-＞KeyData[k]=NULLKEY){/*在溢出桶链表中找到空闲单元*/
                  t-＞KeyData[k]=NewElemKey;   break;
                  }/*if*/
               front=t;
               if(  (4)  )t=t-＞Link;
               else break;
              }/*while*/
        }/*if*/
        if(  (5)  ) {/*申请新溢出桶并将元素存入*/
           s=(BUCKET*)malloe(sizeof(BUCKET));
            if(!s)  return-1;
            s-＞Link=NULL;
            for(k=0; k＜ITEMS; k++)
               s-＞KeyData[k]=NULLKEY;
            s-＞KeyData[0]=NewElemKey;
               (6)  ;
        }/*if*/
       return 0;
   }/*InsertToHashTable*/
选项
答案(1) Index=NewElemKey % P (2) i＜ITEMS (3) front=&Bucket[Index] (4) k==ITEMS (5) t==NULL，或!t (6) front-＞Link=s
解析 本题考查元素的散列存储。
   元素作散列存储时，首先用设定的散列函数计算元素的存储位置。在本题中，将元素存储在预先设定的基桶或根据需要申请的溢出桶中，只要基桶中有空闲单元，就将新元素NewElemKey插入在基桶中，若基桶中无空闲单元，则看是否存在溢出桶，若存在，则在溢出桶中查找空闲单元，若不存在溢出桶或溢出桶中无空闲单元，则申请一个溢出桶并存入新元素。
   在基桶查找空闲单元时使用的桶号为Index，可知空(1)处应填入“Index= NewElemKey % P”。显然，一旦在基桶中找到空闲单元，即“Bucket[Index].KeyData== NULLKEY”(0≤i＜ITEMS)，则可将元素NewElemKey放入Bucket[Index].KeyData,至此元素已经插入散列桶中，函数可返回，因此空(2)处应填入“i＜ITEMS”；反之，若在基桶中没有找到空闲单元，则需查找溢出桶。“t=Bucket[Index].Link”，指针t首先指向桶号Index的第一个溢出桶。下面的代码即为在溢出桶中查找空闲单元。
    if(t!=NULL)  {/*有溢出桶*/
          while(t!=NULL){
            for(k=0; k＜ITEMS;k++)
                if(t-＞KeyData[k]==NULLKEY){/*在溢出桶链表中找到空闲单元*/
                t-＞KeyData[k]=NewElemKey;   break;
               }/*if*/
             front=t;
              if((4))t=t-＞Link;
              else break;
          }/*while*/
    }/*if*/
    由于每个溢出桶都可以存储ITEMS个元素，所以在溢出桶中查找空闲单元与在基桶中的查找过程相同，代码如下。
   for(k=0;k＜ITEMS;k++)
            if(t-＞KcyData[k]==NULLKEY){/*在溢出桶链表中找到空闲单元*/
             t-＞KeyData[k]=NewElemKey;  break;
            }/*if*/
   若在指针t指向的溢出桶中找到空闲单元则插入元素，否则，由“t=t-＞Link”得到下一个溢出桶的指针，因此“k＜ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。
   显然，在桶号Index的基桶和其所有溢出桶都已满的情况下，t的值为空指针。此时才需要申请新的溢出桶并建立链接关系，因此在上面查找溢出桶中空闲单元时，进行指针t的后移“t=t-＞Link”前应先用front记录t的值，以便于后面建立链接关系。所以空(3)处应给front置初值，即“front=&Bucket[Index]”，空(4)填入“k==ITEMS”，空(5)填入“t＝NULL”。空(6)处建立新申请溢出桶的链接关系“front-＞Link=s”。
转载请注明原文地址:https://www.kaotiyun.com/show/mfDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)