2016江西理工大學計算機技術碩士考試大綱

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 江西理工大學2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

085211計算機技術碩士考試大綱

業務課（自命題）考試大綱

《數據結構》

Ⅰ考試性質

普通高等學校專業碩士生招生考試。

Ⅲ考試形式及題型分值

(4)考試形式：閉卷、筆試。

(6)題型分值：單項選擇題、填空題、判斷對錯題、應用題、程序閱讀題、算法設計題。滿分150分，考試時間180分鐘。

Ⅲ考試內容

要求掌握基本數據結構（線性表、棧與隊列、數組、二叉樹、圖等）的特點及其不同實現，掌握常用的算法，同時對算法的時間復雜度有一定的分析能力，并考察學生能否運用數據結構解決實際問題的能力。具體知識點和考核要求如下：

(10)緒論

64掌握數據、數據元素、數據項、數據類型等基本概念和術語；

65掌握數據結構的四種邏輯結構和兩種存儲結構表示方法及其關系；

66理解算法五個要素；

68掌握算法設計的基本要求以及語句頻度和算法時間復雜度的計算方法。

(11)線性表

69深刻理解線性結構及線性表；

70熟練掌握順序表和單鏈表的組織方法；

71熟練掌握線性表在順序存儲結構和鏈式存儲結構上的查找、插入及刪除算法；

72了解順序表與鏈表的特點；

73了解循環鏈表及雙鏈表的組織方法和特點。

(12)棧和隊列

75理解棧和隊列的定義、特點及與線性表的異同；

78掌握順序棧的組織方法及進棧、退棧等基本算法，弄清棧滿和棧空的條件及利用棧解決簡單的實際問題，如：數制轉換、表達式求值等；

79掌握鏈棧的組織方法及進棧、退棧等基本算法；

80掌握鏈隊列上實現的入隊、出隊等基本算法；

83掌握循環隊列上實現的入隊、出隊等基本算法，及隊滿、隊空的條件，弄清順序隊列的“假溢出”現象及其原因。

(13)串

84掌握串的有關概念和術語、串的邏輯結構和特點；

85掌握串的存儲結構；

86掌握模式匹配的定義及KMP算法。

(14)數組和廣義表

87掌握多維數組存在一維數組中的兩種存儲表示方法并綜合運用數組在以行為主的存儲結構中的地址計算方法；

89掌握對特殊矩陣(對稱矩陣,下三角矩陣等)進行壓縮存儲時的下標變換公式；

90了解稀疏矩陣的三元組壓縮存儲表示方法及有關算法；

91理解并掌握廣義表的定義、存儲結構。

(15)樹和二叉樹

92理解樹的概念并熟悉有關術語的含義（如孩子、兄弟、深度、度等概念）；

94深刻領會二叉樹的定義和結構特性，了解相應的證明方法；

95理解常見的二叉樹（如滿二叉樹、完全二叉樹）的概念；

96深刻領會二叉樹的順序存儲和鏈式存儲結構；

97熟悉二叉樹的遍歷次序并熟練掌握遍歷算法；

98掌握二叉樹線索化的實質及線索化的過程；

99了解樹和森林的定義、樹的存儲結構并掌握樹、森林與二叉樹之間的相互轉換方法；

100掌握赫夫曼（Huffman）樹的概念及其構造赫夫曼樹的方法。

(16)圖

101理解圖的概念并熟悉有關術語（如：頂點、邊、有向圖、無向圖、入度、出度、連通性與生成樹等）；

102熟練掌握鄰接矩陣表示法和鄰接表表示法；

104掌握連通圖遍歷的基本思想和算法（深度優先和廣度優先），能夠給出兩種遍歷的頂點訪問序列；

105掌握非連通圖的遍歷方法及圖的連通分量的求法；

106理解最小生成樹的概念及普里姆（Prim）算法和克魯斯卡爾算法（Kruskal）,并能根據算法用圖示法表示出給定網的一棵最小生成樹的過程；

107了解AOE有向無環網的關鍵路徑,關鍵活動的計算思路；

109掌握拓撲排序的基本思想，對給定的有向圖（若拓撲序列存在）能夠寫出所有拓撲序列；

110掌握求單源點最短距離的狄克斯特拉（Dijkstra）算法。

(17)查找

111熟練掌握順序查找算法、折半查找算法；

112掌握查找效率的計算方法-平均查找長度；

113理解二叉排序樹的構造和查找算法；

116掌握哈希表、哈希函數的構造方法、以及處理沖突的方法。

(18)內部排序

117理解內部排序的定義和各種排序算法的基本思想及其特點；

124了解各種內部排序（插入，希爾，選擇，冒泡，快速，堆，歸并等排序）的排序過程及其依據的原則；

125一般了解排序方法“穩定”的含義；

126了解各種內部排序算法的優缺點、各種排序算法的時間花費。