第七章习题答案.doc

第七章习题答案7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。【解答】5096771548975532750179087656125125031700947-14 设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。【解答】464646464646782525782578257825加25加46空树加78371262126262加37加12加62464678257825126237126237加29加702970707-18将关键码DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。【解答】加JUL加OCT加NOV加FEB加DEC+2FEBFEBDEC左单旋DECDECDECNOVDECNOVDECFEBFEBFEBJULOCTOCTNOVNOV+2NOVFEBFEB加AUG左单旋FEBOCTNOVDECNOVDECJULSEPDECOCTJULOCTJUL加SEPAUGSEPSEPNOVNOVNOV加APR加MARFEBOCTOCTFEB右单旋FEBOCT-2JULSEPAUGJULAUGSEPSEPDECJULMARAPRDECAPRDECAPRAUG加MAYNOVNOVFEBOCTFEBOCT+2AUG左单旋SEPJULAUGSEPJULMARMAYDECDECAPRMARAPRMAY-2加JUNMARNOVNOVFEBFEBOCTJULOCTAUGAUG左右双旋MARSEPSEPJUNMAYDECAPRDECJULMAYAPRJUNMAR加JANFEBNOVAUGJULOCTMAYJUNJANDECAPRSEP7-19 从第7-18题所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整?【解答】MARMAR删除关键码MAY， 调整OCTFEBFEBNOVSEPNOVJULAUGJULMAYAUGOCTJANJANJUNDECAPRSEPJUNDECAPRMAR删除关键码FEB， 不用调整 JANOCTNOVSEPJULAUGJUNDECAPR