文档介绍：公共基础知识
笔试部分
第一章数据结构与算法
一、算法:是对题求解步骤的一种描述,它是指令的有限序列。
1、算法的基本特征:
(1)可行性:针对实际问题而设计的算法,执行后能够得到满意的结果。
(2)确定性:每一个步骤必须有明确的定义,不允许有模棱两可的解释和多义性。
(3)有穷性:必须在有限时间内做完,即必须在执行有限个步骤之后停止。
(4)拥有足够的情报。
2、算法的基本要素
(1)对数据的运算和操作:算术运算逻辑运算关系运算数据传输
(2)算法的控制结构:顺序选择循环
3、算法设计的基本方法:列举法、归纳法、递推法、递归法、减半递推、回溯法
4、算法的复杂度
(1)算法的时间复杂度:指执行算法所需要的计算工作量
(2)算法的空间复杂度:执行这个算法所需要的内存空间
二、数据结构:
1、数据结构:相互之间存在一种或多种特定关系和数据元素的集合,即数据的组织形式,它主要研究三个方面:
逻辑结构:数据集合中各数据元素之间固有的逻辑关系
数据结构主要分为线性结构与非线性结构
存储结构:各数据元素在计算机中的存储关系
对各种数据结构进行运算
2、线性结构:非空数据结构满足有且只有一个根结点,每个结点至少有一个前件,也最多有一个后件
3、线性表的顺序存储
线性表是最简单、最常用的一种数据结构。
(1)线性表的所有元素所占的存储空间是连续的。
(2)各数据元素在存储空间是按逻辑顺序存放的。
它是一种随机存取的存储结构
4、栈:只能在表的一端进行插入和删除运算的线性表,能进行插入和删除操作的为栈顶,另一端为栈底,表中没有元素为空栈。
特点:先进后出
栈的操作:入栈、退栈、读取栈的元素
-入栈运算是指在栈顶位置插入一个新的元素
-退栈运算是指取出栈顶元素并赋给一个指定变量
-读栈顶元素是指将栈顶元素赋给一个指定的变量。
当栈顶指针为0时,说明栈空,不可能进行退栈操作。称为“下溢”错误。
例1:ABCD依次入栈又依次出栈,出栈顺序是___
例2:若进栈序列为1、2、3、4,进栈过程可以出栈,则( )不可能是一个出栈序列。
A、1、4、3、2
B、2、3、4、1
C、3、1、4、2
D、3、4、2、1
2 1
5、队列:只允许在一端删除,另一端插入的顺序表,允许删除的一端叫队头(front头指针),允许插入的一端叫队尾(rear尾指针),队中没有元素叫空队。
特点:先进先出
操作:进队,退队
循环队列及其计算
队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列,就是将队列存储空间的最后一个位置绕道第一个位置,形成逻辑上的环状空间,供队列循环使用。
-入队运算(rear=rear+1)
-退队运算(front=front+1)
当循环队列为空(s=0)时,不能进行退队运算,称为“下溢”
*计算公式:*
(非循环队列)元素的个数=尾指针-头指针
(循环队列)元素的个数=[(尾指针-头指针+ 容量)除以容量]所得的余数
6、线性链表:线性表的链式存储结构称为线性链表。在存储时,每个结点有两部分组成,一部分用于存放数据元素值,称为数据域,另一部分用来存放指针,称为指针域,其中指针用来指向该结点的前一个或后一个结点。(即前件或后件)
分为线性单链表与线性双向链表
操作:插入、删除
7、循环链表:最后一个结点的指针域不是空而是指向表头结点,即在循环链表中,所有结点的指针构成了一个环状链。