[精品]常用数据结构分析

《[精品]常用数据结构分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构是计算机专业的核心课程z—,它主要研究的是数据的各种组织形式及建立在这些结构Z上的各种操作的实现。在计算机专业课的学习中，数据结构课程的作用如灵魂似的，它不仅为用程序设计语言进行程序设计提供了方法性的理论指导，还在一个更高的层次上总结了程序设计的常见方法和常用技巧，可以说是程序设计人员的必修课程O由于数据结构在教学和实际应用中的重耍作用，绝大多数院校的研究生入学考试的专业课考核中，都把数据结构列为必考科冃，其考题难度因为院校的不同而T差万别，但一般高于该院校木科生的期末考试难度。1.数据结构课程及考题特点首先，让我们总结一下数据结

2、构课程及考题的特点，数据结构具有以下特点：=概念多，对比性强，易记忆从最简单的线性表到最复杂的图，都冇以下内容：类型定义、结构特点。在这些数据结构的操作中又都有：建立、撤消、插入、删除、杏找等基木操作，学习各章时的对比性很强，使读者很容易建立整体概念。数据结构中概念较多的章节是树、图、査找、排序等章节。这些章节中需要识记的概念请读者最好作好笔记，以备复习中随时査阅Z用。二算法灵活，个性突出，不易把握虽然各种数据结构的基本算法都冇相同的操作，但是因为其建立在不同的存储结构上，所以实现的方法也就截然不同。举个简单的例子：对于删除结点的操作，在

3、线性表中，由于其结点关系是“前后"关系这种单一•的关系，所以删除时只需要考虑最多另外“两个"（前驱与后继）结点的位置；但是，在图这种数据结构中，由于其结点关系是“多对多"的复杂关系，所以删除结点时就需要考虑所有与此结点相关结点信息的修改。二抽象性强，过于形式化，难于联系实际数据结构中的研究对象一一数据元素，都是从现实生活中抽象出来的，在被组织成不同形式时，都只是对单纯的数据进行操作，而忽略了其本身所代表的实际意义，比较抽彖0如果读者能适时地很好地联系实际來思考这些问题，就能较好的把握。=历年考题多有盂同，重复率高对于同一所学校，在不同的年

4、份中可能出现相同或相似的考题；对于不同的学校，也经常考一些在算法上极其相似或相同的题。关于这一点，在本书收录的考研真题中，大家会很深刻的感受到。1.数据结构考试题型总结下面让我们来分析一下数据结构考试题型，由于数据结构的学科特点，概括起来，在考试中可能出现的考题包括两个方而：=概念知识其中概念知识类题的出题内容大概为以下几个方而：各种结构的定义、特点、适用场合，多种数据结构Z间的比较，多种算法性能的比较。在这些内容的基础上，人体可以有以下几种命题方式：填空、选择、判断等小分值的题目，这些多是基础题。=算法分析与设计算法设计与分析类题的出题

5、内容包括以下几个方而：算法设计，算法功能分析，算法功能完善。基于以上内容可以出问答、设计等较大分值的题。在这些题中，难度太高的很少，一般有1至2题是最难的，其他题目较易掌握。从以上分析來看，基础题加上较简单的设计题，其总分值累计约为70到80分左右，也就是说，70%到80%的题是基础题。所以，只要我们努力打好基础，把基木题的分拿到手，不愁数据结构不能顺利过关。2.解题方法分析在进行了数据结构的题型分析之后，我们来探讨一下各种类型题的解题方法=基础题由于此类基础题涉及范围广，含盖信息量大，考生不可能或很难在较短时间内掌握所有概念。所以，请大

6、家在平时的复习中，耍认真做好读书笔记，及时归纳总结基本概念。同时，由于此类题难度不大，但是要求考生必须细致入微，否则极易岀错，丧失不该掉的分值。例1、(同济大学1999年试题)阅读下而的程序并写出程序执行结果：main(){intx,y,z,w;z=(x=−I)?(y=−1,y+=x+5):(x=7,y=3);w=y*'a'/4;printf(44%d%d%d%c",x,y,z,w);木题的难度并不大，仅需知道C语言的基本知识就町以做对。但是大家做的时候，很多同学会得出“一13372”，而实际上正确答案为：“一

7、133H”，因为大家没有注意到w的输出格式是：“％c”。在第一遍审题的时候，可能比较容易看出这里w的输出格式是“％c”，但是在解答过程中，经过若干计算之后，得出了结果为72,心理上很容易发生变化，产生“好啦！终于算出来了”的一瞬间的想法，而受到前三个都是整数的思维惯性影响，忽视了第四个变量要转换成字符來输出。这就是这个题冃的陷阱，大家一定要重视！此外，在考试过程中，得许多解题技巧，各个学科，各种考试，都是相通的，考研究生的同学都是久经沙场的老将了，对于这些技巧应该是不陌生的，比如需选择题的代入法、排除法等等。比如下而这个选择题，在你无法判

8、断或需很长时间才能判断疋确结果的情况下，一种行Z冇效的方法就是把备选答案代入到题FI中，以验证答案的止确性。例2、中国科学院计算技术研究所1996年试题字符串S满足下式,其中Head和Tail