數(shù)據(jù)結(jié)構(gòu)作業(yè)題(已修改)
2025-04-06 03:01 本頁(yè)面
【正文】 第一章設(shè)n為正整數(shù)，利用大O記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。 (1) i=1。 k=0。 while(in) { k=k+10*i。i++?！ (2) i=0。 k=0。 do{ k=k+10*i。 i++?！ while(in)。 (3) i=1。 j=0。 while(i+j=n) { if (ij) j++?！ lse i++?！ (4)x=n。 // n1 while (x=(y+1)*(y+1)) y++。(5) x=91。 y=100。 while(y0) if(x100) {x=x10。y。} else x++。按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 第二章27 針對(duì)帶表頭結(jié)點(diǎn)的單鏈表，試編寫下列函數(shù)。(1) 定位函數(shù)Locate：在單鏈表中尋找第i個(gè)結(jié)點(diǎn)。若找到，則函數(shù)返回第i個(gè)結(jié)點(diǎn)的地址；若找不到，則函數(shù)返回NULL。(2) 求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。第三章 [m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top[0]增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top[1]減1得到新的棧頂位置。當(dāng)top[0]+1 == top[1]時(shí)或top[0] == top[1]1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類型定義，并實(shí)現(xiàn)初始化、判?？铡⑴袟M、插入、刪除算法。1 top[0] top[1] m0 m1【提示】類型定義：define m 100；Typedef int dsType；//雙棧的元素類型Typedef struct{int top[2]。 //雙棧的棧頂指針和棧底指針dsType V[m]。//棧數(shù)組} DoubleStack；初始化空雙棧算法：InitdStack(DoubleStack amp。ds ) {//初始化空雙棧ds[0]=1。[1]=m。}判?？账惴ǎ篿nt DStackEmpty(DoubleStack ds , int i) {//判斷雙棧ds的第i（0或1）個(gè)棧是否為空，空則返回1，否則返回0if (i==0 amp。amp。 [0]==1) return 1。if (i==1 amp。amp。 [1]==m) return 1。return 0。}32. 試?yán)盟惴麅?yōu)先法，畫出對(duì)如下中綴算術(shù)表達(dá)式求值時(shí)運(yùn)算符棧和操作數(shù)棧的變化。 a + b * (c d) – e （表示結(jié)束符）步序掃描項(xiàng)項(xiàng)類型 動(dòng)作OPND棧變化OPTR棧變化0F OPTR棧與OPND棧初始化, ‘’ 進(jìn)OPTR棧, 取第一個(gè)符號(hào)1a操作數(shù)F a 進(jìn)OPND棧, 取下一符號(hào)a2+操作符F ‘ + ’ ‘’, 進(jìn)OPTR棧, 取下一符號(hào)a+………………………………33 分別寫出順序循環(huán)隊(duì)列隊(duì)列Q狀態(tài)為“空”還是“滿”的條件和計(jì)算隊(duì)列中元素個(gè)數(shù)的公式。第四章 設(shè)有模式串T1,T2，T1=‘a(chǎn)aab’，T2=‘a(chǎn)bcabaa’，目標(biāo)串s為‘a(chǎn)bc aaabbabcabaacbacba’，（1）計(jì)算模式串T1的next(j) 和nextval(j)函數(shù)的值,并（按照nextval(j) ）畫出KMP算法匹配過程。（2）計(jì)算模式串T2的next(j) 和nextval(j)函數(shù)的值,并（按照nextval(j) ）畫出KMP算法匹配過程。學(xué)號(hào)尾數(shù)為奇數(shù)做第（1）題；偶數(shù)做第（2）題第五章 51 設(shè)有一個(gè)二維數(shù)組A[m][n]（按照列優(yōu)先存儲(chǔ)，m、n均大于5），假設(shè)A[0][0]存放位置在644(10)，A[2][3]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[4][4](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。52假二維數(shù)組A9180。3180。5180。8，第一個(gè)元素的字節(jié)地址是1000，每個(gè)元素占6個(gè)字節(jié)。問下列元素的存儲(chǔ)地址是什么？（1）a0000 （2）a8247 （3）按行優(yōu)先存儲(chǔ)（最左下標(biāo)優(yōu)先）時(shí)a3125的地址 （4）按照列優(yōu)先存儲(chǔ)（最右下標(biāo)優(yōu)先）時(shí)a1111的地址53矩陣(aij)n180。n的壓縮存儲(chǔ)方式,我們把它們按行存放于一個(gè)一維數(shù)組B中:（1）設(shè)有一個(gè)n180。n的下三角矩陣A，如圖(a)所示。為了節(jié)約存儲(chǔ)，只存對(duì)角線或?qū)蔷€以下的元素。若在一維數(shù)組B中從0號(hào)位置開始存放，則下三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。（2）設(shè)有一個(gè)n180。n的上三角矩陣A，如圖(b)所示。為了節(jié)約存儲(chǔ)，只存對(duì)角線及對(duì)角線以上的元素，若在一維數(shù)組B中從0號(hào)位置開始存放，則上三角矩陣中的任一元素aij在應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。a11 a21 a22 a31 a32 a33 … …an1 an2 an3 … … ann 圖(a)0a11 a12 a13 … … a1n a22 a23 … … a2n a33 … … a3n … … ann圖(b) 圖(b)0 54 利用廣義表和tail操作寫出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來： (1) L1(apple, pear, banana, or
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1