【正文】 元素都是原子，則廣義表便成為線性表。( √ )，則它必是該子樹的前序 遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( )18. 連通分量是無向圖中的極小連通子圖。( √ )22. 中序遍歷二叉排序樹的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列。( √ )26. 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是O(nlog2 n)。( )30. 索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或域。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進(jìn)行的操作的總和。線性表一般有插入、刪除、讀取等對(duì)于任意元素的操作。答：相同點(diǎn)：棧和隊(duì)列都是特殊的線性表，只在端點(diǎn)處進(jìn)行插入，刪除操作。 ACBD。 BACD。 BDCA。 DCBA。求：StrLength (s)， StrLength (t)，SubStr( s，8，7)，SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex (s，t)，StrRep(s，“STUDENT”，q)，SubStr (SubStr (s，6，2)，StrConcat (t，SubStr(s，7，8)))。主串與子串：子串是主串的一個(gè)子集。(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13689. 分別畫出含三個(gè)結(jié)點(diǎn)的無序樹與二叉樹的所有不同形態(tài)。 (2) 后序序列與中序序列相同。答：這棵二叉樹為:13. 分別寫出圖2中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。答：（1）鄰接矩陣:（2）鄰接鏈表：（3）每個(gè)頂點(diǎn)的度：頂點(diǎn) 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個(gè)頂點(diǎn)的入度和出度。 V1 V4 V3 V5 V2廣度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。 (3)它的左、右子樹也分別為二叉排序樹。 二分查找也是有代價(jià)的，因?yàn)槭孪缺仨殞?duì)整個(gè)查找區(qū)間進(jìn)行排序，而排序也是費(fèi)時(shí)的，所以常應(yīng)用于頻繁查找的場合。當(dāng)給定值K與閉散列表中的某個(gè)鍵值是相對(duì)于某個(gè)散列函數(shù)Hi的同義詞因而發(fā)生沖突時(shí)，繼續(xù)計(jì)算該給定值K在下一個(gè)散列函數(shù)Hi+1下的散列地址，直到不再產(chǎn)生沖突為止。插入首先在基本表上進(jìn)行；假如發(fā)生沖突，則將信息存人溢出表。假設(shè)在待排序的文件中存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字，若采用某種排序方法后，使得這些具有相同關(guān)鍵字的記錄在排序前后相對(duì)次序依然保持不變，則認(rèn)為該排序方法是穩(wěn)定的，否則就認(rèn)為排序方法是不穩(wěn)定的。 SeqStackInit_Queue(p)。 SeQueueIn_Queue(q，’h’)。In_Queue(q，’a’ )；while (!Empty_SeqStack(q)) printf(“%c”，y)；}printf(“%C\n”，x)；}答：char。 In_Queue(q, y)。 y=’c’。char x，y；q=amp。 }答：stack3. 寫出下列程序段的運(yùn)行結(jié)果(隊(duì)列中的元素類型是char)：main( ) printf(“％c”，y)；}printf(“％c＼n”，x)；while (!Empty_SeqStack(p))push (p，’t’)。 y= ‘k’；push (p，x)； push (p，’a’)；push (p，y)。；char x，y；p=amp。(每小題4分，共8分)1. 分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。24. 什么是內(nèi)部排序?什么是排序方法的穩(wěn)定性?答：假定給定含有n個(gè)記錄的文件(r1，r2，…，rn)，其相應(yīng)的關(guān)鍵字為(k1，k2，…，kn)，則排序就是確定文件的一個(gè)序列r1，r2，…，rn，使得k1≤k2≤…≤kn，從而使得文件中n個(gè)記錄按其對(duì)應(yīng)關(guān)鍵字有序排列。答：散列表由兩個(gè)一維數(shù)組組成。21. 簡述多重散列法解決沖突的基本思想。盡管有些算法時(shí)間性能很好，但是其他方面可能就存在著不足。 V1 V4 V3 V2 V519. 何謂二叉排序樹?答：一棵二叉排序樹(又稱二叉查找樹)或者是一棵空樹，或者是一棵同時(shí)滿足下列條件的二叉樹： (1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的鍵值均小于它根結(jié)點(diǎn)鍵值。答：深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。答：哈夫曼樹為:15. 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10，試為這8個(gè)設(shè)計(jì)哈夫曼編碼。答：(1) 先序序列和中序序列相同：空樹或缺左子樹的單支樹； (2) 后序序列和中序序列相同：空樹或缺右子樹的單支樹； (3) 先序序列和后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。答：先序遍歷序列:ABDEHICFJG 中序遍歷序列:DBHEIAFJCG 后序遍歷序列:DHIEBJFGCA11. 試找出分別滿足下列條件的所有二叉樹。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的起地址。答：空串：不含任何字符；空格串：所含字符都是空格。答：不能得到4，3，5，6，1，2，最先出棧的是4,則按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式進(jìn)行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。 CBDA。 BCAD。 ABDC。4. 如果進(jìn)棧的元素序列為A，B，C，D，則可能得到的出棧序列有多少種? 寫出全部的可能序列。棧只能在線性表的一端插入（稱為入棧,push）或者讀取棧頂元素或者稱為“彈出、出?！?pop)。2. 簡述棧和線性表的區(qū)別。數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素間的關(guān)系。(共6小題，每小題約5分，共32分) 1. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和算法。( )28. 磁盤上的順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件。( √ )24. 當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素。( √ )20. 散列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。( )16. 在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊處理。( )12. 后序遍歷樹和中序遍歷與該樹對(duì)應(yīng)的二叉樹，其結(jié)果不同。( )8．?dāng)?shù)組是同類型值的集合。( √ )4．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同一數(shù)據(jù)對(duì)象。三、判斷題。(49) 在對(duì)一組記錄(50,40,95，20，15,70,60,45,80)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較____3_____次。(46) 在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是___快速_______，需要內(nèi)存容量最多的是____歸并______。(42) 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用______快速_________排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用______歸并_________排序。(38) 構(gòu)造哈希函數(shù)的方法有(寫二個(gè))______________直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機(jī)數(shù)法_________________________________________。(34) 在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于____ n/m _______。(30) 假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的