《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章 緒論思考題：1.1 簡(jiǎn)述下列術(shù) 語(yǔ)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型作業(yè)題：1.2 設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D=d1, d2, d3, d4 R=r1, r2r1= <d1, d2>, <d2, d3>, <d3, d4>, <d1, d4>, <d4, d2>, <d4, d1> r2= (d1, d2), (d1, d3), (d1, d4), (d2, d4), (d2, d3) 試?yán)L出其邏輯結(jié)構(gòu)示意圖。1.3 設(shè)n是正整數(shù)。試寫(xiě)出下列程序段中用記號(hào)“”標(biāo)

2、注的語(yǔ)句的頻度：(1)i=1; k=0;while(i<=n-1) k+=10*i;i+;(2)i=1; k=0;do k+=10*i;i+;while(i<=n-1)(3) i=1; k=0; do k+ = 10*i; i+;while(i=n);(4)i=1; j=0;while(i+jn) if(i<j) i+; else j+;(5)x=n; y=0; /n是不小于1的常數(shù)while(x>=(y+1)*(y+1)y+;(6)x=91; y=100;while ( y>0 ) if(x>100) x-=10; y-; else x+ ; (7)for

3、( i=0; i<n; i+)for( j=i; j<n; j+)for( k=j; k<n; k+)x+=2;1.4 試寫(xiě)一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值。1.5 已知k階斐波那契序列的定義為：f0=0, f1=0, fk-2=0, fk-1=1；fn= fn-1+ fn-2+ fn-k, n=k,k+1,試編寫(xiě)求k階斐波那契序列的第m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。第二章 線性表思考題：2.1 描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)。2.2 描述以下幾個(gè)概念：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、順序表、有序表。作業(yè)題：2

4、.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫(xiě)一個(gè)算法，將元素x插到La的合適位置上，保持該表的有序性。2.4已知單鏈表La中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫(xiě)出算法，將元素x插到La的合適位置上，保持該表的有序性：（1）La帶頭結(jié)點(diǎn)；（2）La不帶頭結(jié)點(diǎn)。2.5試寫(xiě)一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)2.6試寫(xiě)一個(gè)算法，對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。2.7已知線性表L采用順序存儲(chǔ)結(jié)構(gòu)存放。對(duì)兩種不同情況分別寫(xiě)出算法，刪除L中值相同的多余元素，使得L中沒(méi)有重復(fù)元素：(1)

5、L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。2.8將2.7題中L的存儲(chǔ)結(jié)構(gòu)改為單鏈表，寫(xiě)出相應(yīng)的實(shí)現(xiàn)算法。2.9 設(shè)有兩個(gè)非遞減有序的單鏈表A和B。請(qǐng)寫(xiě)出算法，將A和B“就地”歸并成一個(gè)按元素值非遞增有序的單鏈表C。2.10 設(shè)有一個(gè)長(zhǎng)度大于1的單向循環(huán)鏈表，表中既無(wú)頭結(jié)點(diǎn)，也無(wú)頭指針，s為指向表中某個(gè)結(jié)點(diǎn)的指針,如圖2-1所示。試編寫(xiě)一個(gè)算法，刪除鏈表中指針s所指結(jié)點(diǎn)的直接前驅(qū)。s待刪結(jié)點(diǎn)圖2-12.11 已知線性表用帶頭結(jié)點(diǎn)的單鏈表表示，表中結(jié)點(diǎn)由三類字符組成：字母、數(shù)字和其他字符。試編寫(xiě)算法，將該線性鏈表分割成三個(gè)循環(huán)單鏈表，每個(gè)循環(huán)單鏈表中均只含有一類字符。2.12 已知線

6、性表用順序存儲(chǔ)結(jié)構(gòu)表示，表中數(shù)據(jù)元素為n個(gè)正整數(shù)。試寫(xiě)一算法，分離該表中的奇數(shù)和偶數(shù)，使得所有奇數(shù)集中放在左側(cè)，偶數(shù)集中放在右側(cè)。要求：(1)不借助輔助數(shù)組;(2)時(shí)間復(fù)雜度為O(n)。2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫(xiě)一時(shí)間復(fù)雜度為O(n)的算法，將L改造為L(zhǎng)=(a1,a3,.,an,.,a4,a2)。第三章 棧和隊(duì)列思考題：3.1 簡(jiǎn)述棧和線性表的差別。3.2 如果進(jìn)棧序列為A、B、C、D，寫(xiě)出所有可能的出棧序列。3.3 簡(jiǎn)述棧和隊(duì)列的相同點(diǎn)和差異。3.4 已知棧S中存放了8個(gè)數(shù)據(jù)元素，自棧底至棧頂依次為(1,2,3,4,5,6,7,8

7、)。（1）寫(xiě)出在執(zhí)行了函數(shù)調(diào)用algo1(S)后，S中的元素序列。（2）在（1）的基礎(chǔ)上，又執(zhí)行了函數(shù)調(diào)用algo2(S,5)，寫(xiě)出此時(shí)S中的元素序列。void algo1(Stack &S) int a10, i, n=0; while(!StackEmpty(S) n+; Pop(S, an); for(i=1; i<=n; i+) Push(S, ai);void algo2(Stack &S, int e) Stack T; int d; InitStack(T); while(!EmptyStack(S) Pop(S,d); if(d!=e) Push(T,d)

8、; while(!StackEmpty(T) Pop(T,d); Push(S,d); 3.5已知隊(duì)列Q中自隊(duì)頭至隊(duì)尾依次存放著(1,2,3,4,5,6,7,8)。寫(xiě)出在執(zhí)行了函數(shù)調(diào)用algo3(Q)后，Q中的元素序列。void algo3(Queue &Q) Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue(Q,d); Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue(Q,d); 作業(yè)題：3.6 試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如“序列1&

9、amp;序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“13&31”則不是。3.7 假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào)：圓括號(hào)“(”和“)”、方括號(hào)“”和“”、花括號(hào)“”和“”，且這三種括號(hào)可按任意次序嵌套使用。編寫(xiě)判別給定表達(dá)式中所含的括號(hào)是否正確配對(duì)的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。3.8 設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號(hào)組成（如:“(a*(b+c)-d)/e）”。試寫(xiě)一個(gè)算法，將一個(gè)書(shū)寫(xiě)正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。3.9 試用類C寫(xiě)一個(gè)算法，對(duì)逆波

10、蘭式求值。3.10 假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫(xiě)相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)的算法。3.11 假設(shè)將循環(huán)隊(duì)列定義為：以rear和length分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳遞回隊(duì)頭元素的值）。3.12 試寫(xiě)一個(gè)算法：判別讀入的一個(gè)以為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文）。第五章 多維數(shù)組5.1 已知多維數(shù)組A2233按行優(yōu)先方式存儲(chǔ)。試按存儲(chǔ)位置的先后次序，列出所有數(shù)組元素Aij

11、kl序列（為了簡(jiǎn)化表達(dá)，可以只列出形如“i,j,k,l”的序列，如元素A0021可表示為“0,0,2,1” ）。5.2 假設(shè)有一個(gè)二維數(shù)組A0.50.7，每個(gè)元素占6個(gè)字節(jié)，首元素A00的地址為1000，求： (1)A的體積； (2)最后一個(gè)元素A57的地址； (3)按行主序方式存儲(chǔ)時(shí)，A24的地址； (4)按列主序方式存儲(chǔ)時(shí)，A24的地址；5.3 設(shè)有上三角矩陣An×n， 將其上三角的元素逐行存于數(shù)組B0.m-1中（m充分大），使得Bk=aij且kf1(i)+f2(j)+c。試推導(dǎo)出函數(shù)f1、f2和常數(shù)c（要求f1和f2中不含常數(shù)項(xiàng)）。5.4 設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣按以下方式存于一維數(shù)

12、組B4m中：0123456k4m-24m-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,2m寫(xiě)出由一對(duì)下標(biāo)(i,j)求k的轉(zhuǎn)換公式。5.5 已知稀疏矩陣A4×5如下：(1)用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；(2)用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。5.6 設(shè)稀疏矩陣A和B均以三元組順序表作為存儲(chǔ)結(jié)構(gòu)。試寫(xiě)出計(jì)算矩陣相加CAB的算法，其中，C是另設(shè)的、存放結(jié)果的三元組表（提示：可用類似于兩個(gè)有序順序表歸并的處理方法）。5.7 試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)以三元組的形式打印用十字鏈表表示的稀疏矩陣中所有非零元素及其下標(biāo)。5.8 試編寫(xiě)

13、一個(gè)算法，實(shí)現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣。第六章 樹(shù)和二叉樹(shù)6.1 試分別繪出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。6.2 設(shè)結(jié)點(diǎn)X是二叉樹(shù)上一個(gè)度為1的結(jié)點(diǎn)，X有幾個(gè)子樹(shù)？6.3 描述滿足下列條件的二叉樹(shù)形態(tài)： (1) 先序遍歷序列與中序遍歷序列相同； (2) 后序遍歷序列與中序遍歷序列相同； (3) 先序遍歷序列與后序遍歷序列相同；6.4 一個(gè)深度為H的滿k叉樹(shù)有如下性質(zhì)：第H層上所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)。如果從1開(kāi)始按自上而下、自左向右的次序?qū)θ拷Y(jié)點(diǎn)編號(hào)，問(wèn)：(1) 各層的結(jié)點(diǎn)數(shù)目是多少？(2) 編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存

14、在)的編號(hào)是多少？(3) 編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子(若存在)的編號(hào)是多少？(4) 編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6.5 已知一棵度為k的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，.，nk個(gè)度為k的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？6.6 已知在一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。試求該樹(shù)含有的葉子結(jié)點(diǎn)的數(shù)目。6.7 設(shè)n和m為二叉樹(shù)中兩個(gè)結(jié)點(diǎn)，用“1”、“0”、和“Æ”（分別表示肯定，否定和不一定）填寫(xiě)下表：已知 問(wèn)先序遍歷時(shí)n在m之前？中序遍歷時(shí)n在m之前？后序遍歷時(shí)n在m之前？n在m左方111n在m右方000n是m祖先1

15、Æ0n是m子孫0Æ1（注：如果離n和m的最近的共同祖先X存在，且n位于X的左子樹(shù)中，m位于X的右子樹(shù)中，則稱“n在m的左方”或“m在n的右方”。）6.8已知一棵樹(shù)如圖6-1所示，畫(huà)出與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出該樹(shù)的先根遍歷序列和后根遍歷序列。ABCDEFGHKIJ圖6-16.9 將如圖6-2所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。K圖6-2ACDEBFGHJILMNO6.10 畫(huà)出和下列二叉樹(shù)（如圖6-3所示）相應(yīng)的森林。圖6-3ABCCABCABADEBCFGHJKLI6.11已知某二叉樹(shù)的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請(qǐng)畫(huà)出該二叉樹(shù)。6.12

16、 已知樹(shù)T的先根遍歷訪問(wèn)序列為GFKDAIEBCHJ，后根遍歷訪問(wèn)序列為DIAEKFCJHBG。請(qǐng)畫(huà)出樹(shù)T。6.13 已知森林F的先根遍歷訪問(wèn)序列為ABCDEFGHIJKL，中根遍歷訪問(wèn)序列為CBEFDGAJIKLH。請(qǐng)畫(huà)出這個(gè)森林F。6.14 假設(shè)某個(gè)電文由(a,b,c,d,e,f,g,h)8個(gè)字母組成，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問(wèn)題： (1) 畫(huà)出出huffman樹(shù)； (2) 寫(xiě)出每個(gè)字母的huffman編碼； (3) 在對(duì)該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。6.15 寫(xiě)出復(fù)制一棵二叉樹(shù)的算法。6.16 試編寫(xiě)算法，

17、實(shí)現(xiàn)將二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)互換。6.17 寫(xiě)出按層次遍歷二叉樹(shù)的算法。6.18 寫(xiě)出判斷給定二叉樹(shù)是否為完全二叉樹(shù)的算法。6.19 寫(xiě)出判斷兩棵給定二叉樹(shù)是否相似的算法。(注：兩棵二叉樹(shù)B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹(shù)和B2的左、右子樹(shù)分別相似。)6.20 利用棧的基本操作，寫(xiě)出二叉樹(shù)先序遍歷的非遞歸算法。6.21 寫(xiě)出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。6.22 寫(xiě)出計(jì)算樹(shù)的深度的算法，樹(shù)用孩子兄弟鏈表表示。6.23 寫(xiě)出計(jì)算二叉樹(shù)第K層結(jié)點(diǎn)數(shù)的算法。6.24 寫(xiě)出計(jì)算二叉樹(shù)深度的算法。圖7-1V5V4V2V3V1V6第七章 圖7.1 已知有

18、向圖如圖7-1所示，請(qǐng)給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強(qiáng)連通分量7.2 已知圖G的鄰接矩陣如圖7-2所示。寫(xiě)出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫(huà)出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-27.3 無(wú)向帶權(quán)圖如圖7-3所示， (1)畫(huà)出它的鄰接矩陣，并按Prim算法求其最小生成樹(shù)。

19、 (2)畫(huà)出它的鄰接表，并按Kruskal算法求其最小生成樹(shù)圖7-3ABCEHFDG435555974566237.4 有向圖如圖7-4所示，試寫(xiě)出其所有可能的拓?fù)湫蛄小D7-4V1V5V2V3V6V47.5 試?yán)肈ijkstra算法求圖7-5中頂點(diǎn)A到其他各頂點(diǎn)之間的最短路徑。要求寫(xiě)出執(zhí)行算法過(guò)程中，數(shù)組D、P和S各步的狀態(tài)。GABDCEF圖7-5151225684910437.6 試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.7 試在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本

20、操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.8 設(shè)具有n個(gè)頂點(diǎn)的有向圖用鄰接表存儲(chǔ)。試寫(xiě)出計(jì)算所有頂點(diǎn)入度的算法，可將每個(gè)頂點(diǎn)的入度值分別存入一維數(shù)組int Indegreen中。7.9 假設(shè)有向圖以鄰接表作為存儲(chǔ)結(jié)構(gòu)。試基于圖的深度優(yōu)先搜索策略寫(xiě)一算法，判斷有向圖中是否存在由頂點(diǎn)Vi至頂點(diǎn)Vj(i!=j)的路徑。7.10 假設(shè)有向圖以鄰接表作為存儲(chǔ)結(jié)構(gòu)。試基于圖的廣度優(yōu)先搜索策略寫(xiě)一算法，判斷有向圖中是否存在由頂點(diǎn)Vi至頂點(diǎn)Vj(i!=j)的路徑。7.11 以鄰接表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)求單源最短路徑

21、的Dijkstra算法。第九章 查找9.1 若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？ (1)查找不成功，即表中沒(méi)有關(guān)鍵字等于給的值K的記錄； (2)查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值K的記錄； (3)查找成功，且表中有若干個(gè)關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。9.2 試分別寫(xiě)出在對(duì)有序線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找，查值等于e、f和g的元素時(shí)，先后與哪些元素進(jìn)行了比較。9.3 畫(huà)出對(duì)長(zhǎng)度為13的有序表進(jìn)行折半查找的判定樹(shù)，并分別求其等概率時(shí)查找成功和查找失敗的ASL。9.4 已知如下所示長(zhǎng)度為12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec)表中，每個(gè)元素的查找概率分別為： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (1)若對(duì)該表進(jìn)行順序查找，求查找成功的平均查找長(zhǎng)度； (2)畫(huà)出從初態(tài)為空開(kāi)始，依次插入結(jié)點(diǎn)，生成的二叉排序樹(shù)； (3)計(jì)算該二叉排序樹(shù)查找成功的平均查找長(zhǎng)度