附件2：

    中南民族大學2021年碩士研究生入學考試自命題科目考試大綱

    （計算機科學學院）

    科目名稱：計算機專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計與分析、C語言程序設(shè)計）

    科目代碼：842

    適用學科（類別）專業(yè)（領(lǐng)域）：計算機科學與技術(shù)、電子信息（計算機技術(shù)方向）

    ……………………………………………………………

    一、考試性質(zhì)

    計算機專業(yè)基礎(chǔ)綜合是為招收計算機科學與技術(shù)學科、電子信息的碩士研究生而設(shè)置的具有選拔性質(zhì)的考試科目，其目的是科學、公平、有效地測試考生掌握計算機科學與技術(shù)學科大學本科階段專業(yè)知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術(shù)學科優(yōu)秀本科畢業(yè)生所能達到的及格或及格以上水平，確保碩士研究生的招生質(zhì)量。

    二、考查目標

    要求考生比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計與分析和C語言程序設(shè)計的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際應(yīng)用問題。

    三、考試形式和試卷結(jié)構(gòu)

    1.試卷滿分及考試時間

    本試卷滿分為150分，考試時間為180分鐘。

    2.考試方式為閉卷、筆試。

    3.試卷考查的題型及其比例

    單項選擇題約40分

    簡答題約30分

    綜合分析題約50分

    算法設(shè)計題約30分

    四、考查內(nèi)容

    【考查目標】

    1.掌握數(shù)據(jù)結(jié)構(gòu)、算法的基本概念、基本原理和基本方法。

    2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度的分析。

    3.能夠運用數(shù)據(jù)結(jié)構(gòu)、算法的基本原理和方法進行問題的分析與求解，具備采用C或C++語言設(shè)計與實現(xiàn)算法的能力。

    一、線性表

    (一)線性表的定義和基本操作(二)線性表的實現(xiàn)

    1.順序存儲

    2.鏈式存儲

    3.線性表的應(yīng)用二、棧、隊列

    (一)棧和隊列的基本概念

    (二)棧和隊列的順序存儲結(jié)構(gòu)(三)棧和隊列的鏈式存儲結(jié)構(gòu)(四)棧和隊列的應(yīng)用

    三、串、數(shù)組

    (一)串的存儲表示

    (二)串的模式匹配算法(三)數(shù)組的順序存儲

    (四)特殊矩陣的壓縮存儲四、樹與二叉樹

    (一)樹的基本概念(二)二叉樹

    1.二叉樹的定義及其主要特征

    2.二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

    3.二叉樹的遞歸與非遞歸遍歷

    4.線索二叉樹的基本概念和構(gòu)造(三)樹、森林

    1.樹的存儲結(jié)構(gòu)

    2.森林與二叉樹的轉(zhuǎn)換

    3.樹和森林的遍歷(四)樹與二叉樹的應(yīng)用

    1.哈夫曼(Huffman)樹和哈夫曼編碼五、圖

    (一)圖的基本概念

    (二)圖的存儲及基本操作1.鄰接矩陣法

    2.鄰接表法

    3.鄰接多重表、十字鏈表(三)圖的遍歷

    1.深度優(yōu)先搜索

    2.廣度優(yōu)先搜索(四)圖的基本應(yīng)用

    1.最小(代價)生成樹

    2.最短路徑

    3.拓撲排序

    4.關(guān)鍵路徑六、查找

    (一)查找的基本概念(二)線性表的查找

    1.順序查找法

    2.折半查找法

    3.分塊查找法(三)樹表的查找

    1.二叉排序樹

    2.平衡二叉樹

    3.B-樹

    4.B+樹

    (四)散列(Hash)表的查找

    (五)查找算法的分析及應(yīng)用七、排序

    (一)排序的基本概念(二)插入排序

    1.直接插入排序

    2.折半插入排序

    3.希爾排序(三)交換排序

    1.冒泡排序

    2.快速排序

    (四)選擇排序

    1.簡單選擇排序

    2.堆排序

    (五)二路歸并排序(六)基數(shù)排序

    (七)外部排序

    (八)各種排序算法的比較(九)排序算法的應(yīng)用

    八、算法基礎(chǔ)

    （一）算法的概念、特征

    （二）算法分析基礎(chǔ)

    1.非遞歸算法的分析框架及應(yīng)用

    2.遞歸算法的分析框架及應(yīng)用

    3.三個漸進符號的意義及應(yīng)用

    （三）算法設(shè)計技巧

    1.蠻力法（基本思想）

    2.分治法（基本思想、主定理、具體應(yīng)用）

    3.減治法（基本思想、三個變種、具體應(yīng)用）

    4.變治法（基本思想、三個變種、具體應(yīng)用）

    5.動態(tài)規(guī)劃（基本思想、主要步驟、具體應(yīng)用）

    6.貪心法（基本思想、具體應(yīng)用）九、C語言程序設(shè)計部分

    （一）C語言基礎(chǔ)知識

    1.C數(shù)據(jù)類型、表達式、輸入輸出2.選擇控制結(jié)構(gòu)、循環(huán)控制結(jié)構(gòu)3.函數(shù)

    4.數(shù)組

    5.指針

    （二）C語言高級知識

    1.指針和數(shù)組

    2.指針和字符串

    3.結(jié)構(gòu)體和共用體

    （三）文件操作

    五、參考書目

    1.嚴蔚敏,李冬梅,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）.人民郵電出版社.2015

    2.萊維汀著，潘彥譯.算法設(shè)計與分析基礎(chǔ)(第3版).清華大學出版社.2015

    3.蘇小紅，王宇穎，孫志崗.C語言程序設(shè)計(第3版).高等教育出版社.2015

    六、特殊說明

    本自命題考試科目無需計算器。

添加中南民族大學學姐微信，或微信搜索公眾號“考研派小站”，關(guān)注[考研派小站]微信公眾號，在考研派小站微信號輸入[中南民族大學考研分數(shù)線、中南民族大學報錄比、中南民族大學考研群、中南民族大學學姐微信、中南民族大學考研真題、中南民族大學專業(yè)目錄、中南民族大學排名、中南民族大學保研、中南民族大學公眾號、中南民族大學研究生招生）]即可在手機上查看相對應(yīng)中南民族大學考研信息或資源。