13994數據結構習題及參考答案(編輯修改稿)

　

【文章內容簡介】 en 。 i0 amp。amp。 (*L).elem[ i1 ] x 。 i) (*L).elem[ i ]=(*L).elem[ i1 ] 。 // 比較并移動元素 (*L).elem[ i ] =x。 (*L).len++。return(1)。}習題3一、單項選擇題1. 空串與空格字符組成的串的區別在于（ ）。 2. 一個子串在包含它的主串中的位置是指（ ）。3. 下面的說法中，只有（ ）是正確的。，則T一定是S的一個子串4. 兩個字符串相等的條件是（ ）。 ，并且兩串包含的字符相同，并且對應位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個字符開始的連續k個字符組成的子串的操作，則對于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。 7. 若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing”C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”8. 在長度為n的字符串S的第i個位置插入另外一個字符串，i的合法值應該是（ ）。＞0 B. i≤n ≤i≤n ≤i≤n+19. 字符串采用結點大小為1的鏈表作為其存儲結構，是指（ ）。 二、填空題1. 計算機軟件系統中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。2. 兩個字符串相等的充要條件是_____________________和___________________。3. 設字符串S1= “ABCDEF”，S2= “PQRS”，則運算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。4. 串是指___________________。5. 空串是指___________________，空格串是指___________________。三、算法設計題1. 設有一個長度為s的字符串，其字符順序存放在一個一維數組的第1至第s個單元中（每個單元存放一個字符）。現要求從此串的第m個字符以后刪除長度為t的子串，ms，t(sm)，并將刪除后的結果復制在該數組的第s單元以后的單元中，試設計此刪除算法。2. 設s和t是表示成單鏈表的兩個串，試編寫一個找出s中第1個不在t中出現的字符（假定每個結點只存放1個字符）的算法。習題3參考答案一、單項選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1. 固定長度，設置長度指針2. 兩個串的長度相等，對應位置的字符相等3. “BCDEDE”4. 含n個字符的有限序列 （n≥0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設計題1．算法描述為：int delete(r,s,t,m) //從串的第m個字符以后刪除長度為t的子串char r[ ]。int s,t,m。{ int i,j。 for(i=1。i=m。i++)r[s+i]=r[i]。 for(j=m+ti。j=s。j++)r[st+j]=r[j]。return (1)。} //delete2．算法思想為：（1）鏈表s中取出一個字符；將該字符與單鏈表t中的字符依次比較；（2）當t中有與從s中取出的這個字符相等的字符，則從t中取下一個字符重復以上比較；（3）當t中沒有與從s中取出的這個字符相等的字符，則算法結束。設單鏈表類型為LinkList；注意，此時類型 LinkList中的data成分為字符類型。LinkString find(s,t)LinkString *s, *t。{ LinkString *ps, *pt。 ps=s。while(ps!=NULL){ pt=t。 while((pt!=NULL)amp。amp。(psdata!=ptdata)) pt=ptnext。 if(pt= =NULL) ps=NULL。 else { ps=psnext。s=ps。 }}return s。} //find習題4一、單項選擇題1. 設二維數組A[0…m1][0…n1]按行優先順序存儲在內存中，第一個元素的地址為p，每個元素占k個字節，則元素aij的地址為（ ）。 +[i*n+j1]*k +[(i1)*n+j1]*k+[(j1)*n+i1]*k +[j*n+i1]*k2. 已知二維數組A1010中，元素a20的地址為560，每個元素占4個字節，則元素a10的地址為（ ）。 3. 若數組A[0…m][0…n]按列優先順序存儲，則aij地址為（ ）。(a00)+[j*m+i] B. LOC(a00)+[j*n+i](a00)+[(j1)*n+i1] D. LOC(a00)+[(j1)*m+i1]4. 若下三角矩陣Ann，按列順序壓縮存儲在數組Sa[0…(n+1)n/2]中，則非零元素aij的地址為（ ）。（設每個元素占d個字節）A. [(j1)*n+i1]*dB. [(j1)*n+i]*dC．[(j1)*n+i+1]*dD．[(j1)*n+i2]*d5. 設有廣義表D=(a,b,D)，其長度為（ ），深度為（ ）。 6. 廣義表A=（a），則表尾為（ ）。 B.(( )) D.(a)7. 廣義表A=((x,(a,B)),(x,(a,B),y))，則運算head(head(tail(A)))的結果為（ ）。 B.(a,B) C.(x,(a,B)) 8. 下列廣義表用圖來表示時，分支結點最多的是（ ）。=((x,(a,B)),(x,(a,B),y)) =(s,(a,B))=((x,(a,B),y)) =((a,B),(c,(a,B),D)9. 通常對數組進行的兩種基本操作是（ ）。 10. 假定在數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放在存儲器內，存放該數組至少需要的單元數為（ ）。 11. 數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放在存儲器內，該數組按行存放時，元素A[8][5]的起始地址為（ ）。+141 +144 +222 +22512. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。 13. 若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種觀點（ ）。 14. 一個廣義表的表頭總是一個（ ）。 15. 一個廣義表的表尾總是一個（ ）。 16. 數組就是矩陣，矩陣就是數組，這種說法（ ）。 ，后句錯 二、填空題1. 一維數組的邏輯結構是______________，存儲結構是______________；對于二維或多維數組，分為______________和______________兩種不同的存儲方式。2. 對于一個二維數組A[m][n]，若按行序為主序存儲，則任一元素A[i][j]相對于A[0][0]的地址為______________。3. 一個廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長度為_____，深度為_____。4. 一個稀疏矩陣為 ，則對應的三元組線性表為_____________。5. 一個nn的對稱矩陣，如果以行為主序或以列為主序存入內存，則其容量為______________。6. 已知廣義表A=((a,b,c),(d,e,f))，則運算head(tail(tail(A)))=____________。7. 設有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a的地址為______________。8. 已知廣義表Ls=(a,(b,c,d),e)，運用head和tail函數取出Ls中的原子b的運算是______________。9. 三維數組R[c1…d1,c2…d2,c3…d3]共含有______________個元素。（其中：c1≤d1,c2≤d2,c3≤d3）10. 數組A[1…10，2…6，2…8]以行優先的順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。三、判斷題1. 數組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進行插入、刪除等操作。（ ）2. 多維數組可以看作數據元素也是基本線性表的基本線性表。（ ）3. 以行為主序或以列為主序對于多維數組的存儲沒有影響。（ ）4. 對于不同的特殊矩陣應該采用不同的存儲方式。（ ）5. 采用壓縮存儲之后，下三角矩陣的存儲空間可以節約一半。（ ）6. 在一般情況下，采用壓縮存儲之后，對稱矩陣是所有特殊矩陣中存儲空間節約最多的。（ ）7. 矩陣不僅是表示多維數組，而且是表示圖的重要工具。（ ）8. 距陣中的數據元素可以是不同的數據類型。（ ）9. 矩陣中的行列數往往是不相等的。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個元素。（ ）11. 廣義表的表尾一定是一個廣義表。（ ）12. 廣義表的元素可以是子表，也可以是單元素。（ ）13. 廣義表不能遞歸定義。（ ）14. 廣義表實際上是基本線性表的推廣。（ ）15. 廣義表的組成元素可以是不同形式的元素。（ ）習題4參考答案一、單項選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 二、填空題1. 線性結構，順序結構，以行為主序，以列為主序2. in+j個元素位置3. 5，34.（（0，2，2），（1，0，3），（2，2，1），（2，3，5））5. n(n+1)/26. e7. 418. head(head(tail(Ls)))9.（dc+1）（dc+1）（dc+1）10. 913三、判斷題1. 2.√ 3.√ 4.√ 5. 6. 7.√ 8. 9. 10.√ 11.√ 12.√ 13. 14.√ 15.√習題5一、單項選擇題1. 在一棵度為3的樹中，度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（ ）個。A. 4 B. 5 C. 6 D. 72. 假設在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為（ ）個。A. 15 B. 16 C. 17 D. 473. 假定一棵三叉樹的結點數為50，則它的最小高度為（ ）。A. 3 B. 4 C. 5 D. 64. 在一棵二叉樹上第4層的結點數最多為（ ）。A. 2 B. 4 C. 6 D. 85. 用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組中R[1..n]，結點R[i]若有左孩子，其左孩子的編號為結點（ ）。A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i1]6. 由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。A. 24 B. 48 C. 72 D. 537. 線索二叉樹是一種（ ）結構。A. 邏輯 B. 邏輯和存儲 C. 物理 D. 線性8. 線索二叉樹中，結點p沒有左子樹的充要條件是（ ）。A.