数据结构总结试题5

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

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

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

4、查找某个特定数据元素的各种属性两种类型的基本操作，而不进行插入和 删除操作数据元素的查找表称为 。（低）3. 二义排序树或者是一棵空树，或者是具有下列性质的一棵二叉 树：（1）若左子数不空，则左子树所有结点的值根结点的值。（2）若右子数不空，则右子树所有结点的值均根结点的值。（3）左右子树乂分别是二叉排序树。（小于或大于）（中）4. 在有序表（12, 24, 36, 48, 60, 72, 84）中二分查找关键字72时 所需进行的关键字比较次数为o （高）三、判断对错，对的划“V,错的划“X”（每小题2分，共20分）1. 折半査找法的查找速度一定比顺序查找快。（）（低）2. 连通图的各顶点间均

5、可达。（）（低）3.有序的线 性表不论 如何存 储，都能 釆用折半 查找。（）（低）4. 任何图都能得到拓扑序列。（）（低）5. 查找分为静态查找和动态查找。（）（低）6. 满二叉树一定是完全二叉树，完全二义树不一定是满二叉树。（）（中）7. 哈希查找不需要任何比较。（）（中）&装填因子是哈希表的一个重要参数，它反映了哈希表的装满程度。（）（中）9. 已知一棵二叉树的中序和后序序列能够确定出该二义树的形状。（高）10. 必须把一般树转换成二叉树后才能进行存储。（）（高）四简答题。（每小题8分，共16分）1、列举儿种排序的方法（至少四种）。（低）2、简述二叉排序树查找的过程。（中）五、应用题。（共34分）1、给出4个叶子结点，设其权值分别为3、5、7、9,试构造出哈夫曼树，并求其带权路径长度WPLo （8分）（低）2、设有一组初始记录关键字45,30,20,76,13,50,给出用冒泡排序法对 其排序的过程。（8分）（低）3、已知一组待排序的记录的初始序列为36,45, 60, 92, 78,12, 25,45,用直接插入排序法对其进行排序并给出排序过程。（8分）（中）