数据结构高分笔记摘录之考研数.pdf

《数据结构高分笔记》答疑论坛： 讨论群：108945580  立志于打造最贴近考生实际的辅导书 计算机考研之数据结构高分笔记 率辉 编著 周伟 张浩 审核 《数据结构高分笔记》答疑论坛： 讨论群：108945580  《数据结构高分笔记》精彩摘录之考研数据结构必备基础知识 作者的话： 大部分同学在学习数据结构时，想必对数据结构课本里的伪代码多多少少有点不是很 清楚，特别是自己在动手编写算法的时候，明明知道算法的思路，但是编写出来的程序就 是不标准，可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前，我觉得有必 要将一些基本功提前告知你们，掌握了这些东西，在本章以后的章节中，才能以此为基础 来修炼更高深的武功。 本章概略 ▲ 针对考研数据结构的 CC++语言基础以及代码书写规范 对于考研数据结构，需要 C 与 C++语言作为基础，但是又不需要太多，因此此处讲解 有针对性。现在我们面临的是研究生考试，要在答题纸上写代码，代码的评判者是阅卷老师， 而不是 TC，VC6.0 等编译器。如果之前你只熟悉在这些编译器下写代码，那你要看看这一 部分，这里教你怎么快速的写出能让阅卷老师满意的代码。 ▲ 算法的时间复杂度分析基础 为什么要特别注重这一块的讲解？在 09年批阅数据结构算法那道题的时候，由于当时 阅卷的标准答案是教育部给出的，并且明确说明以此为标准答案，但是教育部给出的算法时 间复杂度太大，对于算法有研究的同学，可以很轻松的写出一个算法，并且时间复杂度远远 小于标准答案。教育部就是权威，没有办法，只能按照教育部的答案改，这样就导致了算法 牛人写出更完美的算法，却得了最低的分。也许是为了避免这种不公平的再次出现，10 年 的考试要求终于改了，考生必须对自己写的算法给出时间复杂度和空间复杂度，并以此来作 为评分的依据。所以这已经成为数据结构 45分里面的必考内容，这一点的考察在图、排序、 查找这三章内体现的尤为明显，因此我会在本章先总体讲一下算法时间复杂度分析的基本方 法，并在以后章节中以题目的形式讲一些具体分析思路，这样考生逐渐的就会掌握考研要求 的算法复杂度分析方法。 ▲ 数据结构和算法的基本概念 这一部分介绍一些贯穿于整本书的基本概念。 1．1针对考研数据结构的代码书写规范以及 CC++语言基础 1．1．1考研综合应用题中算法设计部分的代码书写规范 要在答题纸上快速的写出能让阅卷老师满意的代码，是有些技巧的，这与写出能在编译 器上编译通过的代码有所不同。为了说明这一点我们首先看一个例题： 设将 n （n1）个整数存放到一维数组R 中。设计一个算法，将 R 中的序列循环左移 P （0Pn ） 个 位 置 ， 即 将 R 中 的 数 据 由 {X ,X X } 变 换 为 0 1 n-1 {X ,X ,,X ,X ,X ...X }。要求：写出本题的算法描述。 p p+1 n-1 0 1 p-1 分析：