数据结构总结试题5

1、XXX职业学院2016-2017学年第二学期期末考试数据结构试卷E(闭卷)一、单项选择题（每小题2分，共 20分）1静态查找表可以做以下哪组操作( )。（低）A、插入、删除 B、删除、查询C、查询、检索 D、查询、插入2对线性表进行二分查找时，要求线性表必须( )。（低）A、以顺序方式存储B、以链接方式存储C、顺序存储，且结点按关键字有序排序D、链式存储，且结点按关键字有序排序3下列查找方法中，不属于动态的查找方法是( )。（低）A、二分查找法 B、平衡树法 C、散列法 D、二叉排序树法4当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。（低）A

2、必定快 B不一定C在大部分情况下要快D取决于表递增还是递减5平衡二叉树中平衡因子只可能是:( )。（低）A、-1,0,+1 B、-1,+1 C、0,+1 D、-1,06对二叉排序树进行( )，可以得到各结点键值的递增序列。（中）A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 7关于静态查找和动态查找，说法正确的是：( )。（中）A、静态查找表上可以做一般的查找和插入操作B、动态查找表上不仅可以做查找和检索操作，还可以做插入和删除操作C、所谓静态查找表，是指待查的表以顺序存储方式存储D、所谓动态查找表，是指待查的表以动态方式存储8在对查找表的查找过程中，若被查找的数据元素不存在，则把该数

3、据元素插到集合中，这种方式主要适合于（）。（中）A、静态查找表 B、动态查找表C、静态查找表和动态查找表 D、两种表都不适合91、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ ）次。（高）A、1 B、2 C、3 D、410在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（ ）。（高）A、顺序查找 B、折半查找 C、分块查找 D、哈希查找二、填空题。（每空1分，共10分）1在一个查找表中，能够唯一地确定一个记录的关键字称为_。（低）2如果对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找某个特定数据元素的各种属性两种类型的

4、基本操作，而不进行插入和删除操作数据元素的查找表称为_。（低）3二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值_根结点的值。（2）若右子数不空，则右子树所有结点的值均_根结点的值。（3）左右子树又分别是二叉排序树。（小于或大于）（中）4在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为_。（高）三、判断对错，对的划“”，错的划“”（每小题2分，共20分）1折半查找法的查找速度一定比顺序查找快。 ( )（低）2连通图的各顶点间均可达。 ( )（低）3有序的线性表不论如何存储，都能采用折半查找。

5、( ) （低）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，用直接插入排序法对其进行排序并给出排序