數(shù)據(jù)結(jié)構(gòu)題庫應(yīng)用題上海杉達(dá)學(xué)院期末總復(fù)習(xí)題

1、《數(shù)據(jù)結(jié)構(gòu)》――應(yīng)用題1《數(shù)據(jù)結(jié)構(gòu)》――應(yīng)用題復(fù)習(xí)概要2019年8月1.寫出執(zhí)行下列程序段時(shí)，語句S的執(zhí)行次數(shù)。f(i=1i=ij)S2.假設(shè)n為2的乘冪，并且n2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）intTime(intn)intcount:=0x:=2while(xRL=PRLPRL=QQRLLL=QQLL=P(2)QRL=PPLLRL=QQLL=PLLPLL=Q(3)PLLRL=PRLPRLLL=P

2、LL4.設(shè)棧S的初始狀態(tài)為空，元素abcde和f依次通過棧S，試分析下列各組出棧次序，每組所用的最大容量。（1）abcdef；（2）fedcba；（3）bdcfea5.有字符串ABCD，試寫出利用棧操作將該字符串序列改為ABCD的操作步驟，這里用X和S分別表示字符的進(jìn)棧和出棧操作（例如把字符ABCD改為ACBD的操作步驟為XSXXSSXS）。XSXXSXXSSSXXSS6.一棵二叉樹的結(jié)點(diǎn)數(shù)采用順序存儲(chǔ)結(jié)構(gòu)，存于下列數(shù)組T中，畫出該二叉

3、樹?！稊?shù)據(jù)結(jié)構(gòu)》――應(yīng)用題39.將下列二叉鏈表改為先序線索鏈表12345678dataABCDEFGHLTag00101000lchild24070000RTag00001000rchild3568000010.下表給出用帶二個(gè)標(biāo)識的按先序遍歷進(jìn)行順序存儲(chǔ)的二叉樹，對于結(jié)點(diǎn)k，規(guī)定：ltag(k)=0，k有左孩子；ltag(k)=1，k無左孩子；rtag(k)=0，k有右孩子；rtag(k)=1，k無右孩子。12345678910lta