数据结构----考研
在下列结论中，正确的是（ ）。
① 因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
② 因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
A. 只有①正确 B. 只有②正确
C. ①②都正确 D. ①②都不正确
【2013 年——江苏大学】
【考查内容】栈的链式存储结构和顺序存储结构是否会在用户空间范围内出现栈满的
情况。
【解析】链栈本身是没有容量限制的，结点都是动态申请的。所以，在用户空间范围
内，不会出现栈满的情况。顺序栈则不同，顺序栈其实就是用一维数组存储的堆栈，数组
的大小表示了栈的容量，在用户空间范围内可能出现栈满的情况。
【参考答案】A
中缀表达式就是常见的运算表达式，如(3+4)×5-6
前缀：算右->左 栈顶元素 op 次顶元素 求表达式:右->左
后缀：算左->右 次顶元素 op 栈顶元素 求表达式:左->右
A+(B*(C-D))/E
前:+A/*B-CDE
后:ABCD-*E/+
十字链表:有链接的编号链接。比如a(0)->b(1) 这样的话就有0 1 ^ ^这样的元素
连线要看后面的数字，有没有这个下标。第二个数一样就放在同一列。
稀疏矩阵一般的压缩存储方法有两种：三元组和十字链表
特殊稀疏矩阵
在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为
2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是（ ）。
A. 41 B. 82 C. 113 D. 122
【2010 年统考——第 5 题】
【考查内容】树的基本概念，树的结点计算方法。
【解析】本题画图或者计算，都不太容易。我们可以这样来推理：这棵度为 4 的树 T 中，
若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点。
所以，树的度数为20 × 4 + 10 × 3 + 1 × 2 + 10 × 1 = 122。因为根结点没有父结点，所以，
所以，树中一共有结点 122+1=123 个。除去这 20+10+1+10=41 个结点，其他的 82 个结点是
叶子结点。
注意，这里不用再出去父结点了。因为父结点的度肯定不为零，即不是叶子结点。也
就是说，父结点的度数一定是 1,2,3,4 当中的一个，已经在题目中所述的结点范围之内了。
【参考答案】B
设高度为 h 的二叉树上，只有度为 0 和度为 2 的结点，则这一类二叉树中所包含的结
点个数至少是（ ）。
A. h-1 B. h C. 2h-1 D. 2h
线索二叉树:将二叉树中序遍历之后，将空指针分别指向前一个数和后一个数，
对于只有一个叶子结点的二叉树，前序和后序遍历所得到的序列是一样的满足堆的定义。大（小）顶堆从任意结点出发到根结点（堆顶）的路径上的结点递增（减）有序。
二叉排序树的特点是中序遍历递增
已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的
结点个数是（ ）。
A. 115 B. 116
C. 1895 D. 1896
【2011 年统考——第 6 题】
【考查内容】树转换成二叉树。
【解析】我们可以设想这样一棵树：该树最后一层有 116 个叶子结点，其他的每层都
只有一个结点。那么，除了最后一层，其他层总共有结点个数为 2011-116=1895。也就是说，
这棵特殊的树共有 1896 层，除了最后一层，其他层每层都只有一个结点。
那么，将这样的一棵树转换成二叉树，则除了最后一层的 116-1=115（最后一层最右边
的结点无右孩子结点）个结点之外，其他的结点都没有右孩子。所以，树对应的二叉树中
无右孩子的结点个数是 2011-115=1896。
【参考答案】D
哈夫曼树
注意：为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。
树中一定没有度为 1 的结点
树中两个权值最小的结点一定是兄弟结点
树中任一非叶结点的权值一定不小于下一层任一结点的权值
前缀码： 设Q ={a1, a2, …, am}是一个0~1序列集合 . 如果Q中没有一个序列是另一个序列的前缀 , 则称Q为前缀码. 0 是00 的前缀，1是 11 的前缀，不符合前缀码要求
简单路径是指不存在回路的路径
