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