xx年专插本网络工程《数据结构》考试大纲.doc

xx年专插本网络工程数据结构考试大纲 排版：炎才 数据结构考试大纲一、考试对象计算机科学与技术、网络工程等专业本科插班生二、考试目的学生应认真把握该课程的考试、学习要求、考核知识点和有关考核的具体问题。在学习中要注意理论联系实际,系统掌握所学的知识。1、基本理论知识(l)什么是数据结构、基本概念和基本术语、数据结构的发展简史及它在计算机科学中所处的地位,算法的描述和算法分析。(2)什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。(3)栈和队列的定义、表示方法和实现。(4)串的定义及其基本操作。(5)数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和操作。(6)树的定义、基本术语和存储结构、二叉树的定义和性质,二叉树的存储结构及其各种操作,哈夫曼树。(7)图的定义和术语、图的存储结构及其各种操作。(8)各种查找方法的算法、适用范围及时间复杂度的分析。(9)内部排序、基数排序和比较排序,各种基本排序方法的算法和时间复杂度。2、基本技能(1)能阅读用C+语言编写的算法。(2)能分析算法所完成的功能、运行结果和时间复杂度。(3)能根据要求用C+语言编写算法。三、考试方法和考试时间1、考试方法：闭卷、笔试2、记分方式：百分制，满分为100分3、考试时间：120分钟4、试题总数：36题5、命题的指导思想和原则命题的总的指导思想是：全面考查学生对本课程的基本原理、基本概念和主要知识点学习、理解和掌握的情况。命题的原则是：题目数量多、份量小，范围广，最基本的知识一般要占60%左右，稍微灵活一点的题目要占20%左右，较难的题目要占20%左右。其中绝大多数是中小题目，即使大题目也不应占分太多，应适当压缩大题目在总的考分中所占的比例。客观性的题目应占比较重的份量。6、题目类型（1）选择题（2）填空题（3）简答题（4）程序填空题（5）设计题四、考试内容、要求第一章绪论1.数据、数据元素、数据项、数据类型的概念，要求达到“领会”层次。2.数据逻辑结构要达到“领会”层次。3.运算的概念要达到“识记”层次。4.数据结构的概念要达到领会层次。5.抽象数据类型的概念要达到领会层次。6.存储结构要达到领会层次。7.算法分析，要达到识记层次。第二章线性表1.线性结构的概念，要求达到“领会”层次。2.线性表的概念要求达到领会层次。3.线性表的顺序存储结构顺序表，要求达到“综合应用”层次。4.插入、删除和定位运算在顺序表上的实现，要达到“综合运用”。5.线性表的链式存储结构单链表，要求达到“简单应用”层次。6插入、删除和定位运算在单链表上的实现，达到“综合运用”层次。7循环链表和双链表，达到“简单运用”层次。第三章栈和队列1.栈的定义要达到“领会”层次。2.栈的顺序实现达到“简单运用”层次。3.队列的定义要达到“领会”层次。4.队列的顺序实现要达到“简单运用”层次。第四章串1串的定义要达到“领会”层次。2串的定长表示要达到“简单运用”层次。3串的堆表示要达到“简单运用”层次。第五章数组和广义表1数据元素地址的计算要达到“简单运用”层次。2稀疏矩阵的压缩存储要达到“简单运用”层次。3广义表的特特点和结构要达到“识记”层次。第六章树和二叉树1树形结构的基本概念和基本术语要达到“识记”层次2二叉树的定义要达到“领会”层次。3二叉树的链式存储结构要达到“简单运用”层次。4二叉树的顺序存储结构要达到“领会”层次。5二叉树的遍历要达到“综合运用”层次6树和森林要达到“识记”层次。7树的应用要达到“简单运用”层次。第七章图1图的概念要到达“领会”层次。2图的存储结构要达到“领会”层次。3图的遍历要达到“简单运用”层次。4最小生成树要达到“简单运用”层次。5最小路径要达到“简单运用”层次。第八章查找表1查找表的概念要达到“领会”层次。2静态查找表要达到“领会”层次。3二叉排序树要达到“简单应用”层次。4哈希表的基本概念要达到“领会”层次。5哈希表的构造要达到“简单应用”层次。第九章排序1排序的基本概念要达到领会的层次。2插入排序要达到简单应用3快速排序要达到简单应用的层次。4选择排序要达到简单应用的层次。5归并排序要达到领会的层次。6基数排序要达到简单应用的层次。五、试题结构（内容、题型、分数分配）六、考