數(shù)據(jù)結(jié)構(gòu)復習題及答案(12級)(存儲版)
【正文】 為____2_______，則比較三次查找成功的結(jié)點數(shù)為____4_______，則比較四次查找成功的結(jié)點數(shù)為_____8______，則比較五次查找成功的結(jié)點數(shù)為____5_______，平均查找長度為_____ log2(n+1)1______。(38) 構(gòu)造哈希函數(shù)的方法有(寫二個)______________直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機數(shù)法_________________________________________。(46) 在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是___快速_______，需要內(nèi)存容量最多的是____歸并______。三、判斷題。( )8．數(shù)組是同類型值的集合。( )16. 在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應作特殊處理。( √ )24. 當待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜性的主要因素。(共6小題，每小題約5分，共32分) 1. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)類型和算法。2. 簡述棧和線性表的區(qū)別。4. 如果進棧的元素序列為A，B，C，D，則可能得到的出棧序列有多少種? 寫出全部的可能序列。 BCAD。答：不能得到4，3，5，6，1，2，最先出棧的是4,則按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式進行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。8. 設(shè)有二維數(shù)組A(68)，每個元素占6個字節(jié)存儲，順序存放，A的起地址為1000，計算：(1)數(shù)組A的體積(即存儲量)；(2)數(shù)組的最后一個元素A??的起地址；(3)按行優(yōu)先存放時，元素A1,4的起地址；(4)按列優(yōu)先存放時，元素A4,7的起地址。答：(1) 先序序列和中序序列相同：空樹或缺左子樹的單支樹； (2) 后序序列和中序序列相同：空樹或缺右子樹的單支樹； (3) 先序序列和后序序列相同：空樹或只有根結(jié)點的二叉樹。答：深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。盡管有些算法時間性能很好，但是其他方面可能就存在著不足。答：散列表由兩個一維數(shù)組組成。(每小題4分，共8分)1. 分析下面語句段執(zhí)行的時間復雜度。 y= ‘k’；push (p，x)； push (p，’a’)；push (p，y)。push (p，’t’)。 }答：stack3. 寫出下列程序段的運行結(jié)果(隊列中的元素類型是char)：main( ) y=’c’。 In_Queue(q, y)。Init_Queue(p)。假設(shè)在待排序的文件中存在兩個或兩個以上的記錄具有相同的關(guān)鍵字，若采用某種排序方法后，使得這些具有相同關(guān)鍵字的記錄在排序前后相對次序依然保持不變，則認為該排序方法是穩(wěn)定的，否則就認為排序方法是不穩(wěn)定的。當給定值K與閉散列表中的某個鍵值是相對于某個散列函數(shù)Hi的同義詞因而發(fā)生沖突時，繼續(xù)計算該給定值K在下一個散列函數(shù)Hi+1下的散列地址，直到不再產(chǎn)生沖突為止。 (3)它的左、右子樹也分別為二叉排序樹。答：（1）鄰接矩陣:（2）鄰接鏈表：（3）每個頂點的度：頂點 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個頂點的入度和出度。 (2) 后序序列與中序序列相同。主串與子串：子串是主串的一個子集。 DCBA。 BACD。答：相同點：棧和隊列都是特殊的線性表，只在端點處進行插入，刪除操作。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進行的操作的總和。( )30. 索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。( √ )22. 中序遍歷二叉排序樹的結(jié)點就可以得到排好序的結(jié)點序列。( √ )，則它必是該子樹的前序 遍歷序列中的最后一個結(jié)點。( )6．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。(51) 對于n個記錄的集合進行歸并排序，所需的附加空間消耗是___ O(n)______。(44) 當向一個大根堆插入一個具有最大值的元素時，需要逐層____向上_____調(diào)整，直到被調(diào)整到_____根結(jié)點_______位置為止。(36) 在散列存儲中，裝填因子a的值越大，則_______產(chǎn)生沖突的可能性就越大____________；a的值越小，則_____產(chǎn)生沖突的可能性就越小___________。(28) 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復雜性為______O(n2 ) ______， 采用鄰接表表示的空間復雜性為______ O(n+e) ______。(20) s1=”hello “,s2=”boy”,s1,s2連接后為：________ hello boy ______________(13) 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復雜度為_____Ｏ(n)______，在鏈式存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復雜度為____ O(n)_______。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的____關(guān)系__________。A． n B． 2n1 C． 2n D． n1(78) 下列排序算法中，____ C ____ 算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的間反而最多。A. 46,79,56,38,40,84 ,56,38,79,40,84C. 38,40,46,56,84,79 ,46,79,56,40,84(70) 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做___ A _____ 排序。A. 較慢 B. 較快 C. 相同 D. 不確定(62) 對線性表進行折半查找最方便的存儲結(jié)構(gòu)是____ B _______。A. i+j B. ij C. 1 D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復雜性均為____A____ 。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五層的滿二叉樹中，結(jié)點總數(shù)為____A____。B. BCDEFGB. 模式匹配____ C _____。C. (RF+M)%MA. 1和5C. 3 (28) 字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成___ B ___個不同的字符串？A. 15B. BA、插入操作更加方便 B、刪除操作更加方便C、不會出現(xiàn)下溢的情況 D、不會出現(xiàn)上溢的情況(22) 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)___ D ______。 +1 (14) 鏈表是一種采用____ B ____存儲結(jié)構(gòu)存儲的線性表； (15) 下面關(guān)于線性表的敘述錯誤的是___ D _____。 (6) 設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，則數(shù)據(jù)結(jié)構(gòu)A是____ A ______。(每小題2分，共40分)(1) 。 (9) 對一個算法的評價，不包括如下____ B _____方面的內(nèi)容。 A. pnext=pnextnext B. p=pnext C. p=pnextnext D. pnext=p(18) 下列說法哪個正確？____ D ______(23) 若已知一個棧的入棧序列是1，2，3，…，n，其輸出序
教學教案相關(guān)推薦
鄂ICP備17016276號-1