数据结构：
考点1：栈和队列的特点 典型题例：
(1)栈和队列的共同特点是 D（栈和队列的特点）
A)都是先进先出 B)都是先进后出
C)只允许在端点处插入和删除元素 D)没有共同点
解析:栈和队列都是一种特殊的操作受限的线性表,只允许在端点处进行插入和删除.二者的区别是:栈只允许在表的一端进行插入或删除操作,是一种\"后进先出\"的线性表;而队列只允许在表的一端进行插入操作,在另一端进行删除操作,是一种\"先进先出\"的线性表.所以没有共同点
(2)下列关于栈叙述正确的是(栈)(11.3)A A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除 C)栈底元素永远不能被删除 D)以上三种说法都不对
(3)下列叙述中正确的是(栈)(10.9) C
A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对
(4)如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是B（栈进出顺序）
A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2 D)任意顺序
解析: 由栈\"后进先出\"的特点可知:A)中e1不可能比e2先出,C)中e3不可能比e4先出,且e1不可能比e2先出,D)中栈是先进后出的,所以不可能是任意顺序.B)中出栈过程如图所示:
(5)一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素 A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为【1】(栈)(10.9) 1DCBA2345
(6) (1)一个队列的初始状态为空，先将元素A,CB,C,D,E,F,5,4,3,2,1依次入队，然后再依次
退队，则元素退队的顺序为_ABCDEF__54321__。(队列)(10.3)
(7)设某循环列队的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有___15__个元素。(队列)(10.3)
解析：循环队列中元素个数：尾指针减去头指针，若为负值，再加上队列容量。N=10-45+50=15.
考点2：线性表(链表)特点 典型题例：
(1)链表不具有的特点是 B（链表的特点）
A)不必事先估计存储空间 B)可随机访问任一元素
C)插入删除不需要移动元素 D)所需空间与线性表长度成正比
解析: 链表采用的是链式存储结构,它克服了顺序存储结构的缺点:它的结点空间可以动态申
请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素.但是链式存储结构也有不足之处:① 每个结点中的指针域需额外占用存储空间;② 链式存储结构是一种非随机存储结构.
(2)用链表表示线性表的优点是(链表)C
A)便于随机存取 B)花费的存储空间较顺序存储少 C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同
解析: 链式存储结构克服了顺序存储结构的缺点:它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素.故链式存储结构下的线性表便于插入和删除操作.
(3) 下列叙述中正确的是 A(链表)(10.3)
A)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n B)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2) C)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n) D) 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n log2n) (4)数据结构分为逻辑结构与存储结构,线性链表属于 【1】. 答案：存储结构
解析: 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构;数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式.在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息.
(5)顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中. 答案：相邻 解析: 常用的存储表示方法有4种,顺序存储,链式存储,索引存储,散列存储.其中,顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中.
(6)下列叙述中正确的是(线性表存储)(10.9) B
A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D）上述三种说法都不对
考点3：二叉树特点(遍历、叶子数、深度) 典型题例： (1)设二叉数如下：
A B C D F E G H
对该二叉树进行后序遍历的结果为EDBGHFCA(树)(10.3)
(2)已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为B（树的遍历）
A
B C
D E F
G H
A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG 解析: 利用前序和中序遍历的方法可以确定二叉树的结构,具体步骤如下:① 前序遍历的第一个结点A为树的根结点;② 中序遍历中A的左边的结点为A的左子树,A右边的结点为A的右子树;③ 再分别对A的左右子树进行上述两步处理,直到每个结点都找到正确的位置.
(3)已知二叉树后序遍历序列是dAbec,中序遍历序列是debac,它的前序遍历序列是 D （树遍历）
C E
D B
A
A)acbed B)decab C)deabc D)cedba
解析: 依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成,右子树为空;又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成,如下图所示.求得该二叉树的前序遍历序列为选项D).
(4)一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 【2】 。(数据结构)(11.3) DEBFCA
(5)一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有【3】个结点。(树)(10.9)25
(6)树是结点的集合,它的根结点数目是 A（树） A)有且只有1 B)1或多于1 C)0或1 D)至少2
解析: 树是一个或多个结点组成的有限集合,其中一个特定的结点称为根,其余结点分为若干个不相交的集合.每个集合同时又是一棵树.树有且只有1个根结点. (7)在深度为5的满二叉树中,叶子结点的个数为 C(二叉树) A)32
B)31
C)16
D)15
解析: 所谓满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个叶
k-1
子结点.这就是说,在满二叉树中,层上的结点数都达到最大值,即在满二叉树的第k层上有2个结点,且深度为m的满二叉树有2m-1个结点.
(8)下列叙述中正确的是(树)( 11.3)B
A)有一个以上根结点的数据结构不一定是非线性结构
B)只有一个根结点的数据结构不一定是线性结构 C)循环链表是非线性结构
D)双向链表是非线性结构
(9)某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) (树)( 11.3)D
A)3 B)4 C)6 D)7
考点4：算法的复杂度
典型题例：
(1)算法的空间复杂度是指(算法的复杂) D
A)算法程序的长度 B)算法程序中的指令条数
C)算法程序所占的存储空间 D)执行过程中所需要的存储空间
解析: 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度.所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度一般是指执行这个算法所需要的内存空间.
(2) 算法的时间复杂度是指 D(算法的时间复杂度)(10.3) A)算法的执行时间 B)算法所处理的数据量
C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数
(3)算法的基本特征是可行性,确定性, 【1】 和拥有足够的情报. 答案:有穷性
解析: 算法是指解题方案的准确而完整的描述.它有4个基本特征,分别是可行性,确定性,有穷性和拥有足够的情报.
(4)在长度为n的有序线性表中进行二分查找.最坏的情况下,需要的比较次数为 【2】 .答案:log2n
解析: 对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次.
(5)在长度为n的线性表中，寻找最大项至少需要比较【2】次。(线性表)(10.9) 1
(6)有序线性表能进行二分查找的前提是该线性表必须是 【1】 存储的。 顺序(数据结构)(11.3)
考点5：综合 典型题例：
(1)数据结构中,与所使用的计算机无关的是数据的(数据结构)C A)存储结构 B)物理结构 C)逻辑结构 D)物理和存储结构
解析: 数据结构概念一般包括3个方面的内容,数据的逻辑结构,存储结构及数据上的运算集合.数据的逻辑结构只抽象的反映数据元素之间的逻辑关系,而不管它在计算机中的存储表示形式.
(2)一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用.而实现递归调用中的存储分配通常用A(程序设计基础) A)栈 B)堆 C)数组 D)链表
解析: 一些较流行的程序语言允许过程的递归调用.递归调用就是过程调用本身.递归实现的是:当过程每一次执行后,都能返回到最近一次调用它的过程中.这样各调用点之间形成一种后进先出关系,而栈结构正适合来存储这些调用点.
(3)数据的逻辑结构有线性结构和 【1】 两大类. 答案：非线性结构 解析: 数据的逻辑结构有线性结构和非线性结构两大类.
排序技术（需要记住的最坏情况比较次数）
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列. 交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2;
(2)快速排序法. 插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较; (2)希尔排序法,最坏情况需要O(n1.5)次比较. 选择类排序法:(1)简单选择排序法, 最坏情况需要n(n-1)/2次比较;
n
(2)堆排序法,最坏情况需要O(nlog2)次比较.
二分类排序法: 最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次.
堆排序的比较次数为nlog2n;直接插入排序的比较次数为n(n-1)/2;快速排序的比较次数为nlog2n。
因篇幅问题不能全部显示，请点此查看更多更全内容