计算机公共基础知识考点.doc

计算机公共基础知识考点.doc第一章:数据结构与算法考点1算法的复杂度【考点精讲】算法的基本概念计算机算法为计算机解题的过程实际上是在实施某种算法。算法的基本特征:可行性、确是性、有穷性、拥仃足够的情报。算法复杂度算法复杂度包括时间复杂度和空间复杂度。名称描述时间复杂度是指执行筛法所需要的计算工作鲍空间复杂度是指执行这个算法所需要的内存空间考点2逻辑结构和存储结构【考点精讲】逻辑结构数据的逻辑结构是对数据元索之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系來表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D:二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成B=(D,R)其屮B表示数据结构。为了反映D屮各数据元索之间的前后件关系,一般用二元组來表示。例如,如果把一年四季看作一个数据结构,则可表示成B=(D,R)D={春季,夏季,秋季,冬季}R={(春季,夏季),(夏季,秋季),(秋季,冬季)}存储结构数据的逻辑结构在计算机存储空间屮的存放形式称为数据的存储结构(也称数据的物理结构)。山于数据元素在计算机存储空间屮的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据兀索之间的逻辑关系(即前后件关系),在数据的存储结构屮,不仅要存放各数据元索的信息,还需要存放各数据元索之间的前后件关系的信息。•…种数据的逻緝结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接等存储结构。顺序存储方式生要用于线性的数据结构,它把逻紺上相邻的数据元索存储在物理上相邻的存储单元里,结点之间的关系山存储单元的邻接关系來体现。链式存储结构就是在毎个结点中至少包含一个指针域,用指针來体现数据兀索之间逻辑上的联系。考点3线性结构和非线性结构【考点精讲】根据数据结构屮各数据元索之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件:(1) 有且只有一个根结点:(2) 每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。考点4栈【考点精讲】栈的基本概念栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。在栈中,一端是封闭的,既不允许进行插入元索,也不允许删除元索:另一端是开口的,允许插入和删除元索。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元索时称为空栈。栈顶元索总是后被插入的元索,从而也是最先被删除的元素;栈底元素总是最先被插入的元索,从而也是最后才能被删除的元索。找星孩辱:***:麻世九用:似原则组级数帮职。例如,枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被弹出。栈的顺序存储及其运算栈的基木运算有三种:△找、退栈与读栈顶元索。(1) 入栈运算:入栈运算是指在栈顶位置插入一个新元索。(2) 退栈运算:退栈是指取出栈顶元索并赋给一个指定的变最。(3) 读栈顶元索:读栈顶元索是指将栈顶元索赋给一个指定的变杲。考点5队列【考点精讲】队列的基本概念队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾。当表中没有元素时称为空队列。队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,或者•后进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾。若有队列:Q=(qi,q2,…,q“)那么,qi为队头元索(排头元索),q“为队尾元索。队列屮的元索是按照5,…,q”的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在q”q2,…,都退队之后,q”才能退出队列。因最先进入队列的元索将最先出队,所以队列具有先进先出的特性,体现“先來先服务”的原则。队头元索5是最先被插入的兀索,也是最先被删除的元索。队尾元索q“是最后被插入的元素,也是最后被删除的元索。因此,与栈相反,队列又称为“先进先HV,(FirstInFirstOut,简称FIFO)或“后进后Hr,(LastInLastOut,简称LILO)的线性表。入队运算为往队列队尾插入一个数据元索,退队运算为从队列的队头删除一个数据元索。考点6链表【考点精讲】在链式存储方式屮,要求每个结点山两部分组成:一部分用于存放数据元素值,称为数据域,另一•部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前