联系客服

联系客服

400-023-1785

在线咨询

微信咨询

微信扫码咨询

微博关注

在线客服

顶部

切换栏目
选择分类
升本政策
考试科目
考试大纲
招生简章
报名时间
考试时间
招生计划
专业对照
招生院校
历年试题
分数线
成绩查询
报考流程
升本培训
选择地区
重庆专升本
云南专升本
贵州专升本
四川专升本
山东专升本
湖北专升本
河南专升本
陕西专升本
浙江专升本
山西专升本
安徽专升本
河北专升本
甘肃专升本
江西专升本
新疆专升本
湖南专升本
辽宁专升本
海南专升本
天津专升本
宁夏专升本
内蒙古专升本
黑龙江专升本
广西专升本
点击筛选
取消筛选
您现在的位置:首页 > 升本资讯 > 正文

云南省普高专升本专业课《数据结构》考试大纲

2021-07-27
来源:专升本社区
阅读 1827
导读:云南省普高专升本专业课《数据结构》考试大纲

一、考试内容概述

(一)基本理论知识

1.数据结构的基本概念和基本术语,算法的描述,算法的时间复杂度和空间复杂度分析。

2.线性表的定义,在线性表上常进行的基本操作,这些操作在顺序和链式存储结构下的实现及复杂度分析。

3.栈和队列的定义、特点、表示方法和实现。

4.串的定义及其基本操作。

5.数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和基本操作。

6.树德定义、基本术语和存储结构,二叉树的定义和性质、二叉树的存储结构及其各种操作,Huffman和Huffman编码。

7.图的定义和常用术语、图的存储结构及其遍历操作,求最小生成树、最短路径的算法,拓扑排序。

8.各种查找方法的算法、使用范围及时间复杂度的分析。

9.各种内排序算法的基本思想和算法的时间复杂度分析,不同排序方法的比较。

(二)基本技能

1.能阅读用类C语言编写的算法。

2.能分析算法所实现的功能、运行结果和时间、空间复杂度。

3.能根据要求用类C语言编写一些经典、常用算法。

 

二、考试形式

考试采用闭卷、答卷的考试方式。

满分:150分(单科成绩)

考试时间:120分钟。

 

变更,从2015年开始

考试形式:

考试采用局域网计算机化考试(机考)。

满分:150分(单科成绩)。

考试时间:120分钟。

 

三、试题难易程度分布

较易试题:约占50%

中等试题:约占30%

较难试题:约占20%

 

 

四、题型及题型分值分布

单选题:约占20%

多选题:约占10%

取消:填空题:约占15%

算法阅读题:约占10%

综合题:约占30%

程序设计题:约占15%

变更:从2015年开始,考试采用局域网计算机化考试(机考),取消填空题,分值将在要考的题型中作适当调整,可参考历年真题

 

五、内容比例

第一章 绪论:约占5%

第二章 线性表:约占10%

第三章 栈和队列:约占15%

第四章 串:约占5%

第五章 数组和广义表:约占5%

第六章 树和二叉树:约占15%

第七章 图:约占15%

第八章 查找:约占15%

第九章 内部排序:约占15%

 

考试内容及要求

第一章 绪论

1.了解数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。2.理解抽象数据类型的定义、表示和实现方法。3.理解算法的定义、算法的特性,掌握加何用类C语言来描述算法。4.理解算法设计的基本要求,掌握计算语句频度和估算算法时间复杂度的方法。

第二章 线性表

1.了解线性表的定义和操作。2.掌握顺序存储线性表的实现和常用运算:结点的插入、删除等,并掌握其效率分析方法。3.掌握链式存储线性表,带表头结点和不带表头结点的单链表的结点插入、删除操作,建立单链表的方法。4.理解循环链表和双向链表的实现方法,了解其插入,删除等基本操作。

第三章 栈和队列

1.了解栈和认列的定义,理解各自的特点,掌握栈的项序存储结构,理解循环队列存储方法。2.掌握栈和队列的主要运算:入栈、出栈、入队、出对。3.能运用栈和对列解决一些经典问题,如:数制转换、表达式求值、树的按层次遍历、图的广度优先遍历等。

第四章 串

1.了解串的定义、空串、空格串的概念。2.了解串的基本操作。3.了解串的顺序存储结构及在顺序存储结构下基本操作的实现。4.理解串的模式匹配算法。

第五章 数组和广义表

1.理解数组的项序存储结构。2.理解二维数组的按行存储和数组元素的地址计算公式。3.理解矩阵的压缩存储、特殊矩阵的表示。4.了解广义表的定义和基本操作。

第六章 树和二叉树

1.了解树的定义和基本术语口2.掌握二叉树(完全二叉树、满二叉树)的定义和性质,理解二叉树的顺序存储结构,掌握二叉树的二叉链表表示法。3.掌握二叉树遍历的递归算法,理解二叉树中序遍历的非递归算法,掌握根据先序遍历序列建立二叉树的递归算法。4.了解二叉树索化的实质及线索化的过程。5.了解树的存储结构,理解树和森林转换为二叉树的方法。6.掌握树的路径长度和树的带权路径长度的计算方法,Huffman树的构造方法和Huffman编码。

第七章 图

1.了解图的定义。2.了解图的基本术语:图及无向图、有向图、网、子图、连通图、强连通图、顶点的度、入度、出度、顶点间路径、路径长度、环。3.理解图的两种存储结构:邻接矩阵和邻接表(含逆邻接表)。4.掌握遍历图的两种方法:深度优先搜索和广度优先搜索遍历图的算法及其时间复杂度。5.理解生成树、最小生成树的概念,掌握最小生成树的构造过程(Prim的算法和Kruskal算法)及其时间复杂度。6.掌握拓扑排序的方法及最短路径的计算。7.掌握求最短路径问题的Dijkstra算法,了解F1oyd算法.

第八章 查找

1.了解查找、关键字、平均查找长度等概念。2.静态查找表:掌握顺序查找(设哨兵)、折半查找算法及其效率(最坏和平均查找长度)分析,了解分块查找算法及其效率分析。3.动态查找表:掌握二叉排序树的定义、构造过程及其查找算法和效率分析,掌握平衡二叉树的定义和其构造过程。4.了解哈希表的特点,掌握构造哈希函数的方法(除留余数法等),掌握处理冲突的方法及效率分析。

第九章 内部排序

1.了解排序的目的、分类和排序方法的稳定性的定义。2.插入排序:掌握直接插入、折半插入排序算法和希尔排序的思想。

3.快速排序:掌握起泡排序的算法和快速排序的思想。4.选择排序:掌握简单的选择排序的算法和堆的定义,堆排序的思想。5.理解归并排序的思想、基数排序的思想及特点。6.了解各种内部排序方法的比较。

推荐专题
留言咨询
* 姓名
* 手机
* 所在学校