合肥工业大学实战心得交流

经验杂谈专业课考研，我个人认为主要还是考察基本的概念，以教材为主，教材就是圣经。不可否认，教材是枯燥的，尤其像数据结构这样的课程，比较抽象，就算对于那些计算机专业的学生，学起来有时候也比较头痛。但是别忘了那句话：书读百遍，其意自现，教材我看了 7、8 遍。看不懂，那就多看，总有豁然开朗的一刻。面对困难要这么想：这个知识点难，那我更要掌握，因为对于别人而样，它同样的难！a 数据结构：其实我感觉数据结构相对来说还是比较简单的，重点内容是:树与二叉树(性质、存储方式、遍历、哈夫曼树)、图(存储方式、遍历、连通性问题、关键路径)、查找(二叉排序树、平衡二叉树、B-树、哈希表),内部排序。第一遍主要是对数据结构有一个整体的把握，知道那本书主要讲了什么。对着去年的大纲，把不考的内容刨去，第一章主要讲数据结构研究内容、表示方法以及关于算法一 些概念，第二章线性表的存储分为两种：顺序存储和链式存储，第三章栈和队列，第五章数组和和广义表极少一部分为考试内容，第六章树和第七章图是重中之重， 第九章查找和第十章排序也是蛮重要的。当然了，我感觉要在理解的基础上最好在脑海里形成一个知识框架，将分散的知识点串联起来，那样复习起来就轻松点。第二遍的时候要进行深入的理解，每一部分的知识点要深入理解，数据结构这门课各章知识点联系不大，几乎都是独立的，但是他们都有共性，既然是数据结构，他们就具有一些共性，包括数据结构的特点、初始化，数据结构的逻辑结构，数据结构的物理结构以及应用场景，穿起来这些知识点，那么对这种数据结构的掌握就差不多了，再做些练习题，基本上理解这些知识点问题不大。切记：我们需要的是应对考试，需要多加实践，多做习题。王道的那本复习全书至少做 3 遍。还有一本就是李春葆的数据结构习题与解析也有不少人推荐，应该也蛮不错的。后面的第 N 遍，结合自己的实际情况去复习。实说实话，算法不用太纠结其中，算法的设计主要考察的是面对问题的解题思路和方法，怎么想的就怎么写。我们在解答中，按照题目的要求，（1）算法思想，主要是写出来自己思考解决这个问题的过程的方法，（2）算法描述，用代码把算法思想描述出来，如果用英语写不出来直接写汉字，你只要写上一般都会给你分数的；（3）算法的复杂度分析，在这个部分不要简单的写出来复杂度，尽量给出适当的分析和说明。b 组成原理：我感觉这是这俩门当中最难受的一门,(我的基础比较差，好多硬件的东西不理解)。组成原理的重点内容是:数据的表示和计算、主存与 CPU 的连接、高速缓存与主存的映射、常用寻址方式、CPU 指令执行过程、程序中断方式、微程序控制器。对于这门课，理解基础上的记忆并且要通过适当的练习来加促进理解。唐朔飞那本书配套的习题集还是蛮好的（我自己也用了）。组成原理的好多知识点概念之间的清晰度特别高，掌握好这些概念，做题的时候就会非常的清晰明了。比如，数据寻址有立即寻址，直接寻址，寄存器寻址，寄存器间接寻址，间接寻址，基址寻址，变址寻址，相对寻址，堆栈寻址。那么其中找到数据花费时间最长的当然是间接寻址，因为这种寻址至少要两次访存。花费时间最短的有可能是立即寻址或者是寄存器寻址(立即寻址限制了数据位数)。对于间接寻址，使得编制程序方便，特别是对于子程序的返回。而基址寻址和变址寻址有相似之处，都是借助于寄存器来扩大了寻址范围，但两者使用方法及场合却有着天壤之别。一旦掌握好了这些概念，做题是比较轻松的。组原知识点之间的联系还是相当紧密的，所以可以通过它们之间的联系来加深理解。总之，我感觉课当中组原花费的时间应该适当多一点。而且考试的话，最拉分的也是这一块。其实最主要还是书，理解其中的原理和机制就能以不变应万变。

复习专业课时用的资料：数据结构和组成原理的王道，历年真题，ppt，历年期末试题（这 用处不大，跟真题不是一个出题风格），数据结构实验教程（胡学钢） 专业课暑假得开始复习，跨专业的要早点。 合工大的数据结构和组原分别是 75 分，相对数据结构比较好拿分，组原题出的比较难（这 等你把王道刷过一遍再看真题就知道），所以大家一定要在组原上多花些时间，专业课想拉 分基本全靠组原了。 数据结构我直接刷的王道，课本用的是本科的教材，不过没怎么看，王道上讲的挺清楚了， 不懂时翻翻教材就可以了。跨专业的建议看下视频，直接硬啃很头疼的。数据结构复习分三 个阶段， 一（7-9）刷王道时结合课本主要看知识点，选择题和解答题都做了，算法题挑着简单的看 了下，期间还过了下 ppt，上面一些算法题都比较基础而且容易考。 二（9-11）时课本基本没怎么用了，看了下真题，按着历年真题上历年的题型挑着重点再刷 了遍王道，算法题就做了部分链表，二叉树，图的题（自己动笔写，光看懂没用）。 三（11-12.25）这时候过看王道挺快了，但是还是有不少忘了，所以要挑重点看看，看看错 题，主要重心放在真题上，真题上所有的题型都要掌握。算法题按照往年都挺简单的，我是 最后一个多月发现《数据结构实验教程》的，往年的算法题能在上面找到原题，我抱着试试 看的心思看了这，最后很幸运 18 的算法题都是上面的。19 的希望你好运。另外，它书后有 四张卷子，风格和真题非常相似（数据结构考研题就是胡学钢老师出的）。 计算机组成原理是真的难，也许是因为我本科是软件的，真心怵硬件方面。18 组原题还好， 跟往年相比感觉要简单点。 组原还是看的王道，组原我是看一章课本再看一章王道的，建议王道上的知识点都要看，合 工大组原考纲知识点太少 ，而组原出题非常灵活。组原复习前建议先看一眼真题，将历年 真题上考点都标下来，复习好抓住要点。组原我是 8 月份才开始的，到后期时间比较紧，所 以大家数学进度还可以的话，建议早点开始。大概也分为三个阶段。 一（8-10）看一章课本，刷一章王道，不会的先跳过，注意做好笔记，组原零散的知识点特 别多二（10-11 月中旬）将王道再刷一遍，大题最好都做下，这是对计算机的结构就比较清晰了， 组原和数据结构不一样，你猜不到他最后大题会考哪些知识点，所以想要高分的话，每章都 要掌握。 三（11 月中旬-12 月 25 日）重点还是真题，王道主要看知识点，做真题的同时找王道上同 类型题型进行练习。 以上都是我自己专业课的复习过程，每个人情况不一样，仅供大家参考。

二叉排序树

1. 定义
   一颗二叉树或者空二叉树，或者是具有如下性质的二叉树：
   ①左子树上所有结点的关键字（若存在）均小于根结点的关键字。
   ②右子树上所有结点的关键字（若存在）均大于根结点的关键字。
   ③左子树和右子树又各是一棵二叉排序树。
   二叉排序树的特点：
   中序遍历二叉排序树，可以得到一个递增的有序序列。
   在二叉排序树中删除后又插入同一结点，得到的二叉排序树与原来的不一定相同，但中序序列一定相同，因为在二叉排序树中插入的新结点均作为叶子结点。

2. 二叉排序树的查找
   二叉排序树的查找过程（若二叉树非空）：
   ①将给定值与根结点的关键字比较，若相等，则查找成功。
   ②当根结点的关键字小于给定关键字值时，在根结点的左子树中查找。
   ③否则在根结点的右子树中查找。
   二叉排序树的一条查找路径也必然满足二叉排序树的性质。二叉排序树的查找效率最好为O(log2N)，最差为O(N)。
   二叉排序树的非递归查找算法：
   BSTNode *BST_Search(BiTree T , ElemType key , BSTNode *&p){
   //查找函数返回关键字值为key的结点指针，若不存在，返回NULL
   p=NULL; //p指向被查找结点的双亲，用于插入和删除操作中
   while(T!=NULL&&key!=T->data){
   p=T;
   if(key<T->data) T=T->lchild;
   else T=T->rchild;
   }
   return T;
   }
   二叉排序树的查找也可以用递归算法实现，递归比较简单，但执行效率低。

3. 二叉排序树的插入
   二叉排序树的插入过程（与查找过程类似）：
   ①若原二叉排序树为空，则直接插入结点。
   ②若关键字k小于根结点关键字值，则插入到左子树中。
   ③若关键字k大于根结点关键字值，则插入到右子树中。
   由此可见，插入的新结点一定是某个叶结点。

int BST_Insert(BiTree &T , KeyType k){
//在二叉排序树T中插入一个关键字为k的结点
if(T==NULL){ //原树为空，新插入的记录为根结点
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1; //返回1，表示成功
}
else if(k==T->key) //树中存在相同关键字的结点
return 0;
else if(k<T->key) //插入到T的左子树中
return BST_Insert(T->lchild , k);
else //插入到T的右子树中
return BST_Insert(T->rchild , k);
}

4. 二叉排序树的构造
   构造一棵二叉排序树就是依次输入数据元素，并将它们插入到二叉排序树中的适当位置上的过程。具体过程是，每读入一个元素，就建立一个新结点，若二叉排序树非空，则将新结点的值与根结点的值比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新结点作为二叉排序树的根结点。
   void Creat_BST(BiTree &T , KeyType str[ ] , int n)}
   //用关键字数组str[ ]建立一个二叉排序树
   T=NULL; //初始时bt为空树
   int i=0;
   while(i<n){ //依次将每个元素插入
   BST_Insert(T , str[i]);
   i++;
   }
   }

5. 二叉排序树的删除
   在二叉排序树中删除一个结点时，必须确保删除结点后的二叉排序树仍满足二叉排序树的定义。删除操作的实现过程按以下三种情况来处理。
   ①如果被删除结点x是叶结点，则直接删除。
   ②若结点x只有一棵左子树或右子树，则让x的子树成为x父结点的子树，替代x的位置。
   ③若结点x有左、右两棵子树，则令x的中序后继（或前驱）替代x。然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。