考研辅导讲义-杜小杰

《考研辅导讲义-杜小杰》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、2012年数据结构考研大纲【硕士研究生考试】Ⅰ考查目标计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。Ⅱ考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综

2、合应用题70分III研大纲解析一、大纲变化　　2012年计算机统考的数据结构部分大纲都是变动在第六部分的排序方面，具体如下：2011年大纲2012年大纲变动六、内部排序六、排序将内部排序范围扩展为排序(一)排序的基本概念(一)排序的基本概念无变化(二)插入排序(二)插入排序无变化1.直接插入排序2.直接插入排序无变化2.折半插入排序3.折半插入排序无变化(三)起泡排序(bubblesort)(三)起泡排序(bubblesort)无变化(四)简单选择排序(四)简单选择排序无变化(五)希尔排序(shellsort)(五)希尔排序(shell

3、sort)无变化(六)快速排序(六)快速排序无变化(七)堆排序(七)堆排序无变化(八)二路归并排序(mergesort)(八)二路归并排序(mergesort)无变化(九)基数排序(九)基数排序无变化(十)外部排序新增加(十)各种内部排序算法的比较(十一)各种排序算法的比较将内部排序范围扩展为排序(十一)内部排序算法的应用(十二)排序算法的应用将内部排序范围扩展为排序　二、复习建议　　1）2012年的统考大纲对数据结构的考查目标定位：掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现；能够对算法进

4、行基本的时间复杂度和空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。2）程序设计要求：数据结构算法设计重点是考察你的设计思想及能力，所以大家在综合题中的算法设计中不要求你的程序设计没有语法错误，但是你自己的程序思想要表达清楚。例如：采用什么数据结构，什么存储方式，利用什么思想，解决什么样的问题。具体的思路要很清晰。3)复习重点：理解透大纲要求的知识点，不要脱离课本，所有的参考书中，最好的参考书就是课本，课本至少要看3遍。三、知识点解析一、线性表大纲要求：（一

5、）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用本章考试的知识点不多，主要对顺序表、链表的概念及其插入、删除操作做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。知识点：1、深刻理解数据结构的概念，掌握数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作“运算”。2、时间复杂度和空间复杂度的定义，常用计算语句频度来估算算法的时间复杂度。以下六种计算算法时

6、间的多项式是最常用的。其关系为：O(1)

7、同实现：表空间的静态分配和动态分配。掌握顺序表上实现插入、删除、定位等运算的算法。6、尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。要理解头指针、头结点、首元结点和元素结点的差别。头结点是在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。对链表（不包括循环链表）的任何操作，均要从头结点开始，头结点的指针具有标记作用，故头指针往往被称为链表的名字，如链表head是指链表头结点的指针是head。理解循

8、环链表中设置尾指针而不设置头指针的好处。链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素或删除某元素，必须知道该元素的前驱结点的指针。7、链表是本部分学习的重点和难点。重点掌握以下几种常