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