CACB 11 12 13 14 15 16 17 18 19 20 AABBCBDABA 21 22 23 24 25 26 27 28 ACDCDCDA 四、简答题 1. 画出二叉树的 5 种基本形态。 2. 线性表的顺序存储结构相比链式存储结构,有什么优缺点?适用于什么情况的存储? 优点:1) 是一种随机存储结构, 存取任何元素的时间是一个常数, 速度快;2) 结构简单,逻辑上相邻的元素在物理上也是相邻的; 3 )不使用指针,节省存储空间。缺点:1) 插入和删除元素要移动大量元素, 消耗大量时间;2) 需要一个连续的存储空间; 3 )插入元素可能发生“溢出”;4 )自由区中的存储空间不能被其他数据占用(共享)。适用于经常用于检索、存取元素,但是插入和删除元素操作较少的情况。 3. 已知一颗非空二叉树,按前序遍历的结果是 ACBGDEHFJI ,按中序遍历的结果是 CGBAHEDJFI ,请画出该二叉树,并写出后序遍历的序列结果。二叉树: 12345 线性结构图状结构 2 k -12 i-1 t[i/2] 6789 10 t[2*i] 32 15 48 49 11 12 13 14 O(n) 带权路径长度 2 k -14 后序遍历的结果是 GBCHEJIFDA 4. 若比较频繁的对一个线性表进行插入和删除操作, 该线性表适合采用哪种存储结构?为什么?时间复杂度是多少? 链式存储结构。因为链式存储的线性表,插入和删除操作只需要改变指针,时间复杂度为 O(1) ,而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动,时间复杂度为 O(n)。 5. 简述二叉排序树(二叉查找树)的定义及特点。定义:如果二叉树的任一结点大于其非空左子树的所有节点,而小于等于其非空右子树的所有结点,则这棵二叉树称为二叉排序树。特点:对一颗二叉排序树进行中序排序,所得的结点序列一定是递增有序的。
全文预览
