2015年云南大学085211计算机技术考研大纲

　　考研网快讯，据云南大学研究生院消息，2015年云南大学计算机技术考研大纲已发布，详情如下：

　　《数据结构与操作系统》考试大纲
　　一、考查目标
　　数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容，要求考生掌握相关的概念、方法和技术，并具备较强的程序设计能力，能够灵活应用相关的方法和技术解决实际问题。
　　二、考试形式与试卷结构
　　（一）试卷成绩及考试时间
　　本试卷满分为150分，考试时间为180分钟。
　　（二）答题方式
　　答题方式为闭卷、笔试。
　　（三）试卷内容结构
　　各部分内容所占分值为：
　　数据结构75分
　　操作系统75分
　　（四）试卷题型结构
　　1．数据结构
　　选择题：15小题，每小题2分，共30分
　　简答题：3小题，每小题10分，共30分
　　算法题：1小题，每小题15分，共15分
　　2.操作系统
　　三、考查范围
　　数据结构
　　一、考查目标
　　1、掌握数据结构的基本概念、方法和技术。
　　2、掌握程序设计的基本方法和技巧。
　　3、能够应用相关知识解决一些有实际背景的问题。
　　二、考查内容
　　1.绪论
　　数据结构的概念；基本概念与术语；算法的概念，算法的特性，以及算法设计的要求，算法效率的度量。
　　2.线性表
　　线性表相关的基本概念和结构特点；线性表的顺序存储方式以及两种不同的实现方法：表空间的静态分配和动态分配；线性表的链式存储方式的实现；链表与顺序表的相似及不同之处，优缺点比较，各自适用的场合；线性表的各种实现方式能够实现指定的操作。
　　3.栈和队
　　栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队列等；栈与队列插入删除操作的特点；栈和递归的关系；栈和队列各种实现方式。
　　4.串
　　串的基本概念，朴素的模式匹配算法。
　　5.数组
　　数组的定义；数组的存储，行序和列序；特殊矩阵的定义；特殊矩阵的压缩存储。
　　6.树和二叉树
　　二叉树的概念；二叉树的五个性质；二叉树的存储结构：顺序存储和二叉链表存储的各自优缺点及适用场合；二叉树的三种遍历方法：先序，中序和后序；线索二叉树，线索化后二叉树的遍历方法；哈夫曼树概念，哈夫曼树的构造方法，前缀码概念，哈夫曼编码。树的存储表示方法，树与森林转化为二叉树，树和森林的遍历问题。
　　7.图
　　图的基本概念，图的定义和特点；图的几种存储形式，重点是邻接矩阵和邻接表；深度遍历和广度遍历是图的两种基本的遍历算法；生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法；有向无环图，拓扑排序和关键路径问题；最短路径问题：DIJSKTRA算法和FLOYD算法。
　　8.查找
　　关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果；顺序表的查找，折半查找，索引顺序表；二叉排序树，平衡二叉树，B树；哈希表的概念，哈希函数的设计，冲突解决方法的选择及冲突处理过程。
　　9.内排序
　　要求掌握各种排序方法的思想和算法实现，排序算法稳定性的概念，以及各自的特点。插入排序：直接插入、折半插入、2路插入、希尔排序；冒泡排序，快速排序；选择排序：简单选择、树选择、堆排序；归并排序；基数排序。