計算機專業(yè)基礎綜合數據結構(集合)歷年真題試卷匯編9

計算機專業(yè)基礎綜合數據結構（集合）歷年真題試卷匯編9(總分：70.00，做題時間：90分鐘)一、單項選擇題(總題數：20，分數：40.00)200311(1平衡二叉樹 √二叉查找樹D構造一棵具有n200714(2n／2B.nC.[logD.[log

(n+1)]2(n+1)]√21100036320051(2A.2，252．401，398，330，344，397，363B.924，220，911，244，898，258，363C.925，202，911，240，912，245，363√D.2，399，387，219，266，382，381，278，3632000一、4(2分)】A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，20，110，130) D.(100，80，60，90，120，130，110)2004A.100，80，60，85，110，120，150√B.100，80，60，85，120，110，150C.100，80，85，60，120，110，150D.100，80，60，85，120，150，110在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A0120014(2A.LLB.LRC.RLD.RRAA01”，可見應做RL整。設輸入序列為3020054(1A.LLB.RLC.LRD.RR已知一棵深度為k20062(2A.2k-1-1B.2k-1+1C.2D.2

k-1√k+12C.√2C.√D.在平衡二叉樹中，進行查找的效率()有關?！颈本┖娇蘸教齑髮W2004A.二叉樹的深度 √BC.后序線索樹D.所有線索樹下列關于mB19979(2根結點至多有m所有葉子都在同一層次上非葉結點至少有m／2(mm／2-4—1(m為奇數)棵子樹√根結點中的數據是有序的下面關于mB19995(2m-1B分裂后，樹長高一層。A.①②③B.②③ C.②③④D.③下面關于BB+200117(2A.B樹和B+樹都是平衡的多叉樹B.B樹和B+樹都可用于文件的索引結構C.B樹和B+樹都能有效地支持順序檢索√D.B樹和B+樹都能有效地支持隨機檢索13.m階B一樹是一棵()?！颈本┼]電大學2000二、2(20／8分)】A.m叉排序樹B.m叉平衡排序樹 C.m-1叉平衡排序樹D.m+1叉平衡排序樹在一棵含有nmB20006(2log 21+log n15.m路Bm[m/219995(6A.m路平衡查找樹B.m路平衡索引樹 √C.m路Ptrie樹D.m路鍵樹E.m-13B20472005一、2(2分)】1B.12√C.13D.143階B樹又稱2—3樹。在結點含最少關鍵字的情況下，2—3樹可以看做是滿二叉樹。高度包括葉子層。5B5320068(2A.3B.4C.5√D.65B1211243612418365535層是葉子。18.B+樹是()。【武漢理工大學2004一、13(3分)】一利AVL樹 √索引表的一種組織形式√1一種與二進制Binary當向BB2004A.合并1√分裂 √1在一棵mB2003】A.mB.m+1C.m-1√D.m／2二、填空題(總題數：5，分數：10.00)在有序表A[1．．204 200010(2正確答案：(正確答案：1，3，6，8，11，13，16，19)22.已知有序表當用二分法查找90時需 次查找成功，查47時，次查找成功，查100時，次才能確定不成功。【南京工大學2000二7(4．5分)】正確答案：(正確答案：2，4，3)23.n個結點的用于折半查找的判定樹表示查找失敗的外部結點共有 個【中南大學2003三、12(1分)】正確答案：(正確答案：n+1)1023ASL 20055(2正確答案：(正確答案：9)在一個按值有序排列的順序表示中進行折半查找，其查找過程可以用一棵稱之“判斷樹的二叉樹來描述若順序表的長度為19則對應“判斷樹的根結點的左孩子之值(元素在表中的位置是 【北京航空航天大學2006一、8(1分)】正確答案：(正確答案：5)三、判斷題(總題數：10，分數：20.00)200614(1正確錯誤 √20069(1正確 √錯誤19973(2正確錯誤 √19916(2正確 √錯誤19965(1正確錯誤 √從平衡因子定義看，完全二叉樹任一結點的平衡因子的絕對值確實是小于等于1。但是，平衡二叉樹本質上是二叉排序樹，完全二叉樹不一定是二叉排序樹。故不能說完全二叉樹是平衡二叉樹。12006分)】正確錯誤 √平衡二叉樹是指任意結點的左右子樹層次(高度)差的絕對值小于等于1。AVL12007分)】正確 √錯誤7B632004分)】正確錯誤 √7階B樹每個結點至多7棵子樹，除