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