文档介绍：
1 全国计算机二级 VB 知识点总结
全国计算机等级考试—公共基础知识部分复****简纲
在二级考试中公共基础知识占 30%, 考察题型选择填空，下面我就结合几年考试原题，小结一下这一部分的考点。
第一章 数据结构与算法
本章应考重点：本章内容在二级笔试中会出现 5—6 题，是公共基础知识部分出题量比较多的一章，所占分值也比较大 ,约 10 分 1.1 算法
算法是指解题方案的准确而完整的描述。
算法的基本特征
a 可行性 b 确定性 c 有穷性 d 拥有足够的情报
算法的复杂度
a 算法时间复杂度：是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量 b 算法的空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念
数据结构是指互相有关联的数据元素的集合
2 数据结构 a 数据的逻辑结构 1 表示数据元素的信息 2 表示各数据元素之间的前后件关系
b 数据的存储结构 顺序存储
链接存储
索引存储
对各种数据结构进行的运算
数据结构的图形表示
一个数据结构除了用二元关系外， 还可以直观地用图形表示。 在数据结构的图形表示中， 对于数据集合点 D 中的每一个数据元素用中
间标有元素值的方框表示，一般称之为数据结点，并简称结点：为了进以步表示数据元素之间的前后件关系，对于关系 R 中的每一个
二元组，用一条有向线段从前件结点指向后件结点。
4 数据结构分为二大类 线性结构 a 有且只有一个根结点 b 每个结点最多有一个前件，也最多有一个后件
常见的线性结构有线性表，队列，线性链表，栈
非线性结构 不满足线性结构条件的数据结构
常见的非线性结构有树，二叉树，和图等
1.3 线性表及其顺序存储结构
1 线性表由一组数据元素构成， 数据元素的位置只取决于自己的序号， 元素之间的相对位置是线性的。 表中的每个数据元素， 除了第一个外，由且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以是空表
2 线性表是一种存储结构 顺序结构 a 线性表中所有元素所占的存储空间是连续的
b 线性表中个数据元素在存储空间中是按逻辑顺序依次存放的
链式结构
3 顺序表的插入，删除运算
a 顺序表的插入运算，插入结束后，线性表的长度增加了 1，顺序表的插入运算时需要移动元素，在等概率情况下，平均需要移动 n/2
个元素。
b 顺序表的删除运算， 删除结束后， 线性表的长度减少了 1，顺序表的删除运算时需要移动元素， 在等概率情况下， 平均需要移动 ( n-1)
/2 个元素。插入删除运算不方便
1.4 栈和队列
栈及其基本运算
栈是限定在一端进行插入与删除运算的线性表。栈是按照“先进后出”或“后进先出”的原则来组织数据的。
栈具有记忆作用
栈的基本运算 a 入栈运算 b 出栈运算 c 读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化
队列及其基本运算
队列是指允许在一端(队尾)进行插入，一端(队头)进行删除的线性表队列是“先进先出”或“后进后出”的线性表
1
2 全国计算机二级 VB 知识点总结
队列运算包括 a 入队运算 b 出队运算
循环队列及其运算
循环队列的初始状态为空，即 rear=front=m
循环队列的基本运算分为入队运算和退队运算
队列空的条件： s=0
队列满的条件： s=1 front=rear
1.5 线性链表
线性表顺序存储缺点
插入或删除的运算效率很低
B 线性表的顺序存储结构下，线性表的存储空间不便扩充 Data next 左指针 数据域 右指针
线性表的顺序存储结构不便于对存储空间的动态分配
2 线性链表： 线性表的链式存储结构称为线性链表， 是一种物理存储单元上非连续， 非顺序的存储结构， 数据元素的逻辑顺序是通过链表中的指针链接来实现的。在链式存储方式中每个结点由二部分组成：数据域，指针域
线性链表分为单链表，双向链表和循环链表三种类型
线性链表的基本运算
在线性链表中包含指定元素的结点之前插入一个新元素
在线性链表中删除包含指定元素的结点
将二个线性链表按要求合并成一个线性链表
将一个线性链表按要求进行分解
e 逆转线性链表 f 复制线性链表 g 线性链表的排序 h 线性链表的查找
循环链表及其基本运算
循环链表是另一种形
内容来自淘豆网转载请标明出处.
