重慶科技學院2024年考研初試科目考試大綱《數據結構（820）》

考研專業課大綱對備考具有重要價值。大綱可以幫助考生了解考試的整體結構和考查重點，在備考過程中起到明確方向的作用。大綱所列出的考試范圍和知識要點，可以幫助考生建立知識體系，明確重難點，有針對性地進行備考。同時，弄清大綱要求可以讓考生事先了解復習的時間分配和備考要求，避免在備考過程中盲目浪費時間和精力。以下是重慶科技學院2024年碩士研究生招生考試《數據結構（820）》考試大綱具體內容，報考該校計算機專業相關方向的考生可以根據考試大綱備考。

重慶科技學院2024年碩士研究生初試科目考試大綱《數據結構（820）》

一、考試要求：

本課程要求掌握數據結構的基本理論知識，常用數據結構及對應的基本算法及程序實現技能。內容包括線性表、棧、隊列、樹、圖等常見結構的邏輯結構、存儲結構和對應的常用基本算法，以及查找和排序的基本概念和常用算法。了解算法的時間代價和空間代價基本概念。會分析計算機待處理數據的結構特性，以便為應用涉及到的數據選擇適當的邏輯結構、存儲結構，并實現相應算法。

課程考試中既測試對基本知識、基本理論的掌握程度，又測試對基本知識與基本理論的靈活運用能力。

二、考試要點：

1.緒論

（1）數據結構基本概念和術語；

（2）算法描述的方法；

（3）邏輯結構、存儲結構及數據運算三方面的要領及相互關系；

（4）算法復雜度的分析方法。

2.線性表

（1）線性表的邏輯特性；

（2）兩類不同的存儲結構（順序和鏈式存儲結構）的異同；

（3）單鏈表、循環鏈表、雙向鏈表的特點；

（4）線性表在順序存儲結構中實現基本運算（查找、插入、刪除、合并等）的算法及分析；

（5）線性表在鏈式存儲結構中實現基本運算（查找、插入、刪除、合并等）的算法及分析；

（6）用時間和空間復雜度分析線性表的特點。

3.棧和隊列

（1）棧和隊列的基本概念；

（2）棧和隊列在存儲結構上的基本運算的實現；

（3）循環隊列中對邊界條件的處理；

（4）棧的典型應用并能編程實現。

4.串

（1）串的邏輯結構定義；

（2）串的基本運算及其實現；

（3）串的堆分配存儲結構；

（4）串的模式匹配算法。

5.數組和廣義表

（1）數組的邏輯結構和存儲結構；

（2）數組在以行為主的存儲結構中地址的計算方法；

（3）特殊矩陣的壓縮存儲方式及下標變換公式；

（4）稀疏矩陣壓縮存儲方法的特點和適用范圍，三元組表示的稀疏矩陣進行矩陣運算時采用的處理方法。

6.樹和二叉樹

（1）樹的定義和基本術語；

（2）二叉樹的定義；

（3）二叉樹的結構特性及相應的證明方法；

（4）二叉樹的各種存儲結構特點及使用范圍；

（5）二叉樹的各種遍歷算法；

（6）線索二叉樹的定義；

（7）樹的存儲結構；

（8）樹和二叉樹的轉換方法；

（9）最優二叉樹的特性；

（10）建立最優二叉樹和實現Huffman編碼的方法。

7.圖

（1）圖的基本概念；

（2）圖的兩種常用的存儲結構特點及實現；

（3）圖的兩類遍歷算法：深度優先、廣度優先；

（4）圖的應用：最小生成樹、最短路徑的算法實現。

8.查找

（1）靜態查找表和動態查找表的定義；

（2）順序查找、二分查找以及塊查找的基本思想和算法實現；

（3）二叉排序樹的概念及查找過程；

（4）哈希查找的基本思想、哈希函數的構造方法、處理沖突的方法；

（5）各種算法的時間性能（平均查找長度）分析。

9.排序

（1）排序的基本概念、排序算法的穩定性；

（2）冒泡排序、插入排序、選擇排序、快速排序、希爾排序和堆排序的基本思想、排序過程、算法實現、時間和空間性能的比較分析結論；

（3）歸并排序和基數排序的基本思想。

三、參考書目

《數據結構（C語言版）（第2版）》，人民郵電出版社，2016年，ISBN：9787115379504

原文鏈接：https://yjs.cqust.edu.cn/info/1072/4003.htm