阅读以下函数说明、图和C程序代码，将C程序段中(1)～(6)空缺处的语句填写完整。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出

admin2013-01-05 85

问题阅读以下函数说明、图和C程序代码，将C程序段中(1)～(6)空缺处的语句填写完整。
[说明]
散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
例如，设散列函数为Hash(Key)=Key mod7，记录的关键字序列为15，14，21，87，96，293，35，24， 149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图2-27所示。

为简化起见，散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值0；否则返回值-1。
采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P设定基桶的数目。
函数中使用的预定义符号如下。

选项

答案这是一道要求读者掌握如何在散列文件中插入一个新的数据元素的编程题。本题的解答思路如下。在散列文件中插入一个新的数据元素的基本思路是，首先将要插入的元素代入到散列函数中，从而计算出该元素的散列地址。然后按照散列地址，在基桶中查找空闲单元，若找到，则将元素插入，若基桶已满，则在溢出桶中查找空闲单元。若溢出桶中也查找不到，则申请新的溢出桶，然后将元素存入。在散列文件中查找一个元素的基本思路是，查找指定元素记录时，首先在基桶中查找，若找到，则成功返回，否则沿指针到溢出桶中进行查找。在本试题中，将元素存储在预先设定的基桶或根据需要申请的溢出桶中，只要基桶中有空闲单元，就将新元素NewElemkey插入在基桶中，若基桶中无空闲单元，则看是否存在溢出桶，若存在，则在溢出桶中查找空闲单元，若不存在溢出桶或溢出桶中无空闲单元，则申请一个溢出桶并存入新元素。在基桶查找空闲单元时，使用的桶号为Index，由此可知(1)空缺处所填写的内容是“Index=NewElemKey%P”，或“Index=Hash(NewElemKey)”等其他等价形式。一旦在基桶中找到空闲单元，即“Bucket[1ndex].keyData[i]==NULLKEY”(0≤i＜ITEMS)，则可将元素NewElemkey放入Bucket[Index].keyData[i]，至此元素已经插入散列桶中，函数可返回，因此(2)空缺处所填写的内容是“i＜ITEMS”。反之，若在基桶中没有找到空闲单元，则需查找溢出桶。“t=Bucket[Index].Link”，指针t首先指向桶号Index的第一个溢出桶。以下的代码完成在溢出桶中查找空闲单元的功能。 [*] 由于每个溢出桶都可以存储ITEMS个元素，因此在溢出桶中查找空闲单元与在基桶中的查找过程相同，代码如下。 [*] 若在指针t指向的溢出桶中找到空闲单元则插入元素，否则，由“t=t-＞Link”得到下一个溢出桶的指针，因此“k＜ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。显然，在桶号Index的基桶和其所有溢出桶都已满的情况下，t的值为空指针。此时才需要申请新的溢出桶并建立链接关系，因此在上面查找溢出桶中空闲单元时，进行指针t的后移“t=t-＞Link’’前应先用front记录t的值，以便于后面建立链接关系。所以(3)空缺处应给front置初值，即所填写的内容是“front=＆Bucket[Index]”，或“front=Bucket+Index”等其他等价形式。 (4)空缺处用于判断该溢出桶是否已满，即所填写的内容是“k=ITEMS(或k＞=ITEMS)”。如果该溢出桶已满，则继续查找下一个溢出桶，直到查找到空闲单元为止。若所有溢出桶都不存在空闲单元(即t==NULL)，则申请新的溢出桶，并将新的溢出桶的首地址保存在原有的最后一个溢出桶的Link域中(即front-＞Link=s)。因此(5)空缺处所填写的内容是“t==NULL”， (6)空缺处用于建立新申请溢出桶的链接关系——“front-＞Link=s”。

解析

转载请注明原文地址:https://kaotiyun.com/show/nYDZ777K

本试题收录于：软件设计师下午应用技术考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

系统响应时间和作业吞吐量是衡量计算机系统性能的重要指标。对于一个持续处理业务的系统而言，其(4)。

若某条无条件转移汇编指令采用直接寻址，则该指令的功能是将指令中的地址码送入______。

下图是①设计模式的类图，该设计模式的目的是②，图中，Abstraction和RefinedAbstraction之间是③关系，Abstraction和Implementor之间是④关系。②处应填入？

将源程序中多处使用的同一个常数定义为常量并命名，______。

在引入自动化测试工具以前，手工测试遇到的问题包括()。①工作量和时间耗费过于庞大②衡量软件测试工作进展困难③长时间运行的可靠性测试问题④对并发用户进行模拟的问题⑤确定系统的性能瓶颈问题⑥软件测试过程的管

黑盒测试法是根据产品的______来设计测试用例的。A．功能B．输入数据C．应用范围D．内部逻辑

通用的风险分析表应包括()。(54)①风险问题②发生的呵能性③影响的严重性④风险预测值⑤风险优先级

开展出版活动的基本条件中，首要的是()。

服用胃动力药多潘立酮治疗消化不良，最佳用药时间是()。

常用有效量应比最小有效量大，而比最小中毒量小得多。()

隧道混凝土衬砌实测项目包括()。

商业银行财务管理的核心内容是()。

设计网页时，为了方便浏览者从一个页面跳到另一个页面通常用()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性：

根据下列材料，回答问题。某研究设计院向不同岗位级别职工支付的工资额以及该院职工人员结构资料分别如图1和图2。该研究设计院报告期工资总额较基期的增长率为()。

GeneticallyModifiedFoods—FeedtheWorld?[A]Ifyouwanttosparkaheateddebateatadinnerparty,bringupthetopicaboutg