中级软件设计师问答试卷（中级软件设计师）_12.docVIP

试卷第 PAGE 1 页共 NUMPAGES 1 页 中级软件设计师问答试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、例如：设散列函数为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，建立的散列文件内容如图所示。  为简化起见，散列文件的存储单位以内存单元表示。 函数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[i]=NULLKEY) Bucket[Index].KeyData[i]=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*/