发布时间 : 星期一 文章数据结构精品课程习题更新完毕开始阅读
21、DELLEFT（BT，X）中，BT是指向二叉树的根，X指向一个结点，操作后，删除了 的左子树。
22、若要对某二叉排序树进行遍历，保证输出的所有结点健值序列按递增次序排列，应对该二叉树采用 遍历法。 23、二叉树第i层上至多有 个结点。 24、深度为k的二叉树至多有 个结点。
25、叶子结点的个数比度为2的分支结点个数 一个。 26、具有n个结点的完全二叉树的深度为 。
27、有20个结点的完全二叉树，编号为10的结点的父结点的编号是 。 28、有20个结点的完全二叉树，编号为10的结点的左儿子结点的编号是 。
29、有20个结点的完全二叉树，编号为10的结点的右儿子结点 。 30、二叉树在二叉链表方式下，p指向二叉树的一个结点，指向p结点的左孩子指针是 。
31、二叉树在二叉链表方式下，p指向二叉树的一个结点，p结点无右孩子的条件是 。
32、二叉树在二叉链表方式下，p指向二叉树的根结点，该二叉树是空二叉树的条件是 。
33、二叉树在二叉链表方式下，p指向二叉树的根结点，经运算s=p;while(s->rchild)s=s->rchild运算后，s指针指向 方向的结点。 34、给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。
35、深度为90的满二叉树上，第11层有 个结点。
36、二叉树的后根遍历顺序是G D H I E B J F C W，则二叉树的根是 。 37、设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有 个结点。
38、在树与二叉树之间的转换方法中，树的B结点的右边相邻的兄弟结点是C，在变成二叉树后，C是B的 结点。
33
39、在非空树上， 没有直接前趋。
40、哈夫曼树是访问叶结点的外部路径长 的二叉树。 三、应用题
1、三个结点可以组成哪几种形态的树？
2、设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。 3、写出下列二叉树的前根、中根、后根排序顺序。
4、下列二叉树是由树转化的，将该二叉树转化为树。
5、已知某二叉树的前根排序序列是abedc，中根排序序列是abdac，根据这两个序列能否惟一确定一棵二叉树，若能，请画出。
6、已知某二叉树后的后根排序序列是cdba，中根排序序列是cbda，根据这两个序列能否惟一确定一棵二叉树，若能，请画出。
7、已知某二叉树的前根排序序列和后根排序序列，根据这两个序列能否惟一确定一棵二叉树，若不能，请举出反例。
8、已知某系统在通信联络中只可能出现8个字符，其出现的权值是（5,29,7,8,14,23,3,11），构造一个哈夫曼树，并为这8个字符设计哈夫曼编码。 9、画出下列二叉树的二叉链表表示图。
10、现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。
11、给定表（19、22，18，15，30，20，42，35，16），按数据元素在表中的次序构造一棵二叉排序树。
34
四、设计题（用类C语言写算法）
1、设二叉树以二叉链表为存储结构，每个结点的数据域存储一个整数，编写算法，统计二叉树中数据域为0的结点的个数。
Int Statistic (bt) /* bt 是指向二叉树根指针 */
2、设二叉树以二叉链表为存储结构，每个结点的数据域存储一个整数，编写算法，将每个结点的数据域取反。
Opposition (bt) /* bt 是指向二叉树根指针 */
3、设二叉树以二叉链表为存储结构，编写算法，将每个结点的左右子树交换。
exchange (bt) /* bt 是指向二叉树根指针 */
4、设二叉树以二叉链表为存储结构，编写前根遍历二叉树的非递归算法。
PreorderTraverse(Bitree bt)
5、设二叉树以二叉链表为存储结构，编写中根遍历二叉树的非递归算法。
InorderTraverse (Bitree bt)
6、设二叉树为二叉链表为存储结构，编写后根遍历二叉树的非递归算法。
EndorderTraverse (Bitree bt)
7、设二叉树以二叉链表为存储结构，编写按层次遍历二叉树的算法。
Administrative (bt) /* bt 是指向二叉树根指针 */
8、设二叉树以二叉链表为存储结构，编写算法，求出二叉树的叶子结点数目。
Leaf (bt) /* bt 是指向二叉树根指针 */
9、设二叉树以二叉链表为存储结构，编写判断二叉树是否是完全二叉树的算法。
Full (bt) /* bt 是指向二叉树根指针 */φ
10、设二叉树以二叉链表示为存储结构，编写求二叉树深度的算法。
Deepness(bt) while ( !EmptyStack ( S )) {
Pop (S , y ); Printf (y); }; printf (x); }
35
6、简述下列算法的功能。 algo ( Stack S ) {
int i, n, a[255]; n=0;
while ( !EmptyStack ( s ) ) {n++ ; Pop( S, A[n] ) ; }
for (i=1; i<=n ; i++ ) Push ( S, A[i]) ; } 7、
algo2 ( Stack S) {
stack T ; int d ; InitStack ( T ) ;
while ( !EmptyStack (s) ) {
Pop ( S, d ); Push ( T, d ); }
8、写出循环队列Q在下列运算中队列头和尾变化的情况。 初 态 e1进队 e2进队 e3进队 出 队 出 队 e4进队 Q.front 0 Q.rear 0 9、简述循环队列进行进队、出队操作前应当进行的判断。 10、简述队列的特点及与一般线性表的区别。 11、比较栈和队列的相同点与不同点。 12、写出下列算法的输出结果。
36