2023年?yáng)|北石油大學(xué)計(jì)算機(jī)技術(shù)考研初試820考試大綱

考研考試大綱一般是由各個(gè)院校自行發(fā)布，內(nèi)容包含考試科目的考試范圍、試卷結(jié)構(gòu)、考試形式和主要參考資料等等。考試大綱對(duì)考生來(lái)說(shuō)至關(guān)重要，以下是希賽網(wǎng)小編為大家整理的2023年?yáng)|北石油大學(xué)計(jì)算機(jī)技術(shù)（085404）考研初試820數(shù)據(jù)結(jié)構(gòu)的考試大綱，僅供大家參考。

相關(guān)推薦：2021-2022年分?jǐn)?shù)線 | 研究方向一覽表 | 考試科目 | 學(xué)費(fèi)匯總 | 招生人數(shù) | 歷年真題

（注：以下信息來(lái)自學(xué)院官網(wǎng)，僅供參考，具體內(nèi)容以院校發(fā)布為準(zhǔn)）

820 數(shù)據(jù)結(jié)構(gòu)一初試考試大綱

命題單位：計(jì)算機(jī)與信息技術(shù)學(xué)院

考試科目代碼：820

考試科目名稱：數(shù)據(jù)結(jié)構(gòu)

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

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

二、答題方式

答題方式為閉卷、筆試。

三、答題內(nèi)容結(jié)構(gòu)

線性表20%，樹20%，圖20%，查找20%，排序20%。

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

1.單選題，共10小題，每題1分，共10分;

2.簡(jiǎn)答題，共6小題，每題8分，共48分;

3.算法設(shè)計(jì)題，共5小題，分?jǐn)?shù)分別為13分、13分、22分、22分、22分，共92分。

五、考試內(nèi)容知識(shí)點(diǎn)說(shuō)明

(一)線性表

考試內(nèi)容：線性表的定義;線性表的抽象數(shù)據(jù)類型定義、數(shù)學(xué)表示及含義;線性表常用的基本運(yùn)算;線性表的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn);線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)。

考試要求：了解線性表的邏輯結(jié)構(gòu)和常用的一些運(yùn)算，掌握線性表的兩種存儲(chǔ)結(jié)構(gòu)及其用法，掌握這兩種存儲(chǔ)結(jié)構(gòu)各自的優(yōu)缺點(diǎn)。在算法實(shí)現(xiàn)方面，要求能夠根據(jù)實(shí)際問(wèn)題的需求來(lái)決定采用何種存儲(chǔ)結(jié)構(gòu)并給出具體的算法，如：插入、刪除滿足條件的鏈表節(jié)點(diǎn)，在鏈表上排序等。

(二)棧和隊(duì)列

考試內(nèi)容：棧的定義，邏輯結(jié)構(gòu)和常用運(yùn)算;棧的存儲(chǔ)結(jié)構(gòu);棧的實(shí)際應(yīng)用;棧與遞歸的關(guān)系;隊(duì)列的定義及存儲(chǔ)結(jié)構(gòu);隊(duì)列的應(yīng)用。

考試要求：了解棧和隊(duì)列的邏輯結(jié)構(gòu)定義，掌握棧和隊(duì)列運(yùn)算特點(diǎn)，掌握棧和遞歸的關(guān)系，掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。在算法實(shí)現(xiàn)方面，要求可以熟練利用棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)解決實(shí)際的問(wèn)題，如：走迷宮問(wèn)題、表達(dá)式括號(hào)匹配問(wèn)題等。

(三)串

考試內(nèi)容：串的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn);串的模式匹配;KMP算法

考試要求：掌握字符串的兩種存儲(chǔ)結(jié)構(gòu)，即定長(zhǎng)存儲(chǔ)結(jié)構(gòu)和堆存儲(chǔ)結(jié)構(gòu)，能夠在兩中存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)字符串的各種運(yùn)算，掌握字符串的模式匹配運(yùn)算及相應(yīng)的改進(jìn)算法。

(四)數(shù)組和廣義表

考試內(nèi)容：數(shù)組的邏輯結(jié)構(gòu)定義，數(shù)據(jù)的特點(diǎn);數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu);稀疏矩陣的壓縮存儲(chǔ);廣義表的定義及存儲(chǔ)結(jié)構(gòu)

考試要求：了解數(shù)組及廣義表的定義及特點(diǎn)，掌握數(shù)組的特點(diǎn)、存儲(chǔ)結(jié)構(gòu)及廣義表的實(shí)際應(yīng)用，掌握稀疏矩陣的壓縮存儲(chǔ)方法，能夠在壓縮存儲(chǔ)下實(shí)現(xiàn)矩陣的各種運(yùn)算。

(五)樹和二叉樹

考試內(nèi)容：樹和二叉樹的定義;二叉樹的性質(zhì);樹和二叉樹的存儲(chǔ)結(jié)構(gòu);二叉樹和樹的遍歷，線索二叉樹，二叉樹的層序遍歷;哈夫曼樹及其應(yīng)用。

考試要求：了解樹的邏輯結(jié)構(gòu)定義，掌握二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算，掌握樹和二叉樹之間的關(guān)系。在算法實(shí)現(xiàn)方面，要求熟練掌握二叉樹的遞歸和非遞歸遍歷，并能夠用之解決實(shí)際問(wèn)題，如：計(jì)算樹的層數(shù)、度，查找滿足條件的節(jié)點(diǎn)等。

(六)圖

考試內(nèi)容：圖的定義及基本術(shù)語(yǔ);圖的存儲(chǔ)結(jié)構(gòu);圖的兩種遍歷方法及算法;圖的連通性;拓?fù)渑判蚝完P(guān)鍵路徑;最短路徑;最小生成樹。

考試要求：了解圖的邏輯結(jié)構(gòu)定義，掌握?qǐng)D的術(shù)語(yǔ)、圖的兩種常用存儲(chǔ)結(jié)構(gòu)，即鄰接矩陣和鄰接表。在算法實(shí)現(xiàn)方面，要求熟練掌握?qǐng)D的兩種遍歷方法，并能夠根據(jù)圖的基本原理解決一些應(yīng)用問(wèn)題，如：判定圖的連通性、判定是否有環(huán)、計(jì)算特定路徑等。

(七)查找

考試內(nèi)容：查找方法的分類;各類查找表常用的查找方法;典型查找方法的算法實(shí)現(xiàn)。

考試要求：了解動(dòng)態(tài)查找表和靜態(tài)查找表的邏輯結(jié)構(gòu)定義，掌握靜態(tài)查找表的三類查找方法的思想，對(duì)數(shù)據(jù)元素的要求、數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，平均查找長(zhǎng)度。掌握二叉排序樹的定義及構(gòu)造方法，二叉樹的平衡化處理。掌握散列表的定義及創(chuàng)建散列表的方法，以及查找散列表的方法。在算法實(shí)現(xiàn)方面，要求可以利用各種查找算法解決實(shí)際問(wèn)題。

(八)內(nèi)排序

考試內(nèi)容：排序的基本概念，排序方法分類的依據(jù);插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序中各種常用的排序方法。

考試要求：了解排序的定義及術(shù)語(yǔ)，排序方法的評(píng)價(jià)方法，掌握的排序方法有：直接插入排序、shell插入排序，快速排序，堆排序，二路歸并排序，鏈?zhǔn)交鶖?shù)排序，要知道它們的排序思想，并能描述排序過(guò)程。在算法實(shí)現(xiàn)方面，要求可以利用各種排序算法解決實(shí)際問(wèn)題。

六、參考書

1.嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) [M].清華大學(xué)出版社，1997

數(shù)據(jù)來(lái)源：計(jì)算機(jī)與信息技術(shù)學(xué)院2023年碩士研究生招生考試初試自命題科目