c題庫(kù)期末復(fù)習(xí)ppt課件-資料下載頁(yè)
2025-01-12 09:42本頁(yè)面
【正文】 等有關(guān)概念 – 哈希函數(shù)的選取原則及產(chǎn)生沖突的原因 – 常用的哈希函數(shù)的構(gòu)造方法 – 解決沖突的主要方法 – 產(chǎn)生“堆積”現(xiàn)象的原因 – 哈希表查找和其它表查找的本質(zhì)區(qū)別。 – 采用線性探測(cè)法或拉鏈法解決沖突時(shí)，哈希表的建表方法、查找過(guò)程以及 ASL的分析計(jì)算 BUPT 38 1. 已知含 12個(gè)關(guān)鍵字的有序表及其相應(yīng)權(quán)值為： 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵字 A B C D E F G H I J K L 權(quán)值 4 6 3 4 9 3 2 6 1 5 3 4 (1)畫(huà)出對(duì)以上有序表進(jìn)行折半查找的判定樹(shù)，求折半查找時(shí)查找成功的平均查找長(zhǎng)度 ASL。 (2)若為等概率查找，求折半查找時(shí)查找成功的平均查找長(zhǎng)度 ASL。 BUPT 39 3. 已知如下長(zhǎng)度為 12的表： (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) (1)試按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，請(qǐng)畫(huà)出插入完成之后的二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度 ASL。 BUPT 40 選取哈希函數(shù) H(k)=(3k) MOD 11。 1) 用線性探測(cè)開(kāi)放定址法處理沖突， 2) 用鏈地址法處理沖突 試在 0~10的散列地址空間中對(duì)關(guān)鍵字序列 (22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度和不成功時(shí)的平均查找長(zhǎng)度以及裝填因子 ?。 BUPT 41 第十章 內(nèi)部排序 ? 基本概念 – 排序方法的穩(wěn)定性的含義 – 排序算法評(píng)價(jià)標(biāo)準(zhǔn) BUPT 42 ? 插入排序 – 直接插入排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 希爾排序的基本思想和時(shí)空性能 BUPT 43 ? 交換排序 – 冒泡排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 快速排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 樞軸記錄的選取對(duì)快速排序的影響 – 針對(duì)給定的輸入實(shí)例，寫(xiě)出快速排序的排序過(guò)程 BUPT 44 ? 選擇排序 – 簡(jiǎn)單選擇排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 錦標(biāo)賽排序的基本思想和時(shí)空性能 – 堆的有關(guān)概念和定義 – 堆的性質(zhì)及堆與完全二叉樹(shù)的關(guān)系 – 堆排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 針對(duì)給定的輸入實(shí)例，能寫(xiě)出堆排序的排序過(guò)程 BUPT 45 ? 歸并排序 – 兩路歸并排序的基本思想、算法實(shí)現(xiàn)、時(shí)空性能 – 針對(duì)給定的輸入實(shí)例，能寫(xiě)出歸并排序的排序過(guò)程 BUPT 46 ? 基數(shù)排序 – 基數(shù)排序的基本思想、時(shí)空性能。 – 針對(duì)給定的輸入實(shí)例能寫(xiě)出基數(shù)排序的排序過(guò)程 – 基數(shù)排序和其它幾類排序的本質(zhì)區(qū)別 BUPT 47 ? 各種排序方法的比較 – 掌握各種排序的主要特點(diǎn) – 根據(jù)實(shí)際問(wèn)題的特點(diǎn)和要求選擇合適的排序方法 BUPT 48 (503, 087, 512, 061, 908, 170, 897, 275, 653, 426)為例，手工執(zhí)行以下排序算法，寫(xiě)出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)： (1) 直接插入排序 (2) 希爾排序 (d[1]=5, d[2]=3, d[3]=1) (3) 快速排序（第一個(gè)記錄作為基準(zhǔn)記錄） (4) 堆排序 (5) 歸并排序 (6) 基數(shù)排序
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1