发布时间 : 星期一 文章数据结构习题册更新完毕开始阅读
1、 分块查找方法的平均查找长度低于顺序查找，高于折半查找。
2、 采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位
置置为空，因为这会影响以后的查找。
3、 前序遍历二叉排序树的结点就可以得到排好序的结点序列。
4、 在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。 5、 虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。 6、 对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 7、 在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空
即可。
8、 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即
可。
三、 填空题
1、折半查找效率较高，但要求结点（ ）并且要求线性表（ ）；而对于顺序查找，则线性表的存储方式（ ）。
2、假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ），平均查找长度为（ ）。
3、在n个记录的有序顺序表中进行折半查找，最大的比较次数是（ ）。 4、折半查找判定树既是一种（ ），也是一种（ ）。 5、顺序查找法的平均查找长度为（ ）；折半查找法的平均查找长度为（ ）；分块查找法（以顺序查找确定块）的平均查找长度为（ ）；分块查找法（以折半查找确定块）的平均查找长度为（ ）；哈希表查找法采用链接法处理冲突时的平均查找长度为（ ）。
6、对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）；若进行折半查找，则时间复杂度为（ ）；若采用分块查找（假定总块数和每块长度均接近n的开方），则时间复杂度为（ ）。 7、用二分法查找一个线性表时，该线性表必须具有的特点是（ ），而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（ ）。 8、采用散列技术来实现查找，需要解决的问题有：（ ）和（ ）。 9、在散列存储中，处理冲突有（ ）和（ ）两类方法。 10、（ ）法构造的哈希函数肯定不会发生冲突。
11、在各种查找方法中，平均查找长度与结点个数无关的查找方法为（ ）。
12、在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的基本特点。 13、在开散列表上查找键值等于K的结点，首先必须计算该键值的 ，然后在通过指针查找该结点。
14、在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个\索引项\。每个索引项有两个域：块内最大________值和块________位置。
15、索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________查找。 16、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。
17、在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的右指针到它的右子树中去找。
18、中序遍历一棵二叉排序树所得的结点访问序列是键值的________序列。
19、二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。
20、二叉排序树的查找效率与树的形态有关。当二叉排序树退化为一条单支树时，查找算法退化为________查找，平均查找长度上升为________。
21、有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查找长度也与________同数量级。
21
22、________查找法的平均查找长度与元素个数n个数无关。
23、在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为________，比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均查找长度为________。 24、折半查找方法仅适用于这样的表：表中的记录必须________，其存储结构必须是________。
25、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9.1所示的二叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号）
1
3 2
4 6 5
8 7 9
图9.1
26、设线性表L=（a1,a2,?,an）(n>2),表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找和折半查找与k相等的元素，比较次数分别为s和b ，若检索不成功，则s和b的数量关系是________。 27、某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__________，最大比较次数为__________。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素（最后一组可能小于g）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__________，此时的平均比较次数是__________。
28、长度为225的表，采用分块查找法，每块的最佳长度是__________，应分 块，若每块的长度为10，则平均查找长度为 。
29、已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行 次比较可确定查找成功。查找48时需进行 次比较可确定查找成功，查找100时需进行 次比较才能确定查找不成功。
四、 简答题
1、 简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个元素概率相同，
则对一个长度为n的表，用上面三种方法检索时平均查找长度为多少？
2、 画出长度为10的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长度。
3、 有一个10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多少？若每块为
40 ，则平均查找长度为多少？ 4、 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key，
采用开放地址法的线性探测再散列方法解决冲突，试在0到18的Hash地址空间中对该关键字序列构造Hash表。
5、 若哈希表的地址范围为0到9，Hash函数为H(key)=(key2+2)mod 9,并采用链地址法处理冲突，画出
元素7，4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。
6、 假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中
要做多少次探测？
7、 地址空间为0—14的散列表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，
SEP，OCT，NOV，DEC)构造哈希函数：H(Key)=?i/2?，其中i为关键字中第一个字母在字母表中的序号。用如下两种处理冲突的方法：（1）线性探测法（2）链地址法
22
分别求出这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。 8、有一个400项的表，欲采用索引顺序查找方法进行查找，问
（1）分成多少块最为理想？（2）每块的理想长度是什么？（3）平均查找长度是多少？ 9、设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，采用哈希函数：
H(Key)=Key，采用线性探测再散列方法解决冲突，试在0到14的散列地址空间中对该关键字序列构造哈希函数。并求查找成功和不成功时的平均查找长度。 10、线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为：H(Key)=Key，采用拉链法处理冲突。设计出这种链表结构，并计算该表的查找成功和不成功的平均查找长度。 11、建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。
12、分别画出在线性表(06，10，19，24，37，42，50，83)中进行折半查找，查找关键字10和30的过程。 13、设二叉排序树中的关键字由1到100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列。
（1）12，25，71，68，33，34，37，63 （2）92，20，91，24，88，25，36，63 （3）95，22，91，24，94，25，63
（4）21，89，77，29，36，38，41，47，63
14、给定表(25，18，48，07，76，52，81，70，92，15)。
（1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。
15、二叉排序树中关键字互不相同，则其中最小元无左孩子，最大元无右孩子，此命题是否正确？最小元和最大元一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？
第十章：内部排序练习题
一、 选择题
1、下述几种排序方法中，平均查找长度最小的是（ ）。
A、插入排序 B、选择排序 C、快速排序 D、归并排序
3、下列排序算法中不稳定的有（ ）。
A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序
4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（ ），相应的时间复杂度为（ ），该算法是（ ）排序方法。
A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定 J、不稳定
5、对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法，最费时间的算法是（ ）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（ ）。
A、插入排序 B、选择排序 C、快速排序 D、归并排序
7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序
9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（ ）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序
23
10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（ ）。
A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、 每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（ ）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序
12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A、希尔排序 B、归并排序 C、插入排序 D、选择排序
13、n个记录的直接插入排序所需记录关键码的最大比较次数为（ ）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1
14、n个记录的直接插入排序所需的记录最小移动次数为（ ）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n
15、快速排序在（ ）情况下最不利于发挥其长处，在（ ）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据基本无序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。 16、直接插入排序和冒泡排序的平均时间复杂度为（ ），若初始数据有序（正序），则时间复杂度为（ ）。 A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)
补充选择题
1. 快速排序在最坏的情况下的时间复杂度是（ ）
A 、O(log2n) B、O(n log2n) C、O(n*n) D、O(n*n*n) 2. 具有24个记录的序列，采用冒泡排序最少的比较次数为（ ）
A 、1 B、23 C、24 D、529
3. 用某种排序方法对序列（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、二路归并排序 4. 在排序过程中，键值比较的次数与初始序列的排序顺序无关的是（ ）
A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序
5. （ ）方法是从未排序序列中依次取出元素与已经排序序列中的元素作比较，将其放入已经排序序列的正确位置上。
A、归并排序 B、插入排序 C、快速排序 D、选择排序 6. （ ）方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A、归并排序 B、插入排序 C、快速排序 D、选择排序
7. （ ）方法是对序列中的元素通过适当的位置变换将有关元素一次性的放置在其最终位置上。 A、归并排序 B、插入排序 C、快速排序 D、基数排序
8. 将上万个一组无序并且互不相等的正数序列，存储在顺序存储结构中采取（ ）方法能够最快地找到其中最大的正整数。
A、快速排序 B、插入排序 C、选择排序 D、归并排序 9. 以下四种排序方法，要求附加内存空间最大的是（ ）
A、插入排序 B、选择排序 C、快速排序 D、归并排序
24