二级公共基础考点总结

goodluck · 发表于 2012-4-29 16:27:02

第一章数据结构与算法(八大考点)

考点一:算法

1.算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。

2.算法的复杂度主要包括时间复杂度和空间复杂度

算法的时间复杂度是指执行算法所需要的计算所需要的计算工作量(或算法执行过程中所需要的基本运算次数)算法的空间复杂度是指执行这个算法所需要的内存空间.

考点二:数据结构的基本概念

1.数据结构是研究数据元素及其之间的相互关系和数据运算的一门学科.

数据结构概念一般包括3个方面的内容：数据之间的逻辑关系（逻辑结构）、数据在计算机中的存储方式（存储结构）以及在这些数据上定义的运算的集合（数据的运算）.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

2.在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。

3.一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。

4.线性结构是指各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。否则称之为非线性结构。

考点三:线性表及其顺序存储结构

1.当线性表采用顺序存储结构实现存储时，其主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。

考点四:栈和队列

1. 栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种"后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种"先进先出"的线性表。

栈和队列的共同特点是只允许在端点处插入和删除元素

2. 常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补。

所以,由两个栈共享一个存储空间的好处是节省存储空间，降低上溢发生的机率

(设有两个串p和q，求q在p中首次出现位置的运算称作模式匹配)

(n个顶点的连通图中边的条数至少为n-1 )

游客，如果您要查看本帖隐藏内容请回复

该贴已经同步到 goodluck的微博

h0168 · 发表于 2012-4-29 22:49:18

gege211 · 发表于 2012-11-22 11:54:43

uuuuu

前途无量 · 发表于 2012-12-26 12:17:57

lingjingheer · 发表于 2013-4-19 13:53:36

zhaoyulinalok · 发表于 2013-7-5 09:27:39

二级就靠你了啊啊啊啊啊

yuyexin · 发表于 2013-8-10 21:07:32

916116935 · 发表于 2013-8-13 08:24:19

永志的思科 · 发表于 2013-8-31 12:11:09

谢谢！

mucc · 发表于 2013-9-15 17:11:15

...................

刚少530 · 发表于 2013-9-19 10:49:47

顶c语言

lauruirui · 发表于 2013-10-1 16:44:52

canyming · 发表于 2014-8-28 02:26:41

kevin0304 · 发表于 2015-1-13 15:28:06

顶

kevin0304 · 发表于 2015-1-13 15:28:21

顶

账号		自动登录	找回密码
密码			论坛注册

[计算机二级] 二级公共基础考点总结

相关帖子

客服中心

投诉建议