【答案解析】(1)p-＞numkeys；或其等价形式 (2)p-＞K[mid]＞akey，或其等价形式 (3)p-＞A[hi]，或p-＞A[1w-1]，或其等价形式 [分析]试题五 本题考查C程序设计。 B树是一种多叉平衡查找树，由B树的定义可知，在B树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回：否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败(指针为空)为止。树的内部结点中关键字存储在数组中并按照递增顺序排列，因此可以用二分法查找某个关键字是否在指定的结点中。 二分法查找元素的过程是：首先令待查找的元素与查找表中间位置上的元素进行比较，若相等，则查找成功，否则，根据待查元素与表中间位置元素的大小关系，下一步到查找表的前半区间或后半区间继续进行二分查找。如果在确定的任何一个子区间都找不到指定的元素，则确定查找失败。若查找区间用一对下标1w和hi确定，则1w≤hi表示有效的查找区间，查找失败时所确定的查找区间为1w＞hi。 例如，上图中的结点c包含了关键字60、70、80，那么在c结点中找不到元素65，由于65介于60和70之间，因此下一步必将进入h结点继续查找。 每个结点中的关键字数目由BTreeNode中的numkeys域表示，结点中的查找表存储在数组K[]中，由于下标0未用，因此numkeys个关键字存储在K11)～K[numkeys]中。显然开始在p所指向的结点中进行查找时，确定查找表的下标为1和结点的numkeys域，因此函数5-1的空(1)处应填入“p-＞numkeys”。 若用1w和hi指示出查找区间，则由于查找表元素的递增排列特性，当待查找的元素小于表中间位置的元素时，下一步应在前半区间查找，即查找区间的一对下标为1w、 mid-1，也就是说函数5-1的空(2)处应填入“akey＜p-＞K[mid]。 如果在当前结点中找不到指定的关键字akey，则1w＞hi，由结点中的指针A[hi]或 A[1w-1]指示出下一层的子树结点，因此函数5-1的空(3)处应填入“p＞A[hi]”或“p-＞ A[1w-1]”。 下面分析函数5-2的功能及运算过程。函数5-2用于判断在B树中插入一个关键字时，树的高度是否增加。若指定的关键字已经在B树的某结点中，就不需要插入该关键字，显然树也不会长高。 实现函数调用时实参要向形参传递信息，C语言采取传值调用方式，根据实参向形参的值传递原则，函数4-2中的空(4)处应填入“root,akey,&f"。 根据题目中给出的描述，在M阶B树中插入一个关键字时，首先在最接近外部结点的某个非叶子结点中增加一个关键字，若该结点中关键字的个数不超过M-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来并插入其父结点中，然后以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根，若树根结点也需要分裂，则整棵树的高度增加1。 显然考查插入关键字akey后树的高度是否增加，只需沿其祖先结点关系一直考查直到树根为止，判断依据就是每个待考查的结点中目前已有的关键字个数，因此函数5-2中的空(5)处应填入“t&&t-＞numkeys==M-1”。