2020年吉林大學珠海學院本科插班生招生入學考試《軟件工程》專業考試大綱

2020-02-01 11:41:27網絡整理

　　考試科目名稱：數據結構與算法

　　一、考試的內容、要求和目的

　　1、考試內容

　　第1章概論（考核比重約：5%）

　　1)數據結構的基本概念和術語

　　2)算法和算法分析

　　第2章線性表（考核比重約：10%）

　　1)線性表的順序表示和實現

　　2)線性表的鏈式表示和實現

　　3)雙鏈表

　　4)循環鏈表

　　5)線性表實現方法的比較

　　第3章棧和隊列（考核比重約：5%）

　　1)棧和隊列的基本概念

　　2)棧和隊列的順序存儲結構及其基本操作的實現

　　3)棧和隊列的鏈式存儲結構及其基本操作的實現

　　4)棧和隊列的應用

　　第4章串（考核比重約：5%）

　　1)串的模式匹配

　　第6章樹和二叉樹（考核比重約：20%）

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

　　2)二叉樹的順序存儲結構、鏈式存儲結構及其基本操作的實現

　　3)二叉樹的遍歷（前序遍歷、中序遍歷、后序遍歷、層次序遍歷）

　　4)樹的存儲結構

　　5)森林與二叉樹的轉換

　　6)樹和森林的遍歷

　　第7章樹和二叉樹的應用（考核比重約：10%）

　　1)哈夫曼樹和哈夫曼編碼

　　2)堆和優先級隊列

　　第8章圖（考核比重約：10%）

　　1)圖的概念

　　2)圖的存儲結構（鄰接矩陣法、鄰接表法）

　　3)圖的遍歷（深度優先遍歷、廣度優先遍歷）

　　第9章圖的應用（考核比重約：10%）

　　1)最小生成樹（Prim算法、Kruskal算法）

　　2)拓撲排序

　　3)最短路徑（Dijkstra算法、Floyd算法）

　　第10章集合與查找（考核比重約：10%）

　　1)基本概念

　　2)順序查找

　　3)折半查找

　　4)二叉查找樹

　　5)查找算法的分析及應用

　　第11章散列表（考核比重約：5%）

　　1)散列表的概念

　　2)構造散列函數的方法

　　3)解決沖突的方法

　　4)散列表的查找性能分析

　　第12章排序（考核比重約：10%）

　　1)排序的基本概念

　　2)插入排序（直接插入排序、折半插入排序、希爾排序）

　　3)交換排序（冒泡排序、快速排序）

　　4)選擇排序（直接選擇排序、堆排序）

　　5)二路歸并排序

　　6)各種內部排序算法的比較

　　2、考試的要求和目的

　　軟件工程專業《數據結構》課程本科插班生考試，要求考生比較系統地掌握課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。

　　軟件工程專業本科插班生自命題考試是為測試考生是否具有插班就讀的基本能力，選拔出優秀的�？飘厴I生而設置的具有選拔性質的考試，其目的是科學、公平、有效地測試考生掌握軟件工程專業本科階段專業知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校軟件工程專業本科生所能達到的及格或及格以上水平，以利于軟件工程專業擇優選拔，確保本科插班生的招生質量。

　　二、考試的形式和結構

　　1、考核形式：閉卷

　　2、考試時間：120分鐘

　　3、卷面滿分：100分

　　4、試卷題型及賦分：單項選擇題約20%、判斷題約20%、綜合應用題約30%、算法設計題約30%

　　5、試題難易比例：容易題約35%，中等難度題約45%，難題約20%

　　6、對考試輔助工具的要求：攜帶鋼筆、圓珠筆或中性筆，以及鉛筆、直尺等，禁止攜帶計算器。

　　三、教材及教學參考書

　　教材：算法與數據結構（第1版），馮廣慧等，電子工業出版社

　　參考書：

　　1.數據結構：思想與實現（第2版），翁惠等,高等教育出版社,2017.11

　　2.算法與數據結構考研試題精析（第3版），陳守孔等,北京：機械工業出版社,2015.5