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

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