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