重慶科技學(xué)院2024年考研初試科目考試大綱《數(shù)據(jù)結(jié)構(gòu)（820）》

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

重慶科技學(xué)院2024年碩士研究生初試科目考試大綱《數(shù)據(jù)結(jié)構(gòu)（820）》

一、考試要求：

本課程要求掌握數(shù)據(jù)結(jié)構(gòu)的基本理論知識，常用數(shù)據(jù)結(jié)構(gòu)及對應(yīng)的基本算法及程序?qū)崿F(xiàn)技能。內(nèi)容包括線性表、棧、隊列、樹、圖等常見結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對應(yīng)的常用基本算法，以及查找和排序的基本概念和常用算法。了解算法的時間代價和空間代價基本概念。會分析計算機(jī)待處理數(shù)據(jù)的結(jié)構(gòu)特性，以便為應(yīng)用涉及到的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)，并實現(xiàn)相應(yīng)算法。

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

二、考試要點：

1.緒論

（1）數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語；

（2）算法描述的方法；

（3）邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算三方面的要領(lǐng)及相互關(guān)系；

（4）算法復(fù)雜度的分析方法。

2.線性表

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

（2）兩類不同的存儲結(jié)構(gòu)（順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)）的異同；

（3）單鏈表、循環(huán)鏈表、雙向鏈表的特點；

（4）線性表在順序存儲結(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析；

（5）線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析；

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

3.棧和隊列

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

（2）棧和隊列在存儲結(jié)構(gòu)上的基本運算的實現(xiàn)；

（3）循環(huán)隊列中對邊界條件的處理；

（4）棧的典型應(yīng)用并能編程實現(xiàn)。

4.串

（1）串的邏輯結(jié)構(gòu)定義；

（2）串的基本運算及其實現(xiàn)；

（3）串的堆分配存儲結(jié)構(gòu)；

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

5.數(shù)組和廣義表

（1）數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；

（2）數(shù)組在以行為主的存儲結(jié)構(gòu)中地址的計算方法；

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

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

6.樹和二叉樹

（1）樹的定義和基本術(shù)語；

（2）二叉樹的定義；

（3）二叉樹的結(jié)構(gòu)特性及相應(yīng)的證明方法；

（4）二叉樹的各種存儲結(jié)構(gòu)特點及使用范圍；

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

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

（7）樹的存儲結(jié)構(gòu)；

（8）樹和二叉樹的轉(zhuǎn)換方法；

（9）最優(yōu)二叉樹的特性；

（10）建立最優(yōu)二叉樹和實現(xiàn)Huffman編碼的方法。

7.圖

（1）圖的基本概念；

（2）圖的兩種常用的存儲結(jié)構(gòu)特點及實現(xiàn)；

（3）圖的兩類遍歷算法：深度優(yōu)先、廣度優(yōu)先；

（4）圖的應(yīng)用：最小生成樹、最短路徑的算法實現(xiàn)。

8.查找

（1）靜態(tài)查找表和動態(tài)查找表的定義；

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

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

（4）哈希查找的基本思想、哈希函數(shù)的構(gòu)造方法、處理沖突的方法；

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

9.排序

（1）排序的基本概念、排序算法的穩(wěn)定性；

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

（3）歸并排序和基數(shù)排序的基本思想。

三、參考書目

《數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）》，人民郵電出版社，2016年，ISBN：9787115379504

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