《数据结构1800题》基础回合总结——第1章 绪论

前言：《数据结构1800》这本书相信大家或多或少都有所耳闻，收录了诸多不同档次学校的考研真题，因为和汤老师的1800撞名所以备受调侃。这1800道题目里面有选择有填空，也有简答和一些编程题，总的来说质量良莠不齐——亦或说没什么性价比。因此无论考研还是备战期末或者面试的同学，当学有余力的时候，再去看本题集的内容~

注：基础阶段，强烈建议不要学算法题，这玩意对于大部分人的水平来说非常耽误效率——ACM佬不在此行列。因此本次刷题相当于基础阶段，只针对除了算法设计的一切基础题~

**时间问题直接截图了，排版有点费事~ **

1.17个选择

答案如下：

几个tips：

• 第五题中，不能有二义性指的应该是算法的确定性
• 第六题中，算法原地工作指的是算法需要的辅助空间为常数量级；此外，语言级别越高应该执行效率越高
• 十三题：多型数据结构就是指，你的数据结构可以有很多类型，比如int型链表、或者char型链表。前三种都是多类型的，串类型当然只有字符类型了。这是一个冷门的概念，但是数构紫书中出现过，要注意！

2.13个判断

答案如下：

tips：

• 数据元素是数据的基本单位，数据项则是构成数据元素的不可分割的最小单位；数据处理的最小单位也是数据项；逻辑结构描述的是数据元素之间的逻辑关系。这几个基本概念一定要记清楚
• 第12题的说法建议记一记

3.17个填空

**答案如下： **

tips：前几个概念性的东西一定要牢牢背诵，某些自命题985爱考，分值还不低；**后面这几个复杂度的题忽略，写的不好，会王道的课后题就行~ **

4.28个应用题

这一部分分块给答案：

答案如下：

好好背诵一下，自命题酷爱考这种开放式的东西，而且复试、面试也爱问这些开放性的东西——再不济你也应该能整几句术语吧~

答案如下：

这几道都比较基础，没什么难度，15题中的分类讨论思想是容易骗分的写法；此外16提说链式的复杂度为O(1)，这个太绝对，得看在哪个地方插入节点，毕竟插入前还要先执行查找算法，复杂度有可能也是n。

还是一道比较离奇的题目——这伪码都多遥远的上古写法了，看看就行：

注意：有的题让你数频度（也就是次数），这要严格数出来个数；如果只写出复杂度就好，那就可以忽略常数和系数那些~

都比较老的过时题目，没什么可写的，这里博主主要想展示全给大家看看。现在考的一般都是25题这种——写出大O表示法就行：很明显：依次是常数、平方、立方~

26没什么好说的，27不愧是清华的题，印象中912的数构总是考比较难的数学问题，大家可以挑战一下——不会做也没关系，毕竟912冠绝炎黄的土地没什么异议吧？

28这就是一个趋向于无穷的高阶无穷小，相信也难不倒大家~