【正文】 { y= Out_Queue(q)；x=Out_Queue (q)；In_Queue(q，x)；x= Out_Queue (q)。 In_Queue(q, ’r’)。Init_Queue(q)。a；{x=pops。 (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. 寫(xiě)出下列程序段的運(yùn)行結(jié)果(棧中的元素類型是char)：main( ){如果整個(gè)排序過(guò)程在內(nèi)存中進(jìn)行，則排序叫內(nèi)部排序。一個(gè)稱為基本表，另一個(gè)稱為溢出表。答：此法要求設(shè)立多個(gè)散列函數(shù)Hi，i=1，…，k。比如散列查找的時(shí)間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問(wèn)題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。 (2)若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的鍵值均大于它根結(jié)點(diǎn)鍵值。 V1 V3 V5 V4 V2。答：哈夫曼樹(shù)為:在上述哈夫曼樹(shù)的每個(gè)左分支上標(biāo)以0，右分支上標(biāo)以1，并設(shè)這8個(gè)字母分別為A、B、C、D、E、F、G和H，則它們的哈夫曼樹(shù)為分別為:A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：000116. 畫(huà)出無(wú)向圖G1的鄰接矩陣和鄰接表示意圖，并寫(xiě)出每個(gè)頂點(diǎn)的度。12. 已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫(huà)出這棵二叉樹(shù)。 (1) 先序序列與中序序列相同。串變量和串常量:串常量在程序的執(zhí)行過(guò)程中只能引用不能改變；串變量的值在程序執(zhí)行過(guò)程中是可以改變和重新賦值的。6. 設(shè)s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。 CDBA。 BCDA。 ADCB。答：可能序列有14種：ABCD。3. 簡(jiǎn)述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。答：一般線性表使用數(shù)組來(lái)表示的。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計(jì)算機(jī)程序加工和處理的對(duì)象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。( )29. 在索引順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件。( √ )25. 對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog2 n)。( √ )21. m階B樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于m。( √ )17. 有回路的圖不能進(jìn)行拓?fù)渑判颉? )13. 若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子 樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。 ( √ )9．使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間。( )5．在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素。(每小題1分，共10分)( )1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(50) 二路歸并排序的時(shí)間復(fù)雜度是___ O(nlog2n)______。(47) 堆排序是不穩(wěn)定，空間復(fù)雜度為 ____ O(1)_____。(43) 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_(kāi)__ O(log2n)_____，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)___ O(nlog2n)____。(39) 在分塊查找中首先查找 _____索引________，然后再查找相應(yīng)的______塊_________。(35) 散列表中解決沖突的兩種方法是____開(kāi)放地址法_________和____鏈地址法_________。(31) 在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定_____小于______該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定____大于_______該結(jié)點(diǎn)的值。(27) 在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該 頂點(diǎn)的 ______度數(shù)______，對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的______出度數(shù)______。(23) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為_(kāi)_______模式匹配________。(19) s=” I am a man” 長(zhǎng)度為_(kāi)___10_______(16) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含______數(shù)據(jù)__________域和_____指針__________域。(12) 線性表的存儲(chǔ)結(jié)構(gòu)有_________順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)____________________。(8) 對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱為 空間復(fù)雜度和時(shí)間復(fù)雜度 分析。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 數(shù)據(jù)元素間的邏輯關(guān)系 ，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系 。(2) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 結(jié)構(gòu)和 物理結(jié)構(gòu) 結(jié)構(gòu)。A. 快速排序 B． 堆排序C． 歸并排序 D． 直接插入排序(77) 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是___ B _______。 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)無(wú)關(guān)___ D _____。A. 起泡排序 B. 直接插入排序 C. 二路歸并排序 D. 快速排序(69) 一組記錄為{46，79，56，38，84，40}，則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是___ B _____ 。A．最大概率 B．最小概率 C．同等概率 D．平均概率(65) 下述排序算法中，穩(wěn)定的是___ B _____。 B. 平方取中法 C. 二分法 D. 開(kāi)放地址法(61) 當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有_____ B ______的查找速度。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為_(kāi)__ B _____。A. n1 B. n C. n+1 D. n*(n1)/2(53) 在無(wú)向圖G的鄰接矩陣A中，若A[i,j]等于1，則A[j,i]等于____C ____。 A. 23 B. 37 C. 44 D. 46(49) 在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m (m≥0)個(gè)____A ____的集合T1,T2,T3...Tm,每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)的子結(jié)點(diǎn)(1≤i≤m)。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為_(kāi)___C____。D. 15A. “STRUCTURE” A. BCDEF____ B ______。C. 串中所含字符的個(gè)數(shù)A. 串中不同字符的個(gè)數(shù)B. 串的長(zhǎng)度必須大于零C. rearnext=s；rear=s；(33) 設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為B. FRA. RF____ B _____。B. 4A. 6 A. top=top+1。C. n+1iB. decbaA. edcbaD. top(2