數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)答案2011要點(diǎn)

1、1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)答案 選擇填空 下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？( )A) 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 V B)線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C) 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D) 線性表采用鏈接存儲，便于插入和刪除操作。若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用 ( )存儲方式最節(jié)省時(shí)間。VA )順序表B)雙鏈表 C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D)單循環(huán)鏈表鏈表不具有的特點(diǎn)是( )。 A )插入、刪除不需要移動元素C)不必事先估計(jì)

2、存儲空間VB)可隨機(jī)訪問任一元素D)所需空間與線性長度成正比5若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為( ) (1=inext=s;s-next=p-next;VB) s-next=p-next;p-next=s;C) p-next=s;p-next=s-next;D) p-next=s-next;p-next=s;設(shè)指針變量 p 指向單鏈表結(jié)點(diǎn)VA ) p-next=p-next-nextC) p=p-next-nextA，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為(B ) p=p-nextD) p-next=p)。() 又稱為 FIFO 表； () 又

3、稱為 FILO 表。VA )隊(duì)列B)散列表VC)棧對于棧操作數(shù)據(jù)的原則是( )。A) 先進(jìn)先出 VB) 后進(jìn)先出C) 后進(jìn)后出D )哈希表D ) 不分順序用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時(shí)， 在進(jìn)行刪除操作時(shí) ()。VA )僅修改隊(duì)頭指針其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，B ) 僅修改隊(duì)尾指針C) 隊(duì)頭、隊(duì)尾指針都要修改D) 隊(duì)頭、隊(duì)尾指針都可能要修改假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為( )。VA )(rear-front+m)%mB )rear-front+1C) (front-rear+m)%mD)(rear-fron

4、t)%m 棧和隊(duì)列的共同點(diǎn)是( )。A ) 都是先進(jìn)先出B ) 都是先進(jìn)后出VC) 只允許在端點(diǎn)處插入和刪除元素D) 沒有共同點(diǎn) 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 e1, e2, e3, e4,e5和e6依次通過棧S, 個(gè)元素出棧 后即進(jìn)隊(duì)列Q,若6個(gè)兀素出隊(duì)的序列是 e2, e4, e3,e6,e5,e1則棧S的容量至少應(yīng)該是()。A) 6B) 4VC) 3 D) 2設(shè)有一個(gè)10階的對稱矩陣A,采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ琣11為第一元素，其存儲16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.地址為 1，每個(gè)元素占一個(gè)地址空間，則a85

5、 的地址為( )。A) 12V B)33C) 18D) 40由 3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？ ()A) 2B) 3C) 4VD) 5二叉樹中第i(i 1)層上的結(jié)點(diǎn)數(shù)最多有()個(gè)。A) 2iB)2iVC) 2i-1D) 2i-1在有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為 ()。A)不確定B) 2n C) 2n+1V D) 2n-1一棵二叉樹高度為A) 2h若一棵二叉樹具有A) 9h,所有結(jié)點(diǎn)的度或?yàn)?0、或?yàn)?,則這棵二叉樹最少有()結(jié)點(diǎn)。)。VB) 2h-1C) 2h+1D) h+110個(gè)度為 2的結(jié)點(diǎn), 5個(gè)度為 1 的結(jié)點(diǎn),則度為 0的結(jié)點(diǎn)個(gè)數(shù)是 (V B) 11C) 1

6、5D)不確定樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的 ()。A ) 先序序列VB)中序序列C) 后序序列D )層序序列在二叉樹結(jié)點(diǎn)的先序序列,中序序列和后序序列中,所有葉子結(jié)點(diǎn)的先后順序()。A)都不相同V B )完全相同中序和后序相同,而與先序不同網(wǎng)D ) AOE 網(wǎng)( 2 )倍,在一個(gè)有向圖中,所有頂點(diǎn)的D) 4C)先序和中序相同，而與后序不同D)下列哪一種圖的鄰接矩陣是對稱矩陣？ ()A)有向圖VB)無向圖C) AOV在一個(gè)無向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù) 入度之和等于所有頂點(diǎn)出度之和的 ( 1 )倍。A) 1/2VB) 2VC) 1一個(gè)有 n 個(gè)頂點(diǎn)的無向圖最多有 ()條邊。由

7、 n 個(gè)頂點(diǎn)組成的有向圖,最多可以有 ( )條邊。A) n*n B) 2nVC) n(n-1)VD) n(n-1)/2下列說法不正確的是 ()。A )圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次B )遍歷的基本算法有兩種：深度遍歷和廣度遍歷V C)圖的深度遍歷不適用于有向圖D )圖的深度遍歷是一個(gè)遞歸過程 下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)(回路 ) ()。A )深度優(yōu)先遍歷 V B ) 拓?fù)渑判駽) 求最短路徑 D ) 求關(guān)鍵路徑下列算法中, ()算法用來求圖中每對頂點(diǎn)之間的最短路徑。A ) DijkstraVB ) Floyed C) Prim D ) Kruskal關(guān)鍵路徑是事

8、件結(jié)點(diǎn)網(wǎng)絡(luò)中 ()。VA )從源點(diǎn)到匯點(diǎn)的最長路徑B)從源點(diǎn)到匯點(diǎn)的最短路徑C)最長回路D )最短回路若查找每個(gè)記錄的概率均等, 則在具有 n 個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記 錄,其平均查找長度 ASL 為()。A) (n-1)/2B)n/2VC)(n+1)/2D) n下面關(guān)于二分查找的敘述正確的是() 。A ) 表必須有序,表可以順序方式存儲,也可以鏈表方式存儲B) 表必須有序,而且只能從小到大排列C 表必須有序且表中數(shù)據(jù)必須是整型,實(shí)型或字符型VD ) 表必須有序,且表只能以順序方式存儲32. 折半查找的時(shí)間復(fù)雜性為（）。A） O（n ）B） 0（n）C） 0（nlogn）

9、V D） O（log n）33. 當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為（）。A）數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序（或最?。┑臄?shù)據(jù)V B ）數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大 組成索引塊C） 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引塊D）數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同34. 下面關(guān)于哈希（Hash,雜湊）查找的說法正確的是（）。A）哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B ）除留余數(shù)法是所有哈希函數(shù)中最好的V C）不存在特別好與壞的哈希函數(shù)，要視情況而定35.36.37.38.39.D）若需在哈希表中刪去一個(gè)元素

10、，不管用何種方法解決沖突都只要簡單的將該元素刪去即可 .下面給出的四種排序法中（A）插入B）冒泡.穩(wěn)定的排序方法是（）A ）直接插入排序和快速排序C）簡單選擇排序和四路歸并排序 .有一組數(shù)據(jù)（15, 9, 7, 8, 20,為（）（按遞增序）VA）下面的B, C, D都不對。C） 20, 15, 8, .設(shè)有一個(gè)文件有查找法查索引表，A） 8） 4快速排序在最壞情況下的時(shí)間復(fù)雜性為2A） O（nlog 2n）VB） O（n ）、填空）排序法是不穩(wěn)定性排序法。C）二路歸并V D）堆-1 ,V B）折半插入排序和起泡排序D ）樹形選擇排序和shell排序乙4）用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)

11、的排序B) 9, 7,D) 9, 4,9, 7,-1, 4, 7200個(gè)記錄，按分塊查找法查找記錄, 用順序查找法查塊內(nèi)記錄，B） 10） 58, 4, -1 , 7, 15, 207, 8, 7,如分成則平均查找長度為( C)C) 13)O(n)-1 , 15, 2010塊，每塊20個(gè)記錄，用二分（）V D） 16D) O(nlogn)1. 一個(gè)算法的效率可分為時(shí)間 效率和 空間 效率。2. 線性表L= （a1,a2,n用數(shù)組表示，假定插入、刪除表中任一元素的概率相同，則插入、刪除一個(gè)元素平均需要移動元素的個(gè)數(shù)是n/2和 （n-1）/23. 對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn) *p后

12、插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0（1），在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0（n）4. 順序存儲結(jié)構(gòu)是通過元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”表示元素之間的邏輯關(guān)系的，鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針 表示元素之間的邏輯關(guān)系的。5. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是： p-next=head6. 當(dāng)兩個(gè)棧共享一存儲區(qū)時(shí)，棧利用一維數(shù)組stack（1,n）表示，兩棧頂指針為 top1與top2，則當(dāng)棧1空時(shí)，top1為 1 ，棧2空時(shí)，top2為 n ，棧滿時(shí)為 top1+top2=n 7. 順序棧S用data1） n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是*S）top+=x 8.

13、 已知鏈隊(duì)列Q的頭尾指針分別是f和r ,則將值x入隊(duì)的操作序列是 p-data=e：p-next=NULL:Q ） r-next=p：Q ） r=p： 9. 稀疏矩陣的存儲策略是只存儲非零兀素。10.稀疏矩陣的存儲方法主要有兩個(gè)：一個(gè)是三元組，另一個(gè)是十字鏈表示法11. 二叉樹由 _， 左子樹、 右子樹三個(gè)基本單元組成。12. 一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有 ni=0個(gè)度為1的結(jié)點(diǎn)、有(n-1)/2, (ni+2n2)個(gè)分支(非終端)結(jié)點(diǎn)和(n=ng+ni+n2, ng= n?+1), (n+1)/2 個(gè)葉子，該滿二叉樹的深度為Iog2(n+1)。13. 設(shè)F是由T1,T2,T3三棵樹組成的森林，

14、與F對應(yīng)的二叉樹為 B，已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1，n2和n3則二叉樹B的左子樹中有n1-1個(gè)結(jié)點(diǎn)，右子樹中有n2+n3 個(gè)結(jié)點(diǎn)。14. 線索二叉樹的左線索指向其前驅(qū) 右線索指向其 后繼。15. 設(shè)一棵Huffman樹有6個(gè)葉結(jié)點(diǎn)，權(quán)值分別為3、4、7、14、15、20,則根節(jié)點(diǎn)的權(quán)值是63。當(dāng) 初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序算法的時(shí)間復(fù)雜性為0(n2)。16. 在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為n+1。17. 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為2的結(jié)點(diǎn)，有 1個(gè)度為1的結(jié)點(diǎn)。18. 若用n表示圖中頂點(diǎn)數(shù)目，則

15、有n*(n-1)/2條邊的無向圖成為完全圖。n19. 設(shè)無向圖 G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn) Vi的度為di(1=i，則e=1/2送di。i=120. 在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要n*(n-1) 條弧。21. 在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對于無向圖來說等于該頂點(diǎn)的度；對于有向圖來說等于該頂點(diǎn)的出度。22. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為n 次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為n+1。23. 在順序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查

16、找關(guān)鍵碼值20,需做的關(guān)鍵碼比較次數(shù)為4。24. 對于長度為255的表，采用分塊查找，每塊的最佳長度為16。25. 已知二叉排序樹的左右子樹均不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)值，右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。26. 動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有插入 和 刪除 運(yùn)算，而后者不包含這兩種運(yùn)算。27. 為了能有效地應(yīng)用 HASH查找技術(shù)，必須解決的兩個(gè)問題是設(shè)計(jì)一個(gè)好的哈希函數(shù)和選擇一個(gè)處理沖突的方法。比較 和記錄28. 若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的 的 移動 。29. 屬于不穩(wěn)定排序的有希爾、快速、選擇、堆排序。30

17、. 快速排序算法的時(shí)間復(fù)雜度為O(n2)。三、應(yīng)用題、1.試畫出下列稀疏矩陣的三元組表示。jv00180、1318300021300024000034240066o J5366稀疏矩陣+ a *b c / d eNULL3. 寫出下列二叉樹的前序，中序，后序遍歷序列及對應(yīng)的森林。解答：前序:中序：a + b * c后序：a b c * + d e / -4.試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。126.設(shè)一棵樹 T 中邊的集合為(A , B), (A, C), (A , D), (B , E), (C, F), (C, G)，要求用孩7. 已 知 有 向 圖G=(V,E)其

18、 中V=V1,V2,V3,V4,V5,V6,V7E=vV1,V2,vV1,V3,vV2,V5,vV3,V5,vV3,V6,vV4,V6,vV5,V7,vV6,V7,G 的拓?fù)湫蛄惺?)。8. 有 7 個(gè)頂點(diǎn)(v1,v2,v3,v4,v5,v6,v7)的有向圖的鄰接矩陣如右圖。請回答相關(guān)問題:(1)畫出該有向圖。解答:3v1v4215v22v3v5383v69v75OO253OOOOOOOOOO2OOOO8OOOOOOOO135OOOOOOOOOO5OOOOOOOOOOOOOO39OOOOOOOOOOOO5OOOOOOOOOOOOOO(2) 寫出從v1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。深度優(yōu)

19、先遍歷： V1 V2 V6 V7 V3 V4 V5 廣度優(yōu)先遍歷： V1 V2 V3 V4V6 V5 V79.已知如圖所示的有向圖，請給出該圖的(1) 每個(gè)頂點(diǎn)的入/出度;(2) 鄰接矩陣；(3) 鄰接表；頂點(diǎn)123456入度321122出度022313OOOOOOOOOOOOOO11OOOO1OOOO11OOOO1111鄰接矩陣01A12-0-3A23-1-5A34-2-5-6A45-0A56-0-1-4A鄰接表01-12-2 3-3 4-4 51 -42 -53 A1A3-556-2-3逆鄰接表10.設(shè)無向圖G (所下圖所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列，找出下面網(wǎng)絡(luò)的最小

20、生成樹。解答：深度優(yōu)先：A B D F C E G廣度優(yōu)先： A B D C E F G(4) 逆鄰接表。11.分別說明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。 解答：Huffman算法：最優(yōu)二叉樹，樹的帶權(quán)路徑最短。Dijkstra算法：求單源最短路徑Prim算法：求最小生成樹Kruskal算法：求最小生成樹12.已知圖G如圖所示。（1）畫出圖G的鄰接表；（2）畫出從頂點(diǎn)1出發(fā)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；（3）寫出圖G的拓?fù)渑判蛄?；解答：?）1123A24A345A45A556A66A7A13. 已知AOE網(wǎng)如下，試求其關(guān)鍵路徑。要求寫出計(jì)算

21、過程。a2=3解答:123456ve0438710vl044891014. 設(shè)一組記錄的關(guān)鍵字為4，5，7，2，1，3, 6，請回答相關(guān)問題：（1）按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹， 并求出在等概率情況下查找成功的平均查找長度。（2） 按表中元素的順序進(jìn)行插入生成一棵AVL樹，畫出該樹。并求出在等概率情況下查找成功 的平均查找長度。進(jìn)行散列存設(shè) Hash15. 假定一個(gè)線性表為 L= (18, 75, 60, 43, 54, 90, 46, 31, 58, 73, 15, 34) 儲，采用的Hash函數(shù)為H( K) =K mod 13 ,當(dāng)發(fā)生沖突時(shí)

22、用線性探測法處理沖突, 表的表長為13,試構(gòu)造Hash表，并求出平均查找長度。解答：0123456789101112345415431831466058757390*2+4212=22/1211211414116. 用快速排序方法對下列整數(shù)序列進(jìn)行排序，寫出中間及最后結(jié)果。89,27,52,90,15,28,100,72解答：一趟二趟17解答:三趟：15 ,27,52, 287289100, 90四趟：1527 ,52,287289100, 90五趟：152728, 527289100, 90六趟：15272852728990, 100.序列40 ,38, 60,95, 76,10,25, 5

23、0, 99是堆嗎？若不是，創(chuàng)建一個(gè)堆。100, 9089 72,27,52, 28,15, 89,100, 9072 15,27,52, 28, 7289四、算法設(shè)計(jì)題1. 已知 L 為帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一個(gè)算法計(jì)算數(shù)據(jù)域?yàn)?x 的結(jié)點(diǎn)個(gè)數(shù)。int count(LinkList La,ElemType x)/計(jì)數(shù) x 出現(xiàn)的次數(shù)LinkList p=La-next; /p 為工作指針int n=0;while(p)if(p-data =x) n+;p=p-next ;return n;2. 設(shè) L 為有序順序表，試編寫一個(gè)算法刪除 L 中的重復(fù)元素。要求不要另開辟數(shù)據(jù)存儲空間 例如： L=(1，1， 2，4，4，9，9，9)，執(zhí)行算法后 L=(1，2，4，9) int delduplicate(int a,int n)int i,j