文 彦 考 研

让丨梦想丨有迹可循

这是20计算机考研 第 8 篇文章

小鱼学姐
2017年考入电子科技大学计算机技术专业，专业课成绩129分，研究生入学后便开始做考研辅导，截止目前已辅导三十多名学生，擅长进行大纲、考点剖析，知识点与习题相结合，用通俗的事例让学生理解相关术语，耐心细致、深受好评。
以下内容由小鱼学姐分享，小彦整理。

电子科技大学计算机考研--数据结构习题讲解

大家好~我是电子科大计算机学院的17级的小鱼学姐，这篇文章我们继续讲解数据结构的课后习题：

01

以下关于数据结构的说法中，正确的是（ ）

A.数据的逻辑结构独立于其存储结构

B.数据的存储结构独立于其逻辑结构

C.数据的逻辑结构唯一决定了存储结构

D.数据结构仅由逻辑结构和存储结构决定

这个题的正确答案应该是A。

解析：首先，我们再读一下题目，让选出关于DS正确的选项，然后看四个选项，A和B都在说逻辑结构和存储结构是否独立，C是逻辑结构能否决定存储结构，D是决定了数据结构的因素有哪些。关于逻辑结构和存储结构，在上一篇文章中已经分析了相关的知识点，这里我们再来详细解释一下它们之间的关系，首先逻辑结构就是数据元素之间的关系，它不会去考虑在内存中是怎么存储的，所以和存储没有关系，所以由此可知逻辑结构是独立于存储结构的。那么存储结构（物理结构）和逻辑结构相关吗，答案是肯定的，因为存储结构是逻辑结构的一种体现，一种逻辑结构可能对应多种物理结构，但是这个物理结构必须是逻辑结构在计算机上的映射，不能独立于逻辑结构之外单独存在，所以B选项错误。C选项存储结构是由逻辑结构以及相关的运算操作共同决定的，所以C选项错误。D选项是考查的数据结构的三个要素，缺一不可，还有一个是数据的运算。

02

链式存储设计时，结点内的存储单元地址（ ）

A.一定连续

B.一定不连续

C.不一定连续

D. 部分连续，部分不连续

正确答案应该选择：A一定连续。

解析：这个题目是容易做错的题，因为审查题目不够细致，也是很多同学迷惑的地方，感觉答案是不是错了。如果我把这个题目修改一下：

链式存储设计时，结点间的存储单元地址（ ）

A, 一定连续

B.一定不连续

C.不一定连续

D.部分连续，部分不连续

此时，答案会截然不同，修改后的题目，可能90%以上的同学都能做对。因为每个结点之间的地址是不确定的，每个结点占用两个存储空间，一个用来存储数据，一个用来存储下一个结点的地址，这个地址可能就在下一个存储单元，也可能隔了很多个存储单元。用一幅图展示一下：

这是链表的两个结点，那么它在内存中的存储形式为：

从内存地址分布可知，一个结点会占用两个连续的内存单元，所以结点内部地址一定是连续的，但是结点和结点之间的地址是不确定的，可能连续，也可能不连续。

*接下来，说两个知识点，一个是算法的五个重要的特性和一个好的算法追求的目标（或者是算法设计的要求）

首先应该先了解什么是算法？

它是对特定问题求解步骤的一种描述，是指令的有限序列，一条指令表示一个或多个操作。

算法设计的五个特性：

有穷性：算法应在执行有穷步后结束，并且每一步都可以在有限的时间内完成。

确定性：每步定义都是确切、无歧义的，也就是对于相同的输入只能得出相同的输出。

可行性：算法中描述的操作都可通过已经实现的基本运算执行有限次实现

输入： 有0个或多个输入，可以没有输入。（我们在学习各种语言的时候，一般第一个代码都是输出Hello World，所以可以没有输入，但是必须至少有一个输出）

输出： 有一个或多个输出(处理结果)

算法设计的要求

正确性：

程序不含语法错误；

程序对于几组输入数据能够得出满足要求的结果；

对精心选择带有刁难性的几组数据能得出满足要求的结果；

程序对于一切合法的输入数据都能产生满足要求的结果。

可读性：易于阅读和交流，其次是机器运行。

健壮性：

当输入数据非法时，算法能适当地作出反应或进行处理，保证不会产生莫名其妙的输出结果。

处理出错的方法是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理，不应中断程序的执行。

高效率和低存储量需求：

两者都与问题的规模有关。效率就是该算法所执行的试卷，低存储量需求是在执行算法的过程中，需要的最大的存储空间。

这两个知识点在真题中经常出现，简单一点的是直接考察，但是同学们千万不要记混淆，出题一般是填空或者是选择，但是选择有时候是从侧面考查，不直接问你目标包括哪些，而是写了一段代码，问这是为了满足算法的什么，这种考法就需要我们真正的理解每一个特性以及目标的含义。例如：

03

在数组中插入一个元素时，下列代码，是符合算法的（ ）

if (i<0)

print(数组越界)

这个题当时给的选项是特性和目标掺杂在一起的，很显然这个是考查的目标中的健壮性，数据非法的时候也能做出相应的反应或者相应的处理，不会产生莫名其妙的错误。所以不仅仅要记住内容，还要去真正的理解每个性质表达的含义。

*时间复杂度vs时间频度

一个算法的效率，是通过时间复杂度和空间复杂度面熟的。

时间频度，从频度两个字可知，是指算法中语句的频度之和，是指语句被重复执行的次数，既然是次数就不能存在错误，一次和十次是不一样的。但是时间复杂度是一个数量级，用O( )表示，既然是数量级，那么和相应的系数就没有关系，例如O(N)和100000O(N)的时间复杂度是一样的。

下篇文章我们继续分析一些易错题，以及相应的知识点，把数据结构第一章的分析完后，再进行操作系统第一部分的讲解。加油o~

同学们仍有疑惑的话，欢迎扫码加入下方考研群，或添加微信，与老师一对一交流。

来文彦，考上研！报名方式：淘宝搜文彦考研
电子科大计算机考研群号：612630835
我是文彦考研，wyky66666，加小彦微信 获取更多考研干货~
文彦成电考研微信公众号：uestcwykycom

公众号更多阅读：

20届电子科大计算机|你有一份复习攻略，请查收~

20届成电计算机 | 计算机考研新形势之（一）：预面试

20届成电计算机 | 计算机考研新形势之（二）：初试+复试笔试

20成电计算机 | 暑假来袭，课后作业第一弹！

20届成电计算机 | 计算机考研新形势之（三）：学硕/专硕、