今天看到朋友拿出“计算机二级”考试的试题在做，突然来了兴趣，想看一下我这个正规计算机系毕业的，还会做多少计算机方面的题。
记得大学时老师说过，计算机系毕业的本身就是一种身份证明，不用考这种普通等级证书，于是得意洋洋的拿起试卷来，想炫耀一番。
她做的正好是《数据结构》部分的题，结果一看，懵逼了。毕业3，4年早已忘干净了，题的难度也很大！正好借此机会复习一下。
最近会分享的10个知识:
1.什么是算法？算法的定义。
2.什么是算法复杂度
3.算法的时间复杂度
4.算法的空间复杂度
5.算法的“原地工作”指的是什么
6.非线性结构的特点
7.什么是线性结构
8.什么是“二叉树”
9.循环队列
10.循环链表
之后分享的内容，主要参考由清华大学出版社出版，由严蔚民、吴伟民老师编著的清华大学计算机系列教材中的《数据结构》一书。
在开始分享重点知识点之前，今天先和大家一起再学习一下:“数据结构”是什么？
数据结构，已经不仅是计算机专业里非常核心的一门课程，也是其他非计算机专业的主要选修课程之一。那什么是数据结构呢？
首先，先了解一下用计算机解决一个具体问题时，会经历怎样的过程。大致是要经过下列几个步骤:
1.从具体问题抽象出一个适当的数学模型
2.设计一个解此数学模型的算法
3.编出程序
4.测试、调整直至得到最终答案
其中，寻求数学模型的实质是分析问题，从中提取操作的对象，找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
一些模型可以用数学方程来描述，预报人口增长情况，他的数学模型是微分方程。
然而，更多的非数值计算的问题，无法用数学方程式来描述。
例1:图书馆的书目检索系统自动化问题。
如果利用计算机实现制自动检索。检索条件有:登录号、书名、作者名、分类号、出版单位、出版时间等。每一本书有唯一的登录号，不同的书目之间，可能有相同的书名，相同的作者，或者有相同的分类号。
我们可以在书目检索系统中，建立一张登录号顺序排列的书目文件，和三张分别按书名、作者名、分类号顺序排列的索引表。
这四张表构成的文件就是书目自动检索的数学模型。
例2:计算机人机对弈问题。
计算机之所以能和人对弈是因为有人将对弈的策略事先已存入计算机。若将从对一开始到结束的过程中，棋盘中所有可能出现的状态都画在一张图上，可以得到一颗倒长的树，它也是一种数据结构。
计算机二级-数据结构（什么是数据结构？）
例3:多叉路口交通灯的管理问题。
在多岔路口，需要设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。假设有一个五叉路口路口有13条，可通行的路，有的可以同时同行，有的是单行道。
如何设置交通灯进行车辆管理了？
用圆圈代表通路，圆圈间的连线代表两条路不能同时通行。设置交通灯的问题，等价为对图的顶点染色问题。要求图上每个顶点染一种颜色，有线相连的两个顶点不能具有相同的颜色，总的颜色种类尽可能的少。
提取出的数学模型可以用图来表示。
计算机二级-数据结构（什么是数据结构？）
以上三个例子，描述这类非数值计算问题的数学模型，不是数学方程，而是表、树、图之类的数据结构。
简单来说，数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象及他们之间的关系和操作 等的学科。
网友评论