【文章內(nèi)容簡介】 ashtable[k]。_______________________。}}hashtable[i]=0，hashtable[k]=s9．下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct record{int key。 int others。}。int bisearch(struct record r[ ], int k){ int low=0,mid,high=n1。 while(low=high){ ________________________________。 if(r[mid].key==k) return(mid+1)。 else if(____________) high=mid1。else low=mid+1。 } return(0)。} mid=(low+high)/2，r[mid].keyk10．設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。4，1011．設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有_________個，比較兩次查找成功有結(jié)點數(shù)有_________個。1，212．設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。h13．設(shè)散列表的長度為8，散列函數(shù)H(k)=k % 7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。8/314．設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。19/715．下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。typedef struct node{int data。struct node *lchild。struct node *rchild。}bitree。void bstinsert(bitree *amp。t,int k){if(t==0) {____________________________。tdata=k。tlchild=trchild=0。}else if (tdatak) bstinsert(tlchild,k)。else__________________________。} t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)16．解決散列表沖突的兩種方法是________________和__________________。開放定址法，鏈地址法17．在一棵m階B_樹上，每個非樹根結(jié)點的關(guān)鍵字?jǐn)?shù)目最少為_______個，最多為_____個，其子樹數(shù)目最少為______，最多為____。 、m1 、 、 m18．從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明_______，若元素的值小于根結(jié)點的值，則繼續(xù)向________查找，若元素的大于根結(jié)點的值，則繼續(xù)向________查找。查找成功、左子樹、右子樹19．對于二分查找所對應(yīng)的判定樹，它既是一棵_ ____，又是一棵_____ __ ___。二叉搜索樹、理想平衡樹20．二叉搜索樹的中序遍歷得到的結(jié)點序列為____ ____。 有序序列 21．從有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素時，其查找長度分別為___________和__________。1 ， 322．假定對長度n=144的線性表進行索引查找，并假定每個子表的長度均為,則進行索引查找的平均查找長度為__________，時間復(fù)雜度為___________。13， O()23．一棵B樹中的所有葉子結(jié)點均處在_____________上。同一層24．每次從無序表中順序取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_______排序；每次從無序表中挑選出一個最大或最小元素，把它交換到有序表中的一端，此種排序方法叫做_________排序。插入 選擇25．對于線性表（18，25，63，50，41，32，90，66）進行散列存儲時，若選用H（K）=K%11作為散列函數(shù)，則散列地址為0的元素有______個，散列地址為3的元素有______個，散列地址為8的元素有______個。1 1 226．在一個具有n個結(jié)點的單鏈表中查找值為m的某結(jié)點，若查找成功，則需平均比較的結(jié)點數(shù)為____(n+1)/2________。27．在一棵二叉排序樹上按_____中序_______遍歷得到的結(jié)點序列是一個有序序列。28．實現(xiàn)二分查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu)，且其中元素排列必須是____有序的。29．設(shè)順序表的表長為n，且查找每個元素的概率相等，則采用順序查找法查找表中任一元素，在查找成功時的平均查找長度為___(n+1)/2_______。30．在索引順序表上的查找分兩個階段：一是查找_____索引表_____，二是查找塊。31．一棵平衡二叉樹中任一結(jié)點的平衡因子只可能是__1，0，1_____。32．二分查找的時間復(fù)雜度為__O(log2n)_____。33．查找表的數(shù)據(jù)結(jié)構(gòu)有別于線性表、樹型結(jié)構(gòu)等，其邏輯結(jié)構(gòu)為____集合______。34．長度為L的順序表，采用設(shè)置崗哨方式順序查找，若查找不成功，其查找長度為__L+1_______。35．在開散列表上查找某元素時，通常分兩步進行，首先必須計算該鍵值的散列地址，然后在地址指針?biāo)竉________同義詞子表_______中查找該結(jié)點。36．對二叉排序樹進行__中序______遍歷，可得到排好序的遞增結(jié)點序列。37．采用折半查找方法進行查找的數(shù)據(jù)序列應(yīng)為____順序存儲____且___有序_____。38．查找表的邏輯組織結(jié)構(gòu)實際上是____集合____________結(jié)構(gòu)。39．對于具有n個元素的數(shù)據(jù)序列，采用順序查找法，其平均查找長度為____(n+1)/2______。40．快速排序算法在最差的情況下其時間復(fù)雜度是 。O(n2)41．在線性表的________存儲中，對每一個元素只能采用順序查找。鏈?zhǔn)?2．采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為________________。（n+1）/243．以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為________，時間復(fù)雜度為________。(n+1)/O(n)44．以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于________，時間復(fù)雜度為________。O(log2n)45．以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為________。37/1246．以二分查找方法查找一個線性表時，此線性表必須是________存儲的________表。順序、有序47．從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為________和________。348．對于二分查找所對應(yīng)的判定樹，它既是一棵_______，又是一棵________。二叉搜索樹、理想平衡樹49．假定對長度n=50的有序表進行二分查找，則對應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點數(shù)為________，最后一層的結(jié)點數(shù)為________。31950．在索引表中，每個索引項至少包含有________域和________域這兩項。索引、開始地址51．假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為________、________和________。(12,63,36)、(55,40,82)、(23,74)52．假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為________、________和________。253．在線性表的________存儲中，無法查找到一個元素的前驅(qū)或后繼元素。散列54．在線性表的________存儲中，對每一個元素只能采用順序查找。鏈接55．假定對線性表(38,25,74,52,48)進行散列存儲，采用H(K)=K % 7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進行查找的平均查找長度分別為_______和________。7/556．假定要對長度n=100的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為________。557．在線性表的散列存儲中，處理沖突有________和________兩種方法。開放定址、鏈接58．對于線性表(18,25,63,50,42,32,90)進行散列存儲時，若選用H(K)=K % 9作為散列函數(shù)，則散列地址為0的元素有________個，散列地址為5的元素有________個。259．在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為_________,整個堆排序過程的時間復(fù)雜度為________________。O（log2n）、O(nlog2n)。60. 順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__ __次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為__ __。n n+161. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 。哈希查找 62. 在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為__________。6,9,11,1263. 己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找90時，需__________次查找成功，47時__________成功，查100時，需__________次才能確定不成功。2,4,364. 平衡二叉樹又稱_________，其定義是________。AVL樹(高度平衡樹，高度平衡的二叉排序樹)，或為空二叉樹，或二叉樹中任意結(jié)點左子樹高度與右子樹高度差的絕對值小于等于1。65. 在哈希函數(shù)H（key）=key%p中，p值最好取_________。小于等于表長的最大素數(shù)或不包含小于20的質(zhì)因子的合數(shù)66. 有一個2000項的表，欲采用等分區(qū)間順序查找方法進行查找，則每塊的理想長度是__(1)___，分成__(2)___塊最為理想，平均查找長度是__(3)___。(1)45 (2)45 (3)46(塊內(nèi)順序查找)67. 假定有k個關(guān)鍵字互為同義詞，若用線性探測再散列法把這k個關(guān)鍵字存入散列表中，至少要進行__________次探測。k(k+1)/268. 查找是非數(shù)值程序設(shè)計的一個重要技術(shù)問題，基本上分成__(1)__查找，__(2)__查找和__(3)__查找。處理哈希沖突的方法有__(4)__、__(5)__、__(6)__和__(7)__。(1)順序表 (2)樹表 (3)哈希表 (4)開放定址方法(1) (5)鏈地址方法 (6)再哈希 (7)建立公共溢出區(qū)69. 在含有n個結(jié)點的二叉排序樹中查找一個關(guān)鍵字，進行關(guān)鍵字比較次數(shù)最大值是 。n70. 一棵深度為k的平衡二叉樹，其每個非終端結(jié)點的平衡因子均為0，則該樹共有 個結(jié)點。2k171. 假定查找有序表A[1..12]中每個元素的概率相等，則進行二分查找時的平均查找長度為__________ 37/1272. 動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有__________和__________運算，而后者不包含這兩種運算。插入 刪除73. 對于具有144 個記錄的文件，若采用分塊查找法，且每塊長度為8，則平均查找長度為__________. 1474. 以順序查找方法從長度為 n 的順序表或單鏈表中查找一個元素時，平均查找長度為 ________ ，時間復(fù)雜性為 ________ 。(n+1)/2 O(n)75. 假定一個順序表的長度為 40 ，并假定查找每個元素的概率都相同，則在查找成功情況下的平均查找長度 ________ ，在查找不成功情況下的平均查找長度 ________ 。 4176. 以二分查找方法從長度為 50 的有序表中查找一個元素時，其查找長度不超過 ________ 。677. 以二分查找方法在一個查找表上進行查找時，該查找表必須組織成 ________ 存儲的 ________ 表。順序 有序78. 從有序表 (12,18,30,43,56,78,82,95) 中分別二分查找 43 和 56 元素時，其查找長度分別為 ________ 和 ________ 。1 379. 二分查找所對應(yīng)的判定樹，既是一棵 _______ ，又是一棵 ________ 。二叉排序樹 理想平衡樹80. 假定對長度 n=50 的有序表進行二分查找，則對應(yīng)的判定樹高度為 ________ ，最后一層的結(jié)點數(shù)為 ________ 。6 1981. 假定在索引查找中，查找表長度為 n ，每個子表的長度相等，設(shè)為 s ，則進行成功查找的平均查找長度為 ____________ 。(n/s+s)/2+182. 在索引查找中，假定查找表（即主表）的長度為 96 ，被等分為 8 個子表，則進行索引查找的平均查找長度為 ________ 。1183. 在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定 ________ 該結(jié)點的值，右子樹上所有結(jié)點的值一定 ________ 該結(jié)點的值。小于 大于84. 對一棵二叉排序樹進行中序遍歷時，得到的結(jié)點序列是一個 ________ 。有序序列85. 從一棵二叉排序樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明 _______ ，若元素的值小于根結(jié)點的值，則繼續(xù)向 ________ 查找，若元素的值大于根結(jié)點的值，則繼續(xù)向 ________ 查找。查找成功 左子樹 右子樹86. 向一棵二叉排序樹中插入一個元素時，若元素的值小于根結(jié)