自命题科目考试大纲

《自命题科目考试大纲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、自命题科目考试大纲科目代码及名称：808数据结构与程序设计适用专业：计算机科学与技术计算机技术一、考试目的及要求“数据结构与程序设计”入学考试是为招收计算机科学与技术类硕士生而实施的选拔性考试，主要涉及数据结构、C/C++程序设计课程的内容。主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。要求考生具有较全面的数据结构表示与实现的基础知识；具有较高的分析问题和解决问题的能力；具有较强的综合知识运用能力。二、考

2、试内容1．绪论1.1数据结构的基本概念；1.2抽象数据类型；1.3算法和算法的时间复杂度。2.线性表2.1线性表概述；2.2线性表的顺序表示和实现；2.3线性表的链式表示和实现；2.4静态链表；2.5线性表的基本运算。3.堆栈和队列3.1堆栈；3.2堆栈应用；3.3队列；3.4优先级队列。4.串4.1串概述；4.2串的存储结构；4.3串基本操作的实现算法；4.4串的模式匹配算法-BF和KMP算法。5.数组5.1数组概述；5.2动态数组；5.3特殊矩阵的压缩存储；5.4稀疏矩阵的压缩存储。6.递归算法6.1递归的概念；6.2递归算法的执行过程；6.3递归算法的设计方法；

3、6.4递归过程和运行时栈；6.5递归算法的时间效率分析。7.树和二叉树7.1树；7.2二叉树；7.3二叉树的设计和实现；7.4二叉树遍历；7.5线索二叉树；7.6哈夫曼树；7.7等价问题；7.8树与二叉树的转换；7.9树的遍历。8.图8.1图概述；8.2图的存储结构；8.3图的实现；8.4图的遍历；8.5最小生成树；8.6最短路径；8.7拓扑排序；8.8关键路径。9.排序9.1排序的基本概念；9.2插入排序；9.3选择排序；9.4交换排序；9.5归并排序；9.6基数排序；9.7排序算法性能比较。10.查找10.1查找的基本概念；10.2静态查找；10.3动态查找；10

4、.4哈希查找；三、考试的题型及比例单项选择题（20%）填空题（13%）简答题（20%）算法理解与设计题（47%）四、考试形式及时间考试形式为闭卷笔试。考试时间为3小时。五、主要参考书目（可以多本）1.严蔚敏，《数据结构（C语言版）》（第二版），人民邮电出版社，2016年2．朱战立，《数据结构（使用C语言）》(第五版)，电子工业出版社，2014年3．M.A.韦斯，《数据结构与算法分析---C++语言描述》，(第四版)，电子工业出版社，2016年