計(jì)算機(jī)專業(yè)根底綜合〔查找〕-試卷1分鐘)1.單項(xiàng)選擇題單項(xiàng)選擇題1-40小題。以下每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。假設(shè)查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)挨次文件中承受挨次查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為( )。A.(n—1)／2 B.n／2C.(n+1)／2 D.n挨次查找法適用于查找挨次存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表二分法查找只適用于查找挨次存儲(chǔ)的有序表平均比較次數(shù)為( )在此假定N為線性表中結(jié)點(diǎn)數(shù)且每次查拔都是成功的。N+12log2Nlog2NN／2挨次查找法適用于查找挨次存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表平均比較次數(shù)為( )在此假定N為線性表中結(jié)點(diǎn)數(shù)，且每次查拔都是成功的。N+12log2Nlog2NN／2適用于折半查找的表的存儲(chǔ)方式及元素排列要求為( )。鏈接方式存儲(chǔ)，元素?zé)o序 B.鏈接方式存儲(chǔ)，元素有序C.挨次方式存儲(chǔ)，元素?zé)o序 D.挨次方式存儲(chǔ)，元素有序具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為( )。A.3．1 B.4C.2．5 D.5折半查找的時(shí)間簡(jiǎn)潔性為( )。O(n2)O(n)O(nlog2n)O(log2n)當(dāng)承受分塊查找時(shí)，數(shù)據(jù)的組織方式為( )。數(shù)據(jù)分成假設(shè)干塊，每塊內(nèi)數(shù)據(jù)有序數(shù)據(jù)分成假設(shè)干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊數(shù)據(jù)分成假設(shè)干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊數(shù)據(jù)分成假設(shè)干塊，每塊(除最終一塊外)中數(shù)據(jù)個(gè)數(shù)需一樣下面函數(shù)的功能是實(shí)現(xiàn)分塊查找，空白處應(yīng)當(dāng)添加的內(nèi)容是( )。intBlkSearch(int*nz，intkey，intblock，intBLK，intlen){inti；block=block-1；if(1enlen)BLK=len；for(i=block*BLK；i<(block+1)*BLK&&nz[i]!=0；i++){if(){printf(”dd＼n”，i，key)；return0;}}printf(”＼n”);pfintf(”查找完畢＼n”)；return0；}nz[i]==key B.nz[i]==BLKC.nz[i]==block D.nz[i]==0二叉查找樹的查找效率與二叉樹的( )有關(guān)。高度 B.結(jié)點(diǎn)的多少C.樹形 D.結(jié)點(diǎn)的位置二叉查找樹的查找效率，在( )時(shí)其查找效率最低。A.結(jié)點(diǎn)太多 B.完全二叉樹C.呈單枝樹 D.結(jié)點(diǎn)太簡(jiǎn)潔在一棵高度為h的抱負(fù)平衡二叉樹中，最少含有( )個(gè)結(jié)點(diǎn)，最多含有( )個(gè)結(jié)點(diǎn)。2h2h-12h-12h2h+12h12h-12h1分別以以下序列構(gòu)造二叉排序樹，與用其他三個(gè)序列所構(gòu)造的結(jié)果不同的( )。A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)關(guān)于B-樹，以下說法中不正確的選項(xiàng)是( )。A.B-樹是一種查找樹 B.全部的葉結(jié)點(diǎn)具有一樣的高度C.2-3樹中，全部非葉子結(jié)點(diǎn)有1或者3個(gè)孩子結(jié)點(diǎn) D.通常狀況下，B-樹不是二叉樹在含有15個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(guān)鍵字為28(存在該結(jié)點(diǎn))的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是( )。A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36下面關(guān)于m階B樹的說法中，正確的選項(xiàng)是( )。 ①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹。②樹中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字。 ③全部葉子在同一層上。 ④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹結(jié)點(diǎn)分裂后，樹長(zhǎng)高一層。A.①②③ B.②③C.②③④ D.③下面關(guān)于B和B+樹的表達(dá)中，不正確的選項(xiàng)是( )。B樹和B+樹都是平衡的多又樹B樹和B+樹都可用于文件的索引構(gòu)造B樹和B+樹都能有效地支持挨次檢索B樹和B+樹都能有效地支持隨機(jī)檢索m階B-樹是一棵( )。A.m叉排序樹 B.m叉平衡排序樹C.m-1叉平衡排序樹 D.m+1叉平衡排序樹假設(shè)對(duì)有18個(gè)元素的有序表做二分查找，則查找A[3]的比較序列的下標(biāo)為( )。A.1，2，3 B.9，4，2，3C.10，5，3 D.9，2，319.有一個(gè)有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)用二分查找82的結(jié)點(diǎn)時(shí)，經(jīng)()次比較后查找成功。A.1 B.2C.4 D.8承受分塊查找時(shí)，假設(shè)線性表中共有625個(gè)元素，查找每個(gè)元素的概率一樣，假設(shè)承受挨次查找來確定結(jié)點(diǎn)所在的塊，則每塊分為()個(gè)結(jié)點(diǎn)最正確。A.9 B.25C.6 D.625在有n為()。O(n)O(log2n)O(nlog2n)O(n2)對(duì)包含n個(gè)關(guān)鍵碼的散列表進(jìn)展檢索，平均檢索長(zhǎng)度為( )。O(log2n)O(n)O(nlog2n)不直接依靠于n在散列表上，每個(gè)地址單元所鏈接的同義詞表的( )。A.鍵值一樣 B.元素值一樣C.散列地址一樣 D.含義一樣設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)日(key)=keymod11。表中已有4個(gè)結(jié)點(diǎn)addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空，如用二次探測(cè)再散列法處理沖突，則49的結(jié)點(diǎn)的地址是()。A.8 B.3C.5 D.92.綜合應(yīng)用題41-47小題。請(qǐng)編寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink—rlink法存儲(chǔ)。k個(gè)集合：S1，S2，…，SkSi(1≤i≤k中的元時(shí)用一個(gè)二元組(i，x)來規(guī)定一個(gè)元素，i是集合的序號(hào)，x是元素值。設(shè)計(jì)一種恰當(dāng)?shù)臄?shù)據(jù)構(gòu)造來存儲(chǔ)這k個(gè)集合的元素，并能高效地實(shí)現(xiàn)所要求的查找和插入操作。構(gòu)造數(shù)據(jù)構(gòu)造，并且說明選擇的理由。4．2，3．6，2．7，5．1，3．9}，待插入的元素二元組為(2，11．2)和(1，5．3)，按你的設(shè)計(jì)思想畫出插入元素前后的數(shù)據(jù)構(gòu)造狀態(tài)。K1，…，KNn個(gè)關(guān)鍵詞，試解答：K1，K2，…，Kn時(shí)，用算法建立一棵以LLINK—RLINK鏈接表示的二叉查找樹。設(shè)計(jì)一個(gè)算法，打印出該二叉查找樹的嵌套括號(hào)表示構(gòu)造。假定該二叉查找樹的嵌套括號(hào)表示構(gòu)造為B(A，D(C，E))。寫出在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)的算法，使刪除后仍為二叉排序樹。設(shè)刪除結(jié)點(diǎn)由指針p所指，其雙親結(jié)點(diǎn)由指針f所指，并假設(shè)被刪除結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子。描述上述算法。二叉樹排序樹中某結(jié)點(diǎn)指針pfp，p為fp的左孩子。試編寫算法，刪除p所指結(jié)點(diǎn)。二叉排序樹承受二叉鏈表存儲(chǔ)。寫一個(gè)算法，刪除結(jié)點(diǎn)值是X的結(jié)點(diǎn)。要求刪除該結(jié)點(diǎn)后，此樹照舊是一棵二叉排序樹，并且高度沒有增長(zhǎng)(留意：可不考慮被刪除的結(jié)點(diǎn)是根的狀況)。設(shè)記錄R1，R2，…，Rn按關(guān)鍵字值從小到大挨次存儲(chǔ)在數(shù)組r[1．n]中，在r[n+1]處設(shè)立一個(gè)監(jiān)視哨，其關(guān)鍵字值為+∞。試寫一查找給定關(guān)鍵字k的算法，并畫出此查找過程的判定樹，求出在等概率狀況下查找成功時(shí)的平均查找長(zhǎng)度。給出折半查找的遞歸算法，并給出算法時(shí)間簡(jiǎn)潔度分析。鍵樹(Trie)2一個(gè)或幾個(gè)關(guān)鍵字，而是只含有組成關(guān)鍵字的符號(hào)。請(qǐng)用類C語(yǔ)言或類PASCAL語(yǔ)言編寫一個(gè)在鍵樹T上查找關(guān)鍵字等于給定值KEP的記錄的算法。假設(shè)查找成功，返回指向該記錄的指針；否則返回空指針。寫出從哈希表中刪除關(guān)鍵字為KH，解決沖突的方法為鏈地址法。用C語(yǔ)言或PASCAL編寫一用鏈接表(LinkedList)解決沖突的哈希表插入函數(shù)。在用除余法作為散列函數(shù)線性探測(cè)解決沖突的散列表中，寫一刪除關(guān)鍵字的算法，要求將全部可以前移的元素前移去填充被刪除的空位，以保證探測(cè)序列不至于斷裂。設(shè)排序二叉樹中結(jié)點(diǎn)的構(gòu)造由三個(gè)域構(gòu)成：數(shù)據(jù)域data，指向左兒子結(jié)點(diǎn)的指針域left，指向右兒子結(jié)點(diǎn)的指針域right。 設(shè)data域?yàn)檎麛?shù)，該二又樹樹根結(jié)點(diǎn)地址為T?，F(xiàn)給出一個(gè)正整數(shù)x。請(qǐng)編寫非遞歸程序，實(shí)現(xiàn)將data域的值小于等于x的結(jié)點(diǎn)全部刪除。T的結(jié)點(diǎn)形式為(llink，data，count，rlink)X的結(jié)點(diǎn)，假設(shè)找到，則記數(shù)(count)加1；否則，作為一個(gè)結(jié)點(diǎn)插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。假設(shè)一棵平衡二叉樹的每個(gè)結(jié)點(diǎn)都標(biāo)明白平衡因子b，試設(shè)計(jì)一個(gè)算法，求平衡二叉樹的高度。設(shè)從鍵盤輸入一個(gè)整數(shù)的序列：n，a1，a2，…，an，其中n表示連續(xù)輸入整數(shù)的個(gè)數(shù)。試編寫一程序按整數(shù)值建立一個(gè)二叉排序樹。在(1)的根底上將此二叉樹上的各整數(shù)按降序?qū)懭胍淮疟P文件中。設(shè)二叉排序樹的各元素值均不一樣，承受二叉鏈表作為存儲(chǔ)構(gòu)造，試分