?2021年湖北專升本文華學院計算機科學與技術專業(yè)考試大綱

第一部分 考試說明

一、 考試概況

本課程考試是為在計算機及相關專業(yè)中選拔優(yōu)秀專科畢業(yè)生進入本科階段學習而組織的考試。《數(shù)據結構》是計算機學科的一門專業(yè)核心基礎課，是所有計算機應用程序都要用到的基礎知識，是計算機類后續(xù)專業(yè)課程的基礎。通過本課程的學習，使學生掌握數(shù)據常用的邏輯結構、存儲結構與基本操作以及一些經典的算法實現(xiàn)，為后續(xù)課程的學習及今后的實際工作打下基礎。考試的指導思想是考查學生對本課程概念、理論與主要知識點的掌握程度，以及對具體問題進行分析和解決實際問題的能力。

二、考試方式與考試時間

(1)答卷方式：閉卷，筆試

(2)記分方式：滿分為 150 分

(3)考試時間：90 分鐘

三、參考書目

(1)嚴蔚敏.數(shù)據結構(C 語言版).清華大學出版社.

(2)楊有安等主編.C 語言程序設計教程(第 2 版).人民郵電出版社

第二部分 考試范圍、考試內容及試卷結構

一、 考試范圍及考試內容

1. 緒論

1) 內容與要求

(1)理解數(shù)據結構的基本概念和基本術語;

(2)掌握算法的時間復雜度分析方法;

(3)掌握 C 語言的基本語法規(guī)則和 C 語言程序結構;。

2) 考核要點

(1)基本知識點：數(shù)據結構的一些基本概念;數(shù)據常用的邏輯結構和物理結構;C 語言的基本語法規(guī)則和 C 語言基本程序結構;

(2)拔高知識點：時間復雜度的分析和求解;

2.線性表、棧和隊列、數(shù)組

1) 內容與要求

(1)理解并掌握線性表的基本特點;

(2)掌握線性表的順序存儲和鏈式存儲的實現(xiàn);

(3)理解棧和隊列的特點及存儲實現(xiàn);

(4)掌握數(shù)組的定義及特點;

2) 考核要點

(1)基本知識點：順序存儲和鏈式存儲的特點;用 C 語言實現(xiàn)順序存儲和鏈式存儲插入和刪除操作;棧和隊列的特點以及插入和刪除實現(xiàn);數(shù)組元素地址的求解;

(2)拔高知識點：循環(huán)鏈表和雙向鏈表的插入和刪除;棧和隊列的應用;

3.樹和二叉樹

1) 內容與要求

(1)理解樹的概念及基本術語;

(2)掌握二叉樹的定義和性質;

(3)掌握二叉樹三種遍歷及遞歸算法;

(4)掌握樹與二叉樹的轉換;

(4)掌握哈夫曼樹

2) 考核要點

(1)基本知識點：樹與二叉樹的一些基本概念;二叉樹的存儲方法;二叉樹的三種遍歷方法;樹與二叉樹的轉換;

(2)拔高知識點：構建二叉樹;二叉樹的遞歸算法實現(xiàn);哈夫曼樹;

4.圖

1) 內容與要求

(1)掌握圖的基本概念以及圖的存儲結構(鄰接矩陣、鄰接表);

(2)掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法;

(3)掌握圖的最小生成樹算法;

(4)掌握拓撲排序;

2) 考核要點

(1)基本知識點：圖的基本概念;圖的存儲結構;圖的遍歷;

(2)拔高知識點：prim 算法及 kruskal 算法;拓撲序列;

5.查找

1) 內容與要求

(1)理解靜態(tài)查找表和動態(tài)查找表的特征;

(2) 掌握常見幾種查找算法;

2)考核要點

(1)基本知識點：順序查找、折半查找的特點以及實現(xiàn);

(2)拔高知識點： 二叉排序樹;哈希表的概念和查找方法和哈希函數(shù)的構造方法，解決沖突的基本方法;

6. 排序

1)內容與要求

(1) 理解排序的概念;

(2) 掌握幾種常見的排序算法;

2)考核要點

(1)基本知識點：直接插入排序、冒泡排序、簡單選擇排序的特點;排序方法的穩(wěn)定性;

(2)拔高知識點：快速排序和堆排序特點。