數據結構問題

數據結構問題試卷選擇10.一組記錄的排序碼為(25,48,16,35,79,82,23,40,36,72),其中含有5個長度為2的有序表,按歸并排序的方法對該序列進行一趟歸并后的結果為.A.16,25,35,48,23,40,79,82,36,72B.16,25,35,48,79,82,23,36,40,72C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82填空4?假設在有序線性表A[1..20]上進行折半查找，平均查找長度約為 。簡答4.已知一組關鍵字為(10,24,32,17,31,30,46,47,40,63,49),設哈希函數H(key)=key%7。請解答：寫出用鏈地址法處理沖突構造所得的哈希表；若查找關鍵字31,需要依次與哪些關鍵字進行比較？假定每個關鍵字的查找概率相等,求查找成功時的平均查找長度。試卷二選擇TOC\o"1-5"\h\z若用一個大小為6的數組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3,當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少 。1和5B.2和4 C.4和2 D.5和14?設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a為第一元素，其11存儲地址為1,每個元素占一個地址空間，則a85的地址為 。A.13 B.33 C.18 D.404.在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接插入排序時,當把第7個記錄60插入到有序表時，為尋找插入位置需比 次。簡答有一個1000項的表,要分塊查找(索引表也是順序查找),試問：(1)最理想分多少塊和每塊最理想長度是多少?求此時的ASL。(2)若每塊是10,ASL是多少？Ik ?試卷三若以｛4,5,6,7,8｝作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是 .5?一組記錄的排序碼為(45,29,56,37,40,84,82),則利用堆排序的方法建立的初始堆(大頂堆)為 。(要求寫出序列而不要畫出圖形)試卷五選擇若串S='ABCDEFG',S2='9898' ,S3='###',S4='012345'，執(zhí)行1concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,'8'),length(S2)))，其結果為( )。A.ABC###G0123B.ABCD###2345C.ABC###G1234D.ABCD###1234

8.當采用分快查找時，數據的組織方式為（ ）。A.數據分成若干塊，每塊內數據有序數據分成若干塊，每塊內數據不必有序，但塊間必須有序，每塊內最大（或最?。┑臄祿M成索引塊數據分成若干塊，每塊內數據有序，每塊內最大（或最?。┑臄祿M成索引塊數據分成若干塊，每塊（除最后一塊外）中數據個數需相同10.在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應作（）型調整以使其平衡。（平衡因子=左子樹深度-右子樹深度）A.LL（單向右旋） B.LR（先左后右雙向旋轉）C.RL（先右后左雙向旋轉） D.RR（單向左旋）填空4.當以鄰接表作為存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為 。簡答設有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設計一套二進制哈夫曼編碼，使得上述正文的編碼最短。（求解過程中要求畫出編碼樹）試卷六選擇&在等概率情況下,線性表的順序查找的平均查找長度ASL為（（1））,有序表的折半查找的ASL為（（2）），對二叉排序樹表,在最壞情況下,ASL為（（3）），而當它是一棵平衡樹時,ASL為((4)）。A.(1)(2)(3)(4)B.(1)(2)時,ASL為((4)）。A.(1)(2)(3)(4)B.(1)(2)(3)(4)C.(1)(2)(3)(4)D.(1)(2)(3)(4)O(1),O(n),O(n),O(n),供選擇的答案：O(n)O(log）。,O(logn),O(nlogn)22O(nlogn),O(1)2O(logn)2,O(n),O(logn)2O(logn),O(n),O(nlogn)22填空TOC\o"1-5"\h\zn階上二角矩陣A（當i〉j時，有a..=0,1<i,j<n）壓縮的下標對應關系為： 。j若a=1，b=2，c=3,d=4,則后綴式db/cc*a-b*+的運算結果為 。試卷七填空2.一棵二叉樹有67個結點,這些結點的度要么是0，要么是2。這棵二叉樹中度數為2的結點有 個。3?線性表L=（al,a2,…,a采用順序結構存儲，假定在不同的位置上插入的概率相同，則插入一個新元素平均需要移動的元素個數是 。棧S和隊列Q的初始狀態(tài)皆為空，元素al,a2,a3,a4,a5和a6依次通過S棧，一個元素出棧后即進入隊列Q,若6個元素出隊列的順序是a3,a5,a4,a6,a2,a1，則棧S至少應該容納 個元素。簡答5?設散列表為HT[13],散列函數為H（key）=key%13。用閉散列法解決沖突，對下列關鍵

碼序列12,23,45,57,20,03,78,31,15,36造表。(1)采用線性探查法尋找下一個空位,畫出相應的散列表,并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。(2)采用雙散列法尋找下一個空位,再散列函數為RH(key)=(7*key)%10+1,尋找下一個空位的公式為H.=(H「+RH(key))%13,H,=H(key)。畫出相應的散列表，并計算等概率下i i-1 1搜索成功的平均搜索長度。試卷十選擇設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用( )最節(jié)省時間。A.單鏈表 B.單循環(huán)鏈表 C.帶尾指針的單循環(huán)鏈表 D.帶頭結點的雙循環(huán)鏈表25.當一個有N個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是()。n乙A[i,刀為Ab,j]n乙A[j,i]Ai=1B．j=1C． i=15.下列程序判斷字符串s是否對稱，對稱則返回1否則返回0；如f("abba")返回1f("abab")返回0；TOC\o"1-5"\h\zintf(_ ___){inti=0,j=0;while(sj])_ _ __;for(j--;i<j&&s[i]==s[j];i++,j--);return(— __)}練習題8查找填空6．已知有序表為(12， 18，24， 35， 47， 50， 62， 83， 90， 115， 134)，當用折半查找90時，需進行 次查找可確定成功；查找47時，需進行 次查找成功；查找100時,需進行次查找才能確定不成功。練習題9排序選擇一組記錄的排序碼為(46，79，56，38，40，84)，則利用堆排序的方法建立的初始堆為A.79，46，56，38，40，A.79，46，56，38，40，84C.84，79，56，38，40，465.一組記錄的關鍵碼為(46，79，56D.84，56，79，40，46，3838，40，84)，則利用快速排序的方法，以第一個記TOC\o"1-5"\h\z錄為基準得到的一次劃分結果為 。A.38， 40， 46， 56， 79， 84 B.40， 38， 46， 79， 56， 84C.40， 38， 46， 56， 79， 84 D.40， 38， 46， 84， 56， 799.用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進行排序時，元素序列的變化情況如下：⑴25， 84， 21， 47， 15， 27， 68， 35， 20⑵20， 15， 21， 25， 47， 27， 68， 35， 84\o"CurrentDocument"⑶15， 20， 21， 25， 3