您当前所在的位置: 网站首页 -> 人才培养 -> 研究生教育 -> 正文

2023年硕士研究生招生初试科目的考试内容范围说明

发布日期:2022-11-01   来源:云顶4008网站   点击量:

数据结构(803)

一、考试范围

1.数据结构基本概念及简单的算法分析

(1)数据结构、抽象数据类型、数据类型、算法的基本概念

(2)算法性能分析与度量:算法的性能标准;算法的空间复杂度与时间复杂度概念与分析方法;时间复杂度的渐进表示法;

2.线性表

(1)顺序表:顺序表的定义和特点;顺序表的类定义;顺序表的查找、插入和删除;顺序表的优缺点

(2)单链表:单链表的结构;单链表的类定义;单链表中的插入与删除;带表头结点的单链表;静态链表 ;链表的优缺点

(3)循环链表:循环链表的类定义;用循环链表解约瑟夫问题;

(4)双向链表的基本操作

3.栈和队列

(1)栈:栈的抽象数据类型;栈的顺序存储表示;栈的链接存储表示

(2)队列:队列的抽象数据类型;队列的顺序存储表示;队列的链接存储表示;

(3)栈和队列的应用

4.树与森林

(1)树和森林的概念:树的定义;树的术语;树的抽象数据类型

(2)二叉树:二叉树的定义;二叉树的性质;二叉树的抽象数据类型

(3)二叉树的表示:顺序表表示;链表存储表示

(4)二叉树遍历:中序遍历;前序遍历;后序遍历;不用栈的二叉树中序遍历算法

(5)线索化二叉树:线索;中序线索化二叉树;前序与后序的线索化

(6)树与森林:树的存储表示;森林与二叉树的转换;树的遍历;森林的遍历;

(7)哈夫曼树:带权路径长度;哈夫曼树;哈夫曼编码

5. 图

(1)图的基本概念:图的基本概念;图的抽象数据类型。

(2)图的存储表示:邻接矩阵;邻接表。

(3)图的遍历与连通性:深度优先搜索;广度优先搜索;连通分量;

(4)图的基本算法:最小生成树:Prim普里姆算法;Kruskal克鲁斯卡尔算法;Dijkstra最短路径;拓扑排序AOV;关键路径AOE。

6.查找

(1)查找、查找表及平均查找长度的基本概念

(2)顺序查找;基于有序顺序表的二分查找算法及分析

(3)二叉排序树:定义,二叉排序树的查找、插入和删除;

(4)平衡二叉树(AVL树):AVL树的定义,查找,插入和删除,平衡二叉树的调整;

(5)散列:散列表的基本概念,构造方法(除留余数法),解决冲突的方法(线性探测,二次线性探测),查找性能的分析。

7.排序

(1)排序的基本术语与概念

(2)插入排序:直接插入排序;折半插入排序;希尔排序

(3)交换排序:冒泡排序;快速排序

(4)选择排序:简单选择排序;堆排序

(5)归并排序:二路归并排序

(6)基数排序:基数排序

(7)各种内排序方法的比较与选择

二、考试形式

(一)试卷成绩及考试时间

本试卷满分为150分,考试时间为180分

(二)答题方式

答题方式为闭卷、笔试

(三)推荐参考书

1. 李春葆,《数据结构教程(第5版)》,清华大学出版社

2. 李春葆,《数据结构教程(第5版)学习指导》,清华大学出版社

3.严蔚敏,吴伟民,数据结构(C语言版)

(四)试卷内容结构

数据结构基本概念:20%,顺序与链式线性表:15%,栈与队列:15%

树与二叉树:20%,图:15%,查找与排序:15%

(五)试卷题型结构

选择题(约30分),填空题(约20分);判断题(约20分);应用题(约50分)算法分析设计题(约30分)