北華航天工業(yè)學(xué)院研究生入學(xué)考試
數(shù)據(jù)結(jié)構(gòu)（508）復(fù)試科目大綱
一、考試總體要求
本
考試大綱適用于報考我校航空宇航科學(xué)與技術(shù)專業(yè)-航天遙感技術(shù)與應(yīng)用方向、電子信息專業(yè)-遙感與空間信息工程方向的碩士研究生入學(xué)考試。
《數(shù)據(jù)結(jié)構(gòu)》課程考試目標(biāo)：理解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和方法；掌握數(shù)據(jù)的
邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。具備運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本原理、基本方法進(jìn)行分析和解決有關(guān)問題的能力，能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析，并運(yùn)用數(shù)據(jù)結(jié)構(gòu)對問題進(jìn)行求解。
二、考試形式：待定。
三、考試內(nèi)容及要求
（一）概述
1．理解數(shù)據(jù)的
邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的基本概念。
2．理解算法定義、基本性質(zhì)以及算法分析，包括時間復(fù)雜度和空間復(fù)雜度的計算。
（二）線性表
1．理解線性關(guān)系、線性表的定義和線性表的基本操作。
2．掌握線性表的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理。
3．熟練掌握在以上兩種存儲結(jié)構(gòu)的基礎(chǔ)上對線性表實(shí)施的基本操作，包括順序表的插入、刪除、查找等以及鏈表的建立、插入、刪除、查找等操作對應(yīng)的算法設(shè)計。
4．掌握鏈表的常用應(yīng)用。
（三）棧和隊列
1．理解棧與隊列的基本概念與基本操作。
2．掌握棧與隊列的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)的構(gòu)造原理。
3．熟練掌握在不同存儲結(jié)構(gòu)的基礎(chǔ)上對棧與隊列實(shí)施插入與刪除等基本操作的算法設(shè)計。
4．掌握棧和隊列在解決實(shí)際問題中應(yīng)用。例如：遞歸過程、表達(dá)式求值、數(shù)制轉(zhuǎn)換、迷宮求解、排隊問題等。
（四）串、數(shù)組和廣義表
1．理解串的基本概念及其順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
2．掌握串的模式匹配過程及算法設(shè)計。
3．掌握數(shù)組的順序存儲結(jié)構(gòu)及地址計算。
4．理解特殊矩陣的壓縮存儲方法。
5．理解廣義表的基本概念、存儲結(jié)構(gòu)。
（五）樹與二叉樹
1．理解樹與二叉樹的基本概念，名詞術(shù)語。
2．掌握二叉樹的基本性質(zhì)和存儲結(jié)構(gòu)。
3．掌握二叉樹與樹、森林之間的轉(zhuǎn)換。
4．熟練掌握二叉樹的遍歷，包括遞歸和非遞歸算法。
5．掌握以二叉鏈表形式存儲的二叉樹遍歷算法的應(yīng)用。
6．掌握哈夫曼樹的基本概念，哈夫曼樹和哈夫曼編碼的構(gòu)造和算法設(shè)計。
（六）圖
1．理解圖的基本概念和名詞術(shù)語。
2．掌握圖的鄰接矩陣和鄰接表（含逆鄰接表）存儲方法的構(gòu)造原理及特點(diǎn)。
3．熟練掌握圖的深度優(yōu)先搜索與廣度優(yōu)先搜索過程和算法設(shè)計。
4．掌握最小生成樹和最短路徑的構(gòu)造和算法設(shè)計。
5．掌握AOV網(wǎng)與拓?fù)渑判蚧靖拍钆c求解過程。
（七）查找
1．掌握順序查找、折半查找和分塊查找的查找算法的設(shè)計與算法復(fù)雜性的分析過程。
2．掌握二叉排序樹的概念、構(gòu)造、基本操作及實(shí)現(xiàn)算法的設(shè)計。
3．掌握平衡二叉樹的概念、構(gòu)造、插入和刪除過程。
4．掌握散列(Hash)表的構(gòu)造、散列函數(shù)的構(gòu)造、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計算。
（八）內(nèi)部排序
1．理解排序的基本概念，各種內(nèi)排序方法的基本原理和特點(diǎn)，包括排序過程中進(jìn)行的元素之間的比較次數(shù)，排序總趟數(shù)、排序穩(wěn)定性以及時間復(fù)雜度與空間復(fù)雜度計算。
2．掌握直接插入排序、折半插入排序、選擇排序、起泡排序、希爾排序、快速排序、堆排序、二路歸并排序、基數(shù)排序的排序思想；
3．了解各種內(nèi)部排序算法的應(yīng)用。
四、參考書目
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》 嚴(yán)蔚敏 吳偉民主編 清華大學(xué)出版社
京公安網(wǎng)備11010802020593號
