數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案(12級)-文庫吧資料
2025-06-28 14:40本頁面
【正文】 許且要求排序是穩(wěn)定時，宜采用______歸并_________排序。(40) 散列表的查找效率主要取決于散列表造表時選擇的_____哈希函數(shù)________ 和______裝填因子_________。(38) 構(gòu)造哈希函數(shù)的方法有(寫二個)______________直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機(jī)數(shù)法_________________________________________。(36) 在散列存儲中，裝填因子a的值越大，則_______產(chǎn)生沖突的可能性就越大____________；a的值越小，則_____產(chǎn)生沖突的可能性就越小___________。(34) 在線性表的散列存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于____ n/m _______。 (32) 對一棵二叉排序樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個_______增序序列_______________。(30) 假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為____1_______，則比較二次查找成功的結(jié)點(diǎn)數(shù)為____2_______，則比較三次查找成功的結(jié)點(diǎn)數(shù)為____4_______，則比較四次查找成功的結(jié)點(diǎn)數(shù)為_____8______，則比較五次查找成功的結(jié)點(diǎn)數(shù)為____5_______，平均查找長度為_____ log2(n+1)1______。(28) 假定一個圖具有n個頂點(diǎn)和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為______O(n2 ) ______， 采用鄰接表表示的空間復(fù)雜性為______ O(n+e) ______。(26) 由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為______ 55______。(24) 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有______前趨______結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且僅有______一______個前驅(qū)結(jié)點(diǎn)；樹葉結(jié)點(diǎn)沒有______后繼______結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的______后繼______結(jié)點(diǎn)數(shù)不受限制。(22) int a[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________(20) s1=”hello “,s2=”boy”,s1,s2連接后為：________ hello boy ___________________ FIFO ______表。(17) 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為___Ο(1)______，在表尾插入元素的時間復(fù)雜度為_____Ο(n)_______。(15) 若頻繁地對線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_____鏈?zhǔn)絖________存儲結(jié)構(gòu)。(13) 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_____Ｏ(n)______，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為____ O(n)_______。(11) 線性表是n個元素的_________有限序列____________________。(9) 算法的效率可分為______空間_________效率和______時間_________效率。當(dāng)結(jié)點(diǎn)之間存在1對N（1：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____樹結(jié)構(gòu)__________。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的____關(guān)系__________。(5) 一種抽象數(shù)據(jù)類型包括_____變量的取值范圍_____和 ____操作的類別_____兩個部分。(3) 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：____線性數(shù)據(jù)結(jié)構(gòu)_______、____樹型結(jié)構(gòu)______和_____圖結(jié)構(gòu)______。(每空1分，共10分)(1) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 數(shù)據(jù) 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。A． n B． 2n1 C． 2n D． n1(78) 下列排序算法中，____ C ____ 算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費(fèi)的間反而最多。A. 直接插入排序 B. 直接選擇排序C． 快速排序 D． 歸并排序(76) 若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是___ C _____ 。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接選擇排序(74) 設(shè)有關(guān)鍵碼初始序列{Q，H，C，Y，P，A,M,S,R,D,F,X}，新序列{F，H，C，D，P，A，M，Q，R，S，Y,X}是采用____ C ____ 方法對初始序列進(jìn)行第一趟掃描的結(jié)果。A. 插入 B. 堆 (72) 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為____ C ____。A. 46,79,56,38,40,84 ,56,38,79,40,84C. 38,40,46,56,84,79 ,46,79,56,40,84(70) 每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做___ A _____ 排序。A. 快速排序 B. 堆排序 C. 歸并排序 D. 冒泡排序(68) 在基于關(guān)鍵碼比較的排序算法中，____ C _____算法在最壞情況下，關(guān)鍵碼比較次數(shù)不高于O(nlog2n)。 B. 直接插入排序 (66) 下列排序算法中，____ A ____需要的輔助存儲空間最大。A．分塊 B．順序 C．折半 D．散列(64) 散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)按___ C ______取其值域的每一個值。A. 較慢 B. 較快 C. 相同 D. 不確定(62) 對線性表進(jìn)行折半查找最方便的存儲結(jié)構(gòu)是____ B _______。A. 小于等于m的最大奇數(shù) B. 小于等于m的最大素數(shù)C. 小于等于m的最大偶數(shù) D. 小于等于m的最大合數(shù)(60) ____ D _____是HASH查找的沖突處理方法。A. O(1) B. O(log2n) C. O(n) D. O(n2)(58) 依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索樹中，查找元素35要進(jìn)行__ A ___元素間的比較。 (56) 對線性表進(jìn)行折半查找時，必須要求線性表 ____ C ____。A. i+j B. ij C. 1 D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為____A____ 。A. 1/2 B. 1 C. 2 D. 4(52) 具有n個頂點(diǎn)的無向完全圖，邊的總數(shù)為____ D____條。A. 互不相交 B. 可以相交 C. 葉結(jié)點(diǎn)可以相交 D. 樹枝結(jié)點(diǎn)可以相交(50) 如果結(jié)點(diǎn)A有三個兄弟，而且B是A的雙親，則B的出度是____B____。A. 1 B. 2 C. D. 4(48) 由分別帶權(quán)為7的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為____C____。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為____A____。 A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18個，則它的最小高度____B____。C. 14D. “DATASTRUCTURE”(42) 設(shè)串S=”I AM A TEACHER!”，其長度是____ D ______。B. “DATA” D. BCDEFEF (41) 函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為___ A ______。B. BCDEFGD. 求串長(4
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1