c題庫期末復習ppt課件(編輯修改稿)
2025-02-08 09:42 本頁面
【文章內(nèi)容簡介】 earnext。 //空隊列 free(s)。 } BUPT 15 第四章 串 ? 串及其運算 – 串的概念及其與線性表的關系 – 串上定義的基本運算，并能利用基本運算構造出較復雜的運算 BUPT 16 ? 串的存儲結構和基本運算的實現(xiàn) – 串的兩種主要存儲結構 —順序串和鏈串的存儲結構定義（ C語言的類型描述） – 順序串上串的基本運算的實現(xiàn) – 樸素的模式匹配算法與 KMP算法的算法思想及時間復雜度分析 – KMP算法中 next和 nextval數(shù)組的求值方法 BUPT 17 ? 求模式串 t1=?aaab‘， t2=?abcabaa‘ ， ? t3=?adabbadada‘的 next和 nextval數(shù)組值 BUPT 18 第六章 樹 ? 樹的概念 – 樹的邏輯結構特征 – 樹的常用術語及含義 BUPT 19 ? 二叉樹 – 二叉樹的定義，二叉樹與樹的差別 – 完全二叉樹和滿二叉樹的概念 – 二叉樹的性質(zhì) – 二叉樹的順序存儲結構和鏈式存儲結構的定義（ C語言的類型描述）和表示方法 BUPT 20 ? 二叉樹的遍歷 – 二叉樹的先序、中序、后序、層序遍歷算法 – 求給定二叉樹的先序、中序、后序遍歷對應的結點訪問序列 – 由二叉樹的先序和中序、中序和后序、中序和層序的序列確定二叉樹 – 以遍歷算法為基礎，設計有關算法解決簡單的應用問題 BUPT 21 ? 線索二叉樹 – 二叉樹線索化的目的 – 線索二叉樹存儲結構的表示方法 – 在線索二叉樹中查找給定結點的前趨和后繼的方法 BUPT 22 ? 樹和森林 – 樹和森林與二叉樹之間的轉(zhuǎn)換方法和對應關系 – 樹的各種存儲結構的表示方法及其特點 – 樹的先序和后序遍歷方法 – 森林的先序和中序遍歷方法 BUPT 23 ? 哈夫曼樹及其應用 – 最優(yōu)二叉樹的概念及特點 – 求哈夫曼樹的方法 – 設計哈夫曼編碼的方法 BUPT 24 ? 一、下面是用 c語言編寫的對 不帶頭結點的單鏈表 進行就地逆置的算法，該算法用 L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句（ 不允許使用額外的輔助變量 ）。 void reverse（ linklist amp。L） { p=NULL。q=L。 while（ q!=NULL） { (1) 。 qnext=p。 p=q。 (2)___ 。 } (3)_____。 } ? 二、假設以 I和 O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由 I和 O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。 （ 1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （ 2）通過對（ 1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回 TRUE，否則返回 FALSE（假定被判定的操作序列已存入一維數(shù)組 A中）。 BUPT 25 ? 三、設模式串 t=‘a(chǎn)bcabaa’，試求出該模式串的next和 nextval數(shù)組的值。 ? 四、設一棵二叉樹的先序、中序遍歷序列分別為 先序遍歷序列： A B D F C E G H 中序遍歷序列： B F D A G E H C （ 1）畫出這棵二叉樹。 （ 2）畫出這棵二叉樹的后序線索樹。 （ 3）將這棵二叉樹轉(zhuǎn)換成對應的樹（或森林）。 BUPT 26 第七章 圖 ? 圖的概念 – 圖的邏輯結構特征
教學課件相關推薦
鄂ICP備17016276號-1