數(shù)據(jù)結(jié)構(gòu)(C語言版)第三四章習(xí)題答案

數(shù)據(jù)結(jié)構(gòu)(C語言版)第三四章習(xí)題答案數(shù)據(jù)結(jié)構(gòu)(C語言版)第三四章習(xí)題答案數(shù)據(jù)結(jié)構(gòu)(C語言版)第三四章習(xí)題答案數(shù)據(jù)結(jié)構(gòu)(C語言版)第三四章習(xí)題答案編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:第3章棧和隊(duì)列習(xí)題1．選擇題（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。A．iB．n-iC．n-i+1D．不確定（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個數(shù)小于ｎ，計(jì)算隊(duì)列中元素個數(shù)的公式為（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n（4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（）。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；（5）設(shè)有一個遞歸算法如下

intfact(intn){

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧（11）用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改（12）循環(huán)隊(duì)列存儲在數(shù)組A[0..m]中，則入隊(duì)時的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)（13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front（14）棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)（15）一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)

根據(jù)提示，算法可設(shè)計(jì)為：

IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過對=1\*GB3①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。=1\*GB3①A和D是合法序列，B和C是非法序列。=2\*GB3②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])M-1]實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時為隊(duì)空，(rear+1)%m=front為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。（1）#defineM隊(duì)列可能達(dá)到的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;（2）elemtpdelqueue(cycqueueQ)100,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．1020（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為（）。A．BA+141B．BA+180C．BA+222D．BA+225（8）設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A．13B．33C．18D．40（9）若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i（10）A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N(N+1)/2]中，則對任一上三角元素a[i][j]對應(yīng)T[k]的下標(biāo)k是（）。A．i(i-1)/2+jB．j(j-1)/2+iC．i(j-i)/2+1D．j(i-1)/2+1（11）設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-1（12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（）。A．55B．45C．36D．16（13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（）。A．(g)B．(d)C．cD．d（14）廣義表((a,b,c,d))的表頭是（），表尾是（）。A．a(chǎn)B．()C．(a,b,c,d)D．(b,c,d)（15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（）。A．1和1B．1和3C．1和2D．2和3（1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計(jì)算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。=1\*GB3①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。=2\*GB3②利用KMP(改進(jìn)的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素A[i,j]的長度均為32個二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：=1\*GB3①存放該數(shù)組所需多少單元=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元=3\*GB3③數(shù)組按行存放時，元素A[7,4]的起始地址是多少=4\*GB3④數(shù)組按列存放時，元素A[4,7]的起始地址是多少每個元素32個二進(jìn)制位，主存字長16位，故每個元素占2個字長，行下標(biāo)可平移至1到11。（1）242（2）22（3）s+182（4）s+142(4)請將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）寫一個算法統(tǒng)計(jì)在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個字母和0-9這10個數(shù)字）。voidCount（）是字符串輸入結(jié)束標(biāo)志 {InvertStore(A); A[i++]=ch;m,1..n]含有m*n個整數(shù)。=1\*GB3①寫一個算法判斷a中所有元素是否互不相同輸出相關(guān)信息(yes/no)；=2\*GB3②試分析算法的時間復(fù)雜度。[題目分析]判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互