[考研类试卷]计算机专业基础综合数据结构（查找）历年真题试卷汇编1及答案与解析.doc

《[考研类试卷]计算机专业基础综合数据结构（查找）历年真题试卷汇编1及答案与解析.doc》由会员分享，可在线阅读，更多相关《[考研类试卷]计算机专业基础综合数据结构（查找）历年真题试卷汇编1及答案与解析.doc（29页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业基础综合数据结构（查找）历年真题试卷汇编 1 及答案与解析一、单项选择题1 顺序查找法适合于存储结构为_的线性表。【北京航空航天大学 2002 年】（A）顺序存储结构或链式存储结构（B）散列存储结构（C）索引存储结构（D）压缩存储结构2 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为_。【北京航空航天大学 2004 年】（A）(n 1)2（B） n2（C） (n+1)2（D）n3 当采用分块查找时，数据的组织方式为_。【太原科技大学 2007 年】（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据

2、不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同4 对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。【华中科技大学 2007 年】（A）50（B） 125（C） 500（D）log 225005 下面关于二分查找的叙述正确的是_。【南京理工大学 1996 年】（A）表必须有序，表可以顺序方式存储，也可以链表方式存储（B）表必须有序且表中数据必须是整型、实型或字符型（C）表必须有序，而且只能从小到大排列（D）表必须有序，且表只能

3、以顺序方式存储6 当 n 足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是_。【北京航空航天大学 2002 年】（A）(n+1) 2（B） n2（C） log2(n+1)一 1（D）log 2(n+1)7 在具有 15 个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录需要进行_次关键字值的比较。【北京航空航天大学 2004 年】（A）0（B） 4（C） 5（D）158 对一个长度为 50 的有序表进行折半查找，最多比较_次就能查找出结果。【北京邮电大学 2005 年】（A）6（B） 7（C） 8（D）99 已知一个有序表(13，

4、18，24，35，47，50，62，83，90，115，134)，当二分查找值为 90 的元素时，查找成功的比较次数为_。【浙江大学 2004 年】（A）1（B） 2（C） 4（D）610 折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素 75，需依次与表中元素_进行比较。【华中科技大学 2007 年】（A）6582，75（B） 70，82，75（C） 65，8l，75（D）65，81，70，7511 折半查找过程所对应的判定树是一棵_。【北京交通大学 2007 年】（A）最小生成树（B）平衡二叉树（C）完全二叉树（D）赫夫曼树12 对表长为

5、 n 的有序表进行折半查找，其判定树高度为_。【北京交通大学2004 年】（A）log 2(n+1)（B） log2(n+1)（C） log2n（D）log 2n13 图 5-1 是一棵_。【华南理工大学 2007 年】（A）4 阶 B-树（B） 4 阶 B+树（C） 3 阶 B-树（D）3 阶 B+树14 下列关于 m 阶 B-树的说法错误的是_。【南京理工大学 1997 年】（A）根结点至多有 m 棵子树（B）所有叶子都在同一层次上（C）非叶结点至少有 m2(m 为偶数)或 m2+1(m 为奇数)棵子树（D）根结点中的数据是有序的15 当向 B-树插入关键字时，可能引起结点的_；最终可能导

6、致整个 B-树的高度_。【浙江大学 2004 年】（A）合并（B）增加 1（C）分裂（D）减少 116 m 阶 B-树的每个分支结点中最多包含_个关键字值。 【北京航空航天大学2007 年】（A）m 2（B） m 一 1（C） m（D）m+117 在一棵 m 阶 B-树中，若在某结点中插入一个新关键字而引起该结点的分裂，则此结点中原有的关键字的个数是_。【湖南大学 2003 年】（A）m（B） m+1（C） m1（D）m218 理想情况下，散列表的平均比较次数为_。【北京邮电大学 2005 年】（A）1（B） 2（C） 4（D）n19 设有一组记录的关键字为19，14，23，1，68，20，8

7、4，27，55，11，10，79 ，用链地址法构造散列表，散列函数为 H(key)=keyMOD13，散列地址为 1 的链中有_个记录。【南京理工大学 1997 年】（A）1（B） 2（C） 3（D）420 若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需(1)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(2)。【南京理工大学 1999 年】21 关于杂凑查找说法不正确的有_个。【南京理工大学 2000 年】(1)采用链地址法解决冲突时，查找一个元素的时间是相同的(2)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3)用链

8、地址法解决冲突易引起聚集现象(4)再散列法不易产生聚集（A）1（B） 2（C） 3（D）421 散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列 26，25，72，38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】22 采用链地址法解决冲突的散列表中，查找成功的平均查找长度_。【北京交通大学 2007 年】（A）直接与关键字个数有关（B）直接与装填因子有关（C）直接与表的容量有关（D）直接与散列函数有关23 在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值_。【北京交

9、通大学 2006 年】（A）一定都是同义词（B）不一定都是同义词（C）都相同（D）一定都不是同义词24 设初始为空的散列表的地址空间为(O10)，散列函数为 H(k)=kmod11，采用线性探测再散列法处理冲突，若依次插入关键字 37，95，27，14，48，则最后一个关键字值 48 的插入位置是_。【北京航空航天大学 2007 年】（A）4（B） 5（C） 6（D）725 在构造散列表方面，下面的说法_是正确的。【华南理工大学 2006 年】（A）再散列法在处理冲突时不会产生聚集（B）散列表的装填因子越大，说明空间利用率越好，因此应使装填因予尽量大（C）散列函数选的好可减少冲突现象（D）对于

10、任何具体关键字都不可能找到不产生冲突的散列函数26 将 10 个元素散列到 100000 个单元的散列表中，则_产生冲突。【北京邮电大学 2001 年】（A）一定会（B）一定不会（C）仍可能会27 用二分(对半) 查找表的元素的速度比用顺序法_。【南京理工大学 1998】（A）必然快（B）必然慢（C）相等（D）不能确定28 折半查找的时间复杂度为_。【中山大学 1999 年】【华南理工大学 2007 年】（A）O(n 2)（B） O(n)（C） O(nlog2n)（D）O(log 2n)29 在等概率情况下，线性表的顺序查找的平均查找长度(ASL)为_，有序表的折半查找的 ASL，为_。【上海

11、海事大学 1999 年】（A）O(1)（B） O(log2n)（C） O(log2n)2)（D）O(nlog 2n)EO(n)30 衡量查找算法性能好坏的主要标准是_。【北京航空航天大学 2004 年】（A）参加比较的关键字值的多少（B）被查找的关键字值在关键字序列中的位置（C）关键字值序列中是否存在被查找关键字值（D）关键字值的平均比较次数的多少31 只能在顺序存储结构上进行的查找方法是_。【北京航空航天大学 2005 年】（A）顺序查找法（B）折半查找法（C）树型查找法（D）散列查找法31 若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需(1)个链表。这些链的链首

12、指针构成一个指针数组，数组的下标范围为(2)。【南京理工大学 1999 年】32 (1)（A）17（B） 13（C） 16（D）任意33 (2)（A）017（B） 117（C） 016（D）11633 散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列 26，25，72，38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】34 元素 59 存放在散列表中的地址是_。（A）8（B） 9（C） 10（D）1135 存放元素 59 需要搜索的次数是_。（A）2（B） 3（C） 4（D）5二、综合题35 假定折半查找表长为 10

13、的有序表：【华中科技大学 2006 年】36 试画出描述折半查找过程的带外表结点(表示查找不成功情况的结点)的判定树。37 假定每个元素的查找概率相等，试计算查找成功时的平均查找长度。38 写出二分查找的递归程序。【北京交通大学 2006 年】初始调用时，low 为1，high 为 ST.1ength。39 请写一非递归算法，该算法在按值严格递增排序的顺序表 A【1n】中采用折半查找法查找值不小于 item 的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息 0。【北京航空航天大学 2007 年】39 对图 5-2 所示的 3 阶 B-树，依次执行下列操作，画出

14、各步操作的结果。【合肥工业大学 1999 年】40 插入 9041 插入 2542 插入 4543 删除 6044 删除 8044 对下面的关键字集30，15，21，40，25，26，36，37)若查找表的装填因子为08，采用线性探测再散列方法解决冲突，做：45 设计散列函数。46 画出散列表。47 计算查找成功和查找失败的平均查找长度。48 写出将散列表中某个数据元素删除的算法。【东北大学 2001 年】48 设散列函数 H(K)=3Kmod11，散列地址空间为 010，对关键字序列(32，13 ，49，24，38，21，4，12)按下述两种解决冲突的方法构造散列表：49 线性探测再散列。5

15、0 链地址法。并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLSUCO 和 ASLunsucc。【北方交通大学 1998 年】51 将一组数据元素按散列函数 H(key)散列到散列表 H(0m) 中，用线性探测法处理冲突(H(key)+1、H(key)+2、H(key) 一 1)，假设空单元用 EMPTY 表示，删除操作是将散列表中结点标志位从 INIJSE 标记为 DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001 年】计算机专业基础综合数据结构（查找）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 A【试题解析】 考查顺序

16、查找的适合结构。顺序查找从线性表的一端开始，逐个检查关键字是否满足给定的条件。存储结构为顺序存储或链式存储。【知识模块】 查找2 【正确答案】 C【试题解析】 考查顺序查找法平均查找长度。查找第 1 个记录的查找长度为 1，查找第 n 个记录的查找长度为 n，查找每个记录的概率为 1n。ASL 为n(1+n)2 n=(n+1)2。【知识模块】 查找3 【正确答案】 B【试题解析】 考查分块查找的定义。分块查找要求将查找表按照关键码的区间分成若干个子表，并对子表建立索引表。索引表有序，子表不一定有序。子表中最大或最小的数据组成索引块。【知识模块】 查找4 【正确答案】 A【试题解析】 考查分块查

17、找的最优块长。分块查找的平均查找长度不仅和表的总长度 n 有关，而且和所分的子表个数 s 有关，对于 n 给定的情况下，s 取 时，ASL 取得最小值 。所以，最理想块长为 50。【知识模块】 查找5 【正确答案】 D【试题解析】 考查折半查找的条件。顺序查找只要求是线性表，顺序存储还是链式存储都可以，元素不要求有序。折半查找要求以顺序方式存储且数据元素有序。【知识模块】 查找6 【正确答案】 C【试题解析】 考查折半查找平均查找长度的计算。在等概率查找时，查找成功的平均查找长度为 其中，h 代表判定树的高度，并且有元素个数为 n 时树高 h=log2(n+1)。【知识模块】 查找7 【正确答

18、案】 B【试题解析】 考查折半查找不存在的记录所需比较次数。可以通过分析判定树的方式计算。判定树中共有 4 层，是一棵满二叉树。查找一个文件中不存在的记录需要进行 4 次比较。【知识模块】 查找8 【正确答案】 A【试题解析】 考查折半查找最多比较次数的计算。对应判定树总共 6 层，其中，第 6 层未满。所以比较次数最多为 6 次。【知识模块】 查找9 【正确答案】 B【试题解析】 考查折半查找某元素的详细过程。开始时 low 指向 13，high 指向134，mid 指向 50，比较第 1 次 9050，所以将 low 指向 62，high 指向 134，mid指向 90，第 2 次比较找到

19、 90.【知识模块】 查找10 【正确答案】 D【试题解析】 考查折半查找某元素的详细过程。开始时 low 指向 2，high 指向100，mid 指向 65。第 1 次比较 7565。然后 low 指向 70，high 指向 100，mid 指向 81。第 2 次比较，7570。low 指向 75，high 指向 75，mid 指向 75。第 4 次比较查找成功。【知识模块】 查找11 【正确答案】 B【试题解析】 考查折半查找判定树的类型。判定树只有最低一层有可能不满，其他各层都是满的。最低一层叶子结点不一定全在左边，所以不一定是完全二叉树，是一棵平衡二叉树。【知识模块】 查找12 【正确

20、答案】 A【试题解析】 考查折半查找判定树的高度。判定树只有最低一层有可能不满。类似完全二叉树的计算过程，可得，高度应该为log 2(n+1)或者log 2(n)+1。【知识模块】 查找13 【正确答案】 A【试题解析】 考查 B 树的识别。关键字数目比子树数目少 1，所以不是 B+树，是 B 树。又有 m 阶 B 树结点关键字数最多为 m 一 1，有一个结点关键字个数为3，所以，不可能为 3 阶。【知识模块】 查找14 【正确答案】 C【试题解析】 考查 B 树的相关性质。除根之外的所有非终端结点至少有m2棵子树。对于根结点，最多有 m 棵子树，若不是叶子结点至少有 2 棵子树。【知识模块】

21、 查找15 【正确答案】 C【试题解析】 B。考查 B-树的插入。如果遇到添加新关键字使得某结点个数超过了上限，引起结点分裂，则将其按中间一个关键字为界分裂两个新的结点，分别包含m21 和 mm2个关键字，而将中间的第m2个关键字添加到其父结点中去。若此时导致其父结点也超过了上限，则继续这种分裂操作。最终可能导致B-树高度加 1。【知识模块】 查找16 【正确答案】 B【试题解析】 考查 B-树结点关键字个数。B-树中每个结点至多有 m 棵子树，m一 1 个关键字值。【知识模块】 查找17 【正确答案】 C【试题解析】 考查 B-树结点关键字最大限制。m 阶 B 树中结点最大关键字数目为 m

22、一 1。【知识模块】 查找18 【正确答案】 A【试题解析】 考查散列表的理想甲均比较次数。敞列表平均比较次数和装填因了直接相关，在最理想情况下，散列表的平均比较次数为 1，通过散列函数直接计算即可得到元素位置。【知识模块】 查找19 【正确答案】 D【试题解析】 考查通过散列函数计算散列地址。易得，14，1，27，79 的散列地址为 1。【知识模块】 查找20 【正确答案】 A【知识模块】 查找21 【正确答案】 B【试题解析】 考查散列查找法的几种冲突解决办法。链地址法解决冲突时查找一个元素可能需要在链表中遍历，所需时间不一样。聚集又称堆积，是指散列地址不同的结点争夺同一个后继散列地址的现

23、象。注意：同义词发生冲突不是聚集，链地址法解决冲突时将同义词放在同一个链表中，不会引起聚集现象。【知识模块】 查找【知识模块】 查找22 【正确答案】 B【试题解析】 考查链地址法散列表查找成功的平均查找长度的决定因素。实际上，散列表的平均性能依赖于散列表的装载因子 ，并不直接依赖于关键字个数或表长，见表 5-1。【知识模块】 查找23 【正确答案】 A【试题解析】 考查链地址法散列表的查找。在此种散列表中，同一条链中存放的元素必然是同义词。每次查找时先计算元素在表中的位置，然后遍历链，直到找到所查找元素为止。【知识模块】 查找24 【正确答案】 C【试题解析】 考查线性探测法实现的散列表的插

24、入。前 4 个元素分别插入到4、7、5、3 的位置上，关键字 48 的元素通过散列函数计算得应插入到位置 4 当中，有冲突，依次探测 5、6，发现 6 为空则插入。【知识模块】 查找25 【正确答案】 C【试题解析】 考查散列表相关性质。再散列法也可能产生聚集。装填因予越大，则空闲空间越少，探测的次数便越多，平均查找长度变长。对于具体的关键字可以找到不产生冲突的散列函数。【知识模块】 查找26 【正确答案】 C【试题解析】 考查冲突的产生。无论散列表表长多大，只要插入的元素不止一个，通过散列函数计算的插入位置便有可能相同。【知识模块】 查找27 【正确答案】 D【试题解析】 考查折半查找和顺序

25、查找的速度比较。【知识模块】 查找28 【正确答案】 D【试题解析】 考查折半查找的时间复杂度。【知识模块】 查找29 【正确答案】 E,B【试题解析】 考查顺序查找和折半查找的 ASL。顺序查找的平均查找长度为(n+1)2，折半查找查找成功的 ASL 为(n+1)，n10g 2(n+1)1。【知识模块】 查找30 【正确答案】 D【试题解析】 考查查找算法性能的衡量方式。关键字值的平均比较次数越少，查找时间越短，算法的性能越好。【知识模块】 查找31 【正确答案】 B【试题解析】 考查各种查找所要求的存储结构。顺序查找可以是顺序存储或者链式存储，折半查找只能是顺序存储并且元素值有序，树型查找

26、法要求采用树的存储结构，即可以采用顺序存储也可以采用链式，散列查找中连接法解决冲突的时候是采用顺序存储与链式存储结合的方式。【知识模块】 查找【知识模块】 查找32 【正确答案】 A【知识模块】 查找33 【正确答案】 C【试题解析】 考查链地址法构造散列表。根据散列函数可得，最终计算的地址共有 17 种可能，所以需要 17 个链表。指针数组中下标从 0 开始，共 17 个地址。【知识模块】 查找【知识模块】 查找34 【正确答案】 D【知识模块】 查找35 【正确答案】 C【试题解析】 考查线性探测法实现的散列表的散列过程。将前面各元素分别放入散列表中，其中 8、9、10 的位置分别存放 2

27、5、26、8。元素 59 经过散列函数计算应该存入位置 8，有冲突，采用线性探测再散列，依次比较 9、10、11，发现 11 为空，所以放入 11 中。总过程需搜索 4 次。【知识模块】 查找二、综合题【知识模块】 查找36 【正确答案】 折半查找过程的带外表结点的判定树如图 5-3 所示。【知识模块】 查找37 【正确答案】 ASL SUCC=(1+22+34+43)10=29。【知识模块】 查找38 【正确答案】 算法的基本设计思想：根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键字在哪一部分，然后用新的序列起始位置和终止位置递归求解。算法的代码：typedef stru

28、ct 查找表的数据结构E1emType*elem； 存储空间基址，建表时按实际长度分配，0 号留空int length; 表的长度SSTable；int Search(SSTable ST，ElemType Key，int low，int high)在有序表中递归折半查找其关键字为 Key 的元素，返回其在表中序号int mid=(10w+high)2;if(10whigh)return 0；if(KeySTelemmid)Search(ST， Key，mid+l，high)；向后半部分查找else if(Keyhigh 则返回 mid+l 这种情况while(10wSTelemmid)low

29、=mid+1； 向后半部分查找e1Se if(itemSTelemmid)high=mid 一 1， 向前半部分查找elsereturn mid; 查找成功if(midSTlength)return mid+1 ;elsereturn o;/Search【知识模块】 查找【知识模块】 查找40 【正确答案】 插入 90，如图 5-4 所示。【知识模块】 查找41 【正确答案】 插入 25，如图 5-5 所示。【知识模块】 查找42 【正确答案】 插入 45，如图 5-6 所示。【知识模块】 查找43 【正确答案】 删除 60，如图 5-7 所示。【知识模块】 查找44 【正确答案】 删除 80

30、，如图 5-8 所示。【知识模块】 查找【知识模块】 查找45 【正确答案】 由于装填因子为 08，关键字有 8 个，所以表长为808=10 。用除留余数法，取关键字被某个不大于散列表表长 m 的数 P 除后所得余数为散列地址。H(key)=keyp(pm)，一般是对表长求余，为了不失一般性，本题采用不对表长求余的情况，设散列函数为 H(key)=key7。【知识模块】 查找46 【正确答案】 散列表见表 5-2。【知识模块】 查找47 【正确答案】 计算查找失败时的平均查找长度，是根据查找失败位置来计算平：均次数。在等概率的情况下，查找失败，MOD7 后的位置 06 的概率都是均等的。需计算

31、在每个位置(散列后的位置)上查找失败时的查找次数，故查找失败时的平均查找长度为 ASLunsucc(9+8+7+6+5+4+3)7=6 查找成功时，则仅仅需要计算每个元素的查找次数来计算平均长度。ASL succ=(1+1+1+3+l+1+2+6)8=2 此题，2010 年统考有涉及，得分率很低。不少辅导书中，类似于 ASLunsucc 的问题给出的解答是(9+8 十 7+6+5+4+3+2+1+1)10=46。请大家仔细思考和分析一下为什么会错?【知识模块】 查找48 【正确答案】 算法的基本设计思想：先通过散列函数计算元素的地址，查找散：列表，若此地址中恰为所要查找的关键字，则将元素标记；

32、如果为空，则查找失败。若不是所查找的关键字，则依次向后线性探测，直到找到元素进行标记或者查找失败为止。算法的代码：int Delete(int hn，int k) 从散列表 hn中删除元素 k，若删除成功返回 1，否则返回 0int i=k7； 散列函数用 H(key)=key7if(hi=maxint) maxint 代表此存储单元为空return 0；if(hi=k)hi=一 maxint； 被删元素标记为最大机器数的负数retUrn 1；else 采用线性探测再散列解决冲突inu=i；for(int d=1;d=n 一 1；d+)i=(J+d)n； n 为表长，此处为 10if(hi=m

33、axint)return 0；if(hi=k)hi=一 maxint；return 1，/forreturn 0Delete【知识模块】 查找【知识模块】 查找49 【正确答案】 线性探测再散列解决冲突法构造散列表，见表 5-3。ASLsucc=(1+1+1+2+l+2+1+2)8=118。ASL unsucc=(1+2+1+8+7+6+5 十 4+3+2+1)11=4011。【知识模块】 查找50 【正确答案】 链地址法构造散列表，如图 5-9 所示。ASLsucc=(1x5+23)8=118。ASL UNSUCC=(1+2+1+2 十3+1+3+1+3+1+1)11=1911。对用链接法求

34、查找失败时的平均查找长度。散列地址 0、2、5、7、9 和 10 均为比较 1 次失败，而散列地址 1 和 3 比较 2 次失败，其余散列地址均为比较 3 次失败，因此，查找失败时的平均查找长度为 1911。【知识模块】 查找51 【正确答案】 定义散列表结点的数据结构如下：typedef structE1emType elem；int flag，item；1)散列表的查找。算法的基本设计思想：先通过散列函数计算元素在散列表中位置，若此位置为空，则查找失败；若此位置为所查找元素，则查找成功：若此位置不为所查找元素，则使用线性探测法依次探测，直到找到元素或者查找失败。算法的代码：int Sear

35、ch(item hm+1，ElemType k)从散列表 hm+1中查找元素 k，若查找成功返回元素下标，否则返回一 1int i=hash(k)； 调用散列函数 hash()计算地址if(h(ielem=EMPTY) 元素为空则查找失败return 一 1，if(hiflag!=DELETEDhielem=k)与所查找关键字相同并且没有被删除则成功return i;else 采用线性探测法继续查找int j=i;for (jnt d=1：d=m：d+)i=(j+d)(m+1)；if(hielem=EMPTY)遇到有元素为空，则说明查找失败return 一 1；if(hiflag!=DELET

36、EDhi-elem=k)return i；return 一 1； 查找失败IISearch另一种算法：int Search(item hm+1，E1emType k)int i=hash(k)，j；for(int d=0;d=m；d+)j=(i+d)(m+1);if(hjeIem=EMPTY)return 一 1；if(hJflag!=DELETEDhj.elem=k)return i;2)散列表的插入。算法的基本设计思想：先通过散列函数计算元素在散列表中位置，若此位置为空或元素已被删除，则直接插入；若此位置已满，则使用线性探测法依次探测，直到找到为空或元素已被删除的结点进行插入。算法的代码：

37、int Insert(item hm+1， ElemType k)向散列表 hm+1中插入元素 k，若插入成功返回元素下标，否则返回一 1int i=hash(k)； 调用散列函数 hash()计算地址if(hiflag=DELETEDhi elem=EMPTY) 元素为空或者已删除，则插入hielem=k；hiflag=INUSE； 插入成功return i；e1Se 否则，采用线性探测法继续寻找可以插入的结点int j=i;for(int d=1；d=m；d+)i=(j+d)(m+1)；if(hiflag=DELETED hi elem=EMPTY) 遇到可插入结点则插入hielem=k；

38、hiflag=INUSE;return i; 插入成功return 一 1 ; 插入失败Insert3)散列表的删除。算法的基本设计思想与 5 题中第 4 问基本一致。算法的代码：int Delete(int hm+1，ElemType k)从散列表 hm+1中删除元素 k，若删除成功返回 1，否则返回 0int i：hash(k)， 调用散列函数 hash()计算地址if(hielem=EMPTY) 无此关键字return 0；if(hiflag!=DELETEDhielem=k)hiflag=DELETED ； 将标志位标记为已删除return 1;e1Se 采用线性探测再散列解决冲突int j=i;for(int d=1;d=m;d+)i=(j+d)(m+1)；if(hielem=EMPTY)return 0；if(hiflag!=DELETEDhielem=k)hiflag=DELETED;return 1；return 0； 无此关键字【知识模块】 查找