數(shù)據(jù)結(jié)構(gòu)習(xí)題集基礎(chǔ)教資

數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章 序論思考題：1.1 簡述下列術(shù) 語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(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ù)。試寫出下列程序段中用記號“”標(biāo)注的語句的頻度：(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( i=0; i<n; i+)for( j=i; j<n; j+)for( k=j; k<n; k+)x+=2;1.4 試寫一算法，自大至小依次輸出順序讀入的三個整數(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,試編寫求k階斐波那契序列的第m項(xiàng)值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。第二章 線性表思考題：2.1 描述以下三個概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)。2.2 描述以下幾個概念：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、順序表、有序表。作業(yè)題：2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素x插到La的合適位置上，保持該表的有序性。2.4已知單鏈表La中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x插到La的合適位置上，保持該表的有序性：（1）La帶頭結(jié)點(diǎn)；（2）La不帶頭結(jié)點(diǎn)。2.5試寫一個算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)2.6試寫一個算法，對帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。2.7已知線性表L采用順序存儲結(jié)構(gòu)存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。2.8將2.7題中L的存儲結(jié)構(gòu)改為單鏈表，寫出相應(yīng)的實(shí)現(xiàn)算法。2.9 設(shè)有兩個非遞減有序的單鏈表A和B。請寫出算法，將A和B“就地”歸并成一個按元素值非遞增有序的單鏈表C。2.10 設(shè)有一個長度大于1的單向循環(huán)鏈表，表中既無頭結(jié)點(diǎn)，也無頭指針，s為指向表中某個結(jié)點(diǎn)的指針,如圖2-1所示。試編寫一個算法，刪除鏈表中指針s所指結(jié)點(diǎn)的直接前驅(qū)。s待刪結(jié)點(diǎn)圖2-12.11 已知線性表用帶頭結(jié)點(diǎn)的單鏈表表示，表中結(jié)點(diǎn)由三類字符組成：字母、數(shù)字和其他字符。試編寫算法，將該線性鏈表分割成三個循環(huán)單鏈表，每個循環(huán)單鏈表中均只含有一類字符。2.12 已知線性表用順序存儲結(jié)構(gòu)表示，表中數(shù)據(jù)元素為n個正整數(shù)。試寫一算法，分離該表中的奇數(shù)和偶數(shù)，使得所有奇數(shù)集中放在左側(cè)，偶數(shù)集中放在右側(cè)。要求：(1)不借助輔助數(shù)組;(2)時間復(fù)雜度為O(n)。2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時間復(fù)雜度為O(n)的算法，將L改造為L=(a1,a3,.,an,.,a4,a2)。第三章 棧和隊(duì)列思考題：3.1 簡述棧和線性表的差別。3.2 如果進(jìn)棧序列為A、B、C、D，寫出所有可能的出棧序列。3.3 簡述棧和隊(duì)列的相同點(diǎn)和差異。3.4 已知棧S中存放了8個數(shù)據(jù)元素，自棧底至棧頂依次為(1,2,3,4,5,6,7,8)。（1）寫出在執(zhí)行了函數(shù)調(diào)用algo1(S)后，S中的元素序列。（2）在（1）的基礎(chǔ)上，又執(zhí)行了函數(shù)調(diào)用algo2(S,5)，寫出此時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); while(!StackEmpty(T) Pop(T,d); Push(S,d); 3.5已知隊(duì)列Q中自隊(duì)頭至隊(duì)尾依次存放著(1,2,3,4,5,6,7,8)。寫出在執(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 試寫一個算法，識別依次讀入的一個以為結(jié)束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“13&31”則不是。3.7 假設(shè)一個算術(shù)表達(dá)式中可以包含三種符號：圓括號“(”和“)”、方括號“”和“”、花括號“”和“”，且這三種括號可按任意次序嵌套使用。編寫判別給定表達(dá)式中所含的括號是否正確配對的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。3.8 設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號組成（如:“(a*(b+c)-d)/e）”。試寫一個算法，將一個書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。3.9 試用類C寫一個算法，對逆波蘭式求值。3.10 假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)的算法。3.11 假設(shè)將循環(huán)隊(duì)列定義為：以rear和length分別指示隊(duì)尾元素和隊(duì)列長度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳遞回隊(duì)頭元素的值）。3.12 試寫一個算法：判別讀入的一個以為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文）。第五章 多維數(shù)組5.1 已知多維數(shù)組A2233按行優(yōu)先方式存儲。試按存儲位置的先后次序，列出所有數(shù)組元素Aijkl序列（為了簡化表達(dá)，可以只列出形如“i,j,k,l”的序列，如元素A0021可表示為“0,0,2,1” ）。5.2 假設(shè)有一個二維數(shù)組A0.50.7，每個元素占6個字節(jié)，首元素A00的地址為1000，求： (1)A的體積； (2)最后一個元素A57的地址； (3)按行主序方式存儲時，A24的地址； (4)按列主序方式存儲時，A24的地址；5.3 設(shè)有上三角矩陣Ann， 將其上三角的元素逐行存于數(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è)有一個準(zhǔn)對角矩陣按以下方式存于一維數(shù)組B4m中：0123456k4m-24m-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,2m寫出由一對下標(biāo)(i,j)求k的轉(zhuǎn)換公式。5.5 已知稀疏矩陣A45如下：(1)用三元組表作為存儲結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；(2)用十字鏈表作為存儲結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。5.6 設(shè)稀疏矩陣A和B均以三元組順序表作為存儲結(jié)構(gòu)。試寫出計(jì)算矩陣相加CAB的算法，其中，C是另設(shè)的、存放結(jié)果的三元組表（提示：可用類似于兩個有序順序表歸并的處理方法）。5.7 試編寫一個算法，實(shí)現(xiàn)以三元組的形式打印用十字鏈表表示的稀疏矩陣中所有非零元素及其下標(biāo)。5.8 試編寫一個算法，實(shí)現(xiàn)以矩形陣列的形式打印用十字鏈表表示的稀疏矩陣。第六章 樹和二叉樹6.1 試分別繪出具有3個結(jié)點(diǎn)的樹和3個結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。6.2 設(shè)結(jié)點(diǎn)X是二叉樹上一個度為1的結(jié)點(diǎn)，X有幾個子樹？6.3 描述滿足下列條件的二叉樹形態(tài)： (1) 先序遍歷序列與中序遍歷序列相同； (2) 后序遍歷序列與中序遍歷序列相同； (3) 先序遍歷序列與后序遍歷序列相同；6.4 一個深度為H的滿k叉樹有如下性質(zhì)：第H層上所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有k棵非空子樹。如果從1開始按自上而下、自左向右的次序?qū)θ拷Y(jié)點(diǎn)編號，問：(1) 各層的結(jié)點(diǎn)數(shù)目是多少？(2) 編號為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號是多少？(3) 編號為i的結(jié)點(diǎn)的第j個孩子(若存在)的編號是多少？(4) 編號為i的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號是多少？6.5 已知一棵度為k的樹中有n1個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，.，nk個度為k的結(jié)點(diǎn)，問該樹中有多少個葉子結(jié)點(diǎn)？6.6 已知在一棵含有n個結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。試求該樹含有的葉子結(jié)點(diǎn)的數(shù)目。6.7 設(shè)n和m為二叉樹中兩個結(jié)點(diǎn)，用“1”、“0”、和“”（分別表示肯定，否定和不一定）填寫下表：已知 問先序遍歷時n在m之前？中序遍歷時n在m之前？后序遍歷時n在m之前？n在m左方111n在m右方000n是m祖先10n是m子孫01（注：如果離n和m的最近的共同祖先X存在，且n位于X的左子樹中，m位于X的右子樹中，則稱“n在m的左方”或“m在n的右方”。）6.8已知一棵樹如圖6-1所示，畫出與該樹對應(yīng)的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。ABCDEFGHKIJ圖6-16.9 將如圖6-2所示的森林轉(zhuǎn)化為對應(yīng)的二叉樹。K圖6-2ACDEBFGHJILMNO6.10 畫出和下列二叉樹（如圖6-3所示）相應(yīng)的森林。圖6-3ABCCABCABADEBCFGHJKLI6.11已知某二叉樹的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請畫出該二叉樹。6.12 已知樹T的先根遍歷訪問序列為GFKDAIEBCHJ，后根遍歷訪問序列為DIAEKFCJHBG。請畫出樹T。6.13 已知森林F的先根遍歷訪問序列為ABCDEFGHIJKL，中根遍歷訪問序列為CBEFDGAJIKLH。請畫出這個森林F。6.14 假設(shè)某個電文由(a,b,c,d,e,f,g,h)8個字母組成，每個字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問題： (1) 畫出出huffman樹； (2) 寫出每個字母的huffman編碼； (3) 在對該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。6.15 寫出復(fù)制一棵二叉樹的算法。6.16 試編寫算法，實(shí)現(xiàn)將二叉樹所有結(jié)點(diǎn)的左右子樹互換。6.17 寫出按層次遍歷二叉樹的算法。6.18 寫出判斷給定二叉樹是否為完全二叉樹的算法。6.19 寫出判斷兩棵給定二叉樹是否相似的算法。(注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)6.20 利用棧的基本操作，寫出二叉樹先序遍歷的非遞歸算法。6.21 寫出統(tǒng)計(jì)樹中葉子結(jié)點(diǎn)個數(shù)的算法，樹用孩子兄弟鏈表表示。6.22 寫出計(jì)算樹的深度的算法，樹用孩子兄弟鏈表表示。6.23 寫出計(jì)算二叉樹第K層結(jié)點(diǎn)數(shù)的算法。6.24 寫出計(jì)算二叉樹深度的算法。圖7-1V5V4V2V3V1V6第七章 圖7.1 已知有向圖如圖7-1所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強(qiáng)連通分量7.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-27.3 無向帶權(quán)圖如圖7-3所示， (1)畫出它的鄰接矩陣，并按Prim算法求其最小生成樹。 (2)畫出它的鄰接表，并按Kruskal算法求其最小生成樹圖7-3ABCEHFDG435555974566237.4 有向圖如圖7-4所示，試寫出其所有可能的拓?fù)湫蛄?。圖7-4V1V5V2V3V6V47.5 試?yán)肈ijkstra算法求圖7-5中頂點(diǎn)A到其他各頂點(diǎn)之間的最短路徑。要求寫出執(zhí)行算法過程中，數(shù)組D、P和S各步的狀態(tài)。GABDCEF圖7-5151225684910437.6 試在鄰接矩陣存儲結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.7 試在鄰接表存儲結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVex(G,v)，InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。7.8 設(shè)具有n個頂點(diǎn)的有向圖用鄰接表存儲。試寫出計(jì)算所有頂點(diǎn)入度的算法，可將每個頂點(diǎn)的入度值分別存入一維數(shù)組int Indegreen中。7.9 假設(shè)有向圖以鄰接表作為存儲結(jié)構(gòu)。試基于圖的深度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點(diǎn)Vi至頂點(diǎn)Vj(i!=j)的路徑。7.10 假設(shè)有向圖以鄰接表作為存儲結(jié)構(gòu)。試基于圖的廣度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點(diǎn)Vi至頂點(diǎn)Vj(i!=j)的路徑。7.11 以鄰接表作為存儲結(jié)構(gòu)，實(shí)現(xiàn)求單源最短路徑的Dijkstra算法。第九章 查找9.1 若對大小均為n的有序順序表和無序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？ (1)查找不成功，即表中沒有關(guān)鍵字等于給的值K的記錄； (2)查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄； (3)查找成功，且表中有若干個關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。9.2 試分別寫出在對有序線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找，查值等于e、f和g的元素時，先后與哪些元素進(jìn)行了比較。9.3 畫出對長度為13的有序表進(jìn)行折半查找的判定樹，并分別求其等概率時查找成功和查找失敗的ASL。9.4 已知如下所示長度為12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec)表中，每個元素的查找概率分別為： (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)若對該表進(jìn)行順序查找，求查找成功的平均查找長度； (2)畫出從初態(tài)為空開始，依次插入結(jié)點(diǎn)，生成的二叉排序樹； (3)計(jì)算該二叉排序樹查找成功的平均查找長度； (4)將二叉排序樹中的結(jié)點(diǎn)Mar刪除，畫出經(jīng)過刪除處理后的二叉排序樹。9.5已知關(guān)鍵字序列10,25,33,19,06,49,37,76,60，哈希地址空間為010，哈希函數(shù)為H (Key)=Key % 11, 求：（1） 用開放定址線性探測法處理沖突，構(gòu)造哈希表HT1，分別計(jì)算在等概率情況下HT1查找成功和查找失敗的ASL；（2） 用開放定址二次探測法處理沖突，構(gòu)造哈希表HT2，計(jì)算在等概率情況下HT2查找成功的ASL；（3） 用拉鏈法解決沖突，構(gòu)造哈希表HT3，計(jì)算HT3在等概率情況查找成功的ASL。9.6 寫出折半查找的遞歸算法。9.7 寫出判別一棵二叉樹是否為二叉排序樹的算法，設(shè)二叉排序樹中不存在關(guān)鍵字值相同的結(jié)點(diǎn)。9.8 假設(shè)哈希表長為m， 哈希函數(shù)為H(x)，用鏈地址法解決沖突。編寫輸入一組關(guān)鍵字，建造哈希表的算法。第十章 內(nèi)部排序10.1 以關(guān)鍵字序列（5，1，6，0，9，2，8，3，7，4）為例，手工執(zhí)行下列排序算法，寫出每一趟排序結(jié)束時關(guān)鍵字序列狀態(tài)(1) 直接插入排序(2) 希爾排序（取增量為5，3，1）(3) 快速排序(4) 冒泡排序(5) 歸并排序(6) 堆排序10.2 10.1題中哪些排序方法是穩(wěn)定的，哪些是不穩(wěn)定的？并為每種不穩(wěn)定的排序方法舉一個不穩(wěn)定的實(shí)例。10.3 判別以下序列是否為堆（小頂堆或大頂堆），若不是，則吧它調(diào)整為堆(1) (96,86,48,73,35,39,42,57,66,21);(2) (12,70,33,65,24,56,48,92,86,33);10.4 編寫一個雙向起泡的排序算法，即相鄰兩遍向相反方向起泡。10.5 試以單鏈表為存儲結(jié)構(gòu)，實(shí)現(xiàn)簡單選擇排序算法。15教資