《數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用》筆記含答案 第四章

第4章串、數(shù)組和廣義表一、填空題1、零個(gè)或多個(gè)字符組成的有限序列稱為——。二、判斷題1、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（J）2、數(shù)組是線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入，刪除等操作。（X）3、若采用三元組存儲(chǔ)稀疏矩陣，把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（X）4、若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（X5、所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（X三、單項(xiàng)選擇題1、串是一種特殊的線性表，其特殊性體現(xiàn)在（B）。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符若2、串下面關(guān)于串的的敘述中，（B）是不正確的？A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)解釋：空格常常是串的字符集合中的一個(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長(zhǎng)度為零。3、串"ababaaababaa”的next數(shù)組為（C）。A.012345678999B.012121111212C.011234223456D.01230123223454、串"ababaabab”的nextval為（A）。A.010104101B.010102101C.010100011D.0101010115、串的長(zhǎng)度是指（B）。A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)解釋：串中字符的數(shù)目稱為串的長(zhǎng)度。6、假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（B）。A.808B.818C.1010D.1020解釋：以行序?yàn)橹?，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。7、設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8,j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（B）。A.BA+141B.BA+180C.BA+222D.BA+225解釋：以列序?yàn)橹鳎瑒tLOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。8、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（C）。A.13B.32C.33D.409、若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑兀òㄖ鲗?duì)角線上所有元素）依次存放于一維數(shù)組B[1..（n（n+1））/2]中，則在B中確定ai.（i<j）的位置k的關(guān)系為（B）。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i10、二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,-,10。若A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素(B)的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]解釋：設(shè)數(shù)組從內(nèi)存首地址M開(kāi)始順序存放，若數(shù)組按行先存儲(chǔ)，元素A[8,5]的起始地址為:M+[(8-0)*10+(5-1)]*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A[3,10]的起始地址為：M+[(10-1)*9+(3-0)]*1=M+84。故選B。11、設(shè)二維數(shù)組A[1..m，1..n](即m行n列)按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為(A)。A.(i-1)*n+jB.(i-1)*n+j-1C.i*(j-1)D.j*m+i-1解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。12、數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)(B)。A.55B.45C.36D.16解釋：共有5*3*3=45個(gè)元素。13、廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A))))的值為(D)。A.(g)B.(d)C.cD.d解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=((c,d),(e,(f,g)))；Head(Tail(Tail(A)))=(c,d)；Tail(Head(Tail(Tail(A))))=(d)Head(Tail(Head(Tail(Tail(A)))))=d。14、廣義表((a,b,c,d))的表頭是(C)，表尾是(B)。A.aB.()C.(a,b,c,d)D.(b,c,d)解釋：表頭為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，((a,b,c,d))的表頭為一個(gè)子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，((a,b,c,d))的表尾為空表()。15、設(shè)廣義表L=((a,b,c))，則L的長(zhǎng)度和深度分別為(C)。A.1和1B.1和3C.1和2D.2和3解釋：廣義表的深度是指廣義表中展開(kāi)后所含括號(hào)的層數(shù)，廣義表的長(zhǎng)度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為1，深度為2。四、應(yīng)用題1、已知模式串t=‘a(chǎn)bcaabbabcab'寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：1123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]0110213011052、設(shè)目標(biāo)為t="abcaabbabcabaacbacba”，模式為p="abcabaa”計(jì)算模式p的naxtval函數(shù)值；答案：①p的nextval函數(shù)值為0110132。(p的next函數(shù)值為0111232)。不寫出算法，只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。②利用KMP(改進(jìn)的nextval)算法，每趟匹配過(guò)程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)3、數(shù)組A中，每個(gè)元素A[i,j]的長(zhǎng)度均為32個(gè)二進(jìn)位，行下標(biāo)從-1到9,列下標(biāo)從1到11，從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求：存放該數(shù)組所需多少單元？存放數(shù)組第4列所有元素至少需多少單元？數(shù)組按行存放時(shí)，元素A[7,4]的起始地址是多少？數(shù)組按列存放時(shí)，元素A[4,7]的起始地址是多少？答案：每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng)16位，故每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至1到11。(1)242(2)22(3)s+182(4)s+1424、請(qǐng)將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H(H(T(H(T(H(T(L)))))))5、計(jì)算GetHead(A)、GetHead(B)