全国计算机二级基础§1基本数据结构和算法1.1算法算法概念：是对一个问题求解步骤的一种描述，是求解问题的方法，它是指令的有限序列，其中每条指令表示一个或者多个操作。
算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。
(2011.9)（1）下列叙述中正确的是（）A)算法就是程序 B)设计算法时只要考虑数据结构的设计C)设计算法时只需要考虑结果的可靠性 D）以上说法都不对算法的基本特征：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）输入(>=0)和输出性（>=1）。
例一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（）。
A．有零个或多个输入 B．有零个或多个输出C．有穷性 D．可行性答案：B算法的基本要素：（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。
（2）算法的控制结构一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
算法的复杂度：算法时间复杂和算法空间复杂度。
（1）算法时间复杂度是指执行算法所需要的计算工作量。
（2）算法空间复杂度是指执行这个算法所需要的内存空间。
程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。
运算成分：描述程序中所需的运算。
控制成分：用来构造程序的逻辑控制结构。
传输成分：定义数据传输成分，如输入输出语言。
例：程序设计语言的基本成分是数据成分、运算成分、控制成分和（）。
A) 对象成分 B) 变量成分C) 语句成分 D) 传输成分1.2数据结构的基本概念数据结构研究的三个方面：（1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
(基于逻辑结构)数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
(2011.3)（2）下列叙述中正确的是（）Ａ）有一个以上根结点的数据结构不一定是非线性结构Ｂ）只有一个根结点的数据结构不一定是线性结构Ｃ）循环链表是非线性结构Ｄ）双向链表是非线性结构1.3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数n称为线性表的长度，当n=0时，称为空表。
线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)×k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
(2011.9)（2）长度为n的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中【2】元素。
(2010.9)（1）下列叙述中正确的是A）线性表的链式存储结构与顺序存储结构所需要的空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D)上述三种说法都不对1.4 栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
(2011.9)（1）数据结构分为线性结构与非线性结构，带链的栈属于【1】。
(2011.3)（1）下列关于栈叙述正确的是（）A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除C)栈底元素永远不能被删除 D）以上三种说法都不对栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。
用top表示栈顶位置，用bottom表示栈底。
(2010.9)（2）下列叙述中正确的是A)在栈中，栈中元素随栈底指针不变与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D)上述三种说法都不对(2010.9)（1）一个栈的初始状态为空。
首先将元素5、4、3、2、1依次入栈，然后退栈一次，再将元素A，B，C，D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为【1】。
队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。
Rear指针指向队尾，指针指向队头。
front队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。
队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。
循环队列：s=0表示队列空，s=1且front=rear表示队列满1.5 线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
(2011.9)（2）下列关于线性链表的叙述中，正确是（）A)各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致B)各数据结点的存储顺序与逻辑顺序可以不一致，但他们的存储空间必须连续C)进行插入与删除时，不需要移动表中的元素 D）以上三种说法都不对1.6 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。
树的最大层次称为树的深度。
二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的基本性质：1）在二叉树的第k层上，最多有2(k≥1)个结点；k-1（2）深度为m的二叉树最多有2-1个结点；m（（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为[logn]+1,其中[logn]表示取logn的整数部分；222（5）具有n个结点的完全二叉树的深度为[logn]+1；2(2011.3)（３）某二叉树共有７个结点，其中叶子结点只有１个，则该二叉树的深度为（假设根结点在第１层）Ａ）３Ｂ）４Ｃ）６ D)7(2010.9)（3）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有【3】个结点。
(2011.9)（3）以下关于二叉树的叙述中，正确的是（）A)叶子结点总是比度为2的结点少一个B)叶子结点总是比度为2的结点多一个C)叶子结点数是度为2的结点数的两倍 D）度为2的结点数是度为1的结点数的两倍是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2个结点，深度k-1满二叉树为m的m满二叉树有2-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行存储。
二叉树的遍历：（1）前序遍历（DLR）:首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR）:首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）: 首先遍历左子树，然后遍历右子树, 最后访问根结点.。
】2，则后序遍历结果为【ABDECF，前序遍历结果为DBEAFC）一棵二叉树的中序遍历结果为2（(2011.3)1.7查找技术顺序查找的使用情况：）表采用链式存储结构。
（2（1）线性表为无序表；对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较logn次，而顺序查找需要比较n-12次。
(2011.3)（1）有序线性表能进行二分差找的前提是该线性表必须是【1】存储的。
(2010.9)（2）在长度为n的线性表中，寻找最大项至少需要比较【2】次。
1.8排序技术交换类排序法：（1）冒泡排序法，需要比较的次数为n(n-1)/2；（2）快速排序法。
2。
）nO（O（nnlog），而快速排序法的平均执行时间是冒泡排序法的平均执行时间是2插入类排序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O（n ）次比较。
选择类排序法：（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O（nlog n）次比较。
21.9 例题详解一、选择题【例1】算法的时间复杂度取决于_______。
A）问题的规模B）待处理的数据的初态C）问题的难度D）A）和B）解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。
即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。
答案：D）【例2】在数据结构中，从逻辑上可以把数据结构分成_______。
A）内部结构和外部结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）动态结构和静态结构解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。
答案：B）【例3】以下_______不是栈的基本运算。
A）判断栈是否为空B）将栈置为空栈C）删除栈顶元素D）删除栈底元素解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。
答案：D）【例4】链表不具备的特点是_______。
A）可随机访问任意一个结点B）插入和删除不需要移动任何元素C）不必事先估计存储空间D）所需空间与其长度成正比解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。
所以答案为A）。
答案：A）【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是_______。