本书所选习题,紧密围绕教育部考试**发布的考试大纲,并以梯度的形式呈现给读者(从基础题进阶到拔高题),使考生的学习更具有针对性。
本书作者对近四年统考真题所考查的知识点进行了深入剖析,在每章的*前面都给出了本章节的考点预测,使得考生可以有**地进行复习,提高复习效率。在今年的版本中,本书增加了与高分笔记对应的“知识点讲解提纯”部分,可以使考生更加精准地定位考点并做针对性练习。此外,考生还可以关注一下信息平台来了解本书的*新更新并反馈信息:weibo.com/sijieshuai(新浪微博),微信:shuaihui_ds(微信),www.csbiji.com(天勤论坛)。
本书可作为参加计算机专业研究生入学考试的考生的复习指导用书,也可作为全国各高校计算机专业或非计算���专业的学生学习相关课程的辅导用书。

第6章 排 序
本章复习建议
根据历年考查情况来看,2009~2012年本章分值分别为4分、4分、4分、4分,且均为选择题。本章知识点需要在理解的基础上进行记忆,虽然难度并不大,但是考生也不能放松警惕,特别需要注意各种排序算法的比较以及其稳定性,这些是考得比较多的知识点。
建议**复习
· 各种排序算法比较(2009年、2010年、2012年选择题)。
· 快速排序算法(2010年、2011年选择题)。
· 堆的基本性质(2011年选择题)。
· 快速排序递归次数(2010年选择题)。
· 堆的定义、插入和重新形成堆的调整方法(2009年选择题)。
历年考题分布
年份 单项选择题 综合应用题 考查内容 小计
2012年 1题×2 0题 各种排序算法比较 4分
2011年 1题×2 0题 快速排序算法、堆的基本性质 4分
2010年 1题×2 0题 快速排序递归次数、几种排序方法比较 4分
2009年 1题×2 0题 堆的定义、插入和重新形成堆的调整方法、几种排序方法比较 4分
考题大预测(仅供参考)
从历年考题来看,本章以选择题的考查为主,并且以每年两道题的数量稳定出现,在2014年的考研中可能也会延续以往的特征,望考生多加注意。
知识点提纯
1.直接插入排序
(1)算法思想。
每趟将一个待排序的元素作为关键字,按照其关键字值的大小插入到已经排好的部分序列的适当位置上,直到插入完成。
由此可以写出直接插入排序的算法代码:
void InsertSort(int R[],int n) //待排数据存在R[]中,默认为整型,个数为n
{
int i,j;
int temp;
for(i=2;i<=n;++i) //数组从下标1开始存储,**个元素有序,所以从第二个开始处理
{
temp=R[i]; //将待插入元素暂存于temp中
j=i-1;
/*这个循环完成了从待排元素之前的元素开始扫描,如果大于待排元素则后移一位。*/
while(j>=1&&temp
{
R[j+1]=R[j];
--j;
}
R[j+1]=temp; //找到插入位置,将temp中暂存的待排元素插入
}
}
(2)时间复杂度分析。
由插入排序算法代码,可以选取*内层循环里的R[j+1]=R[j];这一句作为基本操作。
1)考虑*坏的情况,即整个序列是逆序的,则内层循环中temp
2)考虑*好的情况,即整个序列已经有序,则对于内层循环中temp
综合上述两种情况,本算法平均时间复杂度为O(n2)。
(3)空间复杂度分析。
由算法代码知,算法所需的额外空间只有一个temp,因此空间复杂度为O(1)。
2.折半插入排序
(1)算法思想。
折半插入排序的基本思想和直接插入排序一样,区别在于寻找插入位置的方法不同,折半插入排序是采用折半查找法来寻找插入位置的。
折半查找法的一个基本条件是序列已经有序,这时用折半查找将快于顺序查找。从直接插入排序的流程中可以看出,每次都是在一个已经有序的序列中插入一个新的记录,所以在这个有序序列寻找插入位置,就可以用折半查找的方式来进行。"
……

序
前言
第1章 算法复杂度相关问题专练
算法复杂度综合题目专练
算法复杂度综合题目专练答案
第2章 线性表
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第3章 栈、队列和多维数组
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第4章 树与二叉树
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第5章 图
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第6章 排序
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第7章 查找
本章复习建议
建议**复习
历年考题分布
考题大预测(仅供参考)
知识点提纯
基础题部分
拔高题部分
基础题部分参考答案
拔高题部分参考答案
第8章 历年真题
计算机考研全国联考2009年真题
2009年真题答案
计算机考研全国联考2010年真题
2010年真题答案
计算机考研全国联考2011年真题
2011年真题答案
计算机考研全国联考2012年真题
2012年真题答案
参考文献

本书较之去年的**版有了重大更新:1.为非统考的考生增加常考知识点的讲解。2.作者通过微博(www.weibo.com/sijieshuai)和微信(微信ID:shuaihui_ds)与读者交流,收集读者反馈信息,并将本书的更新信息**时间发布给读者。3.改正所发现的错别字,并进一步优化讲解方式。4.开通在线程序测评系统 ,考生可登陆www.acmclub.com进行上机练习,巩固所学知识点。
5.修正代码中出现的bug,并优化解题代码。