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

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

admin2009-05-15  185
问题 阅读以下函数说明、图和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
   散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
   例如：设散列函数为Hash(Key)=Key mod 7，记录的关键字序列为15，14，21，87，96， 293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图5-3所示。
        
   为简化起见，散列文件的存储单位以内存单元表示。
   函数InsertToHashTable(int NewElemKey)的功能是；若新元素NewElemKey正确插入散列文件中，则返回值1；否则返回值0。
   采用的散列函数为Hash(NewElemKey)=NewElemKey % P，其中P为设定的基桶数目。
   函数中使用的预定义符号如下：
   #define NULLKEY-1                         /*散列桶的空闲单元标识*/
   #define P 7                               /*散列文件中基桶的数目*/
   #define ITEMS 3                           /*基桶和溢出桶的容量*/
   typedef struet BucketNode{                /*基桶和溢出桶的类型定义*/
         int KeyData[ITEMS];
         struct BucketNode *Link;
   }BUCKET;
   BUCKET Bucket[P];                         /*基桶空间定义*/
【函数5-3】
   int InsertToHashTable(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 *)malloc(sizeof(BUCKET));
             if(!s)retum -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=Hash(NewElemKey)，或Index=NewElemKey%P (2) i＜ITEMS (3) front=&Bucket[Index]，或front=Bucket+Index (4) k==ITEMS，或k＞=ITEMS (5) t==NULL (6) front-＞Link=s
解析 本题考查链式存储的插入算法。
   根据题意，空(1)比较简单，应为计算散列值，并将关键字NewElemKey对应的散列值赋给表示基桶编号的变量Index，故空(1)应填Index=Hash(NewElemKey)。
   接下来进行插入操作，分3种情况进行处理：基桶未满、基桶已满但溢出桶未满、基桶和溢出桶(若有)都已满。基桶未满时，直接将关键字插入到基桶中即可；若基桶已满但溢出桶未满，则找到未满的溢出桶，将关键字插入；若基桶和溢出桶(若有)均已满，则新建溢出桶，并将关键字插入到新建的溢出桶中。
   空(1)之后的for语句在基桶中查找空闲单元，若找到则进行插入，如条件空(2)成立，返回0，表示插入成功，可见空(2)表示基桶未满，关键字已经成功插入。故空(2)应填i＜ITEMS。注意break语句，若基桶只剩最后一个单元，即i=ITEMS-1时才进行插入操作，由于有break语句，跳出for循环后，i值仍为ITEMS-1，而不会被加1。所以填成i＜=ITEMS是错误的。
   接着处理基桶已满的情况。空(3)应该是某个变量的初始化，不过暂时无法确定。
   首先处理有溢出桶的情况。既然基桶已满，就只能在溢出桶中查找空闲单元，若找到则进行插入。注意赋值语句“front=t”。空(4)条件成立时继续查找下一个溢出桶，即表示当前溢出桶中已经没有空闲单元了，因此空(4)应填k==ITEMS。这样结束while循环对应两种情况：已经成功插入(对应t不为NULL，front不确定)和所有溢出桶都没有空闲单元(对应 t为NULL，front指向最后一个溢出桶)。
   接着处理基桶和溢出桶(若有)均已满的情况，此时需要新建溢出桶。空(5)即为“基桶和溢出桶(若有)均已满”对应的条件，此处有个特例，基桶已满但没有溢出桶，此时对应 t==NULL。根据上面的分析并结合特例可得空(5)应该为t==NULL。新建溢出桶并将关键字插入后，还需要将溢出桶链接到正确位置。故空(6)应填front-＞link=s。
   注意，对于特例(基桶己满但没有溢出桶，对应t==NULL)，front并未赋值，此时front应该指向相应的基桶。由此可得空(3)应填front=&Bucket[Index]。
转载请注明原文地址:https://kaotiyun.com/show/65xZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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