6、用不带头结点的单链表存储队列，其对头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）
A、仅修改队头指针 B、仅修改队尾指针 C、队头队尾可能都要修改 D、C去掉可能
7、在带头结点的链队列中，队头指针应该指向（ ） 7、已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有（ ） A dacb B cadb C dbca D bdac E all wrong
8、若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双段队列得到的是（ ） A、1234 B、4132 C、4231 D、4213
9、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（ ）
10、队列的队首和队尾分别指向最早进队，最后进队的元素，为使第一个进队元素在A[0]，front和rear分别指向?
A、0,0； B、0,n-1； C、n-1,0; D、n-1,n-1;
11、某队列允许在其两端进行入队操作，但仅允许在一段进行出队操作。若元素abcde依次入队后再进行出队操作，则不可能得到的出队序列是( ) A、bacde B、dbace C、dbcae D、ecbad 12、关于队列的叙述中，正确的是（）
A、只能使用数组构成循环队列 B、可以使用数组或者链表构成循环队列 C、循环队列没有元素数量限制 D、可以将栈看成是一个特殊的队列
13、若以1、2、3、4作为双端队列的输入序列，试分别求以下条件的输出序列： 能由输入受限的双端得到，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端得到，也不能由输出受限的双端队列得到的输出序列；
14、利用两个栈S1、S2模拟一个队列时，如何利用栈的操作实现入队、出队及判断队列是否为空。 15、试用一个不带头结点的循环链表表示队列，说明链表指针指向何处？如何入队、出队及判断队列为空？
16、设栈S中有2n个元素，从栈顶到栈底的元素依次为a2n,a2n-1,?,a1，要求通过一个循环队列重新排序站中元素，使得从栈顶到栈底的元素依次为a2n,a2n-2, ?,a2,a2n-1,a2n-3, ?,a1，设计算法实现，要求空间复杂度和时间复杂度为O(n)。
11
典型题目解析 数组
1、二维数组S[-3..5,0..10]含有的元素个数是（ ）。
2、二维数组A的每个元素由6个字符组成，行下标的范围是0~8，列下标的范围是从0~9，则存放A需要（ ）字节；A的第8列和第5行共占（ ）字节；若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。
3、四维数组A[8,9,10,11]采用行序为主序的方式从地址A[0,0,0,0]开始存放，假设每个元素占用存储空间大小为L，则元素A[3,4,8,10]的存放地址是（ ）。
典型题目解析 矩阵的压缩存储
特殊矩阵是指矩阵中有较多相同的元素且其分布有一定的规律；压缩存储的基本思想是：为多个相同的元素分配一个存储空降；对零元素不分配存储空间。 1、设A[N,N]是对称矩阵，将其下三角包括对角线按行序存储到一维数组T[N(N+1)/2]中，则上三角元素A[i][j]对应数组元素T的下标是（ ） 2、对特殊矩阵采用压缩存储的目的主要是（ ）
A、表达变的简单 B、对矩阵元素的存取变得简单 C、去掉矩阵中的多余元素 D、减少不必要的存储空间
3、设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一维数组B中，A[0][0]存放于B[0]中，则第i行的对角元素A[i][i]存放于B中（ ）处。 4、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，则存放到B[k]中的非零元素aij的下标i,j与k的对应关系是（ ）。
5、将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中元素A[66,65]在B数组中的位置K为（ ）。
第五章 树和二叉树
考纲分析
（一）树的基本概念 （二）二叉树
1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造
（三）树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树与二叉树的应用 1.二叉排序树 2.平衡二叉树 3.哈夫曼（Huffman）树和哈夫曼编码 典型题目解析 树的基本概念
1、假定一颗度为3的树中结点数为50，则其最小高度应为（ ）。 2、下列说法中，（ ）是正确的。
A、二叉树就是度为2的树 B、二叉树中不存在度大于2的结点 C、二叉树是有序树 D、二叉树中每个结点的度均为2 3、二叉树是一棵（ ）
A、度为2的有序树 B、所有结点度均为2的有序树 C、度为2的无序树 D、所有结点度均为2的无序树 4、下列情况中，可称为二叉树的是（ ）
A、每个结点至多有两棵子树的树 B、哈夫曼树
12
C、每个结点只有一棵树 D、每个结点至多有两棵子树的有序树 5、下列结论中正确的是（ ）
① 只有一个结点的二叉树的度为0 ②二叉树的度为2 ③ 二叉树的左右子树可任意交换
④深度为k的完全二叉树的结点个数小于或等于深度相等的满二叉树 A、 ① ② ③ B、 ② ③ ④ C、 ② ④ D、 ① ④ 6、二叉树有n个结点，则其深度为（ ）。
A、n-1 B、n C、log2n+1 D、不能确定
7、若完全二叉树的结点个数为100，则第60个结点的度为（ ） 8、一棵有124个叶子结点的完全二叉树最多有（ ）个结点。
9、一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ） A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-1
10、设二叉树有2n个结点，则对于m A、n个度为0 B、2m个度为0 C、2m个度为1 D、2m个度为2 11、设高度为h的二叉树只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为（ ） A 2h B 2h+1 C 2h-1 D h-1 12、设二叉树只有度为0和2的结点，其结点个数为15，则该二叉树的最大深度为（ ） 13、若一棵二叉树有126个结点，在第7层结点个数最多为（ ） 14、假定在一棵二叉树中，双分支结点个数为15个，单分支结点个数为30个，则叶子结点个数为（ ） A、15 B、16 C、17 D、47 15、若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中有（ ）棵树。 A、K B、N C、N-K D、1 16、设树T的度为4，其中度1,2,3和4的结点个数分别为4,2,1,1，则T中的叶子数为（ ） 17、一棵完全二叉树中共有626个结点，则叶子结点的个数为（ ） A、311 B、312 C、313 D、314 18、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ） A、4 B、5 C、6 D、7 19、一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中叶子结点的数目为多少？ 20、将有关二叉树的概念推广到三叉树，则含有244个结点的完全三叉树的高度是多少？含有244个叶子结点的完全三叉树的高度是多少？ 21、对于一棵含有N个结点的k叉树，请讨论其可能的最大高度和最小高度。 13 22、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树。如果按层次自顶向下、自左向右顺序从1开始对全部结点进行编号，试问： 最多有多少个结点？ 最少有多少个结点？ 结点q的第i个孩子结点的编号为多少？ 结点q的双亲结点的编号为多少？ 典型题目解析 二叉树的存储结构 23、以下说法中，（ ）是正确的。 A、完全二叉树中，叶结点双亲的左兄弟结点一定不是叶结点 B、任何一棵二叉树中，终端结点等于度为2的结点数减1 C、完全二叉树不适合用顺序存储结构存储 D、结点按层次编号的二叉树，第i个结点的左孩子（如果存在）编号为2i 24、若用一维数组保存一个深度为5，结点个数为10的二叉树，数组的长度至少为（ ） A、10 B、16 C、31 D、63 25、一棵有n个结点的二叉树采用顺序存储结构，存储在一维数组A[0?n-1]中，结点A[i]的左孩子是（ ） A、A[2i] B、A[2i+1] C、A[2i+2] D、A[2i+3] 26、在顺序存储的二叉树中， ①编号为i和j的两个结点在同一层上的条件是什么？ ②如何求i和j的最近的共同祖先？ 27、设度为m的树采用多重链表存储，每个结点有m+1个域，其中有1个数据域，m个指向孩子的指针。则空指针的数目是多少？说明这种存储方式的利弊。 28、已知深度为h的二叉树以一维数组BT[1..2h-1]作为存储结构。编写算法求该二叉树的叶子结点个数。为简单起见，假设二叉树中元素结点为非零整数。 29、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。 14 典型题目解析 二叉树的遍历 30、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） A、CABDEFG B、BCDAEFG C、DACEFBG D、ADBCFEG 31、现有先序遍历二叉树的结果为ABCD，则有（ ）种不同的二叉树可以得到这一结果。 A、12 B、13 C、14 D、15 32、二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A、空或者只有一个结点 B、高度等于结点数 C、任一结点无左孩子 D、任一结点无右孩子 33、设n和m是一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（ ） A、n在m的右方 B、n是m的祖先 C、n在m的左方 D、n是m的子孙 34、下面说法正确的是（ ） A、深度为k的二叉树最多有2^k-1个结点，最少有k个结点 B、二叉树中一定存在度为2的结点 C、对二叉树的遍历指的是先序、中序或后续中的一种 D、构造线索二叉树的目的是为了能方便的找到结点的双亲 35、二叉树的叶子结点在先序、中序和后序的遍历序列中相对位置（ ） A、不发生改变 B、发生改变 C、不能确定 D、都不对 36、已知一棵二叉树的每个结点，要其么左右子树为空要么皆不为空。又知该二叉树的前序遍历序列为JFDBACEHXIK，后序遍历序列ACBEDXIHFKJ，试构造该二叉树。 37、已知二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为ABGEHACIJF，试构造二叉树。 38、判断两棵二叉树是否相似。所谓相似，是指要么它们都为空的或都是有一个根结点，要么他们的左右子树均相似。 39、一个二叉树以二叉链表存储，求二叉树第k层上叶子结点的个数。 40、设计算法统计二叉树中每一层结点个数。 15