作業(yè)及答案1ppt課件VIP

數(shù)據(jù)結(jié)構(gòu)作業(yè)及答案 C語(yǔ)言版 2 目錄 1 第2章線(xiàn)性表2 第3章棧和隊(duì)列3 第6章樹(shù)和森林4 第7章圖5 第8章集合與查找6 第9章索引與散列 3 第2章線(xiàn)性表作業(yè)及答案1 1 1 已知有一個(gè)單鏈表L 設(shè)計(jì)一個(gè)算法 通過(guò)一趟遍歷 在L中確定值最大的結(jié)點(diǎn) 返回指向該結(jié)點(diǎn)的指針 注 遍歷是指從頭至尾訪問(wèn)單鏈表中的每一個(gè)結(jié)點(diǎn)且指訪問(wèn)一次 4 第2章線(xiàn)性表作業(yè)及答案1 2 2 設(shè)計(jì)一個(gè)算法 在非遞減有序的單鏈表L中刪除值相同的多余結(jié)點(diǎn) 5 第3章棧和隊(duì)列作業(yè)及答案2 1 假設(shè)以數(shù)組Q m 存放循環(huán)隊(duì)列中的元素 同時(shí)設(shè)置一個(gè)標(biāo)志tag 0和tag 1來(lái)區(qū)別當(dāng)隊(duì)頭指針front和隊(duì)尾指針rear相等時(shí) 隊(duì)列的狀態(tài)是 空 還是 滿(mǎn) 試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的入隊(duì) EnQueue 和出隊(duì) DeQueue 算法 要求先寫(xiě)明結(jié)構(gòu) 再寫(xiě)算法 6 第3章棧和隊(duì)列作業(yè)及答案2 2 StatusEnQueue SqQueue 7 第6章樹(shù)和森林作業(yè)及答案4 1 1 編寫(xiě)遞歸算法 統(tǒng)計(jì)二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù) 8 第6章樹(shù)和森林作業(yè)及答案4 2 2 給定權(quán)值集合 15 3 14 2 6 9 16 17 構(gòu)造相應(yīng)的Huffman樹(shù) 并計(jì)算它的帶權(quán)路徑長(zhǎng)度 要求畫(huà)出Huffman樹(shù)的構(gòu)造過(guò)程 9 第6章樹(shù)和森林作業(yè)及答案4 3 10 第6章樹(shù)和森林作業(yè)及答案4 4 此樹(shù)的帶權(quán)路徑長(zhǎng)度WPL 229 11 第7章圖作業(yè)及答案5 1 1 用數(shù)學(xué)歸納法證明有n個(gè)頂點(diǎn)的完全無(wú)向圖有n n 1 2條邊 證明 1 當(dāng)n 1時(shí) 一個(gè)頂點(diǎn)時(shí) 邊數(shù)為0 成立 2 當(dāng)n 2時(shí) 兩個(gè)頂點(diǎn) 邊數(shù)為1 成立 3 設(shè)n k時(shí)成立 即k個(gè)頂點(diǎn)的完全無(wú)向圖有k k 1 2條邊 則n k 1時(shí) 第k 1個(gè)頂點(diǎn)到其他k個(gè)頂點(diǎn)的邊數(shù)共k條 于是總邊數(shù)為k k 1 2 k k 1 k 2 結(jié)論成立 12 第7章圖作業(yè)及答案5 2 2 對(duì)于如圖所示的有向圖 試畫(huà)出從頂點(diǎn) 出發(fā)進(jìn)行深度優(yōu)先搜索得到的深度優(yōu)先生成樹(shù) 結(jié)果不唯一 13 第8章集合與查找作業(yè)及答案6 1 將關(guān)鍵字 DEC FEB NOV OCT JUL SEP AUG APR MAR MAY JUN JAN 依次插入到一棵初始為空的AVL樹(shù)中 畫(huà)出每插入一個(gè)關(guān)鍵字后的AVL樹(shù) 需要平衡時(shí)標(biāo)明平衡旋轉(zhuǎn)的類(lèi)型和結(jié)果 注 按字典順序比較 DEC 14 第8章集合與查找作業(yè)及答案6 2 15 第8章集合與查找作業(yè)及答案6 3 16 第8章集合與查找作業(yè)及答案6 4 17 第9章索引與散列作業(yè)及答案7 1 給定關(guān)鍵字序列 11 78 10 1 3 2 4 21 分別用順序查找 折半查找 二叉排序樹(shù) 平衡二叉樹(shù) 散列表 用線(xiàn)性探查法和鏈地址法 實(shí)現(xiàn)查找 畫(huà)出它們對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu) 順序查找的順序表 折半查找的二叉判定樹(shù) 二叉排序樹(shù) 平衡二叉樹(shù)以及兩種散列表 并求出每一種查找在等概率下查找成功時(shí)的ASL 其中 散列表為HT 11 散列函數(shù)為H key key 11 18 第9章索引與散列作業(yè)及答案7 2 可以得到順序查找的平均查找長(zhǎng)度為 ASL 1 2 3 4 5 6 7 8 8 8 1 2 4 5 2 先按關(guān)鍵字排序 折半查找的判定樹(shù)如圖所示 從圖可以得到折半查找的平均查找長(zhǎng)度為 ASL 1 2 2 3 4 4 1 8 21 8 2 625 19 第9章索引與散列作業(yè)及答案7 3 3 二叉排序樹(shù)和平衡二叉樹(shù)如圖所示 從圖可以得到二叉排序樹(shù)查找的平均查找長(zhǎng)度為 ASL 1 2 2 3 2 4 1 5 2 8 25 8 3 125平衡二叉樹(shù)的成功平均查找長(zhǎng)度為 ASL 1 1 2 2 3 3 4 2 8 22 8 2 75 20 第9章索引與散列作業(yè)及答案7 4 4 線(xiàn)性探查法解決沖突的散列表如圖所示 從圖可以得到線(xiàn)性探查法的平均查找長(zhǎng)度為ASL 1 1 1 2 1 3 2 8 8 19 8 2 375 5 鏈地址法解決沖突的散列表如圖所示 21 第9章索引與散列作業(yè)及答案7 5 從圖可以得到鏈地址法的