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