数据结构模拟题(开卷).docVIP

《数据结构》模拟题（补） 单项选择题 判断题 数据结构包含四种基本结构，它们是由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为【 】一单项选择题 2 3 4 5 6 7 8 9 10 C A D D B D C A C B 11 12 13 14 15 16 17 18 19 20 A A B B C B D A B A 21 22 23 24 25 26 27 28 A C D C D C D A 二．判断题 2 3 4 5 线性结构 图状结构 2k-1 2i-1 t[i/2] 6 7 8 9 10 t[2*i] 32 15 48 49 11 12 13 14 O(n) 带权路径长度 2k-1 4 四、简答题 画出二叉树的5种基本形态。 线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？ 优点：1）是一种随机存储结构，存取任何元素的时间是一个常数，速度快；2）结构简单，逻辑上相邻的元素在物理上也是相邻的；3）不使用指针，节省存储空间。 缺点：1）插入和删除元素要移动大量元素，消耗大量时间；2）需要一个连续的存储空间；3）插入元素可能发生“溢出”；4）自由区中的存储空间不能被其他数据占用（共享）。 适用于经常用于检索、存取元素，但是插入和删除元素操作较少的情况。 已知一颗非空二叉树，按前序遍历的结果是ACBGDEHFJI，按中序遍历的结果是CGBAHEDJFI，请画出该二叉树，并写出后序遍历的序列结果。 二叉树： 后序遍历的结果是GBCHEJIFDA 4.若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为什么？时间复杂度是多少？ 链式存储结构。 因为链式存储的线性表，插入和删除操作只需要改变指针，时间复杂度为O（1），而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动，时间复杂度为O（n）。 5.简述二叉排序树（二叉查找树）的定义及特点。 定义：如果二叉树的任一结点大于其非空左子树的所有节点，而小于等于其非空右子树的所有结点，则这棵二叉树称为二叉排序树。 特点：对一颗二叉排序树进行中序排序，所得的结点序列一定是递增有序的。 中国地质大学（北京）继续教育学院 2014年12课程考试 第1页（共6页）