计算机二级office选择题笔记整理.docx

*堆排序最坏情况下时间复杂度为nlog2n(时间复杂度最小) 结点中两个指针分别指向前驱点和后继结点是线性结构，当指向两个不同的前驱或者后驱结点时为非线性结构。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和一个后继结点就是线性结构。 线性表的顺序存储结构的两个特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字节数都是一致的。 在二叉树中，度为0的结点个数总比度为2的结点个数多一个。 循环列表的第一个结点就是根结点，最后一个结点就是叶子结点。非空循环链表表示的数据结构有根结点也有叶子结点。 *在排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是快速排序。冒泡排序每次只交换两个相邻的数据。 *程序可以作为算法的一种表达方式，算法的有穷性是指算法必须在有限的时间内结束；算法的复杂度用来衡量算法的好坏；算法的效率与数据的存储结构和逻辑结构有关。 操作系统中的作业调度使用的是队列的思想。 *二叉链表为非线性结构，循环列表、双向链表、循环列队为线性结构。线性结构要求只有一个根结点，只有一个叶子结点，一个前件一个后件。 *空数据结构可以是线性结构也可以是非线性结构，数据结构中的数据元素可以是另一数据结构，非空数据结构可以没有根结点，数据结构中的元素可以是另外一种数据结构。 为了降低算法的空间复杂度，要求算法尽快采用原地工作。原地工作指：执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）。 二分查找法只适用于顺序存储的有序线性表，二分法称拆半查找，能使用二分法查找的线性表必须满足两个条件：顺序存储结构以及线性表有序。循环链表和双向链表都不是顺序存储结构。 算法的时间复杂度是指执行算法所需要的计算工作量。算法所执行的基本运算次数与问题规模有关。固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。对于各种特定的输入，算法的时间复杂度是固定不变的。 长度为n的顺序表中查找一个元素，最好情况的比较次数是1，最坏情况的比较次数是n，则平均情况的比较次数为（n+1）/2。 根结点的值一定大于左子树的结点，并且一定小于右子树的结点，先左子树，再根结点，再右子树，采用中序遍历。 *当头指针和尾针指向同一个元素时，循环队列为空或满。 算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是在顺序存储的线性表中寻找最大项，平均情况和最坏情况的比较次数为n-1。 具有偶数个结点的完全二叉树，其叶子结点数和非叶子结点数各占一半。 *栈底指针不动，栈顶指针随着入栈和出栈操作而变化，所以栈顶指针的动态变化决定了栈中元素个数。 空队列产生下溢错误。 在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。队头指针和队尾指针动态变化，循环列队中的元素个数由队头指针和队尾指针共同决定。 冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下n(n-1)/2，堆排序最小。 *长度为n，最坏情况下比较次数小于n的是二分查找法（log2n） 循环队列是队列的顺序存储结构，二叉链表是二叉树的存储结构；循环队列是队列的存储结构；栈是线性结构。 最坏情况下比较次数小于n的是寻找最大项，顺序表中，（n-1） 算法的空间复杂度是指算法在执行过程中所需要的存储空间，对算法执行中的数据进行压缩存储，会降低算法的空间复杂度。 所有结点都只有一个子结点的特殊二叉树可以用顺序存储结构存储。有的二叉树也能用顺序存储结构表示。 解决一个问题可以有不同算法，且时间复杂度可以不同。 有一个以上根结点的数据结构一定是非线性结构。 能从任意一个结点开始没有重复地扫描到所有结点的数据结构是循环链表。 *算法的空间复杂度与所处理的数据存储空间有关。 有多个指针域的链表有可能是线性结构。 队列是一种逻辑架构，而循环队列是队列的一种存储结构，并不是所有的二叉树都要采用链式存储，二分法查找适用于顺序存储的有序表，一个数据结构是不是二叉树，并不是由结点包含几个指针域决定的，而是有几个后件决定的。 *算法的逻辑结构和存储结构都会影响算法的效率。 比较快速排序、冒泡排序、简单插入排序，希尔排序在最坏情况下是最小的。 非空的数据结构可以是线性结构也可以是非线性结构；图也是没有根结点的数据结构，；有一个以上叶子结点的必定是非线性结构；非线性结构中可以没有根结点与叶子结点。 二叉树采用链式存储结构，也能采用顺序存储，二分查找法只适用于顺序存储的线性有序表；循环队列是队列的存储结构；有多个指针域的链表也有可能是线性结构。 顺序栈的栈底指针在操作过程中是固定不变的；不管是顺序栈还是带链的栈，在操作过程中其栈顶指针均是动态变化的；带链的栈底指针在操作过程中是有可能改变的；带