文档介绍：公共基础知识
—全国计算机等级考试
考试方式 公共基础知识有10道选择题和5道填空题共三十分。
基本要求 。 。 。 。 ,具有初步应用相关技术进行软件开发的能力。 ,了解关系数据库的设计。
一、基本数据结构与算法
;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 ;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 ;线性表的顺序存储结构及其插入与删除运算。 ;栈和队列的顺序存储结构及其基本运算。 、双向链表与循环链表的结构及其基本运算。 ;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 ;基本排序算法(交换类排序,选择类排序,插入类排序)。
;算法复杂度的概念和意义(时间复杂度与空间复杂度)。
1)算法:是对特定问题求解步骤的描述,用来解决某个特定问题的一些指令集合。
性质:有穷性,确定性, 可行性,输入,输出
性能度量:时间复杂度(执行算法所需要的计算工作量),空间复杂度(执行算法所需要的内存空间)
;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
2)数据结构:相互之间存在一种或多种特定关系的数据元素的集合,包括逻辑结构和存储结构(物理结构)。
数据元素之间关系不同,基本结构有:集合,线性结构,树形结构,图状或网状
数据的逻辑结构:数据元素之间的逻辑关系
数据的逻辑结构包含:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系。
数据的存储结构:数据的逻辑结构在计算机中的表示.
数据的存储结构有顺序、链接。
线性结构条件:
(1)有且只有一个”第一个”的数据元素(根结点);
(2)有且只有一个”最后一个”的数据元素;
(3)每一个结点最多有一个前驱,也最多有一个后继。
线性表,栈,队列
非线性结构:不满足线性结构条件的数据结构。
树与二叉树
图(网状)
;线性表的顺序存储结构及其插入与删除运算。
定义:n个有相同特征的数据元素的有限序列.
顺序存储结构(随机存取的存储结构)
插入元素ai,从后往前逐个向后移
删除元素ai,从前往后逐个向前移
链式存储结构
;栈和队列的顺序存储结构及其基本运算。
栈是后进先出的线性表
队列是先进先出的线性表
循环队列(上溢,下溢)
进栈序列是abc,可能的出栈序列有哪些?
进队序列是abc,可能的出队序列有哪些?
、双向链表与循环链表的结构及其基本运算。
线性链表存储空间不一定连续,且各元素的存储顺序任意.