西安交通大學

2019年計算機軟件基礎考試大綱

考試科目：數據結構與算法、程序設計基礎

考試形式和試卷結構

一、試卷滿分及考試時間

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

二、試卷內容結構

數據結構與算法                         　約73%

程序設計基礎    　                       約27%

三、試卷題型結構

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

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

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

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

程序設計題                  3-4小題，共40分

數據結構與算法

一、數據結構基本概念

考試內容

數據、數據元素、數據項、數據對象、數據結構的定義；

數據的邏輯結構、數據的物理結構、數據的運算的定義；

數據類型以及抽象數據類型的定義。

考試要求

掌握數據、數據元素、數據項之間的關系；

掌握數據結構的定義；

掌握數據結構的三要素；

掌握數據類型、抽象數據類型和數據結構之間的關系。

二、算法和算法分析

考試內容

    算法的定義、算法的特性、算法的時間復雜度和算法的空間復雜度的定義及計算。

考試要求

了解算法的定義以及特性；

了解衡量算法在資源上的兩個方面；

掌握算法的漸進性分析方法，會用該方法對算法進行評估；

掌握Ο標記法、，理解大Ο標記法的意義；

掌握Ω標記法、，理解大Ω標記法的意義；

掌握Θ標記法、，理解大Θ標記法的意義；

了解時空權衡原則。

三、線性表

考試內容

線性表的定義；

順序表的定義及其特點；

鏈式表的定義及其特點；

線性表的應用。

考試要求

掌握線性表的邏輯結構，以及基本操作；

掌握用順序存儲結構對線性表基本操作的實現；

掌握鏈式存儲結構的實現技術，比如單向鏈表、雙向鏈表、單循環鏈表、雙向循環鏈表以及帶頭節點的鏈表；

掌握鏈式存儲結構對線性表基本操作的實現；

具有在實際中選取不同存儲結構的判斷能力。

四、棧和隊列

考試內容

棧和隊列的定義；

順序棧和鏈式棧的定義及其特點；

順序隊列和鏈式隊列的定義及其特點；

棧和隊列的應用。

考試要求

掌握棧、隊列的邏輯結構，以及基本操作；

掌握順序存儲結構對棧和隊列基本操作的實現；

掌握鏈式存儲結構對棧和隊列基本操作的實現；

掌握順序存儲結構中實現循環隊列的具體要求；

理解遞歸調用和棧之間的關系；

掌握棧和隊列的經典應用。

五、二叉樹、樹和森林

考試內容

二叉樹、樹和森林的定義；

二叉樹的實現（包括順序存儲結構和鏈式存儲結構）、二叉樹的遍歷；

二叉樹結構下的應用，包括二叉檢索樹、Huffman編碼以及堆；

平衡二叉樹的定義、平衡因子的定義以及平衡二叉樹的旋轉操作；

樹和森林的存儲結構、樹和森林的遍歷以及森林與二叉樹的轉換；

并查集抽象數據類型的定義以及實現；

考試要求

掌握二叉樹、樹和森林的定義以及它們之間的異同點；

掌握二叉樹的四種遍歷，并具有能夠依賴遍歷完成對二叉樹進行操作的能力；

理解二叉樹采用順序存儲結構和鏈式存儲結構的差異性；

掌握二叉樹檢索樹、Huffman編碼以及堆的實現；

理解平衡二叉樹的意義；

掌握平衡二叉樹的旋轉操作；

掌握樹、森林能夠采用的各種存儲方式的差異性；

掌握樹和森林與二叉樹的轉換；

掌握樹、森林在遍歷方面和二叉樹的不同以及相關性；

理解并查集的意義，以及掌握并查集的基本操作的實現。

六、圖

考試內容

圖的定義；

圖的實現（包括鄰接矩陣和鄰接表）和基本操作；

圖的兩種遍歷；

圖的基本應用，包括最小支撐樹、最短路徑、拓撲排序和關鍵路徑。

考試要求

掌握圖的定義，包括完全圖、連通圖、簡單路徑、有向圖、無向圖、無環圖等，明確理解圖和二叉樹、樹和森林這種結構之間的異同點；

掌握圖采用鄰接矩陣和鄰接表進行存儲的差異性；

掌握廣度優先遍歷和深度優先遍歷；

掌握最小支撐樹（Prim算法、Kruskal算法）、最短路徑（Dijkstra算法）、拓撲排序以及關鍵路徑的實現過程。

七、查找

考試內容

查找的定義；

查找的如下算法：順序查找法、折半查找法、散列（Hash）技術。

考試要求

理解查找的定義；

掌握對查找算法進行衡量的一些指標：平均查找長度、成功查找的查找長度、不成功查找的查找長度；

掌握順序查找法和折半查找法，并理解二者之間的異同點；

掌握散列技術，包括散列函數、散列表、散列沖突的發生及其解決和負載因子；

理解不同查找技術的優缺點。

八、排序

考試內容

排序的定義，包括內排序和外排序；

排序的穩定性定義；

直接插入排序、冒泡排序、簡單選擇排序、Shell排序、快速排序、堆排序、歸并排序、基數排序、K路歸并排序的排序過程。

考試要求

理解內排序和外排序的區別；

掌握排序的穩定性；

對直接插入排序、冒泡排序、簡單選擇排序、Shell排序、快速排序、堆排序、歸并排序、基數排序這些算法，掌握其在時間復雜度、空間復雜度以及是否穩定等方面的特點；

了解K路歸并的外排序算法；

具有在不同的應用需求下，能夠根據各種排序算法特點選擇合適排序算法的能力。

九、矩陣和串

考試內容

矩陣和串的定義；

特殊矩陣的壓縮存儲、稀疏矩陣的三元組表示法；

串的模式匹配。

考試要求

掌握特殊矩陣的壓縮存儲方法；

掌握稀疏矩陣的三元組表示法以及相應的操作；

掌握多維數組和一維數組的映射；

掌握模式匹配的兩個算法：Brute-Force和KMP。

程序設計基礎

一、基本輸入輸出

考試內容

控制臺形式的輸入語法；

控制臺形式的輸出語法；

考試要求

掌握對不同類型數據的控制臺輸入方法；

掌握對不同類型數據的控制臺輸出方法，包括一些輸出格式。

二、數據類型及運算

考試內容

相應編程語言內置的數據類型的使用；

相應編程語言內置的運算符的使用；

相應編程語言對自定義數據類型的語法。

考試要求

掌握語言內置的數據類型的正確定義、聲明和使用；

掌握語言內置的運算符的正確使用；

具有自定義數據類型的能力。

三、語句

考試內容

順序語句、選擇語句和循環語句。

考試要求

掌握相應語言對順序語句、選擇語句和循環語句的語法以及運用。

四、函數

考試內容

函數的語法定義；

函數的嵌套調用，特別包括遞歸調用。

考試要求

掌握相應語言對函數定義的語法；

掌握遞歸思想，具有能夠合理使用函數遞歸調用完成算法設計與實現的能力。