全国计算机等级考试二级公共基础知识总结. pdf
全国计算机等级考试二级公共基础知识具有充分的信息，具有确定性、穷举性，总结了第一章数据结构和算法1.1算法1算法基本特征的可行性。2确定性算法的各步骤必须明确定义，不允许模糊解释，不允许多义性； 3算法基本设计方法枚举法、归纳法、递归、递归、减斗递归技术、溯及法。 4归纳法通过观察简单特殊的情况，最后总结出一般结论的算法设计方法。 5算法时间复杂度是指执行算法所需的计算工作量。 算法的工作量可以通过执行算法所需的基本运算的执行次数来测量。 6算法的时间复杂度取决于问题的规模和处理的数据的初始状态。 7在算法p调用另一算法q、算法q调用算法p时，所谓间接递归调用8项目中常用的分割统治法，就是所谓减半递归技术9算法的空间复杂度，就是运行该算法所需的算法10如果要找的x一定在数组中，此时q1、dzddw1/2。 也就是说，这种情况下，需要在长度为n的一维排列中用逐次搜索法搜索值为x的要素，平均调查排列的一半要素。 如果发现数组中有一半的机会需要查找，此时q1/2。 变成dzddw1/4n/23n/4。 如果x不在数组中，则为dzddw。 11下一段的时间复杂度为forint i0； itopMaxSize-1是判断顺序堆栈已满的条件。 4插入堆栈的基本运算(1)要素称为堆栈运算； )2)删除要素称为退避运算。 3 )读取堆栈顶部元素是将堆栈顶部元素分配给指定的变量，指针没有变化。 堆栈的基本运算包括输入、输出、初始化、清空、确定堆栈是空还是已满、提取堆栈顶部元素等，对堆栈的操作在堆栈顶部进行。 5通常，元素被堆叠的顺序是：取出堆叠顶部元素，然后移动堆叠顶部指针，以指向新的堆叠顶部元素。 6从循环队列中删除元素。 通常，在检索元素后移动堆栈顶部指针。 7队列是一个线性表，允许在一端(队列末尾)插入，在另一端(队列末尾)删除。 Rear指针指向队伍的末尾，front指针指向队伍的头部。 在8个容量为25的循环队列中，对于前端指针front6和尾部指针rear9，循环队列共有三个线性列表：“先进”(FIFO )或“先进”(LILO )。 10队列运算包括： (1)入队运算包括从队列末尾插入元素； )从排队运算小组的开头删除一个要素。 如果循环队列s0表示队列为空，s1且前读表示队列已满，并且循环队列为空(s0 )，则无法执行出队操作。 这种情况称为下溢12堆栈的基本操作。 一个堆栈的输入序列是1、2、3、n，其输出序列是P1、P2、P3。Pn、P1n，Pi为n-i1的P1n，即n首先堆栈，根据堆栈的运算原理，n一定是最后堆栈，输入顺序一定是1、2、3、n，则堆栈的序列堆栈的推入和退出只能在堆栈的开头，所以要使堆栈的第一个数成为序列的最后个数5，只能先将序列的所有元素推入堆栈，此时堆栈序列只能是(a5、4、3、2、1 ) 可选的堆栈数组在按下错误的第一个序列时退出一个元素，得到[a]可选的堆栈序列1、2、3、4和5。 首先压入1、2、3、4四个元素，然后退出所有元素，最后压入5，退出堆栈，得到(c )可选的堆栈序列4、3、2、1、5； 压入1、2后，对以后的元素3、4、5分别压入一个退出一个，则得到(d )可选的堆栈序列3、4、5、2、1。 15线性链表1的数据结构分为逻辑结构和存储结构，线性链表属于存储结构。
2数据结构的各节点对应一个存储单元，这种存储单元(一个个小块)称为存储节点，简称节点。 3个节点包括两个部分，(1)用于存储数据元素的值，称为数据域； )2)用于存储指向前或后节点的指针的指针字段。 在四链存储结构中，用于存储数据结构的存储空间可以是不连续的，每个数据节点的存储顺序和数据元素之间的逻辑关系可以不一致，并且数据元素之间的逻辑关系由指针域确定。 因此，链存储结构为散列存储5的第一节点的双向循环链表l为空的条件只有该第一节点。 也就是说，L-nextL或L-priorL 6是链队列结构，而插入元素是在队列末尾进行的，只是修改队列末尾的指针，而不需要修改队列开头的指针。 在链队列中插入节点时，会在单链表的末尾插入一个节点，新插入的节点为末尾节点。 例在链队列中，如果将f和r分别作为团队领导和团队指针，则插入s指向的节点的运算为r-nexts； rs； 7在链栈中插入节点是在单链表的头中插入节点，同时将新节点的位置赋予栈顶指针。 例当一个栈顶指针向HS链栈插入一个s指向的节点时，s-nextHS； HSs； 8线性链表的基本操作插入、删除、查找和排序。 9双向链表中的每个节点都有两个指针字段，这两个指针分别指向前向节点和后续节点。 10在单链路列表中，每个节点都包含一个指针字段，指针指向下一个节点。 因此，在访问单链表中的节点时，必须沿着该指针一个个地进行。 11双向链表的结构比单链表更复杂，因此在插入和删除元素时需要修改更多的指针字段，相对复杂。 单向链表和双向链表在空间存储上的不连续性决定了它们都不能随机访问
问， 在双向链表中由于每个结点包括两个指针域，其中一个指 向该结点的前驱结点， 另一个指向该结点的后继结点， 因此它既可以直接访问前 驱结点，又可以直接访问后继结点， 而单链表每个结点只有一个指针域，指向它 的后继结点， 所以它只能直接访问它的下一个结点，而无法直接访问它的前一个 结点。所以双向链表顺序访问相邻结点更加灵活。 12链表的特点 顺序表可以随机访问任意一个结点，而链表必须从第一个数据 结点出发， 逐一查找每个结点。 链表结构是一些逻辑上相邻，而空间上并不一定 相邻的数据元素的集合， 相邻的结点之间通过指针相互联系，在插入和删除元素 时，只需修改结点指针即可，不需要移动数据元素。当存储空间不足时，可以动 态为其分配内存空间， 所以不必事先估计存储空间的大小。所需空间与其长度成 正比。 13用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。当 往空链表插入元素时， 只要把待插入元素的指针域指向头结点的指针域，把头结 点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置， 执行同样的操作即可完成插入。 当链表只有一个元素时， 删除操作只要修改指针