数据结构考研分类复习真题 第九章 集合[37]

试画出从空树开始由字符序列(tdesugbjakri)构成的二叉平衡树并为每一次的平衡处理指明旋转类型【清华大学 三(分)】

给定关键词输入序列{CAPAQUPISARITAUGEMCANLIBVIRLEOSCO}假定关键词比较按英文字典序

()试画出从一棵空树开始依上述顺序(从左到右)输入关键词用高度平衡树的查找和插入算法生成一棵高度平衡树的过程并说明生成过程中采用了何种转动方式进行平衡调整标出树中各结点的平衡系数

()试画出在上述生成的高度平衡树中用高度平衡树的删除算法先后删除结点CAN和AQU后的树形要求删除后的树形仍为一棵高度平衡树并说明删除过程中采用了何种转动方式进行平衡调整标出树中各结点的平衡系数【吉林大学 一 (分)】

如图所示是一棵正在进行插入运算的AVL树关键码的插入使它失去平衡按照AVL树的插入方法需要对它的结构进行调整以恢复平衡

请画出调整后的AVL树

假设AVL树用llinkrlink法存储t是指向根结点的指针请用Pascal(或C)语句表示出这个调整过程

(说明不必写出完整的程序只需用几个语句表示出在本题中所给出的具体情况下调整过程中指针的变化在调整过程中还有两个指针变量p和q可以使用)【北京大学 六(分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []