数据结构总结试题5.doc

XXX职业学院20162017学年第二学期期末考试数据结构试卷E（闭卷）一、单项选择题（每小题2分,共 20分）1静态查找表可以做以下哪组操作（）。（低)A、插入、删除B、删除、查询C、查询、检索D、查询、插入2对线性表进行二分查找时，要求线性表必须（).(低）A、以顺序方式存储B、以链接方式存储C、顺序存储,且结点按关键字有序排序D、链式存储，且结点按关键字有序排序3下列查找方法中，不属于动态的查找方法是(）.(低)A、二分查找法B、平衡树法C、散列法D、二叉排序树法4当在一个有序的顺序表上查找一个数据时,既可用折半查找,也可用顺序查找，但前者比后者的查找速度()。（低）A必定快B不一定C在大部分情况下要快D取决于表递增还是递减5平衡二叉树中平衡因子只可能是:().(低)A、1，0，+1B、1,+1C、0,+1D、1，06对二叉排序树进行()，可以得到各结点键值的递增序列。（中）A、先序遍历B、中序遍历C、后序遍历D、层次遍历7关于静态查找和动态查找，说法正确的是:().（中)A、静态查找表上可以做一般的查找和插入操作B、动态查找表上不仅可以做查找和检索操作，还可以做插入和删除操作C、所谓静态查找表，是指待查的表以顺序存储方式存储D、所谓动态查找表,是指待查的表以动态方式存储8在对查找表的查找过程中,若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于().(中)A、静态查找表B、动态查找表C、静态查找表和动态查找表D、两种表都不适合91、已知一个有序表为(11，22，33，44，55，66,77,88，99），则折半查找55需要比较（)次。（高）A、1B、2C、3D、410在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（)。（高）A、顺序查找B、折半查找C、分块查找D、哈希查找二、填空题.（每空1分，共10分）1在一个查找表中，能够唯一地确定一个记录的关键字称为_.（低）2如果对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找某个特定数据元素的各种属性两种类型的基本操作，而不进行插入和删除操作数据元素的查找表称为_。（低)3二叉排序树或者是一棵空树,或者是具有下列性质的一棵二叉树:（1）若左子数不空,则左子树所有结点的值_根结点的值.（2)若右子数不空，则右子树所有结点的值均_根结点的值。（3)左右子树又分别是二叉排序树。(小于或大于)（中）4在有序表（12，24,36，48，60，72,84)中二分查找关键字72时所需进行的关键字比较次数为_。（高)三、判断对错，对的划“”，错的划“”(每小题2分,共20分）1折半查找法的查找速度一定比顺序查找快.（）（低)2连通图的各顶点间均可达。( ）（低）3有序的线性表不论如何存储，都能采用折半查找。（ ）（低)4任何图都能得到拓扑序列。（ ）（低)5查找分为静态查找和动态查找。( ）(低）6满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树.( )（中）7哈希查找不需要任何比较.（ ）（中）8装填因子是哈希表的一个重要参数，它反映了哈希表的装满程度.( ）（中)9已知一棵二叉树的中序和后序序列能够确定出该二叉树的形状。（ ）（高）10必须把一般树转换成二叉树后才能进行存储。（ ）（高）四。简答题。（每小题8分，共16分）1、列举几种排序的方法(至少四种）.（低)2、简述二叉排序树查找的过程。（中）五、应用题.（共34分）1、给出4个叶子结点,设其权值分别为3、5、7、9，试构造出哈夫曼树,并求其带权路径长度WPL.(8分）（低)2、设有一组初始记录关键字为45，30，20,76，13，50，给出用冒泡排序法对其排序的过程。(8分)(低）3、已知一组待排序的记录的初始序列为36， 45, 60， 92， 78， 12, 25, 45，用直接插入排序法对其进行排序并给出排序过程。（8分）（中）4、利用给定关键字集合L=100，60,40，80,70，90，150，120,110，130，180，160，200构造一棵二叉排序树（10分)(高)- 4 -（共 4 页）学 号