數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)說(shuō)明(編輯修改稿)
2025-05-14 01:46 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 a(i=3,j=1) 第四趟匹配： aabaabaabaac aabaac(i=9,j=6)第五趟匹配： aabaabaabaac aa(i=6,j=2)第六趟匹配： aabaabaabaac a(i=6,j=1)第七趟匹配： aabaabaabaac 利用KMP算法的匹配過(guò)程： 第一趟匹配：aabaabaabaac aabaac(i=6,j=6,nextval(j)=3) 第二趟匹配：aabaabaabaac (aa)baac (i=9,j=6) 第三趟匹配：aabaabaabaac (成功) (aa)baac(i=13,j=7)例12．一般串定位函數(shù)Index(S,T,pos), 設(shè)S的串長(zhǎng)為n，T的串長(zhǎng)為m,則最壞時(shí)間復(fù)雜度 ；而改進(jìn)的Index_KMP(S,T,pos) 時(shí)間復(fù)雜度為 。 第五章：數(shù)組和廣義表：以行為主序、以列為主序的地址映像函數(shù) B2矩陣的壓縮存儲(chǔ)：（1）特殊陣：包括對(duì)稱(chēng)陣、三角陣、帶狀陣（利用其特性壓縮存儲(chǔ)到一維數(shù)組）B （2）稀疏陣 利用的是三元組順序表來(lái)表示 B 用十字鏈表表示C（本次考試不做要求） B （本次考試不做要求）本章重點(diǎn)：地址映像函數(shù)的計(jì)算（包括數(shù)組和特殊矩陣）例13．已知n階下三角矩陣A（即當(dāng)ij時(shí)，有aij=0），按照壓縮存儲(chǔ)的思想，可以將其主對(duì)角線(xiàn)以下所有元素(包括主對(duì)角線(xiàn)上元素 )依次存放于一維數(shù)組B中，請(qǐng)寫(xiě)出從第一列開(kāi)始采用列序?yàn)橹餍蚍峙浞绞綍r(shí)在B中確定元素aij的存放位置的公式?！ 〈穑簄階下三角矩陣元素A[i][j]（1=i,j=n,i=j）。第1列有n個(gè)元素，第j列有nj+1個(gè)元素，第1列到第j1列是等腰梯形，元素?cái)?shù)為(n+(nj+2)(j1)/2，而aij在第j列上的位置是為ij+1。所以n階下三角矩陣A按列存儲(chǔ)，其元素aij在一維數(shù)組B中的存儲(chǔ)位置k與i和j的關(guān)系為：k=(n+(n(j1)+1)(j1)/2+(ij+1)=(2nj)(j1)/2+i第六章：二叉樹(shù)與樹(shù)： B 幾個(gè)特殊的二叉樹(shù)：滿(mǎn)二叉樹(shù)、完全二叉樹(shù)、二叉排序樹(shù)、平衡二叉樹(shù) B： C： 用二叉鏈表表示與實(shí)現(xiàn) A：先（中、后）序遍歷及應(yīng)用，相應(yīng)遞歸算法和非遞歸算法 A（利用二叉鏈表n+1空指針域來(lái)存放某遍歷下指向該結(jié)點(diǎn)的直接前驅(qū)或直接后繼，使得蘊(yùn)含更多信息） B：算術(shù)表達(dá)式，霍夫曼樹(shù)（最優(yōu)二叉樹(shù)），判定樹(shù) B：….. B B B★本章重點(diǎn)：很熟悉二叉樹(shù)（在二叉鏈表表示下）的基本操作的遞歸算法和遍歷的非遞歸算法，請(qǐng)仔細(xì)復(fù)習(xí)。 本章難點(diǎn)：二叉樹(shù)（含排序樹(shù)、平衡樹(shù)）的遞歸算法和非遞歸算法。線(xiàn)索化二叉樹(shù)及相應(yīng)操作，重在理解，不考編程！例14．引入二叉線(xiàn)索樹(shù)的目的是（ ）A．將非線(xiàn)性序列轉(zhuǎn)化成某種線(xiàn)性序列；加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B．為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親 D．使二叉樹(shù)的遍歷結(jié)果唯一A例15．二叉鏈表在線(xiàn)索化后，仍不能有效求解的問(wèn)題是（ ）。A．前（先）序線(xiàn)索二叉樹(shù)中求前（先）序后繼 B．中序線(xiàn)索二叉樹(shù)中求中序后繼C．中序線(xiàn)索二叉樹(shù)中求中序前驅(qū) D．后序線(xiàn)索二叉樹(shù)中求后序后繼 D例16．在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為1右孩子的平衡因子為0,則應(yīng)作( ) 型調(diào)整以使其平衡。（平衡因子=左子樹(shù)深度右子樹(shù)深度）A. LL （單向右旋） B. LR （先左后右雙向旋轉(zhuǎn)）C. RL （先右后左雙向旋轉(zhuǎn)） D. RR （單向左旋）B例17．一棵非空的二叉樹(shù)其先序序列和后序序列正好相反，畫(huà)出這棵二叉樹(shù)的形狀。先序序列是“根左右” 后序序列是“左右根”，可見(jiàn)對(duì)任意結(jié)點(diǎn)，若至多只有左子女或至多只有右子女，均可使前序序列與后序序列相反，圖示如下：例18：已知二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)如下：用C語(yǔ)言表示 typedef struct BiNode｛ ElemType data。 struct BiNode *lchild,*rchild?！nt val。 ｝BiNode,*BiTree。 其中val域表示該結(jié)點(diǎn)的子孫（含孩子結(jié)點(diǎn)）的個(gè)數(shù)。開(kāi)始時(shí)，val域值均為0，T為指向某二叉樹(shù)根結(jié)點(diǎn)的指針。請(qǐng)寫(xiě)算法填寫(xiě)該二叉樹(shù)中每個(gè)結(jié)點(diǎn)的val域。遞歸算法如下：int writeVal(BiNode *root) {if(root==NULL) rootval=0。 else if(rootlchild==NULLamp。amp。rootrchild==NULL) rootval=1。 else rootval=writeVal(rootlchild)+writeVal(rootrchild)。 return rootval。 }例19．編寫(xiě)一個(gè)算法，將指針S所指的結(jié)點(diǎn)插入到根結(jié)點(diǎn)指針為T(mén)的二叉排序樹(shù)中，若已存在則不再插入返回0；否則返回1。（遞歸的算法見(jiàn)教材）int Insert_BST( BiTree amp。T, BiTNode S ) { BiTree p, q。 //p指向當(dāng)前訪(fǎng)問(wèn)的結(jié)點(diǎn) if(!T) T=S。 else { p=T。 while ( p ) { q = p。 //q指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn) if (S p) p = plchild。 else if(S p) p = prchild。 else p=NULL。 } if (S == q) return 0。 if (S q) qlchild = S。 else qrchild = S。 } return 1。}例20．編寫(xiě)一個(gè)算法，計(jì)算平衡二叉樹(shù)中所有結(jié)點(diǎn)的平衡因子 解：計(jì)算一個(gè)結(jié)點(diǎn)＊bt的bf的值遞歸模型如下：f(bt): btbf 不存在 當(dāng)bt==NULL
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1