商大計(jì)算機(jī)專業(yè)天津商業(yè)練習(xí)

1、練習(xí)九數(shù)據(jù)結(jié)構(gòu)Data Structure11.A)B)C)D)成功的折半查找其時(shí)間復(fù)雜度為 。O(log2n) O(log2n/2) O(n)O(n/2)Data Structure2數(shù)據(jù)結(jié)構(gòu)2.A)B)C)D)成功的折半查找所需最少時(shí)間為。O(1)O(2) O(n-1) O(n+1)Data Structure3數(shù)據(jù)結(jié)構(gòu)3.A)B)C)D)）是指 。在使用散列法時(shí)，碰撞（不同的關(guān)鍵碼值對應(yīng)到相同的兩個(gè)元素具有相同序號地址兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同負(fù)載因子太大Data Structure4數(shù)據(jù)結(jié)構(gòu)4.從理論上講，將數(shù)據(jù)以 結(jié)構(gòu)存放，則查找一個(gè)數(shù)據(jù)所用時(shí)間不依賴于數(shù)據(jù)的個(gè)數(shù)。散列二

2、叉查找樹鏈表 二叉樹A)B)C)D)Data Structure5數(shù)據(jù)結(jié)構(gòu)5.A)B)C)D)對線性表采用折半查找法，該線性表必須。采用順序采用順序采用鏈?zhǔn)讲捎面準(zhǔn)浇Y(jié)構(gòu)，且元素按值有序結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu)，且元素按值有序Data Structure6數(shù)據(jù)結(jié)構(gòu)6.設(shè)哈希表長m=14,哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn): addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7其余地址為空，如用二次探測再散列處理為49的結(jié)點(diǎn)的地址是。，關(guān)鍵字A）8B）9 C）5 D）3Data Structure7數(shù)據(jù)結(jié)構(gòu)7.采用順序查找方法查找長度為n的線性表時(shí),每

3、個(gè)元素的平均查找長度為 。n/2 (n+1)/2n(n-1)/2A)B)C)D)Data Structure8數(shù)據(jù)結(jié)構(gòu)8.有一個(gè)有序表(2，5，9，14，36，54，68，72，77， 82，95，99)，當(dāng)采用折半查找值為82的結(jié)點(diǎn)時(shí)， 次比較后查找成功。2468A)B)C)D)Data Structure9數(shù)據(jù)結(jié)構(gòu)9.性表的散列中，添裝因子是哈希表裝滿程度的標(biāo)志。若用m表示哈希表的長度，n表示待元素的個(gè)數(shù)，則等于 。m/n n/m m/(n-1)(n-1)/mA)B)C)D)Data Structure10數(shù)據(jù)結(jié)構(gòu)10.設(shè)哈希表的表長為14，哈希函數(shù)為H(key)=key%13，表中已有4

4、個(gè)結(jié)點(diǎn): H(15)=2, H(16)=3, H(43)=4,H(83)=5，其余地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為28的結(jié)點(diǎn)的地址是 。0167A)B)C)D)Data Structure11數(shù)據(jù)結(jié)構(gòu)11.A)B)C)D)結(jié)構(gòu)的是。以下術(shù)語，不屬于順序表有序表 Hash表單鏈表Data Structure12數(shù)據(jù)結(jié)構(gòu)12.中，下面不是處理性表的散列方法。開放地址法再哈希法 折半查找法公共溢出區(qū)法的A)B)C)D)Data Structure13數(shù)據(jù)結(jié)構(gòu)13.A)以下說法錯(cuò)誤的是。哈希址的基本是由關(guān)鍵字的值決定數(shù)據(jù)的地B)填裝因子是哈希法的一個(gè)重要參數(shù)，它反映哈希表的填裝程度哈希表

5、的結(jié)點(diǎn)中只包含數(shù)據(jù)元素本身的信息，不包含任何指針哈希表的查找效率主要取決于哈希表構(gòu)造時(shí)選取的哈希C)D)函數(shù)和處理的方法Data Structure14數(shù)據(jù)結(jié)構(gòu)14.A)B)C)D)下面不是靜態(tài)查找表的表示方法。順序表有序表線性表靜態(tài)樹表Data Structure15數(shù)據(jù)結(jié)構(gòu)15.A)B)C)D)下面是動態(tài)查找表的表示方法。順序表散列表平衡二叉樹靜態(tài)樹表Data Structure16數(shù)據(jù)結(jié)構(gòu)16.A)B)C)D)動態(tài)查找表的表示方法是。順序表 散列表 靜態(tài)樹表二叉排序樹Data Structure17數(shù)據(jù)結(jié)構(gòu)二、判斷題1.2.查找表中數(shù)據(jù)元素的任何數(shù)據(jù)項(xiàng)都可以作為關(guān)鍵字。動態(tài)查找表適合用于

6、檢索與修改(行的場合。Hash表的平均查找長度與處理和刪除)交叉進(jìn)3.4.的方法無關(guān)。折半查找法的查找速度一定比順序查找法快。(注意特例)5.二叉樹排序樹中下面。一個(gè)新結(jié)點(diǎn)，總是到葉結(jié)點(diǎn)6.二叉樹排序樹刪除一個(gè)結(jié)點(diǎn)后，仍是二叉樹排序樹。Data Structure18數(shù)據(jù)結(jié)構(gòu)三、填空題1.由1000個(gè)數(shù)據(jù)元素組成的有序表，假設(shè)比較表中一個(gè)元素所需時(shí)間為0.5毫秒，則順序查找時(shí)，平均查找一個(gè)元素的時(shí)間約為毫秒。2502.設(shè)線性表（a1,a2,a500）中所有元素的值由小到大排列，對一個(gè)給定的值k，用二分法查找表中與k相等的元素，在查找不成功的情況下，至多需要比較次。9Data Structure

7、19數(shù)據(jù)結(jié)構(gòu)三、填空題3.在用散列表進(jìn)行檢索時(shí)，處理的方法有幾種，它們是、再哈希法、鏈地址法和建立公共溢出區(qū)法。開放地址法在用散列表進(jìn)行檢索時(shí)，處理4.的方法有幾種，它們是開放地址法、再哈希法、和建立公共溢出區(qū)法。鏈地址法數(shù)據(jù)結(jié)構(gòu)Data Structure20三、填空題5.查找表按其所包含的不同運(yùn)算，可以分為找表和動態(tài)查找表。查靜態(tài)6.查找表按其所包含的不同運(yùn)算，可以分為靜態(tài)查找表和查找表。動態(tài)Data Structure21數(shù)據(jù)結(jié)構(gòu)三、填空題7.在關(guān)鍵字序列（07，12，15，18，27，32，41，92）中用二分法查找和給定值07相等的關(guān)鍵字時(shí)，查找過程中依次和“07”比較的關(guān)鍵字是。1

8、812078.以折半查找方法查找一個(gè)線性表時(shí)，此線性表必須是順的表 。序有序Data Structure22數(shù)據(jù)結(jié)構(gòu)三、填空題在索引查找方法中，首先查找，然后再查對應(yīng)的塊。索引對一棵二叉排序樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序一個(gè) 。有序序列找相列是數(shù)據(jù)結(jié)構(gòu)Data Structure23三、填空題以順序查找方法從長度為n的線性表中查找一個(gè)元時(shí)間復(fù)雜度為 。O(n)素的數(shù)據(jù)結(jié)構(gòu)Data Structure24四、應(yīng)用題1簡述順序查找法、折半查找法和索引順序表查找法對查找表中元素的要求，每種查找法對長度為n的表的等概平均查找長度是多少？被率數(shù)據(jù)結(jié)構(gòu)Data Structure25四、應(yīng)用題1參考：(1

9、)順序查找：表中元素可以任意存放，查找成功平均查找長度為( n+1)/2折半查找：表中元素必須以關(guān)鍵字值的升序或降序進(jìn)行有序排列，并且只能存放在順序表中。查找成功平均查找長度為log2( n+1)-1。索引查找：索引表有兩部分組成，一個(gè)索引表和一個(gè)順序表。順序表中元素被劃分成一些子表（塊），子表內(nèi)數(shù)據(jù)不要求有序；但對于任意兩個(gè)子表塊來說，(2)(3)排面的子表中的任意數(shù)據(jù)的鍵值不能大于或小于排在后面的子表中的所有數(shù)據(jù)元素的鍵值。若用順序查找確定所在的塊，每塊含s個(gè)元素。平均查找長度為( n/s+ s)/2+1。Data Structure26數(shù)據(jù)結(jié)構(gòu)四、應(yīng)用題1已知一個(gè)散列表如下圖所示：其散列

10、函數(shù)為H(key)=key%13，即d0=H(key)；處理的方法為雙重散列法，探查序列為： di=(H(key)+i*H1(key)%13，i=1,2,12其中 H1(key)=key%11+1，回答下列問題：(1)寫出對表中關(guān)鍵字8，15，21和34進(jìn)行查找時(shí)的操作過程，所需進(jìn)行的比較次數(shù)各為多少？該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？(2)23456789101112數(shù)據(jù)結(jié)構(gòu)Data Structure27四、應(yīng)用題： di=(H(key)+i*H1(key)%13, i=1,2,12參考8 ： d0=H(8)=8, d1=(8+1*(8%11+1)%13 =4,查找成功，

11、比較2次。15：d0=H(15)=2, 查找成功，比較1次。21：d0=H(21)=8, 查找成功，比較1次。34：d0=H(34)=8, d1=(8+1*(34%11+1)%13=10,d2=(8+2*(34%11+1)%13=12,查找成功，比較3次。23：d0=H(23)=10，查找成功，比較1次AVL=(2+1+1+1+3)/5=1.623456789101112Data Structure28數(shù)據(jù)結(jié)構(gòu)四、應(yīng)用題2. 設(shè)散列函數(shù)為H(k)=k%7，散列表的地址空間為0-6；對關(guān)鍵字序列32，13，49，55，22，38，21按線性探測法解決的方法構(gòu)造散列表，并查找每個(gè)關(guān)鍵字要進(jìn)行幾次比

12、較？參考散列表Data Structure29數(shù)據(jù)結(jié)構(gòu)比較次數(shù)關(guān)關(guān)鍵字552238322113比較次數(shù)1321161495522383221五、編程用折半查找法在有序表ST中查找某一關(guān)鍵值，若找到，則返回該元素在順序表中的位置；否則，返回0。請用C語言編制實(shí)現(xiàn)該算法的函數(shù)。有序表的結(jié)點(diǎn)類型定義為：typedef structKeyType key; Element; typedef struct Element *elem;length; SSTable;函數(shù)首部為：Search_Bin(SSTable ST, KeyType key)Data Structure30數(shù)據(jù)結(jié)構(gòu)五、編程參考：Search_Bin(SSTable ST, KeyT