2020年新編數(shù)據(jù)結(jié)構(gòu)老師給的復(fù)習(xí)要點(diǎn)嚴(yán)蔚敏版名師精品資料

1、第一章1. 怎樣理解“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這個(gè)公式？舉例說(shuō)明。算法是語(yǔ)句序列解決特定問(wèn)題的固有程序片段。數(shù)據(jù)結(jié)構(gòu)是確定數(shù)據(jù)間的關(guān)系。從具 體問(wèn)題抽象出一個(gè)合適的數(shù)學(xué)模型、然后設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法，最后編寫出程 序。尋求數(shù)學(xué)模型的是指就是數(shù)據(jù)結(jié)構(gòu)要完成的工作。參看書pl前兩段的描述。2. 數(shù)據(jù)結(jié)構(gòu)的概念，它包含哪三方面的內(nèi)容？數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間 餓關(guān)系和操作的學(xué)科。參看書p3包含三方面的內(nèi)容：1、數(shù)據(jù)之間的邏輯關(guān)系 2、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式3、在數(shù)據(jù)上定義的運(yùn)算的集合。3. 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的基本概念。舉例說(shuō)明數(shù)據(jù)元素和

2、數(shù)據(jù)項(xiàng)的聯(lián)系與區(qū)別。數(shù)據(jù)：描述客觀事物的數(shù)字、字符以及所有能直接輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處 理的符號(hào)的集合。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮或處理。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位，是數(shù)據(jù)元的一個(gè)具體值，是數(shù) 據(jù)記錄中最基本的、不可分的有名數(shù)據(jù)單位。例 1 : class Aint c123;int i;；class BA a;B b ;b.a是數(shù)據(jù)項(xiàng)，B是數(shù)據(jù)元素例2: 本書的數(shù)目信息為一個(gè)數(shù)據(jù)元素，而數(shù)目信息中每一項(xiàng)（如書名、作者名等）為一 個(gè)數(shù)據(jù)項(xiàng)4. 從邏輯結(jié)構(gòu)來(lái)看，數(shù)據(jù)結(jié)構(gòu)有哪四種基本結(jié)構(gòu)，各自的特點(diǎn)是什么？1、集合（數(shù)據(jù)元素之間同屬于一

3、個(gè)集合，再無(wú)其他關(guān)系）2、線性結(jié)構(gòu)（數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系）3、樹(shù)形結(jié)構(gòu)（數(shù)據(jù)元素之間一對(duì)多的關(guān)系）4、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)（數(shù)據(jù)元素之間多對(duì)多的關(guān)系）5. 從物理結(jié)構(gòu)來(lái)看，數(shù)據(jù)結(jié)構(gòu)有哪兩種基本結(jié)構(gòu)，各自的特點(diǎn)是什么？1、順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：借助元素在存儲(chǔ)器中的相應(yīng)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特定：借助元素在存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。6. 算法的5個(gè)特征，4個(gè)評(píng)價(jià)標(biāo)準(zhǔn)是什么？ 特征:有窮性、確定性、可行性、輸入、輸出。評(píng)價(jià)標(biāo)準(zhǔn)：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。7. 描述時(shí)間復(fù)雜度。(1)x=0; y=0; z=0;for (i=1; i<

4、;=n; i+) x+;for( j=1; j<=n; j+) y+;for( k=0; kv=(2*n); k+ )z+;程序片段中語(yǔ)句x=0、x+、y+、z+的時(shí)間復(fù)雜度和整段程序的時(shí)間復(fù)雜度。0(1)0(n)0(nA2)0(nA3)0(nA3)第二章線性表1. 描述線性結(jié)構(gòu)的特點(diǎn)。2. 判斷對(duì)錯(cuò)，并解釋說(shuō)明。(1) 線性表中的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素一定具有相同 特性。(2) 線性表采用順序存儲(chǔ)表示時(shí)，必須占用一片連續(xù)的存儲(chǔ)單元。(3) 線性表采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，不能占用一片連續(xù)的存儲(chǔ)單元。3. 順序表的第一個(gè)元素的存儲(chǔ)地址是101，每個(gè)元素的長(zhǎng)度為3,計(jì)算出

5、第6個(gè)元 素的存儲(chǔ)地址是多少？LOC( a6) =LOC(a1)+5*L=101+5*3=1164. 長(zhǎng)度為n的順序表中，在第i個(gè)元素前插入一個(gè)新元素時(shí)，需要移動(dòng)多少個(gè)元素？ 插入算法的平均移動(dòng)次數(shù)是多少，時(shí)間復(fù)雜度是什么？參看書P2425,需要移動(dòng)n-i+1個(gè)元素，平均移動(dòng)次數(shù)為n/2，時(shí)間復(fù)雜度是O(n)5. 長(zhǎng)度為n的順序表中，將第i個(gè)元素刪除時(shí)，需要移動(dòng)多少個(gè)元素？刪除算法的 平均移動(dòng)次數(shù)是多少，時(shí)間復(fù)雜度是什么？參看書P2425,需要移動(dòng)n-i個(gè)元素，平均移動(dòng)次數(shù)為(n-1)/2，時(shí)間復(fù)雜度是O(n)6. 線性鏈表的存儲(chǔ)特點(diǎn)是？單鏈表中的結(jié)點(diǎn)由哪兩部分構(gòu)成，畫圖說(shuō)明。7. 在一個(gè)單鏈

6、表中，q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn)，寫出執(zhí)行的兩條語(yǔ)句(提示：先鏈接、后斷開(kāi))。s->next=p; q->next=s; 或者 s->next=q->next; q->next=s;&在單鏈表中，w所指結(jié)點(diǎn)是s所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)刪除s結(jié)點(diǎn)，寫出執(zhí)行的兩條語(yǔ)句。w->next=s->next;free(s)9. 畫圖說(shuō)明單循環(huán)鏈表為空的狀態(tài)，并寫出循環(huán)鏈表判斷是否為空的語(yǔ)句。參看書P35圖2.12( b) 判空語(yǔ)句 H->next=H10. 雙向鏈表中，要在指針 q指向的結(jié)點(diǎn)后插入新結(jié)點(diǎn)t，

7、寫出執(zhí)行的四條語(yǔ)句。t->prior=q ; t->next=q->next ; q->next=t ; t->next->prior=s11. 雙向鏈表中，要?jiǎng)h除指針 q的后繼結(jié)點(diǎn)，寫出執(zhí)行的兩條語(yǔ)句。T=q->next ; q->next=t->next ; free(t);或者 t=q->next;q->next-q->next->next;free（t）第三章棧和隊(duì)列1. 判斷對(duì)錯(cuò)（1）棧和隊(duì)列是操作受限的線性表。（2）棧的插入操作只需要在表尾端進(jìn)行，隊(duì)列的插入操作只需要在表頭進(jìn)行。（3） 棧的操作只和棧頂指

8、針 TOP相關(guān)，隊(duì)列的操作只和隊(duì)頭指針FRONT相關(guān)。2. 棧的特點(diǎn)是？隊(duì)列的特點(diǎn)是？（先進(jìn)先出、先進(jìn)后出中選擇） 棧的特點(diǎn)是先進(jìn)后出（FILO）隊(duì)列的特點(diǎn)是先進(jìn)先出（FIFO）3. 用文字描述算法。（參照我寫的（1）的算法描述完成）（1）順序存儲(chǔ)的棧插入操作 算法描述：（2）順序棧的刪除操作 算法描述：第一步，判斷棧是否為空，如果?？眨荒苓M(jìn)行刪除操作；第二步，棧不空的時(shí)候，棧頂指針TOP減1，向下移動(dòng)一位；第三步，將要?jiǎng)h除的棧頂元素用新變量保存；（3）鏈?zhǔn)酱鎯?chǔ)的隊(duì)列的插入操作 算法描述：第一步，禾U用指針創(chuàng)建新結(jié)點(diǎn)，新節(jié)點(diǎn)的數(shù)據(jù)域值為要入隊(duì)列的元素，新結(jié)點(diǎn)的指 針域復(fù)制為NULL ;第二步

9、，將鏈隊(duì)列的尾節(jié)點(diǎn)鏈接上新結(jié)點(diǎn)；第三步，修改鏈隊(duì)列的尾指針的指向，讓它指向新結(jié)點(diǎn)；（4）鏈棧的刪除操作 算法描述：第一步，利用指針創(chuàng)建新結(jié)點(diǎn)，新節(jié)點(diǎn)的數(shù)據(jù)域值為要入棧的元素，新結(jié)點(diǎn)的指針 域復(fù)制為NULL ；第二步，新結(jié)點(diǎn)的指針域指向鏈棧的頭結(jié)點(diǎn)；第三步，修改鏈棧的頭指針TOP的指向，讓它指向新結(jié)點(diǎn)；4. 假設(shè)棧為S,寫出判斷語(yǔ)句typedef struct sqstackint datamax;int top; sqstack ; sqstack *s；（1） 順序棧為空的條件判斷語(yǔ)句s->top= =0（2） 順序棧為滿的條件判斷語(yǔ)句s->top = =max5. 假設(shè)隊(duì)列為Q

10、,寫出判斷語(yǔ)句typedef struct SqQueueint dataMAX;int front;int rear;/*定義隊(duì)頭指針 Front和隊(duì)尾指針 Rear*/;SqQueue *Q(1) 循環(huán)隊(duì)列為空的條件判斷語(yǔ)句Q->rear= =Q->front(2) 循環(huán)隊(duì)列為滿的條件判斷語(yǔ)句(Q->rear+1)%MAX= =Q->front6. 總結(jié)說(shuō)明，線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的區(qū)別？參看書P27第一段第六章樹(shù)和二叉樹(shù)1. 一棵二叉樹(shù)的廣義表表示為a(b(c,d),e(f(,g)，它含有雙親結(jié)點(diǎn)(4)個(gè)，單分支結(jié)點(diǎn)(2)個(gè)，葉子結(jié)點(diǎn)(3)個(gè)。二叉樹(shù)根為a；

11、a有左孩子b,右孩子e； b有左孩子c,右孩子d； e只有左孩子f， f只有右孩子g2. 判斷對(duì)錯(cuò)(1) 在樹(shù)中，如果從結(jié)點(diǎn) K出發(fā)，存在兩條分別到達(dá) K'，K''的長(zhǎng)度相等的路徑，則結(jié)點(diǎn) K'，K''互為兄弟。，還可能是堂兄結(jié)點(diǎn)(2) 完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則必是葉結(jié)點(diǎn)。，由完全二叉樹(shù)的性質(zhì)決定(3) 一棵完全二叉樹(shù)按層次遍歷的序列為ABCDEFGH I,則在 后序遍歷中結(jié)點(diǎn)E的直接后繼是F。由于是完全二叉樹(shù)，所以樹(shù)中第一層是A，第二層從左向右是 B和C,第三層是D、E、F、G,第四層從左向右是 H和I。畫出二叉樹(shù)，進(jìn)行后序遍歷，后序遍

12、歷序列 為 HIDEBFGCA。(4) 二叉樹(shù)的后序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子樹(shù)結(jié)點(diǎn)的后 面。后序遍歷算法決定的，左、右、根(5) 由二叉樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉 樹(shù)。不唯一，因?yàn)橹挥性谥行虮闅v中才能劃分左右子樹(shù)(6) 樹(shù)存儲(chǔ)時(shí)采用雙親表示法時(shí)，求某個(gè)結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè) 結(jié)構(gòu)。(7) 一棵有n (n 1)個(gè)結(jié)點(diǎn)的d叉樹(shù)，若用多重鏈表表示，樹(shù)中每 個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在樹(shù)的nd個(gè)鏈域中，有n ( d-1) +1個(gè)是空鏈域，只 有n-1個(gè)是非空鏈域。根據(jù)樹(shù)的特性：一對(duì)多，每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn)，除了根結(jié)點(diǎn)外。因此，n個(gè)結(jié)點(diǎn)的樹(shù)中有n-1個(gè)結(jié)點(diǎn)都有且僅

13、有一個(gè)雙親，這個(gè)關(guān)系表示在鏈?zhǔn)酱鎯?chǔ)里就一定 會(huì)占用它雙親的一個(gè)指針域，所以樹(shù)中一定有n-1個(gè)非空指針域，多叉樹(shù)也適用。(8) 在一棵二叉樹(shù)的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加2。解：二叉鏈表中有n個(gè)結(jié)點(diǎn)時(shí)，一定存在2n個(gè)指針域，n+1個(gè)空鏈域，則非空鏈域?yàn)閚-1個(gè)，所以，空鏈域=非空鏈域+2（9）樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的中序遍歷。，參看書P138筆記（10）樹(shù)利用孩子兄弟表示法轉(zhuǎn)換后的二叉樹(shù)中根結(jié)點(diǎn)一定不存在右子樹(shù)。，參看書P137頁(yè)最后一句話3. 二叉樹(shù)根結(jié)點(diǎn)的層次為1,所有含有15個(gè)結(jié)點(diǎn)的二叉樹(shù)中，最小高度是（4 ）°要想得出最小高度，必須是完全二叉樹(shù)才能保

14、證，因此這個(gè)題目考核的是有15個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度是？參看二叉樹(shù)性質(zhì)4,即可得出4. 設(shè)一棵二叉樹(shù)結(jié)點(diǎn)的先根序列為 ABDECFGH ,中根序列為DEBAFCHG ,則二叉樹(shù)中葉子結(jié)點(diǎn)是（E F H ）°參看書P154例題5. 樹(shù)的存儲(chǔ)結(jié)構(gòu)有幾種？分別是？二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有幾種，分別是？樹(shù)的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有兩：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)（又叫二叉鏈表的表示法）在一棵二叉樹(shù)的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2）°6. 若二叉樹(shù)有7個(gè)度為2的結(jié)點(diǎn)，試問(wèn)有？個(gè)終端結(jié)點(diǎn)。由二叉樹(shù)的性質(zhì)3得出，n0=n2+1，所以度為1的

15、終端結(jié)點(diǎn)有7+1=8個(gè)7. 一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，最多有？個(gè)結(jié)點(diǎn)。首先，由二叉樹(shù)的性質(zhì) 3得出，度為2的結(jié)點(diǎn)個(gè)數(shù)為124-1=123個(gè)； 又根據(jù)二叉樹(shù)的定義可以得出這樣的結(jié)論：完全二叉樹(shù)的前n-1層8. 一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是？500解：設(shè)分支總數(shù)變量為 b,則n=b+1，得出分支數(shù)為1000°分支數(shù)是偶數(shù)，所以不 存在度為1的結(jié)點(diǎn)，只有度為2的結(jié)點(diǎn)和葉子結(jié)點(diǎn)。根據(jù)性質(zhì)3, n0=n2+1,所以1001 =n0+n2= 2*n0+1 ° n0=500°9. w=4,5,6,7,8，如何構(gòu)建哈夫曼樹(shù)？第9章查找1. 查找表

16、的概念？這是四種經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的哪一種？2. 靜態(tài)查找和動(dòng)態(tài)查找有什么聯(lián)系和區(qū)別？3. 查找表中的關(guān)鍵字是數(shù)據(jù)元素還是數(shù)據(jù)項(xiàng)，有什么特點(diǎn)？4. ASL表示什么？寫出計(jì)算的公式，并解釋公式中每個(gè)變量的含義。5. 描述順序查找的算法思想（用漢字描述，不是代碼）6. 描述折半查找的算法思想。7. 給定由以下元素組成的關(guān)鍵字序列（55, 46, 89, 13, 24, 67, 23, 15）,將他們存儲(chǔ)在數(shù)組的第1位至第8位，現(xiàn)在要查找關(guān)鍵字為15和100的元素。描述查找過(guò)程。&畫出包含8個(gè)元素的查找表對(duì)應(yīng)的折半判定樹(shù)。樹(shù)的深度為？9.根據(jù)給定的序列（21,54,43,76,87,65,32），生成一棵二叉排序樹(shù)，并分析該二叉排序 樹(shù)的平均查找長(zhǎng)度 ASL;同時(shí)根據(jù)該序列，生成一棵平衡二叉樹(shù)，并分析該平衡二叉樹(shù) 的平均查找長(zhǎng)度ASL °第10章排序1. 比較分析9種排序方法的時(shí)間復(fù)雜度和穩(wěn)定性。排序方法平均時(shí)間最壞情況輔助空間