第九章查
一、选择题
1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查55需要比较（）次。
A.1
B.2
C.3
D.4
3、解决哈希冲突的主要方法有（）。
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、再哈希法
D.线性探测法、再哈希法、链地址法
4、在一棵深度为h的具有n个元素的二叉排序树中，查所有元素的最长查长度为（）。
A.n
B.log2n
C.(h+1)/2
D.h
5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p建立哈希表，则p应取（）为宜。
A.23
B.24
C.25
D.26
6、设哈希表长m=14，哈希函数H(key)=key MOD11。表中已有4个结点：
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。
A.8
B.3
C.5
D.9
9、m阶B-树中的m是指（）。
A.每个结点至少具有m棵子树
B.每个结点最多具有m棵子树
C.分支结点中包含的关键字的个数
D.m阶B-树的深度
10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD9，与18发生冲突的元素有（）个。
A.1
B.2
C.3
D.4
11、在对查表的查过程中，若被查的数据元素不存在，则把该数据元素插到集合中，
这种方式主要适合于（）。
A.静态查表
B.动态查表
C.静态查表和动态查表
D.两种表都不适合
12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查值为
82的结点时，（B）次比较后查成功。
A.1
B.4
C.2
D.8
13、在各种查方法中，平均查承担与结点个数n无关的查方法是（）。
A.顺序查
B.折半查
C.哈希查
D.分块查
14、下列二叉树中，不．平衡的二叉树是（）。
15、对一棵二叉排序树按（）遍历，可得到结点值从小到大的排列序列。
A.先序
B.中序
C.后序
D.层次
16、解决散列法中出现的冲突问题常采用的方法是（）。
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
17、对线性表进行折半查时，要求线性表必须（）。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
二、填空题
1、在散列函数H(key)=key％p中，p应取。
2、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查90
时，需进行次查可确定成功。
3、具有相同函数值的关键字对哈希函数来说称为。
4、在一棵二叉排序树上实施遍历后，其关键字序列是一个有序表。
5、在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越；α值越小，则存取元素发生冲突的可能性就越。
三、判断题
（）1、折半查只适用于有序表，包括有序的顺序表和链表。
（）2、二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。
（）3、哈希表的查效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法。（）4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。
（）5、AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。
四、综合题
1、选取哈希函数H（k）=（k）MOD11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查成功时的平均查长度。
2、设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查成功的平均查长度ASL。
3、设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（K）=K mod6，采用线性探测法解决冲突，要求：
（1）构造散列表；
（2）求查数34需要比较的次数。
4、已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。
5、若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。画出生成后的二叉排序树（不需画出生成过程）。
6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，采用哈希函数
H(key)=key MOD13，采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查成功时的平均查长度。
7、已知关键字序列{11,2,13,26,5,18,4,9}，设哈希表表长为16，哈希函数H(key)=key MOD13，处理冲突的方法为线性探测法，请给出哈希表，并计算在等概率的条件下的平均查长度。
8、设散列表的长度为m=13，散列函数为H(k)=k MOD m，给定的关键码序列为19，14，23，1，68，20，84，27，55，11，13，7，试写出用线性探查法解决冲突时所构造的散列表。
9、依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉排序树，并计算在等概率情况下该二叉排序树的平均查长度ASL。（要求给出构造过程）
10、设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），采用哈希函数H(key)=key%13，采用二次探测再散列的方法解决冲突，试在0-18的散列地址空间中对该关键字序列构造哈希表。
第十章内部排序
一、选择题
1、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序
B.堆排序
C.归并排序
D.直接插入排序
2、下列排序方法中（）方法是不稳定的。
A.冒泡排序
B.选择排序
C.堆排序
D.直接插入排序
3、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（）方法。
A.快速排序
B.堆排序
C.插入排序
D.归并排序
4、一组待排序序列为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（）。
A.79,46,56,38,40,80
B.84,79,56,38,40,46
C.84,79,56,46,40,38
D.84,56,79,40,46,38
5、快速排序方法在（）情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中有多个相同值
C.要排序的数据已基本有序
D.要排序的数据个数为奇数
6、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（）排序的基本思想。
A.堆排序
B.直接插入排序
C.快速排序
D.冒泡排序
7、在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（）。
A.直接插入
B.快速排序
C.堆排序
D.归并排序
8、如果将所有中国人按照生日来排序，则使用（）算法最快。
A.归并排序
B.希尔排序
C.快速排序
D.基数排序
9、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。
A.O(log2n)
B.O(1)
C.O(n)
D.O(nlog2n)
10、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A.希尔排序
B.冒泡排序
C.插入排序
D.选择排序
11、一组记录的的序列未（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。
A.79，46，56，38，40，80
B.84，79，56，38，40，46
数组和链表
C.84，79，56，46，40，38
D.84，56，79，40，46，38
12、用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
⑴25，84，21，47，15，27，68，35，20
⑵20，15，21，25，47，27，68，35，84
⑶15，20，21，25，35，27，47，68，84
⑷15，20，21，25，27，35，47，68，84
则所采用的排序方法是（）。
A.选择排序
B.希尔排序
C.归并排序
D.快速排序
13、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（）。
A.冒泡排序
B.选择排序
C.快速排序
D.堆排序

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。