東北石油大學(xué)2018年碩士研究生入學(xué)統(tǒng)一考試計算機(jī)與信息技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)自命題科目考試大綱

1、東北石油大學(xué)東北石油大學(xué)20182018年碩士研究生入學(xué)統(tǒng)一考試計算機(jī)與信年碩士研究生入學(xué)統(tǒng)一考試計算機(jī)與信息技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)自命題科目考試大綱息技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)自命題科目考試大綱命題單位：計算機(jī)與信息技術(shù)學(xué)院考試科目代碼：820考試科目名稱：數(shù)據(jù)結(jié)構(gòu)一、試卷滿分及考試時間一、試卷滿分及考試時間試卷滿分為150分，考試時間為180分鐘。二、答題方式二、答題方式答題方式為閉卷、筆試。三、試卷內(nèi)容結(jié)構(gòu)三、試卷內(nèi)容結(jié)構(gòu)線性表25%，樹25%，

2、圖30%，查找10%，排序10%。四、試卷題型結(jié)構(gòu)四、試卷題型結(jié)構(gòu)試卷題型結(jié)構(gòu)為：單選題10小題，每題1分，共10分；簡答題6小題，每題8分，共48分；算法設(shè)計題，共5小題，分?jǐn)?shù)分別為14分、16分、20分、20分、22分，共92分。五、考試內(nèi)容及知識點(diǎn)說明五、考試內(nèi)容及知識點(diǎn)說明（一）線性表考試內(nèi)容：線性表的定義；線性表的抽象數(shù)據(jù)類型定義、數(shù)學(xué)表示及含義；線性表常用的基本運(yùn)算；線性表的順序存儲結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)；線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

3、及基本運(yùn)算的實(shí)現(xiàn)。考試要求：了解線性表的邏輯結(jié)構(gòu)和常用的一些運(yùn)算，掌握線性表的兩種存儲結(jié)構(gòu)及其用法，掌握這兩種存儲結(jié)構(gòu)各自的優(yōu)缺點(diǎn)。在算法實(shí)現(xiàn)方面要求，能夠根據(jù)實(shí)際問題的需求來決定采用何（五）樹和二叉樹考試內(nèi)容：樹和二叉樹的定義；二叉樹的性質(zhì)；樹和二叉樹的存儲結(jié)構(gòu)；二叉樹和樹的遍歷，線索二叉樹，二叉樹的層序遍歷；哈夫曼樹及其應(yīng)用?？荚囈螅毫私鈽涞倪壿嫿Y(jié)構(gòu)定義，掌握二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)和運(yùn)算，掌握樹和二叉樹之間的關(guān)系。在算法實(shí)現(xiàn)

4、方面要求，熟練掌握二叉樹的遞歸和非遞歸遍歷，并能夠用之解決實(shí)際問題，如：計算樹的層數(shù)、度，查找滿足條件的節(jié)點(diǎn)等。（六）圖考試內(nèi)容：圖的定義及基本術(shù)語；圖的存儲結(jié)構(gòu)；圖的兩種遍歷方法及算法；圖的連通性；拓?fù)渑判蚝完P(guān)鍵路徑；最短路徑；最小生成樹?？荚囈螅毫私鈭D的邏輯結(jié)構(gòu)定義，掌握圖的術(shù)語、圖的兩種常用存儲結(jié)構(gòu)，即鄰接矩陣和鄰接表。在算法實(shí)現(xiàn)方面要求，熟練掌握圖的兩種遍歷方法，并能夠根據(jù)圖的基本原理解決一些應(yīng)用問題，如：判定圖的連通性、判定