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

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