计算机二级公共基础知识经典总结

计算机二级公共基础知识经典总结

ID:42755161

大小:24.34 KB

页数:4页

时间:2019-09-20

计算机二级公共基础知识经典总结_第1页
计算机二级公共基础知识经典总结_第2页
计算机二级公共基础知识经典总结_第3页
计算机二级公共基础知识经典总结_第4页
资源描述:

《计算机二级公共基础知识经典总结》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、1、算法是指解决方案的准确而完整的描述2、算法的四个基本特性:可行性确定性有穷性拥有足够的情报3、算法有两个基本的要素组成:一、数据对象的运算和操作二、算法的控制结构4、计算机中的基本操作算术运算逻辑运算关系运算数据运算5、算法的控制结构给出了算法的基本框架,不仅决定了算法中各操作的执行顺序,而且也直接反应了算法的设计是否符合结构化的原则。一个算法都可以用顺序、选择、循环3钟基本控制结构组成6、算法的复杂度主要包括时间复杂度和空间复杂度7、算法的时间复杂度是执行算法所需要的计算工作量。他不仅应该

2、与使用的计算机、程序设计语言及程序编制者无关,而且应该与算法实现过程中的许多细节无关。8、算法的空间复杂度是指执行这个算法所需要的内存空间。9、如果一个数据结构中没有一个数据元素,则称该数据结构为空的数据结构。10、根据数据结构中个数据元素之间前后件关系的复杂程度,一般将数据结构分为线性结构和非线性结构11、如果一个非空的数据结构满足1、有且只有一个根结点;2、每一个结点最多有一个前件,也最多有一个后件,则称该数据结构为线性结构。线性结构又称线性表。12、在一个线性结构中插入或删除任何一个结点后

3、还是线性结构。13、在计算机中存放线性表,一种最简单的方法是顺序存储。、14、线性表的顺序存储结构具有两个基本的特点:一、线性表中所有元素所占的存储空间是连续的。二、线性表中各数据在存储空间中是按逻辑顺序依次存放的。15、线性表的插入运算和删除运算P.8-916、栈是一种特殊的线性表,其插入和删除只能在表的一端进行。17、在栈中允许插入与删除的一端称为栈顶,而不允许插入与删除的一端称为栈底,栈的修改原则是先进后出或后进先出。18、入栈运算:1、首先将栈顶指针进1,然后将新元素入到栈顶指针指向的位

4、置。19、退栈预算:首先将栈顶元素赋予一个指定的变量,然后将栈顶指针退1。20、队列:是指允许在一端进行插入、而在另一端进行删除的线性表,允许插入的一端称为队尾,允许删除的一端称为排头。队列又称先进先出或后进后出的线性表,体现了“先来先服务的原则”21、队列的顺序存储结构一般采用循环队列的形式。即将队列的存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供列队循环使用。22、线性表的顺序存储结构具有简单、运算方便等优点。但是对于大的线性表,特别是元素变动频繁的大线性表不宜采用顺序的存储

5、结构,二是采用链式存储结构23、链式存储结构中,要求每个结点有两部分组成:一用于存放数据元素值,称为数据域。另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点。24、在链式存储结构中的存储空间可以不连续,各数据结点的存储结构与数据之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可以用于表示线性结构,也可以表示非线性结构25、线性链表:线性表的链式存储结构称为线性链表。26、树:树是一种简单的非线性结构。在树结构中,每一个结点只有一个前

6、件,称为父结点,没有前结点的只有1个,称为根结点,简称为树的根。每一个结点可以有多个后件,他们都称为子结点。27、二叉树是一种重要的非线性结构。二叉树具有两个特点:非空二叉树只有一个根结点。每个结点最多有两颗子树,且分别称为该结点的左子树与右子树。1、在二叉树的第K层上,最多有2k-1(k>=1)个结点2、深度为M的二叉树最多有2M-1个结点。深度为M的二叉树是指二叉树共有M层。3、在任意一颗二叉树中,度为0的结点(即叶子结点)总比度为2的结点多一个。4、具有N个结点的二叉树,其深度至少为[lo

7、g2n]+1,5、满二叉树,除了最后一层外,每一层上的所有结点都有两个子结点的二叉树为满二叉树。即深度为K的满二叉树,其第K层上有2k-1个结点,且深度为M的满二叉树共有2M-1个结点。6、在计算机中,二叉树通常采用链式存储结构。与线性链表类似,用于存储二叉树中各元素的存储结点也有两部分组成:数据域和指针域。7、二叉树的遍历可以分为三种:前序遍历中序遍历后序遍历8、前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树。9、中序遍历:首先遍历左子树,然后访问根结点,最后遍历右子树。10、后序遍

8、历:首先遍历左子树,然后遍历右子树,最后访问根结点。11、顺序查找:又称顺序搜索,一般指在线性表中查找指定元素。对于大的线性表来说,顺序查找效率很低。但在以下两种情况只能用顺序查找:1、如果线性表是无序的(即表中的元素是无序的),则不管是顺序存储结构还是链式存储结构,都只能顺序查找。2、即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。12、二分法查找:二分法查找只能用于顺序存储的有序表。对于长度为N的有序线性表,在最坏的情况下,二分查找只需要比较log2n次,而顺序查找则需要比较N次。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。