【正文】 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是___ B _______。(12) 線性表的存儲(chǔ)結(jié)構(gòu)有_________順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)____________________。(27) 在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無向圖來說等于該 頂點(diǎn)的 ______度數(shù)______，對(duì)于有向圖來說等于該頂點(diǎn)的______出度數(shù)______。(43) 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為___ O(log2n)_____，整個(gè)堆排序過程的時(shí)間復(fù)雜度為____ O(nlog2n)____。( )5．在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素。( √ )21. m階B樹每一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)都小于或等于m。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。 ADCB。串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的。答：哈夫曼樹為:在上述哈夫曼樹的每個(gè)左分支上標(biāo)以0，右分支上標(biāo)以1，并設(shè)這8個(gè)字母分別為A、B、C、D、E、F、G和H，則它們的哈夫曼樹為分別為:A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：000116. 畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個(gè)頂點(diǎn)的度。答：此法要求設(shè)立多個(gè)散列函數(shù)Hi，i=1，…，k。s。a； { y= Out_Queue(q)；x=Out_Queue (q)；In_Queue(q，x)；x= Out_Queue (q)。{ (1) for(i＝1；i＝n；i++) for(j＝1；j＝n；j++) s++； (2) for(i＝1；i＝n；i++) for(j＝i；j＝n；j++)s++；(3) for(i＝1；i＝n；i++) for(j＝1；j＝i；j++) s++；(4) i＝1； k＝0；while(i＝n1){k+＝10*i；i++；}(5) for (i＝1；i＝n；i++) for (j＝1；j＝i ；j++) for (k＝1；k＝j(luò)；k++) x=x+1；(1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n1) (5) Ο(n3)2. 寫出下列程序段的運(yùn)行結(jié)果(棧中的元素類型是char)：main( ){比如散列查找的時(shí)間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。12. 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。6. 設(shè)s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。答：可能序列有14種：ABCD。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計(jì)算機(jī)程序加工和處理的對(duì)象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。( √ )17. 有回路的圖不能進(jìn)行拓?fù)渑判颉?每小題1分，共10分)( )1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(39) 在分塊查找中首先查找 _____索引________，然后再查找相應(yīng)的______塊_________。(23) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為________模式匹配________。(8) 對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱為 空間復(fù)雜度和時(shí)間復(fù)雜度 分析。 A. 2，3，5，8，6 B. 3，2，5，8，6 C. 3，2，5，6，8 D. 2，3，6，5，8(73) 下列排序方法中，哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)___ D _____。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長(zhǎng)度為___ B _____。D. 15A. 串中不同字符的個(gè)數(shù)C. n+1i A. pnext=pnextnext B. p=pnext C. p=pnextnext D. pnext=p(18) 下列說法哪個(gè)正確？____ D ______(每小題2分，共40分)(1) 。 +1 (14) 鏈表是一種采用____ B ____存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表； (15) 下面關(guān)于線性表的敘述錯(cuò)誤的是___ D _____。B. BC. 3C. (RF+M)%MB. 模式匹配B. BCDEFGA. i+j B. ij C. 1 D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為____A____ 。A. 46,79,56,38,40,84 ,56,38,79,40,84C. 38,40,46,56,84,79 ,46,79,56,40,84(70) 每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做___ A _____ 排序。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的____關(guān)系__________。(20) s1=”hello “,s2=”boy”,s1,s2連接后為：________ hello boy ______________(36) 在散列存儲(chǔ)中，裝填因子a的值越大，則_______產(chǎn)生沖突的可能性就越大____________；a的值越小，則_____產(chǎn)生沖突的可能性就越小___________。(51) 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的附加空間消耗是___ O(n)______。( √ )，則它必是該子樹的前序 遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( )30. 索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。答：相同點(diǎn)：棧和隊(duì)列都是特殊的線性表，只在端點(diǎn)處進(jìn)行插入，刪除操作。 DCBA。 (2) 后序序列與中序序列相同。 (3)它的左、右子樹也分別為二叉排序樹。假設(shè)在待排序的文件中存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字，若采用某種排序方法后，使得這些具有相同關(guān)鍵字的記錄在排序前后相對(duì)次序依然保持不變，則認(rèn)為該排序方法是穩(wěn)定的，否則就認(rèn)為排序方法是不穩(wěn)定的。 y=’c’。 y= ‘k’；push (p，x)； push (p，’a’)；push (p，y)。答：散列表由兩個(gè)一維數(shù)組組成。答：深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。8. 設(shè)有二維數(shù)組A(68)，每個(gè)元素占6個(gè)字節(jié)存儲(chǔ)，順序存放，A的起地址為1000，計(jì)算：(1)數(shù)組A的體積(即存儲(chǔ)量)；(2)數(shù)組的最后一個(gè)元素A??的起地址；(3)按行優(yōu)先存放時(shí)，元素A1,4的起地址；(4)按列優(yōu)先存放時(shí)，元素A4,7的起地址。 BCAD。2. 簡(jiǎn)述棧和線性表的區(qū)別。( √ )24. 當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素。( )8．?dāng)?shù)組是同類型值的集合。(46) 在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是___快速_______，需要內(nèi)存容量最多的是____歸并______。(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_______，平均查找長(zhǎng)度為_____ log2(n+1)1______。(15) 若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_____鏈?zhǔn)絖________存儲(chǔ)結(jié)構(gòu)。(每空1分，共10