資料結構(分冊)-全國碩士研究生入學統一考試...

目 錄 第1章線性表…………………………………………………………………………………………一1 1．1線性表的定義和基本操作…………………………………………………………………1 1．1．1線性表的邏輯定義與特徵……………………………………………………………………………一l 1．1．2線性表的基本操作……………………………………………………………………………………一2 1．2線性表的實現……………………………………………………………………………4 1．2．1順序存儲結構…………………………………………………………………………………………”4 1．2．2鏈式存儲結構…………………………………………………………………………………………”9 1．2．3線性表的應用…………………………………………………………………………………………21 1_3本章真題解析……………………………………………………………………………23 1．3．1單項選擇題……………………………………………………………………………………………23 1．3．2綜合應用題……………………………………………………………………………………………29 第2章棧、佇列和陣列………………………………………………………………………………～37 2．1棧和佇列的基本概念……………………………………………………………………37 2．2棧和佇列的順序存儲結構………………………………………………………………38 2．2．1順序棧…………………………………………………………………………………………………。39 2．2．2順序佇列………………………………………………………………………………………………40 2-3棧和佇列的鏈式存儲結構………………………………………………………………”42 2．3．1棧的鏈式存儲結構……………………………………………………………………………………42 2．3．2佇列的鏈式存儲結構…………………………………………………………………………………44 2-4棧和佇列的應用…………………………………………………………………………45 2．4．1棧的應用………………………………………………………………………………………………46 2．4．2佇列的應用……………………………………………………………………………………………47 2．5特殊矩陣的壓縮存儲……………………………………………………………………‘47 2．5．1特殊矩陣………………………………………………………………………………………………48 2．5．2疏鬆陣列………………………………………………………………………………………………’49 2．6本章真題解析……………………………………………………………………………53 2．6．1單項選擇題……………………………………………………………………………………………53 2．6．2綜合應用題……………………………………………………………………………………………59 第3章樹和二叉樹……………………………………………………………………………………刑 3．1樹的基本概念……………………………………………………………………………7。 3．1．1二叉樹的基本概念…．．………………………………………………………………………………74 3-l·2二叉樹的存儲結構……………………………………………………………………………………．77 3．1．3二叉樹的遍歷…………………………………………………………………………………………79 3一l-4線索二叉樹……………………………………………………………………………………………81 3．2樹和森林…………………………………………………………………………………84 3．2．1樹的存儲結構…………………………………………………………………………………………84 3．2．2森林與二叉樹的轉換…………………………………………………………………………………87 3．2．3樹和森林的遍歷………………………………………………………………………………………RQ 3．3樹與二叉樹的應用………………………………………………………………………90 3．3．1哈夫曼樹………………………………………………………………………………………………90 3．3．2二叉排序樹……………………………………………………………………………………………93 3．3．3平衡二叉樹…………………………………………………………………………………………．．100 3．4本章真題解析……………………………………………………………………………101 3．4．1單項選擇題…………………………………………………………………………………………～101 3．4．2綜合應用題…………………………………………………………………………………………．．110 第4章 圖……………………………………………………………………………………………………………… 4．1 圖的概念……………………………………………………………………………… 4·2 圖的存儲及基本操作……………………………………………………………………126 4．2．1鄰接矩陣法…………………………………………………………………………………………．．126 4．2．2鄰接表法……………………………………………………………………………………………．．128 4．3 圖的遍歷……………………………………………………………………………… 4．3．1深度優先搜索………………………………………………………………………………………131 4．3．2廣度優先搜索………………………………………………………………………………………．．133 4．4圖的基本應用…………………………………………………………………………… 4．4．1最小生成樹…………………………………………………………………………………………135 4．4．2最短路徑……………………………………………………………………………………………．．140 4．4．3拓撲排序……………………………………………………………………………………………142 4．4．4關鍵路徑…………………………………………………………………………………………… 4·5本章真題解析……………………………………………………………………………146 4．5．1單項選擇題………………………………………………………………………………………… 4．5．2綜合應用題…………………………………………………………………………………………

目 錄 第1章線性表…………………………………………………………………………………………一1 1．1線性表的定義和基本操作…………………………………………………………………1 1．1．1線性表的邏輯定義與特徵……………………………………………………………………………一l 1．1．2線性表的基本操作……………………………………………………………………………………一2 1．2線性表的實現……………………………………………………………………………4 1．2．1順序存儲結構……………………………………...