西安交通大學(xué)

從西安交通大學(xué)研究生招生信息網(wǎng)獲悉，2021年全國碩士研究生招生考試西安交通大學(xué)915計算機軟件基礎(chǔ)（含數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計）參考書目及考試大綱公布，內(nèi)容如下：

2021年計算機軟件基礎(chǔ)考試大綱

考試科目：數(shù)據(jù)結(jié)構(gòu)與算法、程序設(shè)計基礎(chǔ)

考試形式和試卷結(jié)構(gòu)

一、試卷滿分及考試時間

試卷滿分為150分，考試時間為180分鐘。

二、試卷內(nèi)容結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)與算法                         　約73%

程序設(shè)計基礎(chǔ)    　                       約27%

三、試卷題型結(jié)構(gòu)

單項選擇題                   10小題，每小題2分，共20分

填空題                        5小題，每小題2分，共10分

判斷題                        5小題，每小題2分，共10分

解答題                      7-8小題，共70分

程序設(shè)計題                  3-4小題，共40分

數(shù)據(jù)結(jié)構(gòu)與算法

一、數(shù)據(jù)結(jié)構(gòu)基本概念
考試內(nèi)容
數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)的定義；
數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)的運算的定義；
數(shù)據(jù)類型以及抽象數(shù)據(jù)類型的定義。

考試要求
掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關(guān)系；
掌握數(shù)據(jù)結(jié)構(gòu)的定義；
掌握數(shù)據(jù)結(jié)構(gòu)的三要素；
掌握數(shù)據(jù)類型、抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系。

二、算法和算法分析
考試內(nèi)容
    算法的定義、算法的特性、算法的時間復(fù)雜度和算法的空間復(fù)雜度的定義及計算。

考試要求
了解算法的定義以及特性；
了解衡量算法在資源上的兩個方面；
掌握算法的漸進(jìn)性分析方法，會用該方法對算法進(jìn)行評估；
掌握Ο標(biāo)記法、，理解大Ο標(biāo)記法的意義；
掌握Ω標(biāo)記法、，理解大Ω標(biāo)記法的意義；
掌握Θ標(biāo)記法、，理解大Θ標(biāo)記法的意義；
了解時空權(quán)衡原則。

三、線性表
考試內(nèi)容
線性表的定義；
順序表的定義及其特點；
鏈?zhǔn)奖淼亩�義及其特點；
線性表的應(yīng)用。

考試要求
掌握線性表的邏輯結(jié)構(gòu)，以及基本操作；
掌握用順序存儲結(jié)構(gòu)對線性表基本操作的實現(xiàn)；
掌握鏈?zhǔn)酱鎯�結(jié)構(gòu)的實現(xiàn)技術(shù)，比如單向鏈表、雙向鏈表、單循環(huán)鏈表、雙向循環(huán)鏈表以及帶頭節(jié)點的鏈表；
掌握鏈?zhǔn)酱鎯�結(jié)構(gòu)對線性表基本操作的實現(xiàn)；
具有在實際中選取不同存儲結(jié)構(gòu)的判斷能力。

四、棧和隊列
考試內(nèi)容
棧和隊列的定義；
順序棧和鏈?zhǔn)綏５亩�義及其特點；
順序隊列和鏈?zhǔn)疥犃械亩�義及其特點；
棧和隊列的應(yīng)用。

考試要求
掌握棧、隊列的邏輯結(jié)構(gòu)，以及基本操作；
掌握順序存儲結(jié)構(gòu)對棧和隊列基本操作的實現(xiàn)；
掌握鏈?zhǔn)酱鎯�結(jié)構(gòu)對棧和隊列基本操作的實現(xiàn)；
掌握順序存儲結(jié)構(gòu)中實現(xiàn)循環(huán)隊列的具體要求；
理解遞歸調(diào)用和棧之間的關(guān)系；
掌握棧和隊列的經(jīng)典應(yīng)用。

五、二叉樹、樹和森林
考試內(nèi)容
二叉樹、樹和森林的定義；
二叉樹的實現(xiàn)（包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu)）、二叉樹的遍歷；
二叉樹結(jié)構(gòu)下的應(yīng)用，包括二叉檢索樹、Huffman編碼以及堆；
平衡二叉樹的定義、平衡因子的定義以及平衡二叉樹的旋轉(zhuǎn)操作；
樹和森林的存儲結(jié)構(gòu)、樹和森林的遍歷以及森林與二叉樹的轉(zhuǎn)換；
并查集抽象數(shù)據(jù)類型的定義以及實現(xiàn)；

考試要求
掌握二叉樹、樹和森林的定義以及它們之間的異同點；
掌握二叉樹的四種遍歷，并具有能夠依賴遍歷完成對二叉樹進(jìn)行操作的能力；
理解二叉樹采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu)的差異性；
掌握二叉樹檢索樹、Huffman編碼以及堆的實現(xiàn)；
理解平衡二叉樹的意義；
掌握平衡二叉樹的旋轉(zhuǎn)操作；
掌握樹、森林能夠采用的各種存儲方式的差異性；
掌握樹和森林與二叉樹的轉(zhuǎn)換；
掌握樹、森林在遍歷方面和二叉樹的不同以及相關(guān)性；
理解并查集的意義，以及掌握并查集的基本操作的實現(xiàn)。

六、圖
考試內(nèi)容
圖的定義；
圖的實現(xiàn)（包括鄰接矩陣和鄰接表）和基本操作；
圖的兩種遍歷；
圖的基本應(yīng)用，包括最小支撐樹、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑。

考試要求
掌握圖的定義，包括完全圖、連通圖、簡單路徑、有向圖、無向圖、無環(huán)圖等，明確理解圖和二叉樹、樹和森林這種結(jié)構(gòu)之間的異同點；
掌握圖采用鄰接矩陣和鄰接表進(jìn)行存儲的差異性；
掌握廣度優(yōu)先遍歷和深度優(yōu)先遍歷；
掌握最小支撐樹（Prim算法、Kruskal算法）、最短路徑（Dijkstra算法、Floyd算法）、拓?fù)渑判蛞约瓣P(guān)鍵路徑的實現(xiàn)過程。

七、查找
考試內(nèi)容
查找的定義；
查找的如下算法：順序查找法、折半查找法、散列（Hash）技術(shù)。

考試要求
理解查找的定義；
掌握對查找算法進(jìn)行衡量的一些指標(biāo)：平均查找長度、成功查找的查找長度、不成功查找的查找長度；
掌握順序查找法和折半查找法，并理解二者之間的異同點；
掌握散列技術(shù)，包括散列函數(shù)、散列表、散列沖突的發(fā)生及其解決方法、以及負(fù)載因子；
理解不同查找技術(shù)的優(yōu)缺點。

八、排序
考試內(nèi)容
排序的定義，包括內(nèi)排序和外排序；
排序的穩(wěn)定性定義；
直接插入排序、冒泡排序、簡單選擇排序、Shell排序、快速排序、堆排序、歸并排序、基數(shù)排序、K路歸并排序的排序過程。

考試要求
理解內(nèi)排序和外排序的區(qū)別；
掌握排序的穩(wěn)定性；
對直接插入排序、冒泡排序、簡單選擇排序、Shell排序、快速排序、堆排序、歸并排序、基數(shù)排序這些算法，掌握其在時間復(fù)雜度、空間復(fù)雜度以及是否穩(wěn)定等方面的特點；
了解K路歸并的外排序算法；
具有在不同的應(yīng)用需求下，能夠根據(jù)各種排序算法特點選擇合適排序算法的能力。

九、矩陣和串
考試內(nèi)容
矩陣和串的定義；
特殊矩陣的壓縮存儲、稀疏矩陣的三元組表示法；
串的模式匹配。

考試要求
掌握特殊矩陣的壓縮存儲方法；
掌握稀疏矩陣的三元組表示法以及相應(yīng)的操作；
掌握多維數(shù)組和一維數(shù)組的映射；
掌握模式匹配的兩個算法：Brute-Force和KMP。

程序設(shè)計基礎(chǔ)
一、基本輸入輸出
考試內(nèi)容
控制臺形式的輸入語法；
控制臺形式的輸出語法；

考試要求
掌握對不同類型數(shù)據(jù)的控制臺輸入方法；
掌握對不同類型數(shù)據(jù)的控制臺輸出方法，包括一些輸出格式。

二、數(shù)據(jù)類型及運算
考試內(nèi)容
相應(yīng)編程語言內(nèi)置的數(shù)據(jù)類型的使用；
相應(yīng)編程語言內(nèi)置的運算符的使用；
相應(yīng)編程語言對自定義數(shù)據(jù)類型的語法。
考試要求
掌握語言內(nèi)置的數(shù)據(jù)類型的正確定義、聲明和使用；
掌握語言內(nèi)置的運算符的正確使用；
具有自定義數(shù)據(jù)類型的能力。

三、語句
考試內(nèi)容
順序語句、選擇語句和循環(huán)語句。

考試要求
掌握相應(yīng)語言對順序語句、選擇語句和循環(huán)語句的語法以及運用。

四、函數(shù)
考試內(nèi)容
函數(shù)的語法定義；
函數(shù)的嵌套調(diào)用，特別包括遞歸調(diào)用。

考試要求
掌握相應(yīng)語言對函數(shù)定義的語法；
掌握遞歸思想，具有能夠合理使用函數(shù)遞歸調(diào)用完成算法設(shè)計與實現(xiàn)的能力。