五、设一个散列表包含 hash Size=13个表项,其下标从0到12,采用线性探查法解决冲突 请按以下要求,将下列关键码散列到表中。 101003245581263292004000 (1)散列函数采用除留余数法,用% hash size(取模运算)将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 (7分) (2)散列函数采用先将关键码各位数字折叠相加,再用% hash size将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 (8分) 六、设一棵二叉树的结点定义为 struct BinTreeNode t Elem Type data: BinTreeNode *leftChild, *right child 现采用输入广义表表示建立二叉树。具体规定如下 (1)树的根结点作为由子树构成的表的表名放在表的最前面 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树,逗号不能省略 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束 例如,对于如右图所示的二叉树,其广 义表表示为AB(D,E(G,)),C(,F) 此算法的基本思路是:依次从保存广义 表的字符串ls中输入每个字符。若遇到的是 字母(假定以字母作为结点的值),则表示是 结点的值,应为它建立一个新的结点,并把 该结点作为作为左子女(当k=0)或右子女(当k=1)链接到其双亲结点上。若遇到的是左括号"( 则表明子表的开始将k置为0;若遇到的是右括号)”,则表明子表结束。若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将k置为1。 在算法中使用了—个栈s,在进入子表之前,将根结点指针进栈,以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下 Make Empty(s) 置空栈 Push(s, p) 元素p进栈 Pop(s) 退栈 Top(s 存取栈顶元素的函数2 五、设一个散列表包含 hashSize = 13 个表项，其下标从 0 到 12，采用线性探查法解决冲突。 请按以下要求，将下列关键码散列到表中。 10 100 32 45 58 126 3 29 200 400 0 (1) 散列函数采用除留余数法，用%hashSize（取模运算）将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 （7 分） (2) 散列函数采用先将关键码各位数字折叠相加，再用 %hashSize 将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 （8 分） 六、设一棵二叉树的结点定义为 struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; } 现采用输入广义表表示建立二叉树。具体规定如下： (1) 树的根结点作为由子树构成的表的表名放在表的最前面； (2) 每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3) 在整个广义表表示输入的结尾加上一个特殊的符号（例如“#”）表示输入结束。 例如，对于如右图所示的二叉树，其广 义表表示为 A(B(D, E(G, ) ), C( , F) )。 此算法的基本思路是：依次从保存广义 表的字符串 ls 中输入每个字符。若遇到的是 字母 (假定以字母作为结点的值)，则表示是 结点的值，应为它建立一个新的结点，并把 该结点作为作为左子女(当 k=0)或右子女(当 k=1)链接到其双亲结点上。若遇到的是左括号”(”， 则表明子表的开始，将 k 置为 0；若遇到的是右括号”)”，则表明子表结束。若遇到的是逗号”,”， 则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 1。 在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下： MakeEmpty(s) 置空栈 Push(s, p) 元素 p 进栈 Pop(s) 退栈 Top(s) 存取栈顶元素的函数 A B C D E F G