考研数据结构辅导.doc

《考研数据结构辅导.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲Ⅰ．考查目标计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等学校计算机科学与技术学科优秀本科生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的入学质量。计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专

2、业基础课程。要求考生系统地掌握上述专业基础课程的概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。Ⅱ．考试形式和试卷结构一、试卷满分及考试时间：本试卷满分为150分，考试时间为180分钟。二、答题方式：答题方式为闭卷、笔试。三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分Ⅲ．考查内容数据结构[考查目标]1．掌握数据结构的基本概念、基本原理和基本方法。2．掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基

3、本的时间复杂度与空间复杂度的分析。3．能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++或Java语言设计与实现算法的能力。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1．顺序存储结构2．链式存储结构3．线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1．二叉树的定义及其主要特证2．二叉树的顺序存储结构和链式存储结构3．二叉树的遍历4．线索二叉树的基本概念和构造（三）树、森林1．树的

4、存储结构2．森林与二叉树的转换3．树和森林的遍历（四）树与二叉树的应用1．二叉排序树2．平衡二叉树3．哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作1．邻接矩阵法2．邻接表法（三）图的遍历1．深度优先搜索2．广度优先搜索（四）图的基本应用1．最小（代价）生成树2．最短路径3．拓扑排序4．关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B树及其基本操作、B树的基本概念+（五）散列（Hash）表（六）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序1．直接插入排序2．折半插入排序（三）起泡

5、排序（bubblesort）（四）简单选择排序（五）希尔排序（shellsort）（六）快速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（十）外部排序（十一）各种排序算法的比较（十二）排序算法的应用=================================================================重点章：绪论线性表栈和队列（数组）树图查找排序第1章绪论【复习要点】1.数据结构相关的基本概念和术语2.数据结构的三要素：逻辑结构、物理结构和数据运算3.算法的时间复杂度和空间复杂度的分析与计算【考题分析】年份单选题

6、/分综合题/分考查内容2009年002010年0√分析给定程序段的时间复杂度2011年1题/2√分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2012年1题/2√分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2013年1题/2√分析给定程序段的时间复杂度；大题中分析所写算法的时间复杂度2014年1题/20分析给定程序段的时间复杂度2011年1．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是。x=2；while(x

7、)阶乘的算法如下，其时间复杂度是。intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2013年1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是。A.O(n)B.O(m×n)C.O(min(m,n))D.O(max(m,n))第2章线性表【考纲内容】（一）线性表的定义和基本操作（二）线性表的实现1．顺序存储结构2．链式存储结构3．线性表的应用【考题分析】年份单选题/分综合题/分考查内容2009

8、年01题/