西安交通大學(xué)

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

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

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

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

一、試卷滿分及考試時(shí)間

試卷滿分為150分，考試時(shí)間為180分鐘。

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

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

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

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

單項(xiàng)選擇題                   10小題，每小題2分，共20分

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

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

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

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

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

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

考試要求
掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(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)容
    算法的定義、算法的特性、算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度的定義及計(jì)算。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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