2011数据结构答案2.doc

参考答案 一、单项选择题 1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 14.B 15D 二、填空题 1. (n+1)/2, O(n) 2. 3. 20.5, 41 4. (log2(n+1)(，O(log2n) 5. 顺序 有序 6. 1，3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于 11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O(nlog2n) 15. 5 三、应用题 1. 折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。 1 2 3 4 5 6 7 8 9 10 15 26 34 39 45 56 58 63 74 76 2. 二叉排序树如图7-4所示，平均查找长度等于32/10。 3. H(K)=K % 13平均查找长度为14/10，其余解答如下。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最终哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 25 4. H(K)=K % 11，哈希表如图7-5所示，平均查找长度17/12。 四、算法设计题 1. 设计思路：进入判别算法之前，pre取初值为min(小于树中任一结点值)，fail=FALSE,即认为bt是二叉排序树。按中序遍历bt，并在沿向根结点，与前趋比较，若逆序，则fail为TRUE,则bt不是二叉排序树。 void bisorttree(bitree bt,keytype pre, bool fail) { //fail初值为FALSE，若非二叉序树，则fail值TRUE if (!fail) { if (bt) { bisosrttree(bt-lchild,pre,fail); //判断左子树 if (bt-data_keypre) fail=TRUE; else { pre=bt-data_key; bisorttree(bt-rchild,pre,fail); //判断右子树 } } } } //bisorttree 说明：较为直观的方法，可套用中序遍历非递归算法。 2. int search_bin(SeqTable st , keytype k , int low , int high) { if (lowhigh) return (0); //不成功 else { mid=(low+high)/2; if (k= =st.elem[mid].key) return (mid) ; //成功 else if (kst.elem[mid].key) return (st,k,low,mid-1); else return(st,k,mid+1,high); } } //search-bin  图7-3 10 9 4 5 6 7 8 1 2 3 图7-4 38 52 25 16 74 30 68 90 54 72 图7-5 0 ∧