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