计算机公共基础知识点汇总

《计算机公共基础知识点汇总》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。2.算法的特点：可行性、确定性、有穷性、拥有足够的情报。3.算法复杂程度主要包括吋I'可的复杂程度和空I'可复杂程度。4.时间复杂程度指的是需要运算的次数；空间复杂程度指的是运算所需的内存空间。5.数据结构包插数据的逻辑结构和数据的存储结构。6.算法的执行效率是与数据的存储结构有关。数据的存储结构有顺序、链接、索引等。7.数据结构中与所使用的据算计无关的是数据的逻辑结构。8.数据结构应该包含的信息有：数据元素的集合d和数据的前后件关系r。9.数据结构屮包扌舌两种基本的操作：插入运算和删除运算。10.根结点：表示没有前件的结

2、点叶子节点：表示没有后件的结点11.线性表中的每一个数据元素，除了第一个外，有且只有一个前件；除了最后一个外，有且只有一个后件。12.常见的线性结构有线性表、栈、队列和线性链表等。13.常见的非线性结构有树、二叉树和图等。14.线性表是一种存储结构，它的存储方式：顺序和链式。15.栈是限定在一端进行插入和删除运算的线性表。16.栈是按照“先进后出”或“后进先出”的原则组织数据的。17.队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。18.队列是“先进先出”或“后进后出”的线性表。19.线性链表：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表

3、中的指针链接來实现的。20.每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点（即前件或后件）。21.线性链表分为单链表、双向链表和循环链表三种类型。22.顺序表的插入运算时需要移动元素，在等概率情况下，平均需移动n/2个元素。23.在树结构中，每一个结点只有一个前件，称为父结点。24.没有前件的结点只有一个，称为树的根结点，简称树的根。25.每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。26.在树结构中，一个断点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。27.树

4、的最大层次称为树的深度。2&二叉树是一种很有用的非线性结构，它具有以下两个特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质性质1在二叉树的第k层上，最多有2〜（k-1）（k>=l）个结点。性质2深度为m的二叉树最多有个2^m-l个结点。性质3在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。性质4具有n个结点的二叉树，其深度至少为log2~n+l,其屮log2~n表示取log2~n的整数部分。性质5具有n个结点的完全二叉树深度为log2~n。29.满二叉树：每一层上的所有结点都有两个子结点。29.完全二

5、叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。30.前序：根左右中序：左根右后序：左右根31.顺序查找最坏的情况下需要比较n次顺序查找一个具有n个元素的线性表，其平均复杂度为o（n）.32.下来两种情况下只能采用顺序查找：1）如果线性表示无序表（即表中的元素是无序的），则不管是顺序存储结构海华丝链式存储结构，都只能顺序查找。2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。33.二分法查找最坏的悄况下，需要比较log2~n次。34.二分法查找只适用于顺序存储的线性表，且表小元素必须按关键字有序（升序），进行二分法查找，其时间复杂程度为。（lo

6、g2^n）035.交换类排序法（方法：冒泡排序，快速排序）。插入类排序法（方法：简单插入排序，希尔排序）。选择类排序法（方法：简单选择排序，堆排序）。类别排序方法时间复杂度交换类冒泡排序N(N-l)/2快速排序O(nlog2n)插入类简单插入排序N(N-l)/2希尔排序0(nl.5)选择类简单选择排序N(N-l)/2堆排序O(nlog2n)36.程序设计的风格主要强调：“清晰第一，效率第二”。37.结构化程序设计方法的主要原则可以概扌舌为：自顶向下，逐步求精，模块化，限制使用goto语句。38.结构化程序的基本结构：顺序结构，选择结构，重复结构。39.面向对象方法的主要优点：（1）与人类习惯

7、的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。40.面向对象的程序设计主要考虑的是提高软件的可重用性。41.—个对象由对彖名、属性和操作三部分组成。42.对鑛的基本特点：标识惟一性，分类性，多态性,封装性，模块迪立倍43.信JS隐蔽是通过对桑的封装性来实现的.44.计算机软件是包括程序.数据及相关文档的主整集合•45.软件工程源自软件危机46.软件危机可以归结