計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(集合)歷年真題試卷匯編9

計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（集合）歷年真題試卷匯編9（總分：70.00，做題時間：90分鐘）、單項選擇題（總題數(shù)：20，分?jǐn)?shù)：40.00）1.下列二叉排序樹中查找效率最高的是（）。【中南大學(xué)2003二、11（1分）】平衡二叉樹丿二叉查找樹沒有左子樹的二叉排序樹沒有右子樹的二叉排序樹2?構(gòu)造一棵具有n個結(jié)點的二叉排序樹，最理想情況下的深度為（）。【華中科技大學(xué)2007—、14（2分）】n／2n[log （n+1）]2[log （n+1）]V2設(shè)二叉排序中關(guān)鍵字由1到1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點，下述關(guān)鍵字序列中，不可能是在二叉排序樹上查找的序列的是（）?！颈本┙煌ù髮W(xué)2005一、1（2分）】2，252．401，398，330，344，397，363924， 220， 911，244， 898， 258， 363925， 202， 911，240， 912， 245， 363 V2，399，387，219，266，382，381，278，363分別以下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是（）。【合肥工業(yè)大學(xué)2000一、4（2分）】（100，80，90，60，120，110，130）（100，120，110，130，80，60，90）（100，60，80，90，20，110，130）V（100，80，60，90，120，130，110）分別以下列序列構(gòu)造二叉排序樹，與眾不同的是（）。【中國科學(xué)技術(shù)大學(xué)2004】A.100，80，60，85，110，120，150VB.100，80，60，85，120，110，150C.100，80，85，60，120，110，150D.100，80，60，85，120，150，1106?在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A,并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整以使其平衡。【合肥工業(yè)大學(xué)2001一、4（2分）】LLLRRLVRR根據(jù)A是最低的不平衡結(jié)點，“A的左孩子的平衡因子為0,右孩子的平衡因子為1”，可見應(yīng)做RL型調(diào)整。7?設(shè)輸入序列為{20,35,???},構(gòu)造一棵平衡二叉樹，當(dāng)在樹中插入值30時發(fā)生不平衡，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是（）。【南京理工大學(xué)2005一、4（1分）】TOC\o"1-5"\h\zLLRLVLRRR已知一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0,則該樹共有結(jié)點總數(shù)為（）。【北京交通大學(xué)2006一、2（2分）】A.2k-1-1B.2k-1+12k-1丿2k+1該平衡二叉樹實際上是深度為k的滿二又樹。在平衡二叉樹中，進(jìn)行查找的效率與（）有關(guān)。【北京航空航天大學(xué)2004】二叉樹的深度丿二叉排序樹的結(jié)點的個數(shù)后序線索樹所有線索樹下列關(guān)于m階B一樹的說法錯誤的是（）。【南京理工大學(xué)1997—、9（2分）】根結(jié)點至多有m棵子樹所有葉子都在同一層次上非葉結(jié)點至少有m/2（m為偶數(shù)）或m/2-4—1（m為奇數(shù)）棵子樹丿根結(jié)點中的數(shù)據(jù)是有序的下面關(guān)于m階B樹說法正確的是（）?！灸暇├砉ご髮W(xué)1999一、5（2分）】①每個結(jié)點至少有兩棵非空子樹；②樹中每個結(jié)點至多有m-1個關(guān)鍵字；③所有葉子在同一層上；④當(dāng)插入一個數(shù)據(jù)項引起B(yǎng)樹結(jié)點分裂后，樹長高一層。TOC\o"1-5"\h\z①②③②③丿②③④③下面關(guān)于B和B+樹的敘述中，不正確的是（）。【北方交通大學(xué)2001一、17（2分）】B樹和B+樹都是平衡的多叉樹B樹和B+樹都可用于文件的索引結(jié)構(gòu)B樹和B+樹都能有效地支持順序檢索丿B樹和B+樹都能有效地支持隨機檢索m階B一樹是一棵（）?！颈本┼]電大學(xué)2000二、2（20/8分）】m叉排序樹m叉平衡排序樹 丿m-1叉平衡排序樹m+1叉平衡排序樹在一棵含有n個關(guān)鍵字的m階B一樹中進(jìn)行查找，至多讀盤（）次?！局锌圃河嬎闼?000一、6（2分）】logn2m路B+樹是一棵（（1））,其結(jié)點中關(guān)鍵字最多為m個，最少［m/2］個。【中科院計算所1999一、5（6分）】m路平衡查找樹m路平衡索引樹丿m路Ptrie樹m路鍵樹m-1一棵3階B一樹中含有2047個關(guān)鍵字，包括葉子結(jié)點層，該樹的最大深度為（）?！颈本┙煌ù髮W(xué)2005一、2（2分）】1112丿13143階B樹又稱2—3樹。在結(jié)點含最少關(guān)鍵字的情況下，2—3樹可以看做是滿二叉樹。咼度包括葉子層。已知一棵5階B樹有53個關(guān)鍵字，并且每個結(jié)點的關(guān)鍵字都達(dá)到最少狀態(tài)，則它的深度是（）?！救A南理工大學(xué)2006一、8（2分）】TOC\o"1-5"\h\z345丿65階B樹根結(jié)點最少1個關(guān)鍵字，其他結(jié)點最少2個關(guān)鍵字。所以，第1層1個關(guān)鍵字（兩棵子樹），第2層4個關(guān)鍵字，第3層6個結(jié)點12個關(guān)鍵字，第4層18個結(jié)點36個關(guān)鍵字，上面5層53個關(guān)鍵字。第5層是葉子。B+樹是（）?！疚錆h理工大學(xué)2004一、13（3分）】一利AVL樹V索引表的一種組織形式V一種咼度不小于1的樹一種與二進(jìn)制Binary有關(guān)的樹當(dāng)向B一樹插入關(guān)鍵字時，可能引起結(jié)點的（），最終可能導(dǎo)致整個B一樹的高度（）。【浙江大學(xué)2004】合并增加1V分裂V減少1在一棵m階B一樹中，若在某結(jié)點中插入一個新關(guān)鍵字而引起該關(guān)鍵字的分裂，則此結(jié)點中原有的關(guān)鍵字個數(shù)是（）?！竞洗髮W(xué)2003】TOC\o"1-5"\h\zmm+1m-1Vm／2二、填空題（總題數(shù)：5，分?jǐn)?shù)：10.00）21?在有序表A[1..20】中，按二分查找方法進(jìn)行查找，查找長度為4的元素的下標(biāo)從小到大依次是 。【合肥工業(yè)大學(xué)2000三、10（2分）】正確答案：（正確答案：1，3，6，8，11，13，16，19）已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用二分法查找90時，需 次查找成功，查47時，需 次查找成功，查100時，需 次才能確定不成功?！灸暇├砉ご髮W(xué)2000二、7（4.5分）】正確答案：（正確答案：2， 4， 3）n個結(jié)點的用于折半查找的判定樹，表示查找失敗的外部結(jié)點共有 個?！局心洗髮W(xué)2003三、12（1分）】正確答案：（正確答案：n+1）設(shè)表長為1023的有序線性表，查找每個元素的概率相等，采用折半查找方法，查找成功的ASL是 。【北京交通大學(xué)2005二、5（2分）】正確答案：（正確答案：9）在一個按值有序排列的順序表示中進(jìn)行折半查找，其查找過程可以用一棵稱之為“判斷樹”的二叉樹來描述。若順序表的長度為19，則對應(yīng)的“判斷樹”的根結(jié)點的左孩子之值（元素在表中的位置）是 ?！颈本┖娇蘸教齑髮W(xué)2006一、8（1分）】正確答案：（正確答案：5）三、判斷題（總題數(shù)：10，分?jǐn)?shù)：20.00）對一個堆，按二叉樹層次進(jìn)行遍歷可以得到一個有序序列。（）【中國海洋大學(xué)2006二、14（1分）】正確錯誤丿以同一組數(shù)的不同序列來構(gòu)造平衡二叉樹，可能會得到不同的解。（）【北京郵電大學(xué)2006二、9（1分）】正確丿錯誤在平衡二叉樹中，向某個平衡因子不為零的結(jié)點的樹中插入一新結(jié)點，必引起平衡旋轉(zhuǎn)。（）【南京理工大學(xué)1997二、3（2分）】正確錯誤丿平衡二叉樹中，若某個結(jié)點的左、右孩子的平衡因子為零，則該結(jié)點的平衡因子一定是零。（）【中國科學(xué)技術(shù)大學(xué)1991一、6（2分）】正確丿錯誤完全二叉樹肯定是平衡二叉樹。（）【南京航空航天大學(xué)1996六、5（1分）】正確錯誤丿從平衡因子定義看，完全二叉樹任一結(jié)點的平衡因子的絕對值確實是小于等于1。但是，平衡二叉樹本質(zhì)上是二叉排序樹，完全二叉樹不一定是二叉排序樹。故不能說完全二叉樹是平衡二叉樹。一棵平衡二叉樹中的任意兩個葉子結(jié)點的層次差的絕對值不大于1。（）【北京郵電大學(xué)2006二、8（1分）】正確錯誤丿平衡二叉樹是指任意結(jié)點的左右子樹層次（高度）差的絕對值小于等于1。AVL樹是一棵二叉樹，該樹上任一結(jié)點的平衡因子的絕對值不大于1。（）【中國海洋大學(xué)2007二、13（1分）】正確丿錯誤在一棵7階B樹中，一個結(jié)點中最多有6棵子樹，最少有3棵子樹。（）【南京理工大學(xué)2004二、9（1分）】正確錯誤丿7階B樹每個結(jié)點至多7棵子樹，除根結(jié)點最少可以有2棵子樹外，其余非終端結(jié)點最少有4